Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

246
LINES

< > BotCompany Repo | #1028249 // LineComp_PairIndex_v2 with bucket list [OK]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (3332L/21K).

1  
fsclass LineComp_PairIndex_v2 {
2  
  bool verbose;
3  
  new HashMap<IntPair, PairInfo> pairInfos;
4  
  new LinkedHashMap<S, Ch> chains;
5  
  
6  
  // buckets
7  
  Bucket oneBucket = new Bucket(1), highest = oneBucket; // 1-bucket is lowest
8  
  
9  
  // duplicates counting didn't work for some reason...
10  
  //int /*bucketCount = 1,*/duplicates;
11  
12  
  fclass PairInfo {
13  
    IntPair pair;
14  
    Bucket bucket;
15  
    new LinkedHashSet<Node> nodes;
16  
    
17  
    *(IntPair *pair) {}
18  
    
19  
    public bool equals(O o) { if (o cast PairInfo) ret pair.equals(o.pair); false; }
20  
    public int hashCode() { ret pair.hashCode(); }
21  
  }
22  
  
23  
  // a bucket lists all pairs with the same number of duplicates
24  
  // and it also knows its next-highest and next-lowest non-empty bucket
25  
  fclass Bucket {
26  
    Bucket higher, lower;
27  
    int level; // number of duplicates of each IntPair in this bucket
28  
    new LinkedHashSet<PairInfo> pairs;
29  
    
30  
    *(int *level) {}
31  
    
32  
    toString { ret "Bucket " + level + appendBracketed(nPairs(pairs)); }
33  
    
34  
    Bucket oneHigher() {
35  
      if (higher != null && higher.level == level+1) ret higher;
36  
      Bucket b = new(level+1);
37  
      //++bucketCount;
38  
      b.lower = this;
39  
      b.higher = higher;
40  
      if (highest == this) highest = b; else higher.lower = b;
41  
      ret higher = b;
42  
    }
43  
    
44  
    Bucket oneLower() {
45  
      if (level == 1) fail("Can't go lower than oneBucket");
46  
      if (lower.level == level-1) ret lower;
47  
      //print("Making bucket " + (level-1) + " (lower: " + lower + ")");
48  
      if (lower.level < 0) fail("Invalid lower bucket");
49  
      Bucket b = new(level-1);
50  
      //++bucketCount;
51  
      b.higher = this;
52  
      b.lower = lower;
53  
      lower.higher = b;
54  
      ret lower = b;
55  
    }
56  
    
57  
    void add(PairInfo pair) {
58  
      pairs.add(pair);
59  
      pair.bucket = this;
60  
    }
61  
    
62  
    void movePairOneHigher(PairInfo pair) {
63  
      //if (level == 1) ++duplicates;
64  
      
65  
      // shortcut: just lift ourselves if we only contain one pair
66  
      if (pairs.size() == 1 && higher != null && higher.level != level+1) {
67  
        //print("shortcut higher");
68  
        ret with level++;
69  
      }
70  
          
71  
      oneHigher().add(pair);
72  
      remove(pair);
73  
    }
74  
    
75  
    void remove(PairInfo pair) {
76  
      pairs.remove(pair);
77  
      if (empty(pairs) && this != oneBucket)
78  
        dropMe();
79  
    }
80  
    
81  
    void dropMe {
82  
      //print("Dropping " + this);
83  
      if (level == 1) fail("Trying to drop oneBucket");
84  
      if (nempty(pairs)) fail("Bucket still has pairs");
85  
      if (higher != null) higher.lower = lower; else highest = lower;
86  
      lower.higher = higher;
87  
      level = -1; // mark invalid for safety
88  
      //--bucketCount;
89  
    }
90  
    
91  
    void movePairOneLower(PairInfo pair) {
92  
      //if (verbose) print("Moving pair lower: " + pair);
93  
      if (this == oneBucket) {
94  
        remove(pair);
95  
        forgetPair(pair);
96  
      } else {
97  
        //if (level == 2) --duplicates;
98  
        
99  
        // shortcut: just lower ourselves if we only contain one pair
100  
        if (pairs.size() == 1 && lower.level != level-1) {
101  
          //print("shortcut lower");
102  
          ret with level--;
103  
        }
104  
          
105  
        oneLower().add(pair);
106  
        remove(pair);
107  
      }
108  
    }
109  
  }
110  
  
111  
  Bucket oneBucket() { ret oneBucket; }
112  
  
113  
  // a "chain" of nodes (one input file)
114  
  fclass Ch {
115  
    Node tail;
116  
    
117  
    *(L<Int> l) {
118  
      fOr (int i : l) add(i);
119  
    }
120  
    
121  
    L<Int> toList() {
122  
      new L<Int> l;
123  
      Node node = tail;
124  
      while (node != null) {
125  
        l.add(node.value);
126  
        node = node.prev;
127  
      }
128  
      ret reverseInPlace(l);
129  
    }
130  
    
131  
    void add(int i) {
132  
      new Node n;
133  
      n.ch = this;
134  
      n.value = i;
135  
      n.prev = tail;
136  
      if (tail != null) tail.next = n;
137  
      tail = n;
138  
      addToIndex(n.prev);
139  
    }
140  
  }
141  
  
142  
  fclass Node {
143  
    Ch ch;
144  
    int value;
145  
    Node prev, next;
146  
    
147  
    int a() { ret value; }
148  
    int b() { ret next == null ? -1 : next.value; }
149  
    IntPair pair() { ret next == null ? null : IntPair(a(), b()); }
150  
  }
151  
  
152  
  IntPair nodeToPair(Node n) {
153  
    ret n?.pair();
154  
  }
155  
  
156  
  // add node to pair index (add to lowest or move to higher bucket)
157  
  void addToIndex(Node n) {
158  
    IntPair p = nodeToPair(n), ret if null;
159  
    PairInfo pi = getPairInfo(p);
160  
    if (pi == null) {
161  
      pi = new PairInfo(p);
162  
      pairInfos.put(p, pi);
163  
      oneBucket.add(pi);
164  
    } else
165  
      pi.bucket.movePairOneHigher(pi);
166  
    pi.nodes.add(n);
167  
  }
168  
  
169  
  // remove node from pair index (move to lower bucket or drop)
170  
  void removeFromIndex(Node n) {
171  
    IntPair p = nodeToPair(n), ret if null;
172  
    PairInfo pi = getPairInfo(p);
173  
    if (pi == null) fail("Can't remove pair " + p);
174  
    pi.nodes.remove(n);
175  
    pi.bucket.movePairOneLower(pi);
176  
  }
177  
  
178  
  IntPair mostPopularDuplicate() {
179  
    //if (verbose) print("Highest bucket: " + highest);
180  
    if (highest == oneBucket) null; // no more duplicates
181  
    PairInfo pi = first(highest.pairs);
182  
    if (pi == null) fail("Bucket empty! " + highest);
183  
    ret pi.pair;
184  
  }
185  
  
186  
  int getCount(IntPair pair) {
187  
    ret getPairInfo(pair).bucket.level;
188  
  }
189  
  
190  
  int numberOfDuplicates() {
191  
    //ret duplicates;
192  
    ret l(pairInfos)-l(oneBucket.pairs);
193  
  }
194  
  
195  
  void replacePair(int pa, int pb, int replaceWith) {
196  
    IntPair p = IntPair(pa, pb);
197  
    PairInfo pi = getPairInfo(p);
198  
    //print("Have " + nNodes(pi.nodes));
199  
    for (Node n : cloneList(pi.nodes)) {
200  
      //print("Processing node " + n.pair());
201  
      continue if n.a() != pa || n.b() != pb; // nodes might have been deleted or changed
202  
      replacePair(n, replaceWith);
203  
    }
204  
  }
205  
  
206  
  void replacePair(Node node, int replaceWith) {
207  
    removeFromIndex(node.prev);
208  
    removeFromIndex(node);
209  
    removeFromIndex(node.next);
210  
    node.value = replaceWith;
211  
    deleteNode(node.next);
212  
    addToIndex(node.prev);
213  
    addToIndex(node);
214  
  }
215  
  
216  
  void deleteNode(Node node) {
217  
    if (node.next != null) node.next.prev = node.prev; else node.ch.tail = node.prev;
218  
    if (node.prev != null) node.prev.next = node.next;
219  
    node.value = -1; // mark invalid
220  
  }
221  
  
222  
  void newChain(S version, L<Int> encoding) {
223  
    chains.put(version, new Ch(encoding));
224  
  }
225  
  
226  
  PairInfo getPairInfo(IntPair pair) {
227  
    ret pairInfos.get(pair);
228  
  }
229  
  
230  
  void forgetPair(PairInfo pair) {
231  
    pairInfos.remove(pair.pair);
232  
    pair.bucket = null;
233  
  }
234  
  
235  
  void fullCheck {
236  
    assertTrue(oneBucket.lower == null);
237  
    assertTrue(oneBucket.level == 1);
238  
    Bucket b = highest;
239  
    while (b != oneBucket) {
240  
      assertNempty(b.pairs);
241  
      assertSame(b.lower.higher, b);
242  
      assertEquals(b.lower.level, b.level-1);
243  
      b = b.lower;
244  
    }
245  
  }
246  
}

Author comment

Began life as a copy of #1028247

download  show line numbers  debug dex  old transpilations   

Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv

No comments. add comment

Snippet ID: #1028249
Snippet name: LineComp_PairIndex_v2 with bucket list [OK]
Eternal ID of this version: #1028249/50
Text MD5: 6bb19fb4bc37d0394e3549817c072311
Transpilation MD5: 72599c9d5f4b9528ce16913438b02193
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2020-05-29 12:29:49
Source code size: 6769 bytes / 246 lines
Pitched / IR pitched: No / No
Views / Downloads: 335 / 698
Version history: 49 change(s)
Referenced in: [show references]