// This doesn't work yet because byCount uses a LinkedHashSet to

// store LinkedHashSets which have equality by contents, so calling

// byCount.remove(x, y) takes like forever.

// We'd need a LinkedIdentityHashSet but I haven't found a good

// implementation of that yet.

!include once #1027304 // Eclipse Collections

import org.eclipse.collections.impl.map.mutable.primitive.*;

import org.eclipse.collections.api.tuple.primitive.*;

set flag NoModCount. // save some space. Make sure that this flag doesn't screw other collections/map you compile with this.

final sclass LineComp_PairIndex {

  bool verbose;

  bool inOrder = true;

  //MultiSetMap<IntPair, Node> nodes;

  new LongObjectHashMap<LinkedHashSet<Node>> nodes;

  MultiSetMap<Int, LinkedHashSet<Node>> byCount;

  new LinkedHashMap<S, Ch> chains;

  Ch firstChain;

  int initialNodesSetCapacity = 1;

  void init {

    /*nodes = inOrder

      ? multiSetMap_innerLinkedHashSet_outerHashMap()

      : multiSetMap_innerHashSet_outerHashMap();*/

  }

  // indicate end of chain-making phase

  void haveChains {

    if (byCount == null) {

      print("n=" + nodes.size());

      time "Making byCount" {

        byCount = multiSetMap_innerCompactHashSet_outerRevTreeMap();

        for (LinkedHashSet<Node> set : nodes.values())

          byCount.put(set.size(), set);

      }

    }

  }

  // a "chain" of nodes (one input file)

  sclass Ch {

    Node tail;

    *(LineComp_PairIndex pi, L<Int> l) {

      int count = 0;

      fOr (int i : l) {

        add(pi, i);

        if (((++count) % oneMillion()) == 0)

          print("Added " + count + " entries to chain");

      }

    }

    // TODO: optimize

    L<Int> toList() {

      new L<Int> l;

      Node node = tail;

      while (node != null) {

        l.add(node.value);

        node = node.prev;

      }

      ret reverseInPlace(l);

    }

    void add(LineComp_PairIndex pi, int i) {

      new Node n;

      ifndef LineComp_SingleChain

        n.ch = this;

      endifndef

      n.value = i;

      n.prev = tail;

      if (tail != null) tail.next = n;

      tail = n;

      pi.addToIndex(n.prev);

    }

  }

  sclass Node {

    ifndef LineComp_SingleChain

      Ch ch;

    endifndef

    int value;

    Node prev, next;

    int a() { ret value; }

    int b() { ret next == null ? -1 : next.value; }

    IntPair pair() { ret next == null ? null : IntPair(a(), b()); }

  }

  IntPair nodeToPair(Node n) {

    ret n?.pair();

  }

  // add node to pair index

  void addToIndex(Node n) {

    IntPair p = nodeToPair(n);

    if (p == null) ret;

    int count = nodes_getSize(p);

    LinkedHashSet<Node> set = nodes_add(p, n);

    if (byCount != null) { // not in init phase

      if (count != 0) byCount.remove(count, set);

      byCount.put(count+1, set);

    }

  }

  // remove node from pair index

  void removeFromIndex(Node n) {

    IntPair p = nodeToPair(n);

    if (p == null) ret;

    LinkedHashSet<Node> set = nodes.get(intPairToLong(p));

    int count = l(set);

    if (count == 0) fail("Can't remove pair " + p);

    nodes_remove(p, n);

    byCount.remove(count, set);

    if (--count > 0) byCount.put(count, set);

  }

  IntPair mostPopularDuplicate() {

    ret toInt(firstKey(byCount)) < 2 ? null : first(firstValue(byCount)).pair();

  }

  int numberOfDuplicates() {

    ret byCount.size()-l(byCount.get(1));

  }

  int getCount(IntPair p) {

    ret nodes_getSize(p);

  }

  void replacePair(int pa, int pb, int replaceWith) {

    IntPair p = IntPair(pa, pb);

    Set<Node> set = nodes.get(intPairToLong(p));

    if (set != null)

      for (Node n : cloneList(set)) {

        continue if n.a() != pa || n.b() != pb; // nodes might have been deleted or changed

        replacePair(n, replaceWith);

      }

  }

  void replacePair(Node node, int replaceWith) {

    removeFromIndex(node.prev);

    removeFromIndex(node);

    removeFromIndex(node.next);

    node.value = replaceWith;

    deleteNode(node.next);

    addToIndex(node.prev);

    addToIndex(node);

  }

  void deleteNode(Node node) {

    if (node.next != null) node.next.prev = node.prev; else getChain(node).tail = node.prev;

    if (node.prev != null) node.prev.next = node.next;

    node.value = -1; // mark invalid

  }

  void newChain(S version, L<Int> encoding) {

    Ch ch = new(this, encoding);

    chains.put(version, ch);

    ifdef LineComp_SingleChain

      assertNull(firstChain);

      firstChain = ch;

    endifdef

  }

  int nodes_getSize(IntPair p) {

    ret l(nodes.get(intPairToLong(p)));

  }

  LinkedHashSet<Node> nodes_add(IntPair p, Node n) {

    long l = intPairToLong(p);

    LinkedHashSet<Node> set = nodes.get(l);

    if (set == null)

      nodes.put(l, set = new LinkedHashSet(initialNodesSetCapacity);

    set.add(n);

    ret set;

  }

  void nodes_remove(IntPair p, Node n) {

    long l = intPairToLong(p);

    LinkedHashSet<Node> set = nodes.get(l);

    if (set == null) ret;

    set.remove(n);

    if (set.isEmpty())

      nodes.remove(l);

  }

  // also shrinks sets...

  void printStats {

    print("Different pairs: " + l(nodes));

    print("Different counts: " + byCount.keysSize() + " (highest count: " + firstKey(byCount) + ")");

    long count = 0, waste = 0, newWaste = 0;

    long count1 = 0, waste1 = 0;

    for (HashSet set : nodes.values()) {

      count1 += set.size();

      int capacity = hashSetCapacity(set);

      waste1 += capacity-set.size();

      //if (capacity > set.size()*3) set.shrink(); // TODO

    }

    for (CompactHashSet set : (Cl<CompactHashSet>) (Cl) values(byCount.data)) {

      count += set.size();

      waste += set.capacity()-set.size();

      set.shrinkToFactor(0.5);

      newWaste += set.capacity()-set.size();

    }

    print("Nodes set count: " + count1 + ". Waste: " + waste1);

    print("Set count: " + count + ". Waste: " + waste + (waste == newWaste ? "" : " => " + newWaste));

  }

  Ch getChain(Node node) {

    ifdef LineComp_SingleChain

      ret firstChain;

    endifdef

    ifndef LineComp_SingleChain

      ret node.ch;

    endifndef

  }

}