sclass LineComp_PairIndex {

  bool verbose;

  bool inOrder = true;

  MultiSetMap<IntPair, Node> nodes;

  MultiSetMap<Int, IntPair> byCount

    //= multiSetMap_innerHashSet_outerRevTreeMap(); // makes a difference in selecting a pair if there are multiple with the same count

    = multiSetMap_innerCompactHashSet_outerRevTreeMap(); // same but more compact

    //= multiSetMap_innerTreeSet_outerRevTreeMap(); // initial version that kind of pointlessly sorts the same-count nodes lexicographically

  new LinkedHashMap<S, Ch> chains;

  void init {

    nodes = inOrder

      ? multiSetMap_innerLinkedHashSet_outerHashMap()

      : multiSetMap_innerHashSet_outerHashMap();

  }

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

  sclass Ch {

    Node tail;

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

      fOr (int i : l) add(pi, i);

    }

    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;

      n.ch = this;

      n.value = i;

      n.prev = tail;

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

      tail = n;

      pi.addToIndex(n.prev);

    }

  }

  sclass Node {

    Ch ch;

    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);

    nodes.add(p, n);

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

    byCount.put(count+1, p);

  }

  // remove node from pair index

  void removeFromIndex(Node n) {

    IntPair p = nodeToPair(n);

    if (p == null) ret;

    int count = nodes.getSize(p);

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

    nodes.remove(p, n);

    byCount.remove(count, p);

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

  }

  IntPair mostPopularDuplicate() {

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

  }

  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(p);

    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 node.ch.tail = node.prev;

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

    node.value = -1; // mark invalid

  }

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

    chains.put(version, new Ch(this, encoding));

  }

}