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