diff options
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.java | 1392 |
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 | */ | ||
24 | package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval; | ||
25 | |||
26 | import java.lang.reflect.Array; | ||
27 | import java.util.Collection; | ||
28 | import java.util.Comparator; | ||
29 | import java.util.HashSet; | ||
30 | import java.util.Iterator; | ||
31 | import 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 | */ | ||
63 | public 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 | } | ||