| 1 | /* |
| 2 | |
| 3 | Derby - Class org.apache.derby.impl.store.access.sort.SortBuffer |
| 4 | |
| 5 | Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable. |
| 6 | |
| 7 | Licensed under the Apache License, Version 2.0 (the "License"); |
| 8 | you may not use this file except in compliance with the License. |
| 9 | You may obtain a copy of the License at |
| 10 | |
| 11 | http://www.apache.org/licenses/LICENSE-2.0 |
| 12 | |
| 13 | Unless required by applicable law or agreed to in writing, software |
| 14 | distributed under the License is distributed on an "AS IS" BASIS, |
| 15 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 16 | See the License for the specific language governing permissions and |
| 17 | limitations under the License. |
| 18 | |
| 19 | */ |
| 20 | |
| 21 | package org.apache.derby.impl.store.access.sort; |
| 22 | |
| 23 | import org.apache.derby.iapi.services.sanity.SanityManager; |
| 24 | import org.apache.derby.iapi.error.StandardException; |
| 25 | import org.apache.derby.iapi.store.access.SortObserver; |
| 26 | |
| 27 | import org.apache.derby.iapi.types.DataValueDescriptor; |
| 28 | |
| 29 | /** |
| 30 | |
| 31 | This class implements an in-memory ordered set |
| 32 | based on the balanced binary tree algorithm from |
| 33 | Knuth Vol. 3, Sec. 6.2.3, pp. 451-471. |
| 34 | Nodes are always maintained in order, |
| 35 | so that inserts and deletes can be intermixed. |
| 36 | <P> |
| 37 | This algorithm will insert/delete N elements |
| 38 | in O(N log(N)) time using O(N) space. |
| 39 | |
| 40 | **/ |
| 41 | |
| 42 | class SortBuffer |
| 43 | { |
| 44 | /** |
| 45 | Returned from insert when the row was inserted |
| 46 | without incident. |
| 47 | **/ |
| 48 | public static final int INSERT_OK = 0; |
| 49 | |
| 50 | /** |
| 51 | Returned from insert when the row which was |
| 52 | inserted was a duplicate. The set will have |
| 53 | aggregated it in. |
| 54 | **/ |
| 55 | public static final int INSERT_DUPLICATE = 1; |
| 56 | |
| 57 | /** |
| 58 | Returned from insert when the row was not able to be |
| 59 | inserted because the set was full. |
| 60 | **/ |
| 61 | public static final int INSERT_FULL = 2; |
| 62 | |
| 63 | /** |
| 64 | The sort this set is associated with. |
| 65 | **/ |
| 66 | private MergeSort sort; |
| 67 | |
| 68 | /** |
| 69 | Where to allocate nodes from. |
| 70 | **/ |
| 71 | private NodeAllocator allocator = null; |
| 72 | |
| 73 | /** |
| 74 | Special head node for the tree. Head.rightLink is the |
| 75 | root of the tree. |
| 76 | **/ |
| 77 | private Node head = null; |
| 78 | |
| 79 | /** |
| 80 | The current height of the tree. |
| 81 | **/ |
| 82 | private int height = 0; |
| 83 | |
| 84 | /** |
| 85 | Set, as a side effect of deleteLeftMost (only), to the |
| 86 | key from the node that was deleted from the tree. This |
| 87 | field is only valid after a call to deleteLeftMost. |
| 88 | **/ |
| 89 | private DataValueDescriptor[] deletedKey; |
| 90 | |
| 91 | /** |
| 92 | Set, as a side effect of deleteLeftMost and rotateRight, |
| 93 | if the subtree they're working on decreased in height. |
| 94 | This field is only valid after a call to deleteLeftMost |
| 95 | or rotateRight. |
| 96 | **/ |
| 97 | private boolean subtreeShrunk; |
| 98 | |
| 99 | /** |
| 100 | Set by the setNextAux() method. This value is stuffed |
| 101 | into the aux field of the next node that's allocated. |
| 102 | **/ |
| 103 | private int nextAux; |
| 104 | |
| 105 | /** |
| 106 | Read by the getLastAux() method. This value is read out |
| 107 | of the last node that was deallocated from the tree. |
| 108 | **/ |
| 109 | private int lastAux; |
| 110 | |
| 111 | /** |
| 112 | Arrange that the next node allocated in the tree have |
| 113 | it's aux field set to the argument. |
| 114 | **/ |
| 115 | public void setNextAux(int aux) |
| 116 | { |
| 117 | nextAux = aux; |
| 118 | } |
| 119 | |
| 120 | /** |
| 121 | Retrieve the aux value from the last node deallocated |
| 122 | from the tree. |
| 123 | **/ |
| 124 | public int getLastAux() |
| 125 | { |
| 126 | return lastAux; |
| 127 | } |
| 128 | |
| 129 | /** |
| 130 | Construct doesn't do anything, callers must call init |
| 131 | and check its return code. |
| 132 | **/ |
| 133 | public SortBuffer(MergeSort sort) |
| 134 | { |
| 135 | this.sort = sort; |
| 136 | } |
| 137 | |
| 138 | /** |
| 139 | Initialize. Returns false if the allocator |
| 140 | couldn't be initialized. |
| 141 | **/ |
| 142 | public boolean init() |
| 143 | { |
| 144 | allocator = new NodeAllocator(); |
| 145 | |
| 146 | boolean initOK = false; |
| 147 | |
| 148 | if (sort.sortBufferMin > 0) |
| 149 | initOK = allocator.init(sort.sortBufferMin, sort.sortBufferMax); |
| 150 | else |
| 151 | initOK = allocator.init(sort.sortBufferMax); |
| 152 | |
| 153 | if (initOK == false) |
| 154 | { |
| 155 | allocator = null; |
| 156 | return false; |
| 157 | } |
| 158 | reset(); |
| 159 | return true; |
| 160 | } |
| 161 | |
| 162 | public void reset() |
| 163 | { |
| 164 | allocator.reset(); |
| 165 | head = allocator.newNode(); |
| 166 | height = 0; |
| 167 | } |
| 168 | |
| 169 | public void close() |
| 170 | { |
| 171 | if (allocator != null) |
| 172 | allocator.close(); |
| 173 | allocator = null; |
| 174 | height = 0; |
| 175 | head = null; |
| 176 | } |
| 177 | |
| 178 | /** |
| 179 | Grow by a certain percent if we can |
| 180 | */ |
| 181 | public void grow(int percent) |
| 182 | { |
| 183 | if (percent > 0) |
| 184 | allocator.grow(percent); |
| 185 | } |
| 186 | |
| 187 | |
| 188 | /** |
| 189 | Return the number of elements this sorter can sort. |
| 190 | It's the capacity of the node allocator minus one |
| 191 | because the sorter uses one node for the head. |
| 192 | **/ |
| 193 | public int capacity() |
| 194 | { |
| 195 | if (allocator == null) |
| 196 | return 0; |
| 197 | return allocator.capacity() - 1; |
| 198 | } |
| 199 | |
| 200 | /** |
| 201 | Insert a key k into the tree. Returns true if the |
| 202 | key was inserted, false if the tree is full. Silently |
| 203 | ignores duplicate keys. |
| 204 | <P> |
| 205 | See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm. |
| 206 | **/ |
| 207 | public int insert(DataValueDescriptor[] k) |
| 208 | throws StandardException |
| 209 | { |
| 210 | int c; |
| 211 | Node p, q, r, s, t; |
| 212 | |
| 213 | if (head.rightLink == null) |
| 214 | { |
| 215 | if ((sort.sortObserver != null) && |
| 216 | ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null)) |
| 217 | { |
| 218 | return INSERT_DUPLICATE; |
| 219 | } |
| 220 | |
| 221 | q = allocator.newNode(); |
| 222 | q.key = k; |
| 223 | q.aux = nextAux; |
| 224 | head.rightLink = q; |
| 225 | height = 1; |
| 226 | return INSERT_OK; |
| 227 | } |
| 228 | |
| 229 | // [A1. Initialize] |
| 230 | t = head; |
| 231 | p = s = head.rightLink; |
| 232 | |
| 233 | // Search |
| 234 | while (true) |
| 235 | { |
| 236 | // [A2. Compare] |
| 237 | c = sort.compare(k, p.key); |
| 238 | if (c == 0) |
| 239 | { |
| 240 | // The new key compares equal to the |
| 241 | // current node's key. |
| 242 | |
| 243 | // See if we can use the aggregators |
| 244 | // to get rid of the new key. |
| 245 | if ((sort.sortObserver != null) && |
| 246 | ((k = sort.sortObserver.insertDuplicateKey(k, p.key)) == null)) |
| 247 | { |
| 248 | return INSERT_DUPLICATE; |
| 249 | } |
| 250 | |
| 251 | // Keep the duplicate key... |
| 252 | // Allocate a new node for the key. |
| 253 | q = allocator.newNode(); |
| 254 | if (q == null) |
| 255 | return INSERT_FULL; |
| 256 | q.aux = nextAux; |
| 257 | |
| 258 | // Link the new node onto the current |
| 259 | // node's duplicate chain. The assumption |
| 260 | // is made that a newly allocated node |
| 261 | // has null left and right links. |
| 262 | q.key = k; |
| 263 | q.dupChain = p.dupChain; |
| 264 | p.dupChain = q; |
| 265 | |
| 266 | // From the caller's perspective this was |
| 267 | // not a duplicate insertion. |
| 268 | return INSERT_OK; |
| 269 | } |
| 270 | |
| 271 | if (c < 0) |
| 272 | { |
| 273 | // [A3. Move left] |
| 274 | q = p.leftLink; |
| 275 | if (q == null) |
| 276 | { |
| 277 | q = allocator.newNode(); |
| 278 | if (q == null) |
| 279 | return INSERT_FULL; |
| 280 | q.aux = nextAux; |
| 281 | p.leftLink = q; |
| 282 | break; |
| 283 | } |
| 284 | } |
| 285 | else // c > 0 |
| 286 | { |
| 287 | // [A4. Move right] |
| 288 | q = p.rightLink; |
| 289 | if (q == null) |
| 290 | { |
| 291 | q = allocator.newNode(); |
| 292 | if (q == null) |
| 293 | return INSERT_FULL; |
| 294 | q.aux = nextAux; |
| 295 | p.rightLink = q; |
| 296 | break; |
| 297 | } |
| 298 | } |
| 299 | |
| 300 | if (q.balance != 0) |
| 301 | { |
| 302 | t = p; |
| 303 | s = q; |
| 304 | } |
| 305 | p = q; |
| 306 | } |
| 307 | |
| 308 | /* |
| 309 | * [A5. Insert] |
| 310 | * Node has been allocated and placed for k. |
| 311 | * Initialize it. |
| 312 | */ |
| 313 | |
| 314 | if ((sort.sortObserver != null) && |
| 315 | ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null)) |
| 316 | { |
| 317 | return INSERT_DUPLICATE; |
| 318 | } |
| 319 | q.key = k; |
| 320 | |
| 321 | /* |
| 322 | * [A6. Adjust balance factors for nodes between |
| 323 | * s and q] |
| 324 | */ |
| 325 | |
| 326 | c = sort.compare(k, s.key); |
| 327 | if (c < 0) |
| 328 | r = p = s.leftLink; |
| 329 | else |
| 330 | r = p = s.rightLink; |
| 331 | |
| 332 | while (p != q) |
| 333 | { |
| 334 | if (sort.compare(k, p.key) < 0) |
| 335 | { |
| 336 | p.balance = -1; |
| 337 | p = p.leftLink; |
| 338 | } |
| 339 | else // sort.compare(k, p.key) > 0 |
| 340 | { |
| 341 | p.balance = 1; |
| 342 | p = p.rightLink; |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | // [A7. Balancing act] |
| 347 | |
| 348 | int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1)); |
| 349 | |
| 350 | if (s.balance == 0) |
| 351 | { |
| 352 | //debug("A7 (i). The tree has gotten higher"); |
| 353 | s.balance = a; |
| 354 | height++; |
| 355 | return INSERT_OK; |
| 356 | } |
| 357 | |
| 358 | if (s.balance == -a) |
| 359 | { |
| 360 | //debug("A7 (ii). The tree has gotten more balanced"); |
| 361 | s.balance = 0; |
| 362 | return INSERT_OK; |
| 363 | } |
| 364 | |
| 365 | //debug("A7 (iii). The tree has gotten more out of balance"); |
| 366 | |
| 367 | // s.balance == a |
| 368 | if (r.balance == a) |
| 369 | { |
| 370 | //debug("A8. Single rotation"); |
| 371 | p = r; |
| 372 | s.setLink(a, r.link(-a)); |
| 373 | r.setLink(-a, s); |
| 374 | s.balance = 0; |
| 375 | r.balance = 0; |
| 376 | } |
| 377 | else // r.balance == -a |
| 378 | { |
| 379 | //debug("A8. Double rotation"); |
| 380 | p = r.link(-a); |
| 381 | r.setLink(-a, p.link(a)); |
| 382 | p.setLink(a, r); |
| 383 | s.setLink(a, p.link(-a)); |
| 384 | p.setLink(-a, s); |
| 385 | |
| 386 | if (p.balance == a) |
| 387 | { |
| 388 | s.balance = -a; |
| 389 | r.balance = 0; |
| 390 | } |
| 391 | else if (p.balance == 0) |
| 392 | { |
| 393 | s.balance = 0; |
| 394 | r.balance = 0; |
| 395 | } |
| 396 | else // p.balance == -a |
| 397 | { |
| 398 | s.balance = 0; |
| 399 | r.balance = a; |
| 400 | } |
| 401 | |
| 402 | p.balance = 0; |
| 403 | } |
| 404 | |
| 405 | // [A10. Finishing touch] |
| 406 | if (s == t.rightLink) |
| 407 | t.rightLink = p; |
| 408 | else |
| 409 | t.leftLink = p; |
| 410 | |
| 411 | return INSERT_OK; |
| 412 | } |
| 413 | |
| 414 | /** |
| 415 | Return the lowest key and delete it from |
| 416 | the tree, preserving the balance of the tree. |
| 417 | **/ |
| 418 | public DataValueDescriptor[] removeFirst() |
| 419 | { |
| 420 | if (head.rightLink == null) |
| 421 | return null; |
| 422 | head.rightLink = deleteLeftmost(head.rightLink); |
| 423 | if (this.subtreeShrunk) |
| 424 | height--; |
| 425 | return this.deletedKey; |
| 426 | } |
| 427 | |
| 428 | /** |
| 429 | Delete the node with the lowest key from the subtree defined |
| 430 | by 'thisNode', maintaining balance in the subtree. Returns |
| 431 | the node that should be the new root of the subtree. This |
| 432 | method sets this.subtreeShrunk if the subtree of thisNode |
| 433 | decreased in height. Saves the key that was in the deleted |
| 434 | node in 'deletedKey'. |
| 435 | **/ |
| 436 | private Node deleteLeftmost(Node thisNode) |
| 437 | { |
| 438 | // If this node has no left child, we've found the |
| 439 | // leftmost one, so delete it. |
| 440 | if (thisNode.leftLink == null) |
| 441 | { |
| 442 | |
| 443 | // See if the current node has duplicates. If so, we'll |
| 444 | // just return one of them and not change the tree. |
| 445 | if (thisNode.dupChain != null) |
| 446 | { |
| 447 | Node dupNode = thisNode.dupChain; |
| 448 | |
| 449 | //System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode); |
| 450 | |
| 451 | // Return the key from the duplicate. Note that even |
| 452 | // though the keys compare equal they may not be equal, |
| 453 | // depending on how the column ordering was specified. |
| 454 | this.deletedKey = dupNode.key; |
| 455 | lastAux = dupNode.aux; |
| 456 | |
| 457 | // Unlink the dup node and free it. |
| 458 | thisNode.dupChain = dupNode.dupChain; |
| 459 | allocator.freeNode(dupNode); |
| 460 | dupNode = null; |
| 461 | |
| 462 | // Tree is not changing height since we're just removing |
| 463 | // a node from the duplicate chain. |
| 464 | this.subtreeShrunk = false; |
| 465 | |
| 466 | // Preserve the current node as the root of this subtree.. |
| 467 | return thisNode; |
| 468 | } |
| 469 | else // thisNode.dupChain == null |
| 470 | { |
| 471 | //System.out.println("deleteLeftmost(" + thisNode + "): found key"); |
| 472 | |
| 473 | // Key to return is this node's key. |
| 474 | this.deletedKey = thisNode.key; |
| 475 | lastAux = thisNode.aux; |
| 476 | |
| 477 | // We're removing this node, so it's subtree is shrinking |
| 478 | // from height 1 to height 0. |
| 479 | this.subtreeShrunk = true; |
| 480 | |
| 481 | // Save this node's right link which might be cleared |
| 482 | // out by the allocator. |
| 483 | Node newRoot = thisNode.rightLink; |
| 484 | |
| 485 | // Free the node we're deleting. |
| 486 | allocator.freeNode(thisNode); |
| 487 | |
| 488 | // Rearrange the tree to put this node's right subtree where |
| 489 | // this node was. |
| 490 | return newRoot; |
| 491 | } |
| 492 | } |
| 493 | |
| 494 | // Since this wasn't the leftmost node, delete the leftmost |
| 495 | // node from this node's left subtree. This operation may |
| 496 | // rearrange the subtree, including the possiblility that the |
| 497 | // root note changed, so set the root of the left subtree to |
| 498 | // what the delete operation wants it to be. |
| 499 | thisNode.leftLink = deleteLeftmost(thisNode.leftLink); |
| 500 | |
| 501 | // If the left subtree didn't change size, then this subtree |
| 502 | // could not have changed size either. |
| 503 | if (this.subtreeShrunk == false) |
| 504 | return thisNode; |
| 505 | |
| 506 | // If the delete operation shrunk the subtree, we may have |
| 507 | // some rebalancing to do. |
| 508 | |
| 509 | if (thisNode.balance == 1) |
| 510 | { |
| 511 | // Tree got more unbalanced. Need to do some |
| 512 | // kind of rotation to fix it. The rotateRight() |
| 513 | // method will set subtreeShrunk appropriately |
| 514 | // and return the node that should be the new |
| 515 | // root of this subtree. |
| 516 | return rotateRight(thisNode); |
| 517 | } |
| 518 | |
| 519 | if (thisNode.balance == -1) |
| 520 | { |
| 521 | // Tree became more balanced |
| 522 | thisNode.balance = 0; |
| 523 | |
| 524 | // Since the left subtree was higher, and it |
| 525 | // shrunk, then this subtree shrunk, too. |
| 526 | this.subtreeShrunk = true; |
| 527 | } |
| 528 | else // thisNode.balance == 0 |
| 529 | { |
| 530 | // Tree became acceptably unbalanced |
| 531 | thisNode.balance = 1; |
| 532 | |
| 533 | // We had a balanced tree, and just the left |
| 534 | // subtree shrunk, so this subtree as a whole |
| 535 | // has not changed in height. |
| 536 | this.subtreeShrunk = false; |
| 537 | } |
| 538 | |
| 539 | // We have not rearranged this subtree. |
| 540 | return thisNode; |
| 541 | } |
| 542 | |
| 543 | /** |
| 544 | Perform either a single or double rotation, as appropriate, |
| 545 | to get the subtree 'thisNode' back in balance, assuming |
| 546 | that the right subtree of 'thisNode' is higher than the |
| 547 | left subtree. Returns the node that should be the new |
| 548 | root of the subtree. |
| 549 | <P> |
| 550 | These are the cases depicted in diagrams (1) and (2) of |
| 551 | Knuth (p. 454), and the node names reflect these diagrams. |
| 552 | However, in deletion, the single rotation may encounter |
| 553 | a case where the "beta" and "gamma" subtrees are the same |
| 554 | height (b.balance == 0), so the resulting does not always |
| 555 | shrink. |
| 556 | <P> |
| 557 | Note: This code will not do the "mirror image" cases. |
| 558 | It only works when the right subtree is the higher one |
| 559 | (this is the only case encountered when deleting leftmost |
| 560 | nodes from the tree). |
| 561 | **/ |
| 562 | private Node rotateRight(Node thisNode) |
| 563 | { |
| 564 | Node a = thisNode; |
| 565 | Node b = thisNode.rightLink; |
| 566 | |
| 567 | if (b.balance >= 0) |
| 568 | { |
| 569 | // single rotation |
| 570 | |
| 571 | a.rightLink = b.leftLink; |
| 572 | b.leftLink = a; |
| 573 | |
| 574 | if (b.balance == 0) |
| 575 | { |
| 576 | a.balance = 1; |
| 577 | b.balance = -1; |
| 578 | this.subtreeShrunk = false; |
| 579 | } |
| 580 | else // b.balance == 1 |
| 581 | { |
| 582 | a.balance = 0; |
| 583 | b.balance = 0; |
| 584 | this.subtreeShrunk = true; |
| 585 | } |
| 586 | |
| 587 | return b; |
| 588 | } |
| 589 | else // b.balance == -1 |
| 590 | { |
| 591 | // double rotation |
| 592 | |
| 593 | Node x = b.leftLink; |
| 594 | |
| 595 | a.rightLink = x.leftLink; |
| 596 | x.leftLink = a; |
| 597 | b.leftLink = x.rightLink; |
| 598 | x.rightLink = b; |
| 599 | |
| 600 | if (x.balance == 1) |
| 601 | { |
| 602 | a.balance = -1; |
| 603 | b.balance = 0; |
| 604 | } |
| 605 | else if (x.balance == -1) |
| 606 | { |
| 607 | a.balance = 0; |
| 608 | b.balance = 1; |
| 609 | } |
| 610 | else // x.balance == 0 |
| 611 | { |
| 612 | a.balance = 0; |
| 613 | b.balance = 0; |
| 614 | } |
| 615 | x.balance = 0; |
| 616 | |
| 617 | this.subtreeShrunk = true; |
| 618 | |
| 619 | return x; |
| 620 | } |
| 621 | } |
| 622 | |
| 623 | public void check() |
| 624 | { |
| 625 | if (SanityManager.DEBUG) |
| 626 | { |
| 627 | String error = null; |
| 628 | if (head.rightLink == null) |
| 629 | { |
| 630 | if (height != 0) |
| 631 | error = "empty tree with height " + height; |
| 632 | } |
| 633 | else |
| 634 | { |
| 635 | if (depth(head.rightLink) != height) |
| 636 | error = "tree height " + height + " != depth " + depth(head.rightLink); |
| 637 | else |
| 638 | error = checkNode(head.rightLink); |
| 639 | } |
| 640 | if (error != null) |
| 641 | { |
| 642 | System.out.println("ERROR: " + error); |
| 643 | print(); |
| 644 | System.exit(1); |
| 645 | } |
| 646 | } |
| 647 | } |
| 648 | |
| 649 | private String checkNode(Node n) |
| 650 | { |
| 651 | if (SanityManager.DEBUG) |
| 652 | { |
| 653 | if (n == null) |
| 654 | return null; |
| 655 | int ld = depth(n.leftLink); |
| 656 | int rd = depth(n.rightLink); |
| 657 | if (n.balance != (rd - ld)) |
| 658 | return "node " + n + ": left height " + ld + " right height " + rd; |
| 659 | |
| 660 | String e; |
| 661 | e = checkNode(n.rightLink); |
| 662 | if (e == null) |
| 663 | e = checkNode(n.leftLink); |
| 664 | return e; |
| 665 | } |
| 666 | else |
| 667 | { |
| 668 | return(null); |
| 669 | } |
| 670 | } |
| 671 | |
| 672 | private int depth(Node n) |
| 673 | { |
| 674 | int ld = 0; |
| 675 | int rd = 0; |
| 676 | if (n == null) |
| 677 | return 0; |
| 678 | if (n.leftLink != null) |
| 679 | ld = depth(n.leftLink); |
| 680 | if (n.rightLink != null) |
| 681 | rd = depth(n.rightLink); |
| 682 | if (rd > ld) |
| 683 | return rd + 1; |
| 684 | else |
| 685 | return ld + 1; |
| 686 | } |
| 687 | |
| 688 | public void print() |
| 689 | { |
| 690 | Node root = head.rightLink; |
| 691 | System.out.println("tree height: " + height |
| 692 | + " root: " + ((root == null) ? -1 : root.id)); |
| 693 | if (root != null) |
| 694 | printRecursive(root, 0); |
| 695 | } |
| 696 | |
| 697 | private void printRecursive(Node n, int depth) |
| 698 | { |
| 699 | if (n.rightLink != null) |
| 700 | printRecursive(n.rightLink, depth + 1); |
| 701 | for (int i = 0; i < depth; i++) |
| 702 | System.out.print(" "); |
| 703 | System.out.println(n); |
| 704 | if (n.leftLink != null) |
| 705 | printRecursive(n.leftLink, depth + 1); |
| 706 | } |
| 707 | |
| 708 | private void debug(String s) |
| 709 | { |
| 710 | if (SanityManager.DEBUG) |
| 711 | { |
| 712 | System.out.println(" === [" + s + "] ==="); |
| 713 | } |
| 714 | } |
| 715 | } |