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