Mercurial > hg > truffle
annotate agent/src/share/classes/sun/jvm/hotspot/utilities/RBTree.java @ 1913:3b2dea75431e
6984311: JSR 292 needs optional bootstrap method parameters
Summary: Allow CONSTANT_InvokeDynamic nodes to have any number of extra operands.
Reviewed-by: twisti
| author | jrose |
|---|---|
| date | Sat, 30 Oct 2010 13:08:23 -0700 |
| parents | c18cbe5936b8 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 25 package sun.jvm.hotspot.utilities; | |
| 26 | |
| 27 /** <P> This class implements a Red-Black tree as described in Cormen, | |
| 28 Leiserson, Rivest, <I>Introduction to Algorithms</I>, MIT Press: | |
| 29 Cambridge, MA, 1990. </P> | |
| 30 | |
| 31 <P> A property of this implementation is that it is designed to | |
| 32 allow straightforward augmentation of the data structure. A valid | |
| 33 augmentation is one in which a node contains auxiliary information | |
| 34 that can be computed by examining only this node and its left and | |
| 35 right children (see CLR, section 15.2). </P> | |
| 36 | |
| 37 <P> An RBTree is a structure of RBNodes, each of which contains a | |
| 38 user data element. When the user inserts a piece of data into the | |
| 39 tree, a new RBNode is constructed around it. </P> | |
| 40 | |
| 41 <P> An RBTree takes a Comparator as argument to its constructor | |
| 42 which is used internally to order the nodes in the tree. The | |
| 43 comparator's arguments are obtained by calling the routine | |
| 44 "getNodeData" on two nodes; the default implementaion returns the | |
| 45 node data. This Comparator is also used to perform the generic | |
| 46 "find" operation, which returns the RBNode containing user data | |
| 47 precisely equalling the query data. Different types of user data | |
| 48 will typically require different types of traversals as well as | |
| 49 additional comparison operations; these are left to the RBTree | |
| 50 subclass. </P> | |
| 51 | |
| 52 */ | |
| 53 | |
| 54 import java.io.PrintStream; | |
| 55 import java.util.Comparator; | |
| 56 import java.util.Random; | |
| 57 | |
| 58 public class RBTree { | |
| 59 private RBNode root; | |
| 60 private Comparator comparator; | |
| 61 protected static final boolean DEBUGGING = true; | |
| 62 protected static final boolean VERBOSE = true; | |
| 63 protected static final boolean REALLY_VERBOSE = false; | |
| 64 | |
| 65 public RBTree(Comparator comparator) { | |
| 66 this.comparator = comparator; | |
| 67 } | |
| 68 | |
| 69 public RBNode getRoot() { | |
| 70 return root; | |
| 71 } | |
| 72 | |
| 73 public void insertNode(RBNode x) { | |
| 74 treeInsert(x); | |
| 75 | |
| 76 x.setColor(RBColor.RED); | |
| 77 boolean shouldPropagate = x.update(); | |
| 78 | |
| 79 if (DEBUGGING && REALLY_VERBOSE) { | |
| 80 System.err.println("RBTree.insertNode"); | |
| 81 } | |
| 82 | |
| 83 RBNode propagateStart = x; | |
| 84 | |
| 85 // Loop invariant: x has been updated. | |
| 86 while ((x != root) && (x.getParent().getColor() == RBColor.RED)) { | |
| 87 if (x.getParent() == x.getParent().getParent().getLeft()) { | |
| 88 RBNode y = x.getParent().getParent().getRight(); | |
| 89 if ((y != null) && (y.getColor() == RBColor.RED)) { | |
| 90 // Case 1 | |
| 91 if (DEBUGGING && REALLY_VERBOSE) { | |
| 92 System.err.println(" Case 1/1"); | |
| 93 } | |
| 94 x.getParent().setColor(RBColor.BLACK); | |
| 95 y.setColor(RBColor.BLACK); | |
| 96 x.getParent().getParent().setColor(RBColor.RED); | |
| 97 x.getParent().update(); | |
| 98 x = x.getParent().getParent(); | |
| 99 shouldPropagate = x.update(); | |
| 100 propagateStart = x; | |
| 101 } else { | |
| 102 if (x == x.getParent().getRight()) { | |
| 103 // Case 2 | |
| 104 if (DEBUGGING && REALLY_VERBOSE) { | |
| 105 System.err.println(" Case 1/2"); | |
| 106 } | |
| 107 x = x.getParent(); | |
| 108 leftRotate(x); | |
| 109 } | |
| 110 // Case 3 | |
| 111 if (DEBUGGING && REALLY_VERBOSE) { | |
| 112 System.err.println(" Case 1/3"); | |
| 113 } | |
| 114 x.getParent().setColor(RBColor.BLACK); | |
| 115 x.getParent().getParent().setColor(RBColor.RED); | |
| 116 shouldPropagate = rightRotate(x.getParent().getParent()); | |
| 117 propagateStart = x.getParent(); | |
| 118 } | |
| 119 } else { | |
| 120 // Same as then clause with "right" and "left" exchanged | |
| 121 RBNode y = x.getParent().getParent().getLeft(); | |
| 122 if ((y != null) && (y.getColor() == RBColor.RED)) { | |
| 123 // Case 1 | |
| 124 if (DEBUGGING && REALLY_VERBOSE) { | |
| 125 System.err.println(" Case 2/1"); | |
| 126 } | |
| 127 x.getParent().setColor(RBColor.BLACK); | |
| 128 y.setColor(RBColor.BLACK); | |
| 129 x.getParent().getParent().setColor(RBColor.RED); | |
| 130 x.getParent().update(); | |
| 131 x = x.getParent().getParent(); | |
| 132 shouldPropagate = x.update(); | |
| 133 propagateStart = x; | |
| 134 } else { | |
| 135 if (x == x.getParent().getLeft()) { | |
| 136 // Case 2 | |
| 137 if (DEBUGGING && REALLY_VERBOSE) { | |
| 138 System.err.println(" Case 2/2"); | |
| 139 } | |
| 140 x = x.getParent(); | |
| 141 rightRotate(x); | |
| 142 } | |
| 143 // Case 3 | |
| 144 if (DEBUGGING && REALLY_VERBOSE) { | |
| 145 System.err.println(" Case 2/3"); | |
| 146 } | |
| 147 x.getParent().setColor(RBColor.BLACK); | |
| 148 x.getParent().getParent().setColor(RBColor.RED); | |
| 149 shouldPropagate = leftRotate(x.getParent().getParent()); | |
| 150 propagateStart = x.getParent(); | |
| 151 } | |
| 152 } | |
| 153 } | |
| 154 | |
| 155 while (shouldPropagate && (propagateStart != root)) { | |
| 156 if (DEBUGGING && REALLY_VERBOSE) { | |
| 157 System.err.println(" Propagating"); | |
| 158 } | |
| 159 propagateStart = propagateStart.getParent(); | |
| 160 shouldPropagate = propagateStart.update(); | |
| 161 } | |
| 162 | |
| 163 root.setColor(RBColor.BLACK); | |
| 164 | |
| 165 if (DEBUGGING) { | |
| 166 verify(); | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 /** FIXME: this does not work properly yet for augmented red-black | |
| 171 trees since it doesn't update nodes. Need to figure out exactly | |
| 172 from which points we need to propagate updates upwards. */ | |
| 173 public void deleteNode(RBNode z) { | |
| 174 // This routine splices out a node. Note that we may not actually | |
| 175 // delete the RBNode z from the tree, but may instead remove | |
| 176 // another node from the tree, copying its contents into z. | |
| 177 | |
| 178 // y is the node to be unlinked from the tree | |
| 179 RBNode y; | |
| 180 if ((z.getLeft() == null) || (z.getRight() == null)) { | |
| 181 y = z; | |
| 182 } else { | |
| 183 y = treeSuccessor(z); | |
| 184 } | |
| 185 // y is guaranteed to be non-null at this point | |
| 186 RBNode x; | |
| 187 if (y.getLeft() != null) { | |
| 188 x = y.getLeft(); | |
| 189 } else { | |
| 190 x = y.getRight(); | |
| 191 } | |
| 192 // x is the potential child of y to replace it in the tree. | |
| 193 // x may be null at this point | |
| 194 RBNode xParent; | |
| 195 if (x != null) { | |
| 196 x.setParent(y.getParent()); | |
| 197 xParent = x.getParent(); | |
| 198 } else { | |
| 199 xParent = y.getParent(); | |
| 200 } | |
| 201 if (y.getParent() == null) { | |
| 202 root = x; | |
| 203 } else { | |
| 204 if (y == y.getParent().getLeft()) { | |
| 205 y.getParent().setLeft(x); | |
| 206 } else { | |
| 207 y.getParent().setRight(x); | |
| 208 } | |
| 209 } | |
| 210 if (y != z) { | |
| 211 z.copyFrom(y); | |
| 212 } | |
| 213 if (y.getColor() == RBColor.BLACK) { | |
| 214 deleteFixup(x, xParent); | |
| 215 } | |
| 216 | |
| 217 if (DEBUGGING) { | |
| 218 verify(); | |
| 219 } | |
| 220 } | |
| 221 | |
| 222 public void print() { | |
| 223 printOn(System.out); | |
| 224 } | |
| 225 | |
| 226 public void printOn(PrintStream tty) { | |
| 227 printFromNode(root, tty, 0); | |
| 228 } | |
| 229 | |
| 230 //---------------------------------------------------------------------- | |
| 231 // Functionality overridable by subclass | |
| 232 // | |
| 233 | |
| 234 protected Object getNodeValue(RBNode node) { | |
| 235 return node.getData(); | |
| 236 } | |
| 237 | |
| 238 /** Verify invariants are preserved */ | |
| 239 protected void verify() { | |
| 240 verifyFromNode(root); | |
| 241 } | |
| 242 | |
| 243 //---------------------------------------------------------------------- | |
| 244 // Internals only below this point | |
| 245 // | |
| 246 | |
| 247 // | |
| 248 // Vanilla binary search tree operations | |
| 249 // | |
| 250 | |
| 251 private void treeInsert(RBNode z) { | |
| 252 RBNode y = null; | |
| 253 RBNode x = root; | |
| 254 | |
| 255 while (x != null) { | |
| 256 y = x; | |
| 257 if (comparator.compare(getNodeValue(z), getNodeValue(x)) < 0) { | |
| 258 x = x.getLeft(); | |
| 259 } else { | |
| 260 x = x.getRight(); | |
| 261 } | |
| 262 } | |
| 263 z.setParent(y); | |
| 264 if (y == null) { | |
| 265 root = z; | |
| 266 } else { | |
| 267 if (comparator.compare(getNodeValue(z), getNodeValue(y)) < 0) { | |
| 268 y.setLeft(z); | |
| 269 } else { | |
| 270 y.setRight(z); | |
| 271 } | |
| 272 } | |
| 273 } | |
| 274 | |
| 275 private RBNode treeSuccessor(RBNode x) { | |
| 276 if (x.getRight() != null) { | |
| 277 return treeMinimum(x.getRight()); | |
| 278 } | |
| 279 RBNode y = x.getParent(); | |
| 280 while ((y != null) && (x == y.getRight())) { | |
| 281 x = y; | |
| 282 y = y.getParent(); | |
| 283 } | |
| 284 return y; | |
| 285 } | |
| 286 | |
| 287 private RBNode treeMinimum(RBNode x) { | |
| 288 while (x.getLeft() != null) { | |
| 289 x = x.getLeft(); | |
| 290 } | |
| 291 return x; | |
| 292 } | |
| 293 | |
| 294 // | |
| 295 // Insertion and deletion helpers | |
| 296 // | |
| 297 | |
| 298 /** Returns true if updates must continue propagating up the tree */ | |
| 299 private boolean leftRotate(RBNode x) { | |
| 300 // Set y. | |
| 301 RBNode y = x.getRight(); | |
| 302 // Turn y's left subtree into x's right subtree. | |
| 303 x.setRight(y.getLeft()); | |
| 304 if (y.getLeft() != null) { | |
| 305 y.getLeft().setParent(x); | |
| 306 } | |
| 307 // Link x's parent to y. | |
| 308 y.setParent(x.getParent()); | |
| 309 if (x.getParent() == null) { | |
| 310 root = y; | |
| 311 } else { | |
| 312 if (x == x.getParent().getLeft()) { | |
| 313 x.getParent().setLeft(y); | |
| 314 } else { | |
| 315 x.getParent().setRight(y); | |
| 316 } | |
| 317 } | |
| 318 // Put x on y's left. | |
| 319 y.setLeft(x); | |
| 320 x.setParent(y); | |
| 321 // Update nodes in appropriate order (lowest to highest) | |
| 322 boolean res = x.update(); | |
| 323 res = y.update() || res; | |
| 324 return res; | |
| 325 } | |
| 326 | |
| 327 /** Returns true if updates must continue propagating up the tree */ | |
| 328 private boolean rightRotate(RBNode y) { | |
| 329 // Set x. | |
| 330 RBNode x = y.getLeft(); | |
| 331 // Turn x's right subtree into y's left subtree. | |
| 332 y.setLeft(x.getRight()); | |
| 333 if (x.getRight() != null) { | |
| 334 x.getRight().setParent(y); | |
| 335 } | |
| 336 // Link y's parent into x. | |
| 337 x.setParent(y.getParent()); | |
| 338 if (y.getParent() == null) { | |
| 339 root = x; | |
| 340 } else { | |
| 341 if (y == y.getParent().getLeft()) { | |
| 342 y.getParent().setLeft(x); | |
| 343 } else { | |
| 344 y.getParent().setRight(x); | |
| 345 } | |
| 346 } | |
| 347 // Put y on x's right. | |
| 348 x.setRight(y); | |
| 349 y.setParent(x); | |
| 350 // Update nodes in appropriate order (lowest to highest) | |
| 351 boolean res = y.update(); | |
| 352 res = x.update() || res; | |
| 353 return res; | |
| 354 } | |
| 355 | |
| 356 /** Restores red-black property to tree after splicing out node | |
| 357 during deletion. Note that x may be null, which is why xParent | |
| 358 must be specified. */ | |
| 359 private void deleteFixup(RBNode x, RBNode xParent) { | |
| 360 while ((x != root) && ((x == null) || (x.getColor() == RBColor.BLACK))) { | |
| 361 if (x == xParent.getLeft()) { | |
| 362 // NOTE: the text points out that w can not be null. The | |
| 363 // reason is not obvious from simply examining the code; it | |
| 364 // comes about because of properties of the red-black tree. | |
| 365 RBNode w = xParent.getRight(); | |
| 366 if (DEBUGGING) { | |
| 367 if (w == null) { | |
| 368 throw new RuntimeException("x's sibling should not be null"); | |
| 369 } | |
| 370 } | |
| 371 if (w.getColor() == RBColor.RED) { | |
| 372 // Case 1 | |
| 373 w.setColor(RBColor.BLACK); | |
| 374 xParent.setColor(RBColor.RED); | |
| 375 leftRotate(xParent); | |
| 376 w = xParent.getRight(); | |
| 377 } | |
| 378 if (((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) && | |
| 379 ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK))) { | |
| 380 // Case 2 | |
| 381 w.setColor(RBColor.RED); | |
| 382 x = xParent; | |
| 383 xParent = x.getParent(); | |
| 384 } else { | |
| 385 if ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) { | |
| 386 // Case 3 | |
| 387 w.getLeft().setColor(RBColor.BLACK); | |
| 388 w.setColor(RBColor.RED); | |
| 389 rightRotate(w); | |
| 390 w = xParent.getRight(); | |
| 391 } | |
| 392 // Case 4 | |
| 393 w.setColor(xParent.getColor()); | |
| 394 xParent.setColor(RBColor.BLACK); | |
| 395 if (w.getRight() != null) { | |
| 396 w.getRight().setColor(RBColor.BLACK); | |
| 397 } | |
| 398 leftRotate(xParent); | |
| 399 x = root; | |
| 400 xParent = x.getParent(); | |
| 401 } | |
| 402 } else { | |
| 403 // Same as clause above with "right" and "left" | |
| 404 // exchanged | |
| 405 | |
| 406 // NOTE: the text points out that w can not be null. The | |
| 407 // reason is not obvious from simply examining the code; it | |
| 408 // comes about because of properties of the red-black tree. | |
| 409 RBNode w = xParent.getLeft(); | |
| 410 if (DEBUGGING) { | |
| 411 if (w == null) { | |
| 412 throw new RuntimeException("x's sibling should not be null"); | |
| 413 } | |
| 414 } | |
| 415 if (w.getColor() == RBColor.RED) { | |
| 416 // Case 1 | |
| 417 w.setColor(RBColor.BLACK); | |
| 418 xParent.setColor(RBColor.RED); | |
| 419 rightRotate(xParent); | |
| 420 w = xParent.getLeft(); | |
| 421 } | |
| 422 if (((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) && | |
| 423 ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK))) { | |
| 424 // Case 2 | |
| 425 w.setColor(RBColor.RED); | |
| 426 x = xParent; | |
| 427 xParent = x.getParent(); | |
| 428 } else { | |
| 429 if ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) { | |
| 430 // Case 3 | |
| 431 w.getRight().setColor(RBColor.BLACK); | |
| 432 w.setColor(RBColor.RED); | |
| 433 leftRotate(w); | |
| 434 w = xParent.getLeft(); | |
| 435 } | |
| 436 // Case 4 | |
| 437 w.setColor(xParent.getColor()); | |
| 438 xParent.setColor(RBColor.BLACK); | |
| 439 if (w.getLeft() != null) { | |
| 440 w.getLeft().setColor(RBColor.BLACK); | |
| 441 } | |
| 442 rightRotate(xParent); | |
| 443 x = root; | |
| 444 xParent = x.getParent(); | |
| 445 } | |
| 446 } | |
| 447 } | |
| 448 if (x != null) { | |
| 449 x.setColor(RBColor.BLACK); | |
| 450 } | |
| 451 } | |
| 452 | |
| 453 // Returns the number of black children along all paths to all | |
| 454 // leaves of the given node | |
| 455 private int verifyFromNode(RBNode node) { | |
| 456 // Bottoms out at leaf nodes | |
| 457 if (node == null) { | |
| 458 return 1; | |
| 459 } | |
| 460 | |
| 461 // Each node is either red or black | |
| 462 if (!((node.getColor() == RBColor.RED) || | |
| 463 (node.getColor() == RBColor.BLACK))) { | |
| 464 if (DEBUGGING) { | |
| 465 System.err.println("Verify failed:"); | |
| 466 printOn(System.err); | |
| 467 } | |
| 468 throw new RuntimeException("Verify failed (1)"); | |
| 469 } | |
| 470 | |
| 471 // Every leaf (null) is black | |
| 472 | |
| 473 if (node.getColor() == RBColor.RED) { | |
| 474 // Both its children are black | |
| 475 if (node.getLeft() != null) { | |
| 476 if (node.getLeft().getColor() != RBColor.BLACK) { | |
| 477 if (DEBUGGING) { | |
| 478 System.err.println("Verify failed:"); | |
| 479 printOn(System.err); | |
| 480 } | |
| 481 throw new RuntimeException("Verify failed (2)"); | |
| 482 } | |
| 483 } | |
| 484 if (node.getRight() != null) { | |
| 485 if (node.getRight().getColor() != RBColor.BLACK) { | |
| 486 if (DEBUGGING) { | |
| 487 System.err.println("Verify failed:"); | |
| 488 printOn(System.err); | |
| 489 } | |
| 490 throw new RuntimeException("Verify failed (3)"); | |
| 491 } | |
| 492 } | |
| 493 } | |
| 494 | |
| 495 // Every simple path to a leaf contains the same number of black | |
| 496 // nodes | |
| 497 int i = verifyFromNode(node.getLeft()); | |
| 498 int j = verifyFromNode(node.getRight()); | |
| 499 if (i != j) { | |
| 500 if (DEBUGGING) { | |
| 501 System.err.println("Verify failed:"); | |
| 502 printOn(System.err); | |
| 503 } | |
| 504 throw new RuntimeException("Verify failed (4) (left black count = " + | |
| 505 i + ", right black count = " + j + ")"); | |
| 506 } | |
| 507 | |
| 508 return i + ((node.getColor() == RBColor.RED) ? 0 : 1); | |
| 509 } | |
| 510 | |
| 511 /** Debugging */ | |
| 512 private void printFromNode(RBNode node, PrintStream tty, int indentDepth) { | |
| 513 for (int i = 0; i < indentDepth; i++) { | |
| 514 tty.print(" "); | |
| 515 } | |
| 516 | |
| 517 tty.print("-"); | |
| 518 if (node == null) { | |
| 519 tty.println(); | |
| 520 return; | |
| 521 } | |
| 522 | |
| 523 tty.println(" " + getNodeValue(node) + | |
| 524 ((node.getColor() == RBColor.RED) ? " (red)" : " (black)")); | |
| 525 printFromNode(node.getLeft(), tty, indentDepth + 2); | |
| 526 printFromNode(node.getRight(), tty, indentDepth + 2); | |
| 527 } | |
| 528 | |
| 529 //---------------------------------------------------------------------- | |
| 530 // Test harness | |
| 531 // | |
| 532 | |
| 533 public static void main(String[] args) { | |
| 534 int treeSize = 10000; | |
| 535 int maxVal = treeSize; | |
| 536 System.err.println("Building tree..."); | |
| 537 RBTree tree = new RBTree(new Comparator() { | |
| 538 public int compare(Object o1, Object o2) { | |
| 539 Integer i1 = (Integer) o1; | |
| 540 Integer i2 = (Integer) o2; | |
| 541 if (i1.intValue() < i2.intValue()) { | |
| 542 return -1; | |
| 543 } else if (i1.intValue() == i2.intValue()) { | |
| 544 return 0; | |
| 545 } | |
| 546 return 1; | |
| 547 } | |
| 548 }); | |
| 549 Random rand = new Random(System.currentTimeMillis()); | |
| 550 for (int i = 0; i < treeSize; i++) { | |
| 551 Integer val = new Integer(rand.nextInt(maxVal) + 1); | |
| 552 try { | |
| 553 tree.insertNode(new RBNode(val)); | |
| 554 if ((i > 0) && (i % 100 == 0)) { | |
| 555 System.err.print(i + "..."); | |
| 556 System.err.flush(); | |
| 557 } | |
| 558 } | |
| 559 catch (Exception e) { | |
| 560 e.printStackTrace(); | |
| 561 System.err.println("While inserting value " + val); | |
| 562 tree.printOn(System.err); | |
| 563 System.exit(1); | |
| 564 } | |
| 565 } | |
| 566 // Now churn data in tree by deleting and inserting lots of nodes | |
| 567 System.err.println(); | |
| 568 System.err.println("Churning tree..."); | |
| 569 for (int i = 0; i < treeSize; i++) { | |
| 570 if (DEBUGGING && VERBOSE) { | |
| 571 System.err.println("Iteration " + i + ":"); | |
| 572 tree.printOn(System.err); | |
| 573 } | |
| 574 // Pick a random value to remove (NOTE that this is not | |
| 575 // uniformly distributed) | |
| 576 RBNode xParent = null; | |
| 577 RBNode x = tree.getRoot(); | |
| 578 int depth = 0; | |
| 579 while (x != null) { | |
| 580 // Traverse path down to leaf | |
| 581 xParent = x; | |
| 582 if (rand.nextBoolean()) { | |
| 583 x = x.getLeft(); | |
| 584 } else { | |
| 585 x = x.getRight(); | |
| 586 } | |
| 587 ++depth; | |
| 588 } | |
| 589 // Pick a random height at which to remove value | |
| 590 int height = rand.nextInt(depth); | |
| 591 if (DEBUGGING) { | |
| 592 if (height >= depth) { | |
| 593 throw new RuntimeException("bug in java.util.Random"); | |
| 594 } | |
| 595 } | |
| 596 // Walk that far back up (FIXME: off by one?) | |
| 597 while (height > 0) { | |
| 598 xParent = xParent.getParent(); | |
| 599 --height; | |
| 600 } | |
| 601 // Tell the tree to remove this node | |
| 602 if (DEBUGGING && VERBOSE) { | |
| 603 System.err.println("(Removing value " + tree.getNodeValue(xParent) + ")"); | |
| 604 } | |
| 605 tree.deleteNode(xParent); | |
| 606 | |
| 607 // Now create and insert a new value | |
| 608 Integer newVal = new Integer(rand.nextInt(maxVal) + 1); | |
| 609 if (DEBUGGING && VERBOSE) { | |
| 610 System.err.println("(Inserting value " + newVal + ")"); | |
| 611 } | |
| 612 tree.insertNode(new RBNode(newVal)); | |
| 613 } | |
| 614 System.err.println("All tests passed."); | |
| 615 } | |
| 616 } |