aboutsummaryrefslogtreecommitdiffstats
path: root/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java
diff options
context:
space:
mode:
Diffstat (limited to 'Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java')
-rw-r--r--Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java1392
1 files changed, 1392 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java
new file mode 100644
index 00000000..8c40816b
--- /dev/null
+++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java
@@ -0,0 +1,1392 @@
1/*
2 * The MIT License (MIT)
3 *
4 * Copyright (c) 2016 btrekkie
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval;
25
26import java.lang.reflect.Array;
27import java.util.Collection;
28import java.util.Comparator;
29import java.util.HashSet;
30import java.util.Iterator;
31import java.util.Set;
32
33/**
34 * A node in a red-black tree ( https://en.wikipedia.org/wiki/Red%E2%80%93black_tree ). Compared to a class like Java's
35 * TreeMap, RedBlackNode is a low-level data structure. The internals of a node are exposed as public fields, allowing
36 * clients to directly observe and manipulate the structure of the tree. This gives clients flexibility, although it
37 * also enables them to violate the red-black or BST properties. The RedBlackNode class provides methods for performing
38 * various standard operations, such as insertion and removal.
39 *
40 * Unlike most implementations of binary search trees, RedBlackNode supports arbitrary augmentation. By subclassing
41 * RedBlackNode, clients can add arbitrary data and augmentation information to each node. For example, if we were to
42 * use a RedBlackNode subclass to implement a sorted set, the subclass would have a field storing an element in the set.
43 * If we wanted to keep track of the number of non-leaf nodes in each subtree, we would store this as a "size" field and
44 * override augment() to update this field. All RedBlackNode methods (such as "insert" and remove()) call augment() as
45 * necessary to correctly maintain the augmentation information, unless otherwise indicated.
46 *
47 * The values of the tree are stored in the non-leaf nodes. RedBlackNode does not support use cases where values must be
48 * stored in the leaf nodes. It is recommended that all of the leaf nodes in a given tree be the same (black)
49 * RedBlackNode instance, to save space. The root of an empty tree is a leaf node, as opposed to null.
50 *
51 * For reference, a red-black tree is a binary search tree satisfying the following properties:
52 *
53 * - Every node is colored red or black.
54 * - The leaf nodes, which are dummy nodes that do not store any values, are colored black.
55 * - The root is black.
56 * - Both children of each red node are black.
57 * - Every path from the root to a leaf contains the same number of black nodes.
58 *
59 * @param <N> The type of node in the tree. For example, we might have
60 * "class FooNode<T> extends RedBlackNode<FooNode<T>>".
61 * @author Bill Jacobs
62 */
63public abstract class RedBlackNode<N extends RedBlackNode<N>> implements Comparable<N> {
64 /** A Comparator that compares Comparable elements using their natural order. */
65 private static final Comparator<Comparable<Object>> NATURAL_ORDER = new Comparator<Comparable<Object>>() {
66 @Override
67 public int compare(Comparable<Object> value1, Comparable<Object> value2) {
68 return value1.compareTo(value2);
69 }
70 };
71
72 /** The parent of this node, if any. "parent" is null if this is a leaf node. */
73 public N parent;
74
75 /** The left child of this node. "left" is null if this is a leaf node. */
76 public N left;
77
78 /** The right child of this node. "right" is null if this is a leaf node. */
79 public N right;
80
81 /** Whether the node is colored red, as opposed to black. */
82 public boolean isRed;
83
84 /**
85 * Sets any augmentation information about the subtree rooted at this node that is stored in this node. For
86 * example, if we augment each node by subtree size (the number of non-leaf nodes in the subtree), this method would
87 * set the size field of this node to be equal to the size field of the left child plus the size field of the right
88 * child plus one.
89 *
90 * "Augmentation information" is information that we can compute about a subtree rooted at some node, preferably
91 * based only on the augmentation information in the node's two children and the information in the node. Examples
92 * of augmentation information are the sum of the values in a subtree and the number of non-leaf nodes in a subtree.
93 * Augmentation information may not depend on the colors of the nodes.
94 *
95 * This method returns whether the augmentation information in any of the ancestors of this node might have been
96 * affected by changes in this subtree since the last call to augment(). In the usual case, where the augmentation
97 * information depends only on the information in this node and the augmentation information in its immediate
98 * children, this is equivalent to whether the augmentation information changed as a result of this call to
99 * augment(). For example, in the case of subtree size, this returns whether the value of the size field prior to
100 * calling augment() differed from the size field of the left child plus the size field of the right child plus one.
101 * False positives are permitted. The return value is unspecified if we have not called augment() on this node
102 * before.
103 *
104 * This method may assume that this is not a leaf node. It may not assume that the augmentation information stored
105 * in any of the tree's nodes is correct. However, if the augmentation information stored in all of the node's
106 * descendants is correct, then the augmentation information stored in this node must be correct after calling
107 * augment().
108 */
109 public boolean augment() {
110 return false;
111 }
112
113 /**
114 * Throws a RuntimeException if we detect that this node locally violates any invariants specific to this subclass
115 * of RedBlackNode. For example, if this stores the size of the subtree rooted at this node, this should throw a
116 * RuntimeException if the size field of this is not equal to the size field of the left child plus the size field
117 * of the right child plus one. Note that we may call this on a leaf node.
118 *
119 * assertSubtreeIsValid() calls assertNodeIsValid() on each node, or at least starts to do so until it detects a
120 * problem. assertNodeIsValid() should assume the node is in a tree that satisfies all properties common to all
121 * red-black trees, as assertSubtreeIsValid() is responsible for such checks. assertNodeIsValid() should be
122 * "downward-looking", i.e. it should ignore any information in "parent", and it should be "local", i.e. it should
123 * only check a constant number of descendants. To include "global" checks, such as verifying the BST property
124 * concerning ordering, override assertSubtreeIsValid(). assertOrderIsValid is useful for checking the BST
125 * property.
126 */
127 public void assertNodeIsValid() {
128
129 }
130
131 /** Returns whether this is a leaf node. */
132 public boolean isLeaf() {
133 return left == null;
134 }
135
136 /** Returns the root of the tree that contains this node. */
137 public N root() {
138 @SuppressWarnings("unchecked")
139 N node = (N)this;
140 while (node.parent != null) {
141 node = node.parent;
142 }
143 return node;
144 }
145
146 /** Returns the first node in the subtree rooted at this node, if any. */
147 public N min() {
148 if (isLeaf()) {
149 return null;
150 }
151 @SuppressWarnings("unchecked")
152 N node = (N)this;
153 while (!node.left.isLeaf()) {
154 node = node.left;
155 }
156 return node;
157 }
158
159 /** Returns the last node in the subtree rooted at this node, if any. */
160 public N max() {
161 if (isLeaf()) {
162 return null;
163 }
164 @SuppressWarnings("unchecked")
165 N node = (N)this;
166 while (!node.right.isLeaf()) {
167 node = node.right;
168 }
169 return node;
170 }
171
172 /** Returns the node immediately before this in the tree that contains this node, if any. */
173 public N predecessor() {
174 if (!left.isLeaf()) {
175 N node;
176 for (node = left; !node.right.isLeaf(); node = node.right);
177 return node;
178 } else if (parent == null) {
179 return null;
180 } else {
181 @SuppressWarnings("unchecked")
182 N node = (N)this;
183 while (node.parent != null && node.parent.left == node) {
184 node = node.parent;
185 }
186 return node.parent;
187 }
188 }
189
190 /** Returns the node immediately after this in the tree that contains this node, if any. */
191 public N successor() {
192 if (!right.isLeaf()) {
193 N node;
194 for (node = right; !node.left.isLeaf(); node = node.left);
195 return node;
196 } else if (parent == null) {
197 return null;
198 } else {
199 @SuppressWarnings("unchecked")
200 N node = (N)this;
201 while (node.parent != null && node.parent.right == node) {
202 node = node.parent;
203 }
204 return node.parent;
205 }
206 }
207
208 /**
209 * Performs a left rotation about this node. This method assumes that !isLeaf() && !right.isLeaf(). It calls
210 * augment() on this node and on its resulting parent. However, it does not call augment() on any of the resulting
211 * parent's ancestors, because that is normally the responsibility of the caller.
212 * @return The return value from calling augment() on the resulting parent.
213 */
214 public boolean rotateLeft() {
215 if (isLeaf() || right.isLeaf()) {
216 throw new IllegalArgumentException("The node or its right child is a leaf");
217 }
218 N newParent = right;
219 right = newParent.left;
220 @SuppressWarnings("unchecked")
221 N nThis = (N)this;
222 if (!right.isLeaf()) {
223 right.parent = nThis;
224 }
225 newParent.parent = parent;
226 parent = newParent;
227 newParent.left = nThis;
228 if (newParent.parent != null) {
229 if (newParent.parent.left == this) {
230 newParent.parent.left = newParent;
231 } else {
232 newParent.parent.right = newParent;
233 }
234 }
235 augment();
236 return newParent.augment();
237 }
238
239 /**
240 * Performs a right rotation about this node. This method assumes that !isLeaf() && !left.isLeaf(). It calls
241 * augment() on this node and on its resulting parent. However, it does not call augment() on any of the resulting
242 * parent's ancestors, because that is normally the responsibility of the caller.
243 * @return The return value from calling augment() on the resulting parent.
244 */
245 public boolean rotateRight() {
246 if (isLeaf() || left.isLeaf()) {
247 throw new IllegalArgumentException("The node or its left child is a leaf");
248 }
249 N newParent = left;
250 left = newParent.right;
251 @SuppressWarnings("unchecked")
252 N nThis = (N)this;
253 if (!left.isLeaf()) {
254 left.parent = nThis;
255 }
256 newParent.parent = parent;
257 parent = newParent;
258 newParent.right = nThis;
259 if (newParent.parent != null) {
260 if (newParent.parent.left == this) {
261 newParent.parent.left = newParent;
262 } else {
263 newParent.parent.right = newParent;
264 }
265 }
266 augment();
267 return newParent.augment();
268 }
269
270 /**
271 * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements
272 * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be
273 * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs
274 * any rotations by calling rotateLeft() and rotateRight(). This method is more efficient than fixInsertion if
275 * "augment" is false or augment() might return false.
276 * @param augment Whether to set the augmentation information for "node" and its ancestors, by calling augment().
277 */
278 public void fixInsertionWithoutGettingRoot(boolean augment) {
279 if (!isRed) {
280 throw new IllegalArgumentException("The node must be red");
281 }
282 boolean changed = augment;
283 if (augment) {
284 augment();
285 }
286
287 RedBlackNode<N> node = this;
288 while (node.parent != null && node.parent.isRed) {
289 N parent = node.parent;
290 N grandparent = parent.parent;
291 if (grandparent.left.isRed && grandparent.right.isRed) {
292 grandparent.left.isRed = false;
293 grandparent.right.isRed = false;
294 grandparent.isRed = true;
295
296 if (changed) {
297 changed = parent.augment();
298 if (changed) {
299 changed = grandparent.augment();
300 }
301 }
302 node = grandparent;
303 } else {
304 if (parent.left == node) {
305 if (grandparent.right == parent) {
306 parent.rotateRight();
307 node = parent;
308 parent = node.parent;
309 }
310 } else if (grandparent.left == parent) {
311 parent.rotateLeft();
312 node = parent;
313 parent = node.parent;
314 }
315
316 if (parent.left == node) {
317 boolean grandparentChanged = grandparent.rotateRight();
318 if (augment) {
319 changed = grandparentChanged;
320 }
321 } else {
322 boolean grandparentChanged = grandparent.rotateLeft();
323 if (augment) {
324 changed = grandparentChanged;
325 }
326 }
327
328 parent.isRed = false;
329 grandparent.isRed = true;
330 node = parent;
331 break;
332 }
333 }
334
335 if (node.parent == null) {
336 node.isRed = false;
337 }
338 if (changed) {
339 for (node = node.parent; node != null; node = node.parent) {
340 if (!node.augment()) {
341 break;
342 }
343 }
344 }
345 }
346
347 /**
348 * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements
349 * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be
350 * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs
351 * any rotations by calling rotateLeft() and rotateRight(). This method is more efficient than fixInsertion() if
352 * augment() might return false.
353 */
354 public void fixInsertionWithoutGettingRoot() {
355 fixInsertionWithoutGettingRoot(true);
356 }
357
358 /**
359 * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements
360 * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be
361 * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs
362 * any rotations by calling rotateLeft() and rotateRight().
363 * @param augment Whether to set the augmentation information for "node" and its ancestors, by calling augment().
364 * @return The root of the resulting tree.
365 */
366 public N fixInsertion(boolean augment) {
367 fixInsertionWithoutGettingRoot(augment);
368 return root();
369 }
370
371 /**
372 * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements
373 * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be
374 * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs
375 * any rotations by calling rotateLeft() and rotateRight().
376 * @return The root of the resulting tree.
377 */
378 public N fixInsertion() {
379 fixInsertionWithoutGettingRoot(true);
380 return root();
381 }
382
383 /** Returns a Comparator that compares instances of N using their natural order, as in N.compareTo. */
384 @SuppressWarnings({"rawtypes", "unchecked"})
385 private Comparator<N> naturalOrder() {
386 Comparator comparator = (Comparator)NATURAL_ORDER;
387 return (Comparator<N>)comparator;
388 }
389
390 /**
391 * Inserts the specified node into the tree rooted at this node. Assumes this is the root. We treat newNode as a
392 * solitary node that does not belong to any tree, and we ignore its initial "parent", "left", "right", and isRed
393 * fields.
394 *
395 * If it is not efficient or convenient to find the location for a node using a Comparator, then you should manually
396 * add the node to the appropriate location, color it red, and call fixInsertion().
397 *
398 * @param newNode The node to insert.
399 * @param allowDuplicates Whether to insert newNode if there is an equal node in the tree. To check whether we
400 * inserted newNode, check whether newNode.parent is null and the return value differs from newNode.
401 * @param comparator A comparator indicating where to put the node. If this is null, we use the nodes' natural
402 * order, as in N.compareTo. If you are passing null, then you must override the compareTo method, because the
403 * default implementation requires the nodes to already be in the same tree.
404 * @return The root of the resulting tree.
405 */
406 public N insert(N newNode, boolean allowDuplicates, Comparator<? super N> comparator) {
407 if (parent != null) {
408 throw new IllegalArgumentException("This is not the root of a tree");
409 }
410 @SuppressWarnings("unchecked")
411 N nThis = (N)this;
412 if (isLeaf()) {
413 newNode.isRed = false;
414 newNode.left = nThis;
415 newNode.right = nThis;
416 newNode.parent = null;
417 newNode.augment();
418 return newNode;
419 }
420 if (comparator == null) {
421 comparator = naturalOrder();
422 }
423
424 N node = nThis;
425 int comparison;
426 while (true) {
427 comparison = comparator.compare(newNode, node);
428 if (comparison < 0) {
429 if (!node.left.isLeaf()) {
430 node = node.left;
431 } else {
432 newNode.left = node.left;
433 newNode.right = node.left;
434 node.left = newNode;
435 newNode.parent = node;
436 break;
437 }
438 } else if (comparison > 0 || allowDuplicates) {
439 if (!node.right.isLeaf()) {
440 node = node.right;
441 } else {
442 newNode.left = node.right;
443 newNode.right = node.right;
444 node.right = newNode;
445 newNode.parent = node;
446 break;
447 }
448 } else {
449 newNode.parent = null;
450 return nThis;
451 }
452 }
453 newNode.isRed = true;
454 return newNode.fixInsertion();
455 }
456
457 /**
458 * Moves this node to its successor's former position in the tree and vice versa, i.e. sets the "left", "right",
459 * "parent", and isRed fields of each. This method assumes that this is not a leaf node.
460 * @return The node with which we swapped.
461 */
462 private N swapWithSuccessor() {
463 N replacement = successor();
464 boolean oldReplacementIsRed = replacement.isRed;
465 N oldReplacementLeft = replacement.left;
466 N oldReplacementRight = replacement.right;
467 N oldReplacementParent = replacement.parent;
468
469 replacement.isRed = isRed;
470 replacement.left = left;
471 replacement.right = right;
472 replacement.parent = parent;
473 if (parent != null) {
474 if (parent.left == this) {
475 parent.left = replacement;
476 } else {
477 parent.right = replacement;
478 }
479 }
480
481 @SuppressWarnings("unchecked")
482 N nThis = (N)this;
483 isRed = oldReplacementIsRed;
484 left = oldReplacementLeft;
485 right = oldReplacementRight;
486 if (oldReplacementParent == this) {
487 parent = replacement;
488 parent.right = nThis;
489 } else {
490 parent = oldReplacementParent;
491 parent.left = nThis;
492 }
493
494 replacement.right.parent = replacement;
495 if (!replacement.left.isLeaf()) {
496 replacement.left.parent = replacement;
497 }
498 if (!right.isLeaf()) {
499 right.parent = nThis;
500 }
501 return replacement;
502 }
503
504 /**
505 * Performs red-black deletion fixup. To be more precise, this fixes a tree that satisfies all of the requirements
506 * of red-black trees, except that all paths from the root to a leaf that pass through the sibling of this node have
507 * one fewer black node than all other root-to-leaf paths. This method assumes that this is not a leaf node.
508 */
509 private void fixSiblingDeletion() {
510 RedBlackNode<N> sibling = this;
511 boolean changed = true;
512 boolean haveAugmentedParent = false;
513 boolean haveAugmentedGrandparent = false;
514 while (true) {
515 N parent = sibling.parent;
516 if (sibling.isRed) {
517 parent.isRed = true;
518 sibling.isRed = false;
519 if (parent.left == sibling) {
520 changed = parent.rotateRight();
521 sibling = parent.left;
522 } else {
523 changed = parent.rotateLeft();
524 sibling = parent.right;
525 }
526 haveAugmentedParent = true;
527 haveAugmentedGrandparent = true;
528 } else if (!sibling.left.isRed && !sibling.right.isRed) {
529 sibling.isRed = true;
530 if (parent.isRed) {
531 parent.isRed = false;
532 break;
533 } else {
534 if (changed && !haveAugmentedParent) {
535 changed = parent.augment();
536 }
537 N grandparent = parent.parent;
538 if (grandparent == null) {
539 break;
540 } else if (grandparent.left == parent) {
541 sibling = grandparent.right;
542 } else {
543 sibling = grandparent.left;
544 }
545 haveAugmentedParent = haveAugmentedGrandparent;
546 haveAugmentedGrandparent = false;
547 }
548 } else {
549 if (sibling == parent.left) {
550 if (!sibling.left.isRed) {
551 sibling.rotateLeft();
552 sibling = sibling.parent;
553 }
554 } else if (!sibling.right.isRed) {
555 sibling.rotateRight();
556 sibling = sibling.parent;
557 }
558 sibling.isRed = parent.isRed;
559 parent.isRed = false;
560 if (sibling == parent.left) {
561 sibling.left.isRed = false;
562 changed = parent.rotateRight();
563 } else {
564 sibling.right.isRed = false;
565 changed = parent.rotateLeft();
566 }
567 haveAugmentedParent = haveAugmentedGrandparent;
568 haveAugmentedGrandparent = false;
569 break;
570 }
571 }
572
573 // Update augmentation info
574 N parent = sibling.parent;
575 if (changed && parent != null) {
576 if (!haveAugmentedParent) {
577 changed = parent.augment();
578 }
579 if (changed && parent.parent != null) {
580 parent = parent.parent;
581 if (!haveAugmentedGrandparent) {
582 changed = parent.augment();
583 }
584 if (changed) {
585 for (parent = parent.parent; parent != null; parent = parent.parent) {
586 if (!parent.augment()) {
587 break;
588 }
589 }
590 }
591 }
592 }
593 }
594
595 /**
596 * Removes this node from the tree that contains it. The effect of this method on the fields of this node is
597 * unspecified. This method assumes that this is not a leaf node. This method is more efficient than remove() if
598 * augment() might return false.
599 *
600 * If the node has two children, we begin by moving the node's successor to its former position, by changing the
601 * successor's "left", "right", "parent", and isRed fields.
602 */
603 public void removeWithoutGettingRoot() {
604 if (isLeaf()) {
605 throw new IllegalArgumentException("Attempted to remove a leaf node");
606 }
607 N replacement;
608 if (left.isLeaf() || right.isLeaf()) {
609 replacement = null;
610 } else {
611 replacement = swapWithSuccessor();
612 }
613
614 N child;
615 if (!left.isLeaf()) {
616 child = left;
617 } else if (!right.isLeaf()) {
618 child = right;
619 } else {
620 child = null;
621 }
622
623 if (child != null) {
624 // Replace this node with its child
625 child.parent = parent;
626 if (parent != null) {
627 if (parent.left == this) {
628 parent.left = child;
629 } else {
630 parent.right = child;
631 }
632 }
633 child.isRed = false;
634
635 if (child.parent != null) {
636 N parent;
637 for (parent = child.parent; parent != null; parent = parent.parent) {
638 if (!parent.augment()) {
639 break;
640 }
641 }
642 }
643 } else if (parent != null) {
644 // Replace this node with a leaf node
645 N leaf = left;
646 N parent = this.parent;
647 N sibling;
648 if (parent.left == this) {
649 parent.left = leaf;
650 sibling = parent.right;
651 } else {
652 parent.right = leaf;
653 sibling = parent.left;
654 }
655
656 if (!isRed) {
657 RedBlackNode<N> siblingNode = sibling;
658 siblingNode.fixSiblingDeletion();
659 } else {
660 while (parent != null) {
661 if (!parent.augment()) {
662 break;
663 }
664 parent = parent.parent;
665 }
666 }
667 }
668
669 if (replacement != null) {
670 replacement.augment();
671 for (N parent = replacement.parent; parent != null; parent = parent.parent) {
672 if (!parent.augment()) {
673 break;
674 }
675 }
676 }
677
678 // Clear any previously existing links, so that we're more likely to encounter an exception if we attempt to
679 // access the removed node
680 parent = null;
681 left = null;
682 right = null;
683 isRed = true;
684 }
685
686 /**
687 * Removes this node from the tree that contains it. The effect of this method on the fields of this node is
688 * unspecified. This method assumes that this is not a leaf node.
689 *
690 * If the node has two children, we begin by moving the node's successor to its former position, by changing the
691 * successor's "left", "right", "parent", and isRed fields.
692 *
693 * @return The root of the resulting tree.
694 */
695 public N remove() {
696 if (isLeaf()) {
697 throw new IllegalArgumentException("Attempted to remove a leaf node");
698 }
699
700 // Find an arbitrary non-leaf node in the tree other than this node
701 N node;
702 if (parent != null) {
703 node = parent;
704 } else if (!left.isLeaf()) {
705 node = left;
706 } else if (!right.isLeaf()) {
707 node = right;
708 } else {
709 return left;
710 }
711
712 removeWithoutGettingRoot();
713 return node.root();
714 }
715
716 /**
717 * Returns the root of a perfectly height-balanced subtree containing the next "size" (non-leaf) nodes from
718 * "iterator", in iteration order. This method is responsible for setting the "left", "right", "parent", and isRed
719 * fields of the nodes, and calling augment() as appropriate. It ignores the initial values of the "left", "right",
720 * "parent", and isRed fields.
721 * @param iterator The nodes.
722 * @param size The number of nodes.
723 * @param height The "height" of the subtree's root node above the deepest leaf in the tree that contains it. Since
724 * insertion fixup is slow if there are too many red nodes and deleteion fixup is slow if there are too few red
725 * nodes, we compromise and have red nodes at every fourth level. We color a node red iff its "height" is equal
726 * to 1 mod 4.
727 * @param leaf The leaf node.
728 * @return The root of the subtree.
729 */
730 private static <N extends RedBlackNode<N>> N createTree(
731 Iterator<? extends N> iterator, int size, int height, N leaf) {
732 if (size == 0) {
733 return leaf;
734 } else {
735 N left = createTree(iterator, (size - 1) / 2, height - 1, leaf);
736 N node = iterator.next();
737 N right = createTree(iterator, size / 2, height - 1, leaf);
738
739 node.isRed = height % 4 == 1;
740 node.left = left;
741 node.right = right;
742 if (!left.isLeaf()) {
743 left.parent = node;
744 }
745 if (!right.isLeaf()) {
746 right.parent = node;
747 }
748
749 node.augment();
750 return node;
751 }
752 }
753
754 /**
755 * Returns the root of a perfectly height-balanced tree containing the specified nodes, in iteration order. This
756 * method is responsible for setting the "left", "right", "parent", and isRed fields of the nodes (excluding
757 * "leaf"), and calling augment() as appropriate. It ignores the initial values of the "left", "right", "parent",
758 * and isRed fields.
759 * @param nodes The nodes.
760 * @param leaf The leaf node.
761 * @return The root of the tree.
762 */
763 public static <N extends RedBlackNode<N>> N createTree(Collection<? extends N> nodes, N leaf) {
764 int size = nodes.size();
765 if (size == 0) {
766 return leaf;
767 }
768
769 int height = 0;
770 for (int subtreeSize = size; subtreeSize > 0; subtreeSize /= 2) {
771 height++;
772 }
773
774 N node = createTree(nodes.iterator(), size, height, leaf);
775 node.parent = null;
776 node.isRed = false;
777 return node;
778 }
779
780 /**
781 * Concatenates to the end of the tree rooted at this node. To be precise, given that all of the nodes in this
782 * precede the node "pivot", which precedes all of the nodes in "last", this returns the root of a tree containing
783 * all of these nodes. This method destroys the trees rooted at "this" and "last". We treat "pivot" as a solitary
784 * node that does not belong to any tree, and we ignore its initial "parent", "left", "right", and isRed fields.
785 * This method assumes that this node and "last" are the roots of their respective trees.
786 *
787 * This method takes O(log N) time. It is more efficient than inserting "pivot" and then calling concatenate(last).
788 * It is considerably more efficient than inserting "pivot" and all of the nodes in "last".
789 */
790 public N concatenate(N last, N pivot) {
791 // If the black height of "first", where first = this, is less than or equal to that of "last", starting at the
792 // root of "last", we keep going left until we reach a black node whose black height is equal to that of
793 // "first". Then, we make "pivot" the parent of that node and of "first", coloring it red, and perform
794 // insertion fixup on the pivot. If the black height of "first" is greater than that of "last", we do the
795 // mirror image of the above.
796
797 if (parent != null) {
798 throw new IllegalArgumentException("This is not the root of a tree");
799 }
800 if (last.parent != null) {
801 throw new IllegalArgumentException("\"last\" is not the root of a tree");
802 }
803
804 // Compute the black height of the trees
805 int firstBlackHeight = 0;
806 @SuppressWarnings("unchecked")
807 N first = (N)this;
808 for (N node = first; node != null; node = node.right) {
809 if (!node.isRed) {
810 firstBlackHeight++;
811 }
812 }
813 int lastBlackHeight = 0;
814 for (N node = last; node != null; node = node.right) {
815 if (!node.isRed) {
816 lastBlackHeight++;
817 }
818 }
819
820 // Identify the children and parent of pivot
821 N firstChild = first;
822 N lastChild = last;
823 N parent;
824 if (firstBlackHeight <= lastBlackHeight) {
825 parent = null;
826 int blackHeight = lastBlackHeight;
827 while (blackHeight > firstBlackHeight) {
828 if (!lastChild.isRed) {
829 blackHeight--;
830 }
831 parent = lastChild;
832 lastChild = lastChild.left;
833 }
834 if (lastChild.isRed) {
835 parent = lastChild;
836 lastChild = lastChild.left;
837 }
838 } else {
839 parent = null;
840 int blackHeight = firstBlackHeight;
841 while (blackHeight > lastBlackHeight) {
842 if (!firstChild.isRed) {
843 blackHeight--;
844 }
845 parent = firstChild;
846 firstChild = firstChild.right;
847 }
848 if (firstChild.isRed) {
849 parent = firstChild;
850 firstChild = firstChild.right;
851 }
852 }
853
854 // Add "pivot" to the tree
855 pivot.isRed = true;
856 pivot.parent = parent;
857 if (parent != null) {
858 if (firstBlackHeight < lastBlackHeight) {
859 parent.left = pivot;
860 } else {
861 parent.right = pivot;
862 }
863 }
864 pivot.left = firstChild;
865 if (!firstChild.isLeaf()) {
866 firstChild.parent = pivot;
867 }
868 pivot.right = lastChild;
869 if (!lastChild.isLeaf()) {
870 lastChild.parent = pivot;
871 }
872
873 // Perform insertion fixup
874 return pivot.fixInsertion();
875 }
876
877 /**
878 * Concatenates the tree rooted at "last" to the end of the tree rooted at this node. To be precise, given that all
879 * of the nodes in this precede all of the nodes in "last", this returns the root of a tree containing all of these
880 * nodes. This method destroys the trees rooted at "this" and "last". It assumes that this node and "last" are the
881 * roots of their respective trees. This method takes O(log N) time. It is considerably more efficient than
882 * inserting all of the nodes in "last".
883 */
884 public N concatenate(N last) {
885 if (parent != null || last.parent != null) {
886 throw new IllegalArgumentException("The node is not the root of a tree");
887 }
888 if (isLeaf()) {
889 return last;
890 } else if (last.isLeaf()) {
891 @SuppressWarnings("unchecked")
892 N nThis = (N)this;
893 return nThis;
894 } else {
895 N node = last.min();
896 last = node.remove();
897 return concatenate(last, node);
898 }
899 }
900
901 /**
902 * Splits the tree rooted at this node into two trees, so that the first element of the return value is the root of
903 * a tree consisting of the nodes that were before the specified node, and the second element of the return value is
904 * the root of a tree consisting of the nodes that were equal to or after the specified node. This method is
905 * destructive, meaning it does not preserve the original tree. It assumes that this node is the root and is in the
906 * same tree as splitNode. It takes O(log N) time. It is considerably more efficient than removing all of the
907 * nodes at or after splitNode and then creating a new tree from those nodes.
908 * @param The node at which to split the tree.
909 * @return An array consisting of the resulting trees.
910 */
911 public N[] split(N splitNode) {
912 // To split the tree, we accumulate a pre-split tree and a post-split tree. We walk down the tree toward the
913 // position where we are splitting. Whenever we go left, we concatenate the right subtree with the post-split
914 // tree, and whenever we go right, we concatenate the pre-split tree with the left subtree. We use the
915 // concatenation algorithm described in concatenate(Object, Object). For the pivot, we use the last node where
916 // we went left in the case of a left move, and the last node where we went right in the case of a right move.
917 //
918 // The method uses the following variables:
919 //
920 // node: The current node in our walk down the tree.
921 // first: A node on the right spine of the pre-split tree. At the beginning of each iteration, it is the black
922 // node with the same black height as "node". If the pre-split tree is empty, this is null instead.
923 // firstParent: The parent of "first". If the pre-split tree is empty, this is null. Otherwise, this is the
924 // same as first.parent, unless first.isLeaf().
925 // firstPivot: The node where we last went right, i.e. the next node to use as a pivot when concatenating with
926 // the pre-split tree.
927 // advanceFirst: Whether to set "first" to be its next black descendant at the end of the loop.
928 // last, lastParent, lastPivot, advanceLast: Analogous to "first", firstParent, firstPivot, and advanceFirst,
929 // but for the post-split tree.
930 if (parent != null) {
931 throw new IllegalArgumentException("This is not the root of a tree");
932 }
933 if (isLeaf() || splitNode.isLeaf()) {
934 throw new IllegalArgumentException("The root or the split node is a leaf");
935 }
936
937 // Create an array containing the path from the root to splitNode
938 int depth = 1;
939 N parent;
940 for (parent = splitNode; parent.parent != null; parent = parent.parent) {
941 depth++;
942 }
943 if (parent != this) {
944 throw new IllegalArgumentException("The split node does not belong to this tree");
945 }
946 RedBlackNode<?>[] path = new RedBlackNode<?>[depth];
947 for (parent = splitNode; parent != null; parent = parent.parent) {
948 depth--;
949 path[depth] = parent;
950 }
951
952 @SuppressWarnings("unchecked")
953 N node = (N)this;
954 N first = null;
955 N firstParent = null;
956 N last = null;
957 N lastParent = null;
958 N firstPivot = null;
959 N lastPivot = null;
960 while (!node.isLeaf()) {
961 boolean advanceFirst = !node.isRed && firstPivot != null;
962 boolean advanceLast = !node.isRed && lastPivot != null;
963 if ((depth + 1 < path.length && path[depth + 1] == node.left) || depth + 1 == path.length) {
964 // Left move
965 if (lastPivot == null) {
966 // The post-split tree is empty
967 last = node.right;
968 last.parent = null;
969 if (last.isRed) {
970 last.isRed = false;
971 lastParent = last;
972 last = last.left;
973 }
974 } else {
975 // Concatenate node.right and the post-split tree
976 if (node.right.isRed) {
977 node.right.isRed = false;
978 } else if (!node.isRed) {
979 lastParent = last;
980 last = last.left;
981 if (last.isRed) {
982 lastParent = last;
983 last = last.left;
984 }
985 advanceLast = false;
986 }
987 lastPivot.isRed = true;
988 lastPivot.parent = lastParent;
989 if (lastParent != null) {
990 lastParent.left = lastPivot;
991 }
992 lastPivot.left = node.right;
993 if (!lastPivot.left.isLeaf()) {
994 lastPivot.left.parent = lastPivot;
995 }
996 lastPivot.right = last;
997 if (!last.isLeaf()) {
998 last.parent = lastPivot;
999 }
1000 last = lastPivot.left;
1001 lastParent = lastPivot;
1002 lastPivot.fixInsertionWithoutGettingRoot(false);
1003 }
1004 lastPivot = node;
1005 node = node.left;
1006 } else {
1007 // Right move
1008 if (firstPivot == null) {
1009 // The pre-split tree is empty
1010 first = node.left;
1011 first.parent = null;
1012 if (first.isRed) {
1013 first.isRed = false;
1014 firstParent = first;
1015 first = first.right;
1016 }
1017 } else {
1018 // Concatenate the post-split tree and node.left
1019 if (node.left.isRed) {
1020 node.left.isRed = false;
1021 } else if (!node.isRed) {
1022 firstParent = first;
1023 first = first.right;
1024 if (first.isRed) {
1025 firstParent = first;
1026 first = first.right;
1027 }
1028 advanceFirst = false;
1029 }
1030 firstPivot.isRed = true;
1031 firstPivot.parent = firstParent;
1032 if (firstParent != null) {
1033 firstParent.right = firstPivot;
1034 }
1035 firstPivot.right = node.left;
1036 if (!firstPivot.right.isLeaf()) {
1037 firstPivot.right.parent = firstPivot;
1038 }
1039 firstPivot.left = first;
1040 if (!first.isLeaf()) {
1041 first.parent = firstPivot;
1042 }
1043 first = firstPivot.right;
1044 firstParent = firstPivot;
1045 firstPivot.fixInsertionWithoutGettingRoot(false);
1046 }
1047 firstPivot = node;
1048 node = node.right;
1049 }
1050
1051 depth++;
1052
1053 // Update "first" and "last" to be the nodes at the proper black height
1054 if (advanceFirst) {
1055 firstParent = first;
1056 first = first.right;
1057 if (first.isRed) {
1058 firstParent = first;
1059 first = first.right;
1060 }
1061 }
1062 if (advanceLast) {
1063 lastParent = last;
1064 last = last.left;
1065 if (last.isRed) {
1066 lastParent = last;
1067 last = last.left;
1068 }
1069 }
1070 }
1071
1072 // Add firstPivot to the pre-split tree
1073 N leaf = node;
1074 if (first == null) {
1075 first = leaf;
1076 } else {
1077 firstPivot.isRed = true;
1078 firstPivot.parent = firstParent;
1079 if (firstParent != null) {
1080 firstParent.right = firstPivot;
1081 }
1082 firstPivot.left = leaf;
1083 firstPivot.right = leaf;
1084 firstPivot.fixInsertionWithoutGettingRoot(false);
1085 for (first = firstPivot; first.parent != null; first = first.parent) {
1086 first.augment();
1087 }
1088 first.augment();
1089 }
1090
1091 // Add lastPivot to the post-split tree
1092 lastPivot.isRed = true;
1093 lastPivot.parent = lastParent;
1094 if (lastParent != null) {
1095 lastParent.left = lastPivot;
1096 }
1097 lastPivot.left = leaf;
1098 lastPivot.right = leaf;
1099 lastPivot.fixInsertionWithoutGettingRoot(false);
1100 for (last = lastPivot; last.parent != null; last = last.parent) {
1101 last.augment();
1102 }
1103 last.augment();
1104
1105 @SuppressWarnings("unchecked")
1106 N[] result = (N[])Array.newInstance(getClass(), 2);
1107 result[0] = first;
1108 result[1] = last;
1109 return result;
1110 }
1111
1112 /**
1113 * Returns the lowest common ancestor of this node and "other" - the node that is an ancestor of both and is not the
1114 * parent of a node that is an ancestor of both. Assumes that this is in the same tree as "other". Assumes that
1115 * neither "this" nor "other" is a leaf node. This method may return "this" or "other".
1116 *
1117 * Note that while it is possible to compute the lowest common ancestor in O(P) time, where P is the length of the
1118 * path from this node to "other", the "lca" method is not guaranteed to take O(P) time. If your application
1119 * requires this, then you should write your own lowest common ancestor method.
1120 */
1121 public N lca(N other) {
1122 if (isLeaf() || other.isLeaf()) {
1123 throw new IllegalArgumentException("One of the nodes is a leaf node");
1124 }
1125
1126 // Compute the depth of each node
1127 int depth = 0;
1128 for (N parent = this.parent; parent != null; parent = parent.parent) {
1129 depth++;
1130 }
1131 int otherDepth = 0;
1132 for (N parent = other.parent; parent != null; parent = parent.parent) {
1133 otherDepth++;
1134 }
1135
1136 // Go up to nodes of the same depth
1137 @SuppressWarnings("unchecked")
1138 N parent = (N)this;
1139 N otherParent = other;
1140 if (depth <= otherDepth) {
1141 for (int i = otherDepth; i > depth; i--) {
1142 otherParent = otherParent.parent;
1143 }
1144 } else {
1145 for (int i = depth; i > otherDepth; i--) {
1146 parent = parent.parent;
1147 }
1148 }
1149
1150 // Find the LCA
1151 while (parent != otherParent) {
1152 parent = parent.parent;
1153 otherParent = otherParent.parent;
1154 }
1155 if (parent != null) {
1156 return parent;
1157 } else {
1158 throw new IllegalArgumentException("The nodes do not belong to the same tree");
1159 }
1160 }
1161
1162 /**
1163 * Returns an integer comparing the position of this node in the tree that contains it with that of "other". Returns
1164 * a negative number if this is earlier, a positive number if this is later, and 0 if this is at the same position.
1165 * Assumes that this is in the same tree as "other". Assumes that neither "this" nor "other" is a leaf node.
1166 *
1167 * The base class's implementation takes O(log N) time. If a RedBlackNode subclass stores a value used to order the
1168 * nodes, then it could override compareTo to compare the nodes' values, which would take O(1) time.
1169 *
1170 * Note that while it is possible to compare the positions of two nodes in O(P) time, where P is the length of the
1171 * path from this node to "other", the default implementation of compareTo is not guaranteed to take O(P) time. If
1172 * your application requires this, then you should write your own comparison method.
1173 */
1174 @Override
1175 public int compareTo(N other) {
1176 if (isLeaf() || other.isLeaf()) {
1177 throw new IllegalArgumentException("One of the nodes is a leaf node");
1178 }
1179
1180 // The algorithm operates as follows: compare the depth of this node to that of "other". If the depth of
1181 // "other" is greater, keep moving up from "other" until we find the ancestor at the same depth. Then, keep
1182 // moving up from "this" and from that node until we reach the lowest common ancestor. The node that arrived
1183 // from the left child of the common ancestor is earlier. The algorithm is analogous if the depth of "other" is
1184 // not greater.
1185 if (this == other) {
1186 return 0;
1187 }
1188
1189 // Compute the depth of each node
1190 int depth = 0;
1191 RedBlackNode<N> parent;
1192 for (parent = this; parent.parent != null; parent = parent.parent) {
1193 depth++;
1194 }
1195 int otherDepth = 0;
1196 N otherParent;
1197 for (otherParent = other; otherParent.parent != null; otherParent = otherParent.parent) {
1198 otherDepth++;
1199 }
1200
1201 // Go up to nodes of the same depth
1202 if (depth < otherDepth) {
1203 otherParent = other;
1204 for (int i = otherDepth - 1; i > depth; i--) {
1205 otherParent = otherParent.parent;
1206 }
1207 if (otherParent.parent != this) {
1208 otherParent = otherParent.parent;
1209 } else if (left == otherParent) {
1210 return 1;
1211 } else {
1212 return -1;
1213 }
1214 parent = this;
1215 } else if (depth > otherDepth) {
1216 parent = this;
1217 for (int i = depth - 1; i > otherDepth; i--) {
1218 parent = parent.parent;
1219 }
1220 if (parent.parent != other) {
1221 parent = parent.parent;
1222 } else if (other.left == parent) {
1223 return -1;
1224 } else {
1225 return 1;
1226 }
1227 otherParent = other;
1228 } else {
1229 parent = this;
1230 otherParent = other;
1231 }
1232
1233 // Keep going up until we reach the lowest common ancestor
1234 while (parent.parent != otherParent.parent) {
1235 parent = parent.parent;
1236 otherParent = otherParent.parent;
1237 }
1238 if (parent.parent == null) {
1239 throw new IllegalArgumentException("The nodes do not belong to the same tree");
1240 }
1241 if (parent.parent.left == parent) {
1242 return -1;
1243 } else {
1244 return 1;
1245 }
1246 }
1247
1248 /** Throws a RuntimeException if the RedBlackNode fields of this are not correct for a leaf node. */
1249 private void assertIsValidLeaf() {
1250 if (left != null || right != null || parent != null || isRed) {
1251 throw new RuntimeException("A leaf node's \"left\", \"right\", \"parent\", or isRed field is incorrect");
1252 }
1253 }
1254
1255 /**
1256 * Throws a RuntimeException if the subtree rooted at this node does not satisfy the red-black properties, excluding
1257 * the requirement that the root be black, or it contains a repeated node other than a leaf node.
1258 * @param blackHeight The required number of black nodes in each path from this to a leaf node, including this and
1259 * the leaf node.
1260 * @param visited The nodes we have reached thus far, other than leaf nodes. This method adds the non-leaf nodes in
1261 * the subtree rooted at this node to "visited".
1262 */
1263 private void assertSubtreeIsValidRedBlack(int blackHeight, Set<Reference<N>> visited) {
1264 @SuppressWarnings("unchecked")
1265 N nThis = (N)this;
1266 if (left == null || right == null) {
1267 assertIsValidLeaf();
1268 if (blackHeight != 1) {
1269 throw new RuntimeException("Not all root-to-leaf paths have the same number of black nodes");
1270 }
1271 return;
1272 } else if (!visited.add(new Reference<N>(nThis))) {
1273 throw new RuntimeException("The tree contains a repeated non-leaf node");
1274 } else {
1275 int childBlackHeight;
1276 if (isRed) {
1277 if ((!left.isLeaf() && left.isRed) || (!right.isLeaf() && right.isRed)) {
1278 throw new RuntimeException("A red node has a red child");
1279 }
1280 childBlackHeight = blackHeight;
1281 } else if (blackHeight == 0) {
1282 throw new RuntimeException("Not all root-to-leaf paths have the same number of black nodes");
1283 } else {
1284 childBlackHeight = blackHeight - 1;
1285 }
1286
1287 if (!left.isLeaf() && left.parent != this) {
1288 throw new RuntimeException("left.parent != this");
1289 }
1290 if (!right.isLeaf() && right.parent != this) {
1291 throw new RuntimeException("right.parent != this");
1292 }
1293 RedBlackNode<N> leftNode = left;
1294 RedBlackNode<N> rightNode = right;
1295 leftNode.assertSubtreeIsValidRedBlack(childBlackHeight, visited);
1296 rightNode.assertSubtreeIsValidRedBlack(childBlackHeight, visited);
1297 }
1298 }
1299
1300 /** Calls assertNodeIsValid() on every node in the subtree rooted at this node. */
1301 private void assertNodesAreValid() {
1302 assertNodeIsValid();
1303 if (left != null) {
1304 RedBlackNode<N> leftNode = left;
1305 RedBlackNode<N> rightNode = right;
1306 leftNode.assertNodesAreValid();
1307 rightNode.assertNodesAreValid();
1308 }
1309 }
1310
1311 /**
1312 * Throws a RuntimeException if the subtree rooted at this node is not a valid red-black tree, e.g. if a red node
1313 * has a red child or it contains a non-leaf node "node" for which node.left.parent != node. (If parent != null,
1314 * it's okay if isRed is true.) This method is useful for debugging. See also assertSubtreeIsValid().
1315 */
1316 public void assertSubtreeIsValidRedBlack() {
1317 if (isLeaf()) {
1318 assertIsValidLeaf();
1319 } else {
1320 if (parent == null && isRed) {
1321 throw new RuntimeException("The root is red");
1322 }
1323
1324 // Compute the black height of the tree
1325 Set<Reference<N>> nodes = new HashSet<Reference<N>>();
1326 int blackHeight = 0;
1327 @SuppressWarnings("unchecked")
1328 N node = (N)this;
1329 while (node != null) {
1330 if (!nodes.add(new Reference<N>(node))) {
1331 throw new RuntimeException("The tree contains a repeated non-leaf node");
1332 }
1333 if (!node.isRed) {
1334 blackHeight++;
1335 }
1336 node = node.left;
1337 }
1338
1339 assertSubtreeIsValidRedBlack(blackHeight, new HashSet<Reference<N>>());
1340 }
1341 }
1342
1343 /**
1344 * Throws a RuntimeException if we detect a problem with the subtree rooted at this node, such as a red child of a
1345 * red node or a non-leaf descendant "node" for which node.left.parent != node. This method is useful for
1346 * debugging. RedBlackNode subclasses may want to override assertSubtreeIsValid() to call assertOrderIsValid.
1347 */
1348 public void assertSubtreeIsValid() {
1349 assertSubtreeIsValidRedBlack();
1350 assertNodesAreValid();
1351 }
1352
1353 /**
1354 * Throws a RuntimeException if the nodes in the subtree rooted at this node are not in the specified order or they
1355 * do not lie in the specified range. Assumes that the subtree rooted at this node is a valid binary tree, i.e. it
1356 * has no repeated nodes other than leaf nodes.
1357 * @param comparator A comparator indicating how the nodes should be ordered.
1358 * @param start The lower limit for nodes in the subtree, if any.
1359 * @param end The upper limit for nodes in the subtree, if any.
1360 */
1361 private void assertOrderIsValid(Comparator<? super N> comparator, N start, N end) {
1362 if (!isLeaf()) {
1363 @SuppressWarnings("unchecked")
1364 N nThis = (N)this;
1365 if (start != null && comparator.compare(nThis, start) < 0) {
1366 throw new RuntimeException("The nodes are not ordered correctly");
1367 }
1368 if (end != null && comparator.compare(nThis, end) > 0) {
1369 throw new RuntimeException("The nodes are not ordered correctly");
1370 }
1371 RedBlackNode<N> leftNode = left;
1372 RedBlackNode<N> rightNode = right;
1373 leftNode.assertOrderIsValid(comparator, start, nThis);
1374 rightNode.assertOrderIsValid(comparator, nThis, end);
1375 }
1376 }
1377
1378 /**
1379 * Throws a RuntimeException if the nodes in the subtree rooted at this node are not in the specified order.
1380 * Assumes that this is a valid binary tree, i.e. there are no repeated nodes other than leaf nodes. This method is
1381 * useful for debugging. RedBlackNode subclasses may want to override assertSubtreeIsValid() to call
1382 * assertOrderIsValid.
1383 * @param comparator A comparator indicating how the nodes should be ordered. If this is null, we use the nodes'
1384 * natural order, as in N.compareTo.
1385 */
1386 public void assertOrderIsValid(Comparator<? super N> comparator) {
1387 if (comparator == null) {
1388 comparator = naturalOrder();
1389 }
1390 assertOrderIsValid(comparator, null, null);
1391 }
1392}
generated by cgit v1.2.3-54-g00ecf (git 2.45.1) at 2024-05-29 06:21:37 +0000