Mercurial > projects > hoofbaby

comparison src/impl/hoofbaby/util/redblack.d @ 0:3425707ddbf6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import (hopefully this mercurial stuff works...)
author fraserofthenight
date Mon, 06 Jul 2009 08:06:28 -0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3425707ddbf6
1 /*******************************************************************************
2
3 (this module taken from tango.util.container.RedBlack, since that
4 module is package-protected)
5
6 copyright: Copyright (c) 2008 Kris Bell. All rights reserved
7
8 license: BSD style: $(LICENSE)
9
10 version: Apr 2008: Initial release
11
12 authors: Kris, tsalm
13
14 Since: 0.99.7
15
16 Based upon Doug Lea's Java collection package
17
18 *******************************************************************************/
19
20 module candy.util.redblack;
21
22 template Compare (V) { alias int function (ref V a, ref V b) Compare; }
23
24 private typedef int AttributeDummy;
25
26 /*******************************************************************************
27
28 RedBlack implements basic capabilities of Red-Black trees,
29 an efficient kind of balanced binary tree. The particular
30 algorithms used are adaptations of those in Corman,
31 Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>.
32 This class was inspired by (and code cross-checked with) a
33 similar class by Chuck McManis. The implementations of
34 rebalancings during insertion and deletion are
35 a little trickier than those versions since they
36 don't swap Cell contents or use special dummy nilnodes.
37
38 Doug Lea
39
40 *******************************************************************************/
41
42 struct RedBlack (V, A = AttributeDummy)
43 {
44 alias RedBlack!(V, A) Type;
45 alias Type *Ref;
46
47 enum : bool {RED = false, BLACK = true}
48
49 /**
50 * Pointer to left child
51 **/
52
53 package Ref left;
54
55 /**
56 * Pointer to right child
57 **/
58
59 package Ref right;
60
61 /**
62 * Pointer to parent (null if root)
63 **/
64
65 package Ref parent;
66
67 package V value;
68
69 static if (!is(typeof(A) == AttributeDummy))
70 {
71 A attribute;
72 }
73
74 /**
75 * The node color (RED, BLACK)
76 **/
77
78 package bool color;
79
80 static if (!is(typeof(A) == AttributeDummy))
81 {
82 final Ref set (V v, A a)
83 {
84 attribute = a;
85 return set (v);
86 }
87 }
88
89 /**
90 * Make a new Cell with given value, null links, and BLACK color.
91 * Normally only called to establish a new root.
92 **/
93
94 final Ref set (V v)
95 {
96 value = v;
97 left = null;
98 right = null;
99 parent = null;
100 color = BLACK;
101 return this;
102 }
103
104 /**
105 * Return a new Ref with same value and color as self,
106 * but with null links. (Since it is never OK to have
107 * multiple identical links in a RB tree.)
108 **/
109
110 protected Ref dup (Ref delegate() alloc)
111 {
112 static if (is(typeof(A) == AttributeDummy))
113 auto t = alloc().set (value);
114 else
115 auto t = alloc().set (value, attribute);
116
117 t.color = color;
118 return t;
119 }
120
121
122 /**
123 * See_Also: tango.util.collection.model.View.View.checkImplementation.
124 **/
125 public void checkImplementation ()
126 {
127
128 // It's too hard to check the property that every simple
129 // path from node to leaf has same number of black nodes.
130 // So restrict to the following
131
132 assert(parent is null ||
133 this is parent.left ||
134 this is parent.right);
135
136 assert(left is null ||
137 this is left.parent);
138
139 assert(right is null ||
140 this is right.parent);
141
142 assert(color is BLACK ||
143 (colorOf(left) is BLACK) && (colorOf(right) is BLACK));
144
145 if (left !is null)
146 left.checkImplementation();
147 if (right !is null)
148 right.checkImplementation();
149 }
150
151 /**
152 * Return the minimum value of the current (sub)tree
153 **/
154
155 Ref leftmost ()
156 {
157 auto p = this;
158 for ( ; p.left; p = p.left) {}
159 return p;
160 }
161
162 /**
163 * Return the maximum value of the current (sub)tree
164 **/
165 Ref rightmost ()
166 {
167 auto p = this;
168 for ( ; p.right; p = p.right) {}
169 return p;
170 }
171
172 /**
173 * Return the root (parentless node) of the tree
174 **/
175 Ref root ()
176 {
177 auto p = this;
178 for ( ; p.parent; p = p.parent) {}
179 return p;
180 }
181
182 /**
183 * Return true if node is a root (i.e., has a null parent)
184 **/
185
186 bool isRoot ()
187 {
188 return parent is null;
189 }
190
191
192 /**
193 * Return the inorder successor, or null if no such
194 **/
195
196 Ref successor ()
197 {
198 if (right)
199 return right.leftmost;
200
201 auto p = parent;
202 auto ch = this;
203 while (p && ch is p.right)
204 {
205 ch = p;
206 p = p.parent;
207 }
208 return p;
209 }
210
211 /**
212 * Return the inorder predecessor, or null if no such
213 **/
214
215 Ref predecessor ()
216 {
217 if (left)
218 return left.rightmost;
219
220 auto p = parent;
221 auto ch = this;
222 while (p && ch is p.left)
223 {
224 ch = p;
225 p = p.parent;
226 }
227 return p;
228 }
229
230 /**
231 * Return the number of nodes in the subtree
232 **/
233 int size ()
234 {
235 auto c = 1;
236 if (left)
237 c += left.size;
238 if (right)
239 c += right.size;
240 return c;
241 }
242
243
244 /**
245 * Return node of current subtree containing value as value(),
246 * if it exists, else null.
247 * Uses Comparator cmp to find and to check equality.
248 **/
249
250 Ref find (V value, Compare!(V) cmp)
251 {
252 auto t = this;
253 for (;;)
254 {
255 auto diff = cmp (value, t.value);
256 if (diff is 0)
257 return t;
258 else
259 if (diff < 0)
260 t = t.left;
261 else
262 t = t.right;
263 if (t is null)
264 break;
265 }
266 return null;
267 }
268
269
270 /**
271 * Return node of subtree matching "value"
272 * or, if none found, the one just after or before
273 * if it doesn't exist, return null
274 * Uses Comparator cmp to find and to check equality.
275 **/
276 Ref findFirst (V value, Compare!(V) cmp, bool after = true)
277 {
278 auto t = this;
279 auto tLower = this;
280 auto tGreater = this;
281
282 for (;;)
283 {
284 auto diff = cmp (value, t.value);
285 if (diff is 0)
286 return t;
287 else
288 if (diff < 0)
289 {
290 tGreater = t;
291 t = t.left;
292 }
293 else
294 {
295 tLower = t;
296 t = t.right;
297 }
298 if (t is null)
299 break;
300 }
301
302 if (after)
303 {
304 if (cmp (value, tGreater.value) <= 0)
305 if (cmp (value, tGreater.value) < 0)
306 return tGreater;
307 }
308 else
309 {
310 if (cmp (value, tLower.value) >= 0)
311 if (cmp (value, tLower.value) > 0)
312 return tLower;
313 }
314
315 return null;
316 }
317
318 /**
319 * Return number of nodes of current subtree containing value.
320 * Uses Comparator cmp to find and to check equality.
321 **/
322 int count (V value, Compare!(V) cmp)
323 {
324 auto c = 0;
325 auto t = this;
326 while (t)
327 {
328 int diff = cmp (value, t.value);
329 if (diff is 0)
330 {
331 ++c;
332 if (t.left is null)
333 t = t.right;
334 else
335 if (t.right is null)
336 t = t.left;
337 else
338 {
339 c += t.right.count (value, cmp);
340 t = t.left;
341 }
342 }
343 else
344 if (diff < 0)
345 t = t.left;
346 else
347 t = t.right;
348 }
349 return c;
350 }
351
352 static if (!is(typeof(A) == AttributeDummy))
353 {
354 Ref findAttribute (A attribute, Compare!(A) cmp)
355 {
356 auto t = this;
357
358 while (t)
359 {
360 if (t.attribute == attribute)
361 return t;
362 else
363 if (t.right is null)
364 t = t.left;
365 else
366 if (t.left is null)
367 t = t.right;
368 else
369 {
370 auto p = t.left.findAttribute (attribute, cmp);
371
372 if (p !is null)
373 return p;
374 else
375 t = t.right;
376 }
377 }
378 return null; // not reached
379 }
380
381 int countAttribute (A attrib, Compare!(A) cmp)
382 {
383 int c = 0;
384 auto t = this;
385
386 while (t)
387 {
388 if (t.attribute == attribute)
389 ++c;
390
391 if (t.right is null)
392 t = t.left;
393 else
394 if (t.left is null)
395 t = t.right;
396 else
397 {
398 c += t.left.countAttribute (attribute, cmp);
399 t = t.right;
400 }
401 }
402 return c;
403 }
404
405 /**
406 * find and return a cell holding (key, element), or null if no such
407 **/
408 Ref find (V value, A attribute, Compare!(V) cmp)
409 {
410 auto t = this;
411
412 for (;;)
413 {
414 int diff = cmp (value, t.value);
415 if (diff is 0 && t.attribute == attribute)
416 return t;
417 else
418 if (diff <= 0)
419 t = t.left;
420 else
421 t = t.right;
422
423 if (t is null)
424 break;
425 }
426 return null;
427 }
428
429 }
430
431
432
433 /**
434 * Return a new subtree containing each value of current subtree
435 **/
436
437 Ref copyTree (Ref delegate() alloc)
438 {
439 auto t = dup (alloc);
440
441 if (left)
442 {
443 t.left = left.copyTree (alloc);
444 t.left.parent = t;
445 }
446
447 if (right)
448 {
449 t.right = right.copyTree (alloc);
450 t.right.parent = t;
451 }
452
453 return t;
454 }
455
456
457 /**
458 * There's no generic value insertion. Instead find the
459 * place you want to add a node and then invoke insertLeft
460 * or insertRight.
461 * <P>
462 * Insert Cell as the left child of current node, and then
463 * rebalance the tree it is in.
464 * @param Cell the Cell to add
465 * @param root, the root of the current tree
466 * Returns: the new root of the current tree. (Rebalancing
467 * can change the root!)
468 **/
469
470
471 Ref insertLeft (Ref cell, Ref root)
472 {
473 left = cell;
474 cell.parent = this;
475 return cell.fixAfterInsertion (root);
476 }
477
478 /**
479 * Insert Cell as the right child of current node, and then
480 * rebalance the tree it is in.
481 * @param Cell the Cell to add
482 * @param root, the root of the current tree
483 * Returns: the new root of the current tree. (Rebalancing
484 * can change the root!)
485 **/
486
487 Ref insertRight (Ref cell, Ref root)
488 {
489 right = cell;
490 cell.parent = this;
491 return cell.fixAfterInsertion (root);
492 }
493
494
495 /**
496 * Delete the current node, and then rebalance the tree it is in
497 * @param root the root of the current tree
498 * Returns: the new root of the current tree. (Rebalancing
499 * can change the root!)
500 **/
501
502
503 Ref remove (Ref root)
504 {
505 // handle case where we are only node
506 if (left is null && right is null && parent is null)
507 return null;
508
509 // if strictly internal, swap places with a successor
510 if (left && right)
511 {
512 auto s = successor;
513
514 // To work nicely with arbitrary subclasses of Ref, we don't want to
515 // just copy successor's fields. since we don't know what
516 // they are. Instead we swap positions _in the tree.
517 root = swapPosition (this, s, root);
518 }
519
520 // Start fixup at replacement node (normally a child).
521 // But if no children, fake it by using self
522
523 if (left is null && right is null)
524 {
525 if (color is BLACK)
526 root = this.fixAfterDeletion (root);
527
528 // Unlink (Couldn't before since fixAfterDeletion needs parent ptr)
529 if (parent)
530 {
531 if (this is parent.left)
532 parent.left = null;
533 else
534 if (this is parent.right)
535 parent.right = null;
536 parent = null;
537 }
538 }
539 else
540 {
541 auto replacement = left;
542 if (replacement is null)
543 replacement = right;
544
545 // link replacement to parent
546 replacement.parent = parent;
547
548 if (parent is null)
549 root = replacement;
550 else
551 if (this is parent.left)
552 parent.left = replacement;
553 else
554 parent.right = replacement;
555
556 left = null;
557 right = null;
558 parent = null;
559
560 // fix replacement
561 if (color is BLACK)
562 root = replacement.fixAfterDeletion (root);
563 }
564 return root;
565 }
566
567 /**
568 * Swap the linkages of two nodes in a tree.
569 * Return new root, in case it changed.
570 **/
571
572 static Ref swapPosition (Ref x, Ref y, Ref root)
573 {
574 /* Too messy. TODO: find sequence of assigments that are always OK */
575
576 auto px = x.parent;
577 bool xpl = px !is null && x is px.left;
578 auto lx = x.left;
579 auto rx = x.right;
580
581 auto py = y.parent;
582 bool ypl = py !is null && y is py.left;
583 auto ly = y.left;
584 auto ry = y.right;
585
586 if (x is py)
587 {
588 y.parent = px;
589 if (px !is null)
590 if (xpl)
591 px.left = y;
592 else
593 px.right = y;
594
595 x.parent = y;
596 if (ypl)
597 {
598 y.left = x;
599 y.right = rx;
600 if (rx !is null)
601 rx.parent = y;
602 }
603 else
604 {
605 y.right = x;
606 y.left = lx;
607 if (lx !is null)
608 lx.parent = y;
609 }
610
611 x.left = ly;
612 if (ly !is null)
613 ly.parent = x;
614
615 x.right = ry;
616 if (ry !is null)
617 ry.parent = x;
618 }
619 else
620 if (y is px)
621 {
622 x.parent = py;
623 if (py !is null)
624 if (ypl)
625 py.left = x;
626 else
627 py.right = x;
628
629 y.parent = x;
630 if (xpl)
631 {
632 x.left = y;
633 x.right = ry;
634 if (ry !is null)
635 ry.parent = x;
636 }
637 else
638 {
639 x.right = y;
640 x.left = ly;
641 if (ly !is null)
642 ly.parent = x;
643 }
644
645 y.left = lx;
646 if (lx !is null)
647 lx.parent = y;
648
649 y.right = rx;
650 if (rx !is null)
651 rx.parent = y;
652 }
653 else
654 {
655 x.parent = py;
656 if (py !is null)
657 if (ypl)
658 py.left = x;
659 else
660 py.right = x;
661
662 x.left = ly;
663 if (ly !is null)
664 ly.parent = x;
665
666 x.right = ry;
667 if (ry !is null)
668 ry.parent = x;
669
670 y.parent = px;
671 if (px !is null)
672 if (xpl)
673 px.left = y;
674 else
675 px.right = y;
676
677 y.left = lx;
678 if (lx !is null)
679 lx.parent = y;
680
681 y.right = rx;
682 if (rx !is null)
683 rx.parent = y;
684 }
685
686 bool c = x.color;
687 x.color = y.color;
688 y.color = c;
689
690 if (root is x)
691 root = y;
692 else
693 if (root is y)
694 root = x;
695 return root;
696 }
697
698
699
700 /**
701 * Return color of node p, or BLACK if p is null
702 * (In the CLR version, they use
703 * a special dummy `nil' node for such purposes, but that doesn't
704 * work well here, since it could lead to creating one such special
705 * node per real node.)
706 *
707 **/
708
709 static bool colorOf (Ref p)
710 {
711 return (p is null) ? BLACK : p.color;
712 }
713
714 /**
715 * return parent of node p, or null if p is null
716 **/
717 static Ref parentOf (Ref p)
718 {
719 return (p is null) ? null : p.parent;
720 }
721
722 /**
723 * Set the color of node p, or do nothing if p is null
724 **/
725
726 static void setColor (Ref p, bool c)
727 {
728 if (p !is null)
729 p.color = c;
730 }
731
732 /**
733 * return left child of node p, or null if p is null
734 **/
735
736 static Ref leftOf (Ref p)
737 {
738 return (p is null) ? null : p.left;
739 }
740
741 /**
742 * return right child of node p, or null if p is null
743 **/
744
745 static Ref rightOf (Ref p)
746 {
747 return (p is null) ? null : p.right;
748 }
749
750
751 /** From CLR **/
752 package Ref rotateLeft (Ref root)
753 {
754 auto r = right;
755 right = r.left;
756
757 if (r.left)
758 r.left.parent = this;
759
760 r.parent = parent;
761 if (parent is null)
762 root = r;
763 else
764 if (parent.left is this)
765 parent.left = r;
766 else
767 parent.right = r;
768
769 r.left = this;
770 parent = r;
771 return root;
772 }
773
774 /** From CLR **/
775 package Ref rotateRight (Ref root)
776 {
777 auto l = left;
778 left = l.right;
779
780 if (l.right !is null)
781 l.right.parent = this;
782
783 l.parent = parent;
784 if (parent is null)
785 root = l;
786 else
787 if (parent.right is this)
788 parent.right = l;
789 else
790 parent.left = l;
791
792 l.right = this;
793 parent = l;
794 return root;
795 }
796
797
798 /** From CLR **/
799 package Ref fixAfterInsertion (Ref root)
800 {
801 color = RED;
802 auto x = this;
803
804 while (x && x !is root && x.parent.color is RED)
805 {
806 if (parentOf(x) is leftOf(parentOf(parentOf(x))))
807 {
808 auto y = rightOf(parentOf(parentOf(x)));
809 if (colorOf(y) is RED)
810 {
811 setColor(parentOf(x), BLACK);
812 setColor(y, BLACK);
813 setColor(parentOf(parentOf(x)), RED);
814 x = parentOf(parentOf(x));
815 }
816 else
817 {
818 if (x is rightOf(parentOf(x)))
819 {
820 x = parentOf(x);
821 root = x.rotateLeft(root);
822 }
823
824 setColor(parentOf(x), BLACK);
825 setColor(parentOf(parentOf(x)), RED);
826 if (parentOf(parentOf(x)) !is null)
827 root = parentOf(parentOf(x)).rotateRight(root);
828 }
829 }
830 else
831 {
832 auto y = leftOf(parentOf(parentOf(x)));
833 if (colorOf(y) is RED)
834 {
835 setColor(parentOf(x), BLACK);
836 setColor(y, BLACK);
837 setColor(parentOf(parentOf(x)), RED);
838 x = parentOf(parentOf(x));
839 }
840 else
841 {
842 if (x is leftOf(parentOf(x)))
843 {
844 x = parentOf(x);
845 root = x.rotateRight(root);
846 }
847
848 setColor(parentOf(x), BLACK);
849 setColor(parentOf(parentOf(x)), RED);
850 if (parentOf(parentOf(x)) !is null)
851 root = parentOf(parentOf(x)).rotateLeft(root);
852 }
853 }
854 }
855 root.color = BLACK;
856 return root;
857 }
858
859
860
861 /** From CLR **/
862 package Ref fixAfterDeletion(Ref root)
863 {
864 auto x = this;
865 while (x !is root && colorOf(x) is BLACK)
866 {
867 if (x is leftOf(parentOf(x)))
868 {
869 auto sib = rightOf(parentOf(x));
870 if (colorOf(sib) is RED)
871 {
872 setColor(sib, BLACK);
873 setColor(parentOf(x), RED);
874 root = parentOf(x).rotateLeft(root);
875 sib = rightOf(parentOf(x));
876 }
877 if (colorOf(leftOf(sib)) is BLACK && colorOf(rightOf(sib)) is BLACK)
878 {
879 setColor(sib, RED);
880 x = parentOf(x);
881 }
882 else
883 {
884 if (colorOf(rightOf(sib)) is BLACK)
885 {
886 setColor(leftOf(sib), BLACK);
887 setColor(sib, RED);
888 root = sib.rotateRight(root);
889 sib = rightOf(parentOf(x));
890 }
891
892 setColor(sib, colorOf(parentOf(x)));
893 setColor(parentOf(x), BLACK);
894 setColor(rightOf(sib), BLACK);
895 root = parentOf(x).rotateLeft(root);
896 x = root;
897 }
898 }
899 else
900 {
901 auto sib = leftOf(parentOf(x));
902 if (colorOf(sib) is RED)
903 {
904 setColor(sib, BLACK);
905 setColor(parentOf(x), RED);
906 root = parentOf(x).rotateRight(root);
907 sib = leftOf(parentOf(x));
908 }
909
910 if (colorOf(rightOf(sib)) is BLACK && colorOf(leftOf(sib)) is BLACK)
911 {
912 setColor(sib, RED);
913 x = parentOf(x);
914 }
915 else
916 {
917 if (colorOf(leftOf(sib)) is BLACK)
918 {
919 setColor(rightOf(sib), BLACK);
920 setColor(sib, RED);
921 root = sib.rotateLeft(root);
922 sib = leftOf(parentOf(x));
923 }
924
925 setColor(sib, colorOf(parentOf(x)));
926 setColor(parentOf(x), BLACK);
927 setColor(leftOf(sib), BLACK);
928 root = parentOf(x).rotateRight(root);
929 x = root;
930 }
931 }
932 }
933
934 setColor(x, BLACK);
935 return root;
936 }
937 }