// Note: as nodes are in hash maps, order of pair replacement is rather undefined

sclass LineComp_LinkedList {

  sclass Node {

    int value;

    Node prev, next;

  }

  Node tail;

  new MultiSetMap<Int, Node> indexByElement;

  bool verbose;

  *() {}

  *(L<Int> l) {

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

  }

  void add(int i) {

    new Node n;

    n.value = i;

    n.prev = tail;

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

    tail = n;

    indexByElement.put(i, n);

  }

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

    Set<Node> setA = indexByElement.get(pa);

    if (setA == null) ret;

    Set<Node> setB = indexByElement.get(pb);

    if (setB == null) ret;

    bool change;

    if (setA.size() <= setB.size())

      for (Node na : cloneList(setA)) {

        continue if na.value < 0; // node might have been deleted

        Node nb = na.next;

        if (nb != null && nb.value == pb) {

          if (verbose && !change) print("Before replacement: " + toList());

          replacePair(na, replaceWith, pairCounts);

          set change;

        }

      }

    else

      for (Node nb : cloneList(setB)) {

        continue if nb.value < 0; // node might have been deleted

        Node na = nb.prev;

        if (na != null && na.value == pa) {

          if (verbose && !change) print("Before replacement: " + toList());

          replacePair(na, replaceWith, pairCounts);

          set change;

        }

      }

    if (verbose && change) print("After replacement: " + toList());    

  }

  L<Int> toList() {

    new L<Int> l;

    Node node = tail;

    while (node != null) {

      l.add(node.value);

      node = node.prev;

    }

    ret reverseInPlace(l);

  }

  void deleteNode(Node node) {

    indexByElement.remove(node.value, node);

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

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

    node.value = -1; // mark invalid

  }

  void replacePair(Node node, int replaceWith, LineComp_PairCounts pairCounts) {

    Node nb = node.next;

    int pa = node.value, pb = nb.value;

    if (node.prev != null) pairCounts.remove(node.prev.value, pa);

    pairCounts.remove(pa, pb);

    if (nb.next != null) pairCounts.remove(pb, nb.next.value);

    setValue(node, replaceWith);

    deleteNode(nb);

    if (node.prev != null) pairCounts.add(node.prev.value, replaceWith);

    if (node.next != null) pairCounts.add(replaceWith, node.next.value);

  }

  void setValue(Node node, int value) {

    indexByElement.remove(node.value, node);

    node.value = value;

    indexByElement.add(node.value, node);

  }

}