// assumes LineComp_SingleChain!
// For multi-chain, use v2 of this class (#1028521)
//
// nodeHashCode is not used yet
//
// Some bug with the freeing of nodes...

!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 {
  replace Node with int.
  replace _Node with Int.
  
  bool verbose;
  bool garbageCollect = false; // still buggy
  new LongObjectHashMap<Cousins> nodes;
  MultiSetMap<Int, Cousins> byCount;
  new LinkedHashMap<S, Ch> chains;
  Ch firstChain;
  int objectCounter; // for making deterministic hash codes
  int nodeCounter;

  static int initialNodesSetCapacity = 1;
  
  static final int nodeSize = 6; // 5 ints (hash code + value + 4 pointers)
  static new ChunkedIntList nodeData;
  
  int nodeHashCode(int node) { ret nodeData.get(node); }
  int value(int node) { ret nodeData.get(node+1); }
  int prev(int node) { ret nodeData.get(node+2); }
  int next(int node) { ret nodeData.get(node+3); }
  int prevCousin(int node) { ret nodeData.get(node+4); }
  int nextCousin(int node) { ret nodeData.get(node+5); }
  
  void setNodeHashCode(int node, int x) { nodeDataSet(node, x); }
  void setValue(int node, int x) { nodeDataSet(node+1, x); }
  void setPrev(int node, int x) { nodeDataSet(node+2, x); }
  void setNext(int node, int x) { nodeDataSet(node+3, x); }
  void setPrevCousin(int node, int x) { nodeDataSet(node+4, x); }
  void setNextCousin(int node, int x) { nodeDataSet(node+5, x); }
  
  void nodeDataSet(int idx, int value) {
    nodeData.set(idx, value);
  }
  
  void init {
    for i to nodeSize: nodeData.add(0);
  }
  
  // Cousins is a replacement for LinkedHashSet<Node>
  // - a set of all nodes forming a certain pair with their successor
  // Nodes are linked through prevCousin/nextCousin
  final class Cousins extends CompactHashSet<_Node> {
    Node head, tail;

    int hashCode;
    *(LineComp_PairIndex pi) {
      super(initialNodesSetCapacity);
      hashCode = ++pi.objectCounter;
    }
    @Override public int hashCode() { ret hashCode; }

    public bool add(Node n) {
      setPrevCousin(n, tail);
      if (tail != 0) // there already are entries
        setNextCousin(tail, n); 
      else
        head = n;
      tail = n;
      ret super.add(n);
    }
    
    public bool remove(Node node) {
      if (nextCousin(node) != 0)
        setPrevCousin(nextCousin(node), prevCousin(node));
      else
        tail = prevCousin(node);
      if (prevCousin(node) != 0)
        setNextCousin(prevCousin(node), nextCousin(node));
      else
        head = nextCousin(node);
      setPrevCousin(node, 0);
      setNextCousin(node, 0);
      ret super.remove(node);
    }
    
    // node has changed internal location. don't change the linked list stuff!
    void moveNode(Node from, Node to) {
      super.remove(from);
      super.add(to);
    }
    
    L<_Node> asList() {
      L<_Node> l = emptyList(size());
      Node n = head;
      while (n != 0) {
        l.add(n);
        n = nextCousin(n);
      }
      ret l;
    }
  }
  
  // indicate end of chain-making phase
  void haveChains {
    if (byCount == null) {
      print("n=" + nodes.size());
      time "Making byCount" {
        byCount = multiSetMap_innerCompactHashSet_outerRevTreeMap();
        for (Cousins set : nodes.values())
          byCount.put(set.size(), set);
      }
    }
  }
  
  // a "chain" of nodes (one input file)
  class 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");
      }
    }
    
    L<Int> toList() {
      new L<Int> l;
      Node node = tail;
      while (node != 0) {
        l.add(value(node));
        node = prev(node);
      }
      ret reverseInPlace(l);
    }
    
    void add(LineComp_PairIndex pi, int i) {
      Node n = pi.newNode();
      setValue(n, i);
      setPrev(n, tail);
      if (tail != 0) setNext(tail, n);
      tail = n;
      pi.addToIndex(prev(n));
    }
  }
  
  Node newNode() {
    for i to nodeSize: nodeData.add(0);
    ret nodeCounter += nodeSize;
  }
  
  int node_a(int node) { ret value(node); }
  int node_b(int node) { int next = next(node); ret next == 0 ? -1 : value(next); }
  
  IntPair nodeToPair(int node) {
    if (node == 0) null;
    int next = next(node);
    ret next == 0 ? null : IntPair(node_a(node), node_b(node));
  }

  // add node to pair index
  void addToIndex(Node n) {
    IntPair p = nodeToPair(n);
    if (p == null) ret;
    int count = nodes_getSize(p);
    Cousins 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;
    Cousins 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 : nodeToPair(firstValue(byCount).head);
  }
  
  int numberOfDuplicates() {
    ret byCount.size()-l(byCount.get(1));
  }
  
  int getCount(IntPair p) {
    ret nodes_getSize(p);
  }
  
  L<_Node> replacing;
  Map<_Node, Int> replacing_index;
  
  void replacePair(int pa, int pb, int replaceWith) {
    IntPair p = IntPair(pa, pb);
    Cousins set = nodes.get(intPairToLong(p));
    if (set != null) {
      replacing = set.asList();
      replacing_index = listIndex(replacing);
      
      for i over replacing: {
        Node n = replacing.get(i);
        continue if node_a(n) != pa || node_b(n) != pb; // nodes might have been deleted or changed
        replacePair(n, replaceWith);
      }
      
      replacing = null;
      replacing_index = null;
    }
  }
  
  void replacePair(Node node, int replaceWith) {
    removeFromIndex(prev(node));
    removeFromIndex(node);
    removeFromIndex(next(node));
    setValue(node, replaceWith);
    deleteNode(next(node));
    addToIndex(prev(node));
    addToIndex(node);
  }
  
  void deleteNode(Node node) {
    if (next(node) != 0)
      setPrev(next(node), prev(node));
    else
      firstChain.tail = prev(node);
    if (prev(node) != 0)
      setNext(prev(node), next(node));
    //setValue(node, -1); // mark invalid
    physicallyDisposeOfNode(node);
  }
  
  void physicallyDisposeOfNode(Node node) {
    if (!garbageCollect) ret;
    // move last node in list to place that is now free
    if (node != nodeCounter) {
      //print("Moving node " + nodeCounter + " to " + node);
      moveNode(nodeCounter, node);
    }
    //print("Disposing of node " + nodeCounter);
    nodeData.truncateAt(nodeCounter);
    nodeCounter -= nodeSize;
  }
  
  void moveNode(int from, int to) {
    // Copy hash code & value.
    setNodeHashCode(to, nodeHashCode(from));
    setValue(to, value(from));
    
    // Be sure to update all the pointers there may be to this node!
    // First, find Cousins object.
    IntPair pair = nodeToPair(from);
    if (pair != null) {
      Cousins cousins = nodes.get(intPairToLong(pair));
      if (cousins.head == from) cousins.head = to;
      if (cousins.tail == from) cousins.tail = to;
      cousins.moveNode(from, to);
    }
    
    // Next, check the chain.
    if (firstChain.tail == from) firstChain.tail = to;
    
    // Now the 4 prev and next pointers
    int i;
    if ((i = prev(from)) != 0) setNext(i, to);
    if ((i = next(from)) != 0) setPrev(i, to);
    if ((i = prevCousin(from)) != 0) setNextCousin(i, to);
    if ((i = nextCousin(from)) != 0) setPrevCousin(i, to);
    
    // Finally the list we are currently replacing
    if (replacing_index != null) {
      _Node ref = replacing_index.get(from);
      if (ref != null)
        replacing.set(ref, to);
    }

    // That should be it...!?
  }

  void newChain(S version, L<Int> encoding) {
    Ch ch = new(this, encoding);
    chains.put(version, ch);
    assertNull(firstChain);
    firstChain = ch;
  }
  
  int nodes_getSize(IntPair p) {
    ret l(nodes.get(intPairToLong(p)));
  }
  
  Cousins nodes_add(IntPair p, Node n) {
    long l = intPairToLong(p);
    Cousins set = nodes.get(l);
    if (set == null)
      nodes.put(l, set = new Cousins(this));
    set.add(n);
    ret set;
  }
  
  void nodes_remove(IntPair p, Node n) {
    long l = intPairToLong(p);
    Cousins 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, newWaste1 = 0;
    
    for (Cousins set : nodes.values()) {
      count1 += set.size();
      int capacity = set.capacity();
      waste1 += capacity-set.size();
      set.shrinkToFactor(0.5);
      newWaste1 += capacity-set.size();
    }
     
    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("Chain length   : " + count1 + ". Waste: " + waste1 + (waste1 == newWaste1 ? "" : " => " + newWaste1));
    print("Different pairs: " + count + ". Waste: " + waste + (waste == newWaste ? "" : " => " + newWaste));
  }
  
  Ch getChain(Node node) {
    ret firstChain;
  }
}

Began life as a copy of #1028521