Mercurial > projects > doodle

comparison doodle/containers/tree_set.d @ 40:1f97022e5c6d

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