Mercurial > projects > ldc

comparison tango/tango/util/collection/impl/RBCell.d @ 132:1700239cab2e trunk

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