fsclass LineComp_PairIndex_v2 {
  bool verbose;
  new HashMap<IntPair, PairInfo> pairInfos;
  new LinkedHashMap<S, Ch> chains;
  
  // buckets
  Bucket oneBucket = new Bucket(1), highest = oneBucket; // 1-bucket is lowest
  
  // duplicates counting didn't work for some reason...
  //int /*bucketCount = 1,*/duplicates;

  fclass PairInfo {
    IntPair pair;
    Bucket bucket;
    new LinkedHashSet<Node> nodes;
    
    *(IntPair *pair) {}
    
    public bool equals(O o) { if (o cast PairInfo) ret pair.equals(o.pair); false; }
    public int hashCode() { ret pair.hashCode(); }
  }
  
  // a bucket lists all pairs with the same number of duplicates
  // and it also knows its next-highest and next-lowest non-empty bucket
  fclass Bucket {
    Bucket higher, lower;
    int level; // number of duplicates of each IntPair in this bucket
    new LinkedHashSet<PairInfo> pairs;
    
    *(int *level) {}
    
    toString { ret "Bucket " + level + appendBracketed(nPairs(pairs)); }
    
    Bucket oneHigher() {
      if (higher != null && higher.level == level+1) ret higher;
      Bucket b = new(level+1);
      //++bucketCount;
      b.lower = this;
      b.higher = higher;
      if (highest == this) highest = b; else higher.lower = b;
      ret higher = b;
    }
    
    Bucket oneLower() {
      if (level == 1) fail("Can't go lower than oneBucket");
      if (lower.level == level-1) ret lower;
      //print("Making bucket " + (level-1) + " (lower: " + lower + ")");
      if (lower.level < 0) fail("Invalid lower bucket");
      Bucket b = new(level-1);
      //++bucketCount;
      b.higher = this;
      b.lower = lower;
      lower.higher = b;
      ret lower = b;
    }
    
    void add(PairInfo pair) {
      pairs.add(pair);
      pair.bucket = this;
    }
    
    void movePairOneHigher(PairInfo pair) {
      //if (level == 1) ++duplicates;
      
      // shortcut: just lift ourselves if we only contain one pair
      if (pairs.size() == 1 && higher != null && higher.level != level+1) {
        //print("shortcut higher");
        ret with level++;
      }
          
      oneHigher().add(pair);
      remove(pair);
    }
    
    void remove(PairInfo pair) {
      pairs.remove(pair);
      if (empty(pairs) && this != oneBucket)
        dropMe();
    }
    
    void dropMe {
      //print("Dropping " + this);
      if (level == 1) fail("Trying to drop oneBucket");
      if (nempty(pairs)) fail("Bucket still has pairs");
      if (higher != null) higher.lower = lower; else highest = lower;
      lower.higher = higher;
      level = -1; // mark invalid for safety
      //--bucketCount;
    }
    
    void movePairOneLower(PairInfo pair) {
      //if (verbose) print("Moving pair lower: " + pair);
      if (this == oneBucket) {
        remove(pair);
        forgetPair(pair);
      } else {
        //if (level == 2) --duplicates;
        
        // shortcut: just lower ourselves if we only contain one pair
        if (pairs.size() == 1 && lower.level != level-1) {
          //print("shortcut lower");
          ret with level--;
        }
          
        oneLower().add(pair);
        remove(pair);
      }
    }
  }
  
  Bucket oneBucket() { ret oneBucket; }
  
  // a "chain" of nodes (one input file)
  fclass Ch {
    Node tail;
    
    *(L<Int> l) {
      fOr (int i : l) add(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(int i) {
      new Node n;
      n.ch = this;
      n.value = i;
      n.prev = tail;
      if (tail != null) tail.next = n;
      tail = n;
      addToIndex(n.prev);
    }
  }
  
  fclass 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 (add to lowest or move to higher bucket)
  void addToIndex(Node n) {
    IntPair p = nodeToPair(n), ret if null;
    PairInfo pi = getPairInfo(p);
    if (pi == null) {
      pi = new PairInfo(p);
      pairInfos.put(p, pi);
      oneBucket.add(pi);
    } else
      pi.bucket.movePairOneHigher(pi);
    pi.nodes.add(n);
  }
  
  // remove node from pair index (move to lower bucket or drop)
  void removeFromIndex(Node n) {
    IntPair p = nodeToPair(n), ret if null;
    PairInfo pi = getPairInfo(p);
    if (pi == null) fail("Can't remove pair " + p);
    pi.nodes.remove(n);
    pi.bucket.movePairOneLower(pi);
  }
  
  IntPair mostPopularDuplicate() {
    //if (verbose) print("Highest bucket: " + highest);
    if (highest == oneBucket) null; // no more duplicates
    PairInfo pi = first(highest.pairs);
    if (pi == null) fail("Bucket empty! " + highest);
    ret pi.pair;
  }
  
  int getCount(IntPair pair) {
    ret getPairInfo(pair).bucket.level;
  }
  
  int numberOfDuplicates() {
    //ret duplicates;
    ret l(pairInfos)-l(oneBucket.pairs);
  }
  
  void replacePair(int pa, int pb, int replaceWith) {
    IntPair p = IntPair(pa, pb);
    PairInfo pi = getPairInfo(p);
    //print("Have " + nNodes(pi.nodes));
    for (Node n : cloneList(pi.nodes)) {
      //print("Processing node " + n.pair());
      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(encoding));
  }
  
  PairInfo getPairInfo(IntPair pair) {
    ret pairInfos.get(pair);
  }
  
  void forgetPair(PairInfo pair) {
    pairInfos.remove(pair.pair);
    pair.bucket = null;
  }
  
  void fullCheck {
    assertTrue(oneBucket.lower == null);
    assertTrue(oneBucket.level == 1);
    Bucket b = highest;
    while (b != oneBucket) {
      assertNempty(b.pairs);
      assertSame(b.lower.higher, b);
      assertEquals(b.lower.level, b.level-1);
      b = b.lower;
    }
  }
}