Libraryless. Click here for Pure Java version (4561L/27K).
1 | // based on: https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html |
2 | // TODO: implement NavigableSet |
3 | |
4 | // RAM use in a CompressedOOPS JVM (bytes per element): |
5 | // ~12 when elements are inserted in sorted order |
6 | // ~13.7 when elements are inserted in random order |
7 | // |
8 | // (Obviously more for very small sets.) |
9 | |
10 | sclass HyperCompactTreeSet<A> extends AbstractSet<A> { |
11 | |
12 | // A symbol table implemented using a left-leaning red-black BST. |
13 | // This is the 2-3 version. |
14 | |
15 | // Note: We sometimes cast the nullSentinel to A |
16 | // which is technically incorrect but ok because of type erasure. |
17 | // May want to fix just to be clean on the source level too. |
18 | |
19 | private static final boolean RED = true; |
20 | private static final boolean BLACK = false; |
21 | |
22 | // replacement for null elements |
23 | private static final new O nullSentinel; |
24 | |
25 | // root of the BST (null, Node or sentinelled user object) |
26 | // in the latter case it is assumed to be red |
27 | private O root; |
28 | int size; // size of tree set |
29 | |
30 | // BST helper node data type |
31 | abstract sclass Node<A> { |
32 | A val; // associated data |
33 | |
34 | Node<A> left() { null; } // get left subtree |
35 | abstract Node<A> setLeft(Node<A> left); // set left subtree - return potentially replaced node |
36 | |
37 | Node<A> right() { null; } // get right subtree |
38 | abstract Node<A> setRight(Node<A> right); // set right subtree - return potentially replaced node |
39 | |
40 | abstract bool color(); |
41 | abstract Node<A> convertToBlack(); |
42 | abstract Node<A> convertToRed(); |
43 | abstract Node<A> invertColor(); |
44 | Node<A> convertToColor(bool color) { ret color == RED ? convertToRed() : convertToBlack(); } |
45 | |
46 | abstract bool isLeaf(); |
47 | } |
48 | |
49 | // This represents a common case near a red leaf - a black node |
50 | // containing a red leaf in the left slot and null in the right slot. |
51 | // Combined with the direct storage of black leaf children in NonLeaf, |
52 | // this is all we need to get rid of all the leaf overhead. Yay! |
53 | sclass SpecialNode<A> extends Node<A> { |
54 | A leftVal; |
55 | |
56 | *(A *leftVal, A *val) {} |
57 | |
58 | bool color() { ret BLACK; } |
59 | Node<A> convertToBlack() { this; } |
60 | Node<A> convertToRed() { ret newNode(RED, val, left(), right()); } |
61 | Node invertColor() { ret convertToRed(); } |
62 | |
63 | Node<A> left() { |
64 | ret newLeaf(RED, leftVal); |
65 | } |
66 | |
67 | Node<A> setLeft(Node<A> left) { |
68 | // Can we keep the optimized representation? (Probably this |
69 | // is never going to be true.) |
70 | if (left != null && left.isLeaf() && left.color() == RED) |
71 | ret this with leftVal = left.val; |
72 | else |
73 | ret newNode(BLACK, val, left, right()); |
74 | } |
75 | |
76 | Node<A> right() { |
77 | null; |
78 | } |
79 | |
80 | Node<A> setRight(Node<A> right) { |
81 | if (right == null) this; |
82 | ret newNode(color(), val, left(), right); |
83 | } |
84 | |
85 | bool isLeaf() { false; } |
86 | } |
87 | |
88 | asclass NonLeaf<A> extends Node<A> { |
89 | // either a Node or a (sentinelled) direct user value |
90 | O left, right; |
91 | |
92 | // color of leaf if left is a user value |
93 | bool defaultLeftLeafColor() { ret BLACK; } |
94 | |
95 | // color of leaf if right is a user value |
96 | bool defaultRightLeafColor() { ret BLACK; } |
97 | |
98 | Node<A> left() { |
99 | ret left == null ? null |
100 | : left instanceof Node ? (Node) left |
101 | : newLeaf(defaultLeftLeafColor(), (A) left); |
102 | } |
103 | |
104 | void setLeft_noMorph(Node<A> left) { |
105 | this.left = left != null && left.isLeaf() && left.color() == defaultLeftLeafColor() ? left.val : left; |
106 | } |
107 | |
108 | void setRight_noMorph(Node<A> right) { |
109 | this.right = right != null && right.isLeaf() && right.color() == defaultRightLeafColor() ? right.val : right; |
110 | } |
111 | |
112 | Node<A> setLeft(Node<A> left) { |
113 | ifndef HyperCompactTreeSet_disableSpecialNodes |
114 | if (color() == BLACK && right == null && left != null && left.isLeaf() && left.color() == RED) |
115 | ret new SpecialNode(left.val, val); |
116 | endifndef |
117 | |
118 | setLeft_noMorph(left); |
119 | if (left == null && right() == null) ret newLeaf(color(), val); |
120 | this; |
121 | } |
122 | |
123 | Node<A> right() { |
124 | ret right == null ? null |
125 | : right instanceof Node ? (Node) right |
126 | : newLeaf(defaultRightLeafColor(), (A) right); |
127 | } |
128 | |
129 | Node<A> setRight(Node<A> right) { |
130 | // Setting right to null may produce either a leaf or a |
131 | // special node, so we just go through newNode. |
132 | if (right == null && this.right != null) |
133 | ret newNode(color(), val, left(), null); |
134 | |
135 | // New right is not null, so we compress (if possible) and store it |
136 | setRight_noMorph(right); |
137 | this; |
138 | } |
139 | |
140 | bool isLeaf() { false; } |
141 | } |
142 | |
143 | sclass BlackNode<A> extends NonLeaf<A> { |
144 | *(A *val) {} |
145 | |
146 | bool color() { ret BLACK; } |
147 | Node<A> convertToBlack() { this; } |
148 | Node<A> convertToRed() { ret newNode(RED, val, left(), right()); } |
149 | Node invertColor() { ret convertToRed(); } |
150 | } |
151 | |
152 | sclass RedNode<A> extends NonLeaf<A> { |
153 | *(A *val) {} |
154 | |
155 | bool color() { ret RED; } |
156 | Node<A> convertToBlack() { ret newNode(BLACK, val, left(), right()); } |
157 | Node<A> convertToRed() { this; } |
158 | Node invertColor() { ret convertToBlack(); } |
159 | } |
160 | |
161 | asclass Leaf<A> extends Node<A> { |
162 | bool isLeaf() { true; } |
163 | |
164 | Node<A> setLeft(Node<A> left) { |
165 | ret left == null ? this : newNode(color(), val, left, null); |
166 | } |
167 | |
168 | Node<A> setRight(Node<A> right) { |
169 | ret right == null ? this : newNode(color(), val, null, right); |
170 | } |
171 | } |
172 | |
173 | sclass BlackLeaf<A> extends Leaf<A> { |
174 | *(A *val) {} |
175 | |
176 | bool color() { ret BLACK; } |
177 | Node<A> convertToBlack() { this; } |
178 | Node<A> convertToRed() { ret new RedLeaf(val); } |
179 | Node invertColor() { ret convertToRed(); } |
180 | } |
181 | |
182 | sclass RedLeaf<A> extends Leaf<A> { |
183 | *(A *val) {} |
184 | |
185 | bool color() { ret RED; } |
186 | Node<A> convertToBlack() { ret new BlackLeaf(val); } |
187 | Node<A> convertToRed() { this; } |
188 | Node invertColor() { ret convertToBlack(); } |
189 | } |
190 | |
191 | *() {} |
192 | *(Cl<? extends A> cl) { addAll(cl); } |
193 | |
194 | private static O deSentinel(O o) { |
195 | ret o == nullSentinel ? null : o; |
196 | } |
197 | |
198 | private static O sentinel(O o) { |
199 | ret o == null ? nullSentinel : o; |
200 | } |
201 | |
202 | // returns false on null (algorithm needs this) |
203 | static bool <A> isRed(Node<A> x) { |
204 | ret x != null && x.color() == RED; |
205 | } |
206 | |
207 | static <A> Node<A> newLeaf(bool color, A val) { |
208 | ret color == RED ? new RedLeaf(val) : new BlackLeaf(val); |
209 | } |
210 | |
211 | static <A> Node<A> newNode(bool color, A val, Node<A> left, Node<A> right) { |
212 | // Make leaf (always a temporary object now) |
213 | if (left == null && right == null) |
214 | ret newLeaf(color, val); |
215 | |
216 | ifndef HyperCompactTreeSet_disableSpecialNodes |
217 | // Make special node |
218 | if (color == BLACK |
219 | && right == null |
220 | && left != null && left.isLeaf() && left.color() == RED) |
221 | ret new SpecialNode(left.val, val); |
222 | endifndef |
223 | |
224 | // Make normal non-leaf |
225 | NonLeaf node = color == RED ? new RedNode(val) : new BlackNode(val); |
226 | node.setLeft_noMorph(left); |
227 | node.setRight_noMorph(right); |
228 | ret node; |
229 | } |
230 | |
231 | public int size() { |
232 | ret size; |
233 | } |
234 | |
235 | public bool isEmpty() { |
236 | ret root == null; |
237 | } |
238 | |
239 | Node<A> root() { |
240 | ret root == null ? null |
241 | : root instanceof Node ? (Node) root |
242 | : newLeaf(RED, (A) root); |
243 | } |
244 | |
245 | void setRoot(Node<A> root) { |
246 | if (root == null) this.root = null; |
247 | else if (root.isLeaf()) this.root = root.val; |
248 | else this.root = root; |
249 | } |
250 | |
251 | public bool add(A val) { |
252 | val = (A) sentinel(val); |
253 | int oldSize = size; |
254 | setRoot(put(root(), val).convertToBlack()); |
255 | ifdef CompactTreeSet_debug assertTrue(check()); endifdef |
256 | ret size > oldSize; |
257 | } |
258 | |
259 | // insert the value in the subtree rooted at h |
260 | private Node<A> put(Node<A> h, A val) { |
261 | if (h == null) { ++size; ret new RedLeaf(val); } |
262 | |
263 | int cmp = compare_deSentinel(val, h.val); |
264 | if (cmp < 0) h = h.setLeft(put(h.left(), val)); |
265 | else if (cmp > 0) h = h.setRight(put(h.right(), val)) ; |
266 | else { /*h.val = val;*/ } // no overwriting |
267 | |
268 | // fix-up any right-leaning links |
269 | if (isRed(h.right()) && !isRed(h.left())) h = rotateLeft(h); |
270 | if (isRed(h.left()) && isRed(h.left().left())) h = rotateRight(h); |
271 | if (isRed(h.left()) && isRed(h.right())) h = flipColors(h); |
272 | |
273 | ret h; |
274 | } |
275 | |
276 | final int compare_deSentinel(A a, A b) { |
277 | ret compare((A) deSentinel(a), (A) deSentinel(b)); |
278 | } |
279 | |
280 | // override me if you wish |
281 | int compare(A a, A b) { |
282 | ret cmp(a, b); |
283 | } |
284 | |
285 | public bool remove(O key) { |
286 | if (root == null || !contains(key)) false; |
287 | |
288 | key = sentinel(key); |
289 | |
290 | // if both children of root are black, set root to red |
291 | Node root = root(); |
292 | if (!isRed(root.left()) && !isRed(root.right())) |
293 | root = root.convertToRed(); |
294 | |
295 | root = delete(root, (A) key); |
296 | if (root != null) root = root.convertToBlack(); |
297 | |
298 | setRoot(root); |
299 | // assert check(); |
300 | true; |
301 | } |
302 | |
303 | // delete the key-value pair with the given key rooted at h |
304 | private Node delete(Node<A> h, A key) { |
305 | // assert get(h, key) != null; |
306 | |
307 | if (compare_deSentinel(key, h.val) < 0) { |
308 | if (!isRed(h.left()) && !isRed(h.left().left())) |
309 | h = moveRedLeft(h); |
310 | h = h.setLeft(delete(h.left(), key)); |
311 | } |
312 | else { |
313 | if (isRed(h.left())) |
314 | h = rotateRight(h); |
315 | if (compare_deSentinel(key, h.val) == 0 && (h.right() == null)) { |
316 | --size; null; |
317 | } if (!isRed(h.right()) && !isRed(h.right().left())) |
318 | h = moveRedRight(h); |
319 | if (compare_deSentinel(key, h.val) == 0) { |
320 | --size; |
321 | Node<A> x = min(h.right()); |
322 | h.val = x.val; |
323 | // h.val = get(h.right(), min(h.right()).val); |
324 | // h.val = min(h.right()).val; |
325 | h = h.setRight(deleteMin(h.right())); |
326 | } |
327 | else h = h.setRight(delete(h.right(), key)); |
328 | } |
329 | return balance(h); |
330 | } |
331 | |
332 | // make a left-leaning link lean to the right |
333 | private Node<A> rotateRight(Node<A> h) { |
334 | // assert (h != null) && isRed(h.left()); |
335 | Node<A> x = h.left(); |
336 | h = h.setLeft(x.right()); |
337 | x = x.setRight(h); |
338 | x = x.convertToColor(x.right().color()); |
339 | x = x.setRight(x.right().convertToRed()); |
340 | ret x; |
341 | } |
342 | |
343 | // make a right-leaning link lean to the left |
344 | private Node<A> rotateLeft(Node<A> h) { |
345 | // assert (h != null) && isRed(h.right()); |
346 | Node<A> x = h.right(); |
347 | h = h.setRight(x.left()); |
348 | x = x.setLeft(h); |
349 | x = x.convertToColor(x.left().color()); |
350 | x = x.setLeft(x.left().convertToRed()); |
351 | ret x; |
352 | } |
353 | |
354 | // flip the colors of a node and its two children |
355 | private Node<A> flipColors(Node<A> h) { |
356 | // h must have opposite color of its two children |
357 | // assert (h != null) && (h.left() != null) && (h.right() != null); |
358 | // assert (!isRed(h) && isRed(h.left()) && isRed(h.right())) |
359 | // || (isRed(h) && !isRed(h.left()) && !isRed(h.right())); |
360 | h = h.setLeft(h.left().invertColor()); |
361 | h = h.setRight(h.right().invertColor()); |
362 | ret h.invertColor(); |
363 | } |
364 | |
365 | // Assuming that h is red and both h.left() and h.left().left() |
366 | // are black, make h.left() or one of its children red. |
367 | private Node<A> moveRedLeft(Node<A> h) { |
368 | // assert (h != null); |
369 | // assert isRed(h) && !isRed(h.left()) && !isRed(h.left().left()); |
370 | |
371 | h = flipColors(h); |
372 | if (isRed(h.right().left())) { |
373 | h = h.setRight(rotateRight(h.right())); |
374 | h = rotateLeft(h); |
375 | h = flipColors(h); |
376 | } |
377 | ret h; |
378 | } |
379 | |
380 | // Assuming that h is red and both h.right() and h.right().left() |
381 | // are black, make h.right() or one of its children red. |
382 | private Node<A> moveRedRight(Node<A> h) { |
383 | // assert (h != null); |
384 | // assert isRed(h) && !isRed(h.right()) && !isRed(h.right().left()); |
385 | h = flipColors(h); |
386 | if (isRed(h.left().left())) { |
387 | h = rotateRight(h); |
388 | h = flipColors(h); |
389 | } |
390 | ret h; |
391 | } |
392 | |
393 | // restore red-black tree invariant |
394 | private Node<A> balance(Node<A> h) { |
395 | // assert (h != null); |
396 | |
397 | if (isRed(h.right())) h = rotateLeft(h); |
398 | if (isRed(h.left()) && isRed(h.left().left())) h = rotateRight(h); |
399 | if (isRed(h.left()) && isRed(h.right())) h = flipColors(h); |
400 | |
401 | ret h; |
402 | } |
403 | |
404 | |
405 | /** |
406 | * Returns the height of the BST (for debugging). |
407 | * @return the height of the BST (a 1-node tree has height 0) |
408 | */ |
409 | public int height() { |
410 | ret height(root()); |
411 | } |
412 | |
413 | private int height(Node<A> x) { |
414 | if (x == null) return -1; |
415 | return 1 + Math.max(height(x.left()), height(x.right())); |
416 | } |
417 | |
418 | public bool contains(O val) { |
419 | ret find(root(), (A) sentinel(val)) != null; |
420 | } |
421 | |
422 | public A find(A probeVal) { |
423 | probeVal = (A) sentinel(probeVal); |
424 | Node<A> n = find(root(), probeVal); |
425 | ret n == null ? null : n.val; |
426 | } |
427 | |
428 | // value associated with the given key in subtree rooted at x; null if no such key |
429 | private A get(Node<A> x, A key) { |
430 | x = find(x, key); |
431 | ret x == null ? null : x.val; |
432 | } |
433 | |
434 | Node<A> find(Node<A> x, A key) { |
435 | while (x != null) { |
436 | int cmp = compare_deSentinel(key, x.val); |
437 | if (cmp < 0) x = x.left(); |
438 | else if (cmp > 0) x = x.right(); |
439 | else ret x; |
440 | } |
441 | null; |
442 | } |
443 | |
444 | private boolean check() { |
445 | if (!is23()) println("Not a 2-3 tree"); |
446 | if (!isBalanced()) println("Not balanced"); |
447 | return is23() && isBalanced(); |
448 | } |
449 | |
450 | // Does the tree have no red right links, and at most one (left) |
451 | // red links in a row on any path? |
452 | private boolean is23() { return is23(root()); } |
453 | private boolean is23(Node<A> x) { |
454 | if (x == null) true; |
455 | if (isRed(x.right())) false; |
456 | if (x != root && isRed(x) && isRed(x.left())) false; |
457 | ret is23(x.left()) && is23(x.right()); |
458 | } |
459 | |
460 | // do all paths from root to leaf have same number of black edges? |
461 | private bool isBalanced() { |
462 | int black = 0; // number of black links on path from root to min |
463 | Node<A> x = root(); |
464 | while (x != null) { |
465 | if (!isRed(x)) black++; |
466 | x = x.left(); |
467 | } |
468 | ret isBalanced(root(), black); |
469 | } |
470 | |
471 | // does every path from the root to a leaf have the given number of black links? |
472 | private boolean isBalanced(Node<A> x, int black) { |
473 | if (x == null) return black == 0; |
474 | if (!isRed(x)) black--; |
475 | return isBalanced(x.left(), black) && isBalanced(x.right(), black); |
476 | } |
477 | |
478 | public void clear() { root = null; size = 0; } |
479 | |
480 | // the smallest key in subtree rooted at x; null if no such key |
481 | private Node<A> min(Node<A> x) { |
482 | // assert x != null; |
483 | while (x.left() != null) x = x.left(); |
484 | ret x; |
485 | } |
486 | |
487 | private Node<A> deleteMin(Node<A> h) { |
488 | if (h.left() == null) |
489 | return null; |
490 | |
491 | if (!isRed(h.left()) && !isRed(h.left().left())) |
492 | h = moveRedLeft(h); |
493 | |
494 | h = h.setLeft(deleteMin(h.left())); |
495 | ret balance(h); |
496 | } |
497 | |
498 | public Iterator<A> iterator() { |
499 | ret new MyIterator; |
500 | } |
501 | |
502 | class MyIterator extends ItIt<A> { |
503 | new L<Node<A>> path; |
504 | |
505 | *() { |
506 | fetch(root()); |
507 | } |
508 | |
509 | void fetch(Node<A> node) { |
510 | while (node != null) { |
511 | path.add(node); |
512 | node = node.left(); |
513 | } |
514 | } |
515 | |
516 | public bool hasNext() { ret !path.isEmpty(); } |
517 | |
518 | public A next() { |
519 | if (path.isEmpty()) fail("no more elements"); |
520 | Node<A> node = popLast(path); |
521 | // last node is always a leaf, so left is null |
522 | // so proceed to fetch right branch |
523 | fetch(node.right()); |
524 | ret (A) deSentinel(node.val); |
525 | } |
526 | } |
527 | |
528 | // Returns the smallest key in the symbol table greater than or equal to {@code key}. |
529 | public A ceiling(A key) { |
530 | key = (A) sentinel(key); |
531 | Node<A> x = ceiling(root(), key); |
532 | ret x == null ? null : x.val; |
533 | } |
534 | |
535 | // the smallest key in the subtree rooted at x greater than or equal to the given key |
536 | Node<A> ceiling(Node<A> x, A key) { |
537 | if (x == null) null; |
538 | int cmp = compare_deSentinel(key, x.val); |
539 | if (cmp == 0) ret x; |
540 | if (cmp > 0) ret ceiling(x.right(), key); |
541 | Node<A> t = ceiling(x.left(), key); |
542 | if (t != null) ret t; |
543 | else ret x; |
544 | } |
545 | |
546 | public A floor(A key) { |
547 | key = (A) sentinel(key); |
548 | Node<A> x = floor(root(), key); |
549 | ret x == null ? null : x.val; |
550 | } |
551 | |
552 | // the largest key in the subtree rooted at x less than or equal to the given key |
553 | Node<A> floor(Node<A> x, A key) { |
554 | if (x == null) null; |
555 | int cmp = compare_deSentinel(key, x.val); |
556 | if (cmp == 0) ret x; |
557 | if (cmp < 0) ret floor(x.left(), key); |
558 | Node<A> t = floor(x.right(), key); |
559 | if (t != null) ret t; |
560 | else ret x; |
561 | } |
562 | |
563 | void testInternalStructure() { |
564 | ifndef HyperCompactTreeSet_disableSpecialNodes |
565 | // one leaf object (root) is allowed - could even optimize that |
566 | assertTrue(countLeafObjects() <= 1); |
567 | endifndef |
568 | } |
569 | |
570 | // count leaf objects we didn't optimize away |
571 | int countLeafObjects(Node node default root()) { |
572 | if (node instanceof Leaf) ret 1; |
573 | if (node cast NonLeaf) |
574 | ret countLeafObjects(optCast Node(node.left)) |
575 | + countLeafObjects(optCast Node(node.right)); |
576 | ret 0; |
577 | } |
578 | |
579 | Cl<NonLeaf> unoptimizedNodes() { |
580 | new L<NonLeaf> out; |
581 | findUnoptimizedNodes(out); |
582 | ret out; |
583 | } |
584 | |
585 | void findUnoptimizedNodes(Node node default root(), L<NonLeaf> out) { |
586 | if (node == null) ret; |
587 | if (node cast NonLeaf) { |
588 | if (isUnoptimizedNode(node)) out.add(node); |
589 | findUnoptimizedNodes(optCast Node(node.left), out); |
590 | findUnoptimizedNodes(optCast Node(node.right), out); |
591 | } |
592 | } |
593 | |
594 | bool isUnoptimizedNode(Node node) { |
595 | if (node cast NonLeaf) |
596 | ret node.left instanceof Leaf |
597 | || node.right instanceof Leaf; |
598 | false; |
599 | } |
600 | |
601 | // Compact me (minimize space use). Returns a compacted copy. |
602 | // This only has an effect when elements were inserted in non-sorted |
603 | // or and/or elements were removed. |
604 | selfType compact() { |
605 | ret new HyperCompactTreeSet(this); |
606 | } |
607 | } |
Began life as a copy of #1032628
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
Snippet ID: | #1032641 |
Snippet name: | HyperCompactTreeSet optimized for size=1 [backup] |
Eternal ID of this version: | #1032641/13 |
Text MD5: | 458d07d29e3206a55b8ed1be6de97e3b |
Transpilation MD5: | d3cb45afc4542d9e12be7e50c10a4906 |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2021-09-29 23:54:05 |
Source code size: | 18466 bytes / 607 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 145 / 227 |
Version history: | 12 change(s) |
Referenced in: | [show references] |