|
132
|
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
|
