1 16 17 18 package com.daffodilwoods.rbtreesizesequence.utils.rbtree; 19 20 import java.util.TreeSet ; 21 import java.util.ArrayList ; 22 import java.util.Comparator ; 23 import java.util.Iterator ; 24 25 public class SegmentedRedBlackTree { 26 27 private static final boolean BLACK = true; 28 private static final boolean RED = false; 29 30 private static final boolean LEFT = true; 31 private static final boolean RIGHT = false; 32 33 protected RootWrapper rootOfRootWrapperList; protected Comparator comparator; 36 public SegmentedRedBlackTree() { 37 rootOfRootWrapperList = new RootWrapper(); 38 } 39 40 public SegmentedRedBlackTree(Comparator c) { 41 comparator = c; 42 } 43 44 protected void addRootWrapperToList(RootWrapper rootWrapper){ 45 put(rootOfRootWrapperList, rootWrapper); 46 } 47 48 protected void removeFromRootWrapperList(RootWrapper rootWrapper){ 49 remove(rootOfRootWrapperList, rootWrapper, false); 50 } 51 52 protected RBTreeNode createRBTreeNode(Object key, RBTreeNode parent){ 53 return new RBTreeNode(key, parent); 54 } 55 56 protected void preSwapPosition(RootWrapper rootWrapper, RBTreeNode x, RBTreeNode y){ 57 } 58 59 protected void postSwapPosition(RootWrapper rootWrapper){ 60 } 61 62 public boolean canContain(RootWrapper rootWrapper, Object key){ 63 boolean result = 64 ( compare(firstKey(rootWrapper), key) <= 0 ) 65 && 66 ( compare(lastKey(rootWrapper), key) >= 0 ); 67 return result; 68 } 69 70 private int compare(RootWrapper rootWrapper, Object obj1, Object obj2){ 71 if(obj1 == obj2) return 0; 72 if(obj1 instanceof RootWrapper && obj2 instanceof RootWrapper) 73 return compare(((RootWrapper)obj1).getRoot().getKey(), ((RootWrapper)obj2).getRoot().getKey()); 74 return compare(obj1, obj2); 75 } 76 77 protected int compare(Object obj1, Object obj2){ 78 if(obj1 == obj2) return 0; 79 if(obj1 instanceof RootWrapper && obj2 instanceof RootWrapper) 80 return compare(((RootWrapper)obj1).getRoot().getKey(), ((RootWrapper)obj2).getRoot().getKey()); 81 return (comparator==null ? ((Comparable )obj1).compareTo(obj2) : 82 comparator.compare(obj1, obj2)); 83 } 84 85 public boolean containsKey(RootWrapper rootWrapper, Object key){ 86 return getNode(rootWrapper, key) != null; 87 } 88 89 public RBTreeNode getNode(RootWrapper rootWrapper, Object key){ 90 RBTreeNode root = rootWrapper.getRoot(); 91 while (root != null) { 92 int cmp = compare(rootWrapper, key, root.key); 93 if (cmp == 0) 94 return root; 95 else if (cmp < 0) 96 root = root.left; 97 else 98 root = root.right; 99 } 100 return null; 101 } 102 103 public Comparator getComparator(){ 104 return comparator; 105 } 106 107 public Object firstKey(RootWrapper rootWrapper){ 108 return rootWrapper == null ? null : getKey(firstNode(rootWrapper)); 109 } 110 111 public Object lastKey(RootWrapper rootWrapper){ 112 113 return rootWrapper == null ? null : getKey(lastNode(rootWrapper)); 114 } 115 116 public Object getKey(RBTreeNode node){ 117 if (node==null) 118 return null; 119 return node.key; 120 } 121 122 protected RBTreeNode firstNode(RootWrapper rootWrapper) { 123 RBTreeNode root = rootWrapper.getRoot(); 124 if (root != null) 125 while (root.left != null) 126 root = root.left; 127 return root; 128 } 129 130 protected RBTreeNode lastNode(RootWrapper rootWrapper) { 131 RBTreeNode root = rootWrapper.getRoot(); 132 if (root != null) 133 while (root.right != null) 134 root = root.right; 135 return root; 136 } 137 138 public RBTreeNode getCeilNode(RootWrapper rootWrapper, Object key) { 139 RBTreeNode root = rootWrapper.getRoot(); 140 if (root==null){ 141 return null; 142 } 143 144 while (true) { 145 int cmp = compare(rootWrapper, key, root.key); 146 if (cmp == 0) { 147 return root; 148 } else if (cmp < 0) { 149 if (root.left != null) 150 root = root.left; 151 else{ 152 return root; 153 } 154 } else { 155 if (root.right != null) { 156 root = root.right; 157 } else { 158 RBTreeNode parent = root.parent; 159 RBTreeNode ch = root; 160 while (parent != null && ch == parent.right) { 161 ch = parent; 162 parent = parent.parent; 163 } 164 return parent; 165 } 166 } 167 } 168 } 169 170 public RBTreeNode getFloorNode(RootWrapper rootWrapper, Object key) { 171 RBTreeNode root = rootWrapper.getRoot(); 172 if (root==null){ 173 return null; 174 } 175 while (true) { 176 int cmp = compare(rootWrapper, key, root.key); 177 if (cmp == 0) { 178 return root; 179 } else if (cmp > 0) { 180 if (root.right != null) 181 root = root.right; 182 else{ 183 return root; 184 } 185 } else { 186 if (root.left != null) { 187 root = root.left; 188 } else { 189 RBTreeNode parent = root.parent; 190 RBTreeNode ch = root; 191 while (parent != null && ch == parent.left) { 192 ch = parent; 193 parent = parent.parent; 194 } 195 return parent; 196 } 197 } 198 } 199 } 200 201 public RBTreeNode getNextNode(RootWrapper rootWrapper, Object key) { 202 RBTreeNode root = rootWrapper.getRoot(); 203 if (root==null) 204 return null; 205 206 while (true) { 207 int cmp = compare(rootWrapper, key, root.key); 208 if (cmp < 0) { 209 if (root.left != null) 210 root = root.left; 211 else 212 return root; 213 } else { 214 if (root.right != null) { 215 root = root.right; 216 } else { 217 RBTreeNode parent = root.parent; 218 RBTreeNode ch = root; 219 while (parent != null && ch == parent.right) { 220 ch = parent; 221 parent = parent.parent; 222 } 223 return parent; 224 } 225 } 226 } 227 } 228 229 public RBTreeNode getPrecedingNode(RootWrapper rootWrapper, Object key) { 230 RBTreeNode root = rootWrapper.getRoot(); 231 if (root==null) 232 return null; 233 234 while (true) { 235 int cmp = compare(rootWrapper, key, root.key); 236 if (cmp > 0) { 237 if (root.right != null) 238 root = root.right; 239 else 240 return root; 241 } else { 242 if (root.left != null) { 243 root = root.left; 244 } else { 245 RBTreeNode parent = root.parent; 246 RBTreeNode ch = root; 247 while (parent != null && ch == parent.left) { 248 ch = parent; 249 parent = parent.parent; 250 } 251 return parent; 252 } 253 } 254 } 255 } 256 257 public void invokeFixAfterInsertion(RootWrapper rootWrapper, RBTreeNode x) { 258 if(x != null) 259 fixAfterInsertion(rootWrapper, x); 260 } 261 262 263 264 private void fixAfterInsertion(RootWrapper rootWrapper, RBTreeNode x) { 265 x.color = RED; 266 while (x != null && x != rootWrapper.getRoot() && x.parent.color == RED) { 267 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 268 RBTreeNode y = rightOf(parentOf(parentOf(x))); 269 if (colorOf(y) == RED) { 270 setColor(parentOf(x), BLACK); 271 setColor(y, BLACK); 272 setColor(parentOf(parentOf(x)), RED); 273 x = parentOf(parentOf(x)); 274 } else { 275 if (x == rightOf(parentOf(x))) { 276 x = parentOf(x); 277 rotateLeft(rootWrapper, x); 278 } 279 setColor(parentOf(x), BLACK); 280 setColor(parentOf(parentOf(x)), RED); 281 if (parentOf(parentOf(x)) != null) 282 rotateRight(rootWrapper, parentOf(parentOf(x))); 283 } 284 } else { 285 RBTreeNode y = leftOf(parentOf(parentOf(x))); 286 if (colorOf(y) == RED) { 287 setColor(parentOf(x), BLACK); 288 setColor(y, BLACK); 289 setColor(parentOf(parentOf(x)), RED); 290 x = parentOf(parentOf(x)); 291 } else { 292 if (x == leftOf(parentOf(x))) { 293 x = parentOf(x); 294 rotateRight(rootWrapper, x); 295 } 296 setColor(parentOf(x), BLACK); 297 setColor(parentOf(parentOf(x)), RED); 298 if (parentOf(parentOf(x)) != null) 299 rotateLeft(rootWrapper, parentOf(parentOf(x))); 300 } 301 } 302 } 303 rootWrapper.getRoot().color = BLACK; 304 } 305 306 307 protected void rotateLeft(RootWrapper rootWrapper, RBTreeNode p) { 308 RBTreeNode r = p.right; 309 p.right = r.left; 310 if (r.left != null) 311 r.left.parent = p; 312 r.parent = p.parent; 313 if (p.parent == null) 314 setRootWrapperRoot(rootWrapper, r); 315 else if (p.parent.left == p) 316 p.parent.left = r; 317 else 318 p.parent.right = r; 319 r.left = p; 320 p.parent = r; 321 } 322 323 324 protected void rotateRight(RootWrapper rootWrapper, RBTreeNode p) { 325 326 RBTreeNode l = p.left; 327 p.left = l.right; 328 if (l.right != null) l.right.parent = p; 329 l.parent = p.parent; 330 if (p.parent == null) 331 setRootWrapperRoot(rootWrapper, l); 332 else if (p.parent.right == p) 333 p.parent.right = l; 334 else p.parent.left = l; 335 l.right = p; 336 p.parent = l; 337 } 338 339 348 349 private static boolean colorOf(RBTreeNode p) { 350 return (p == null ? BLACK : p.color); 351 } 352 353 private static RBTreeNode parentOf(RBTreeNode p) { 354 return (p == null ? null: p.parent); 355 } 356 357 private static void setColor(RBTreeNode p, boolean c) { 358 if (p != null) p.color = c; 359 } 360 361 private static RBTreeNode leftOf(RBTreeNode p) { 362 return (p == null)? null: p.left; 363 } 364 365 private static RBTreeNode rightOf(RBTreeNode p) { 366 return (p == null)? null: p.right; 367 } 368 369 protected boolean remove(RootWrapper rootWrapper, Object key) { 370 return remove(rootWrapper, key, true); 371 } 372 373 374 private boolean remove(RootWrapper rootWrapper, Object key, boolean removeFromRootWrapperListIfEmpty) { 375 376 RBTreeNode p = getNode(rootWrapper, key); 377 if(p != null){ 378 if(removeFromRootWrapperListIfEmpty && compare(p.getKey(), rootWrapper.getRoot().getKey()) == 0 && p.left == null && p.right == null){ 379 removeFromRootWrapperList(rootWrapper); 380 return false; 381 } 382 RBTreeNode node = deleteNodeWithoutFix(rootWrapper, p); 383 invokeFixAfterDeletion(rootWrapper, node); 384 } 385 return true; 386 } 387 388 391 public RBTreeNode deleteNodeWithoutFix(RootWrapper rootWrapper, RBTreeNode p) { 392 393 if (p.left != null && p.right != null) { 394 RBTreeNode s = successor(p); 395 swapPosition(rootWrapper, s, p); 396 } 397 RBTreeNode replacement = (p.left != null ? p.left : p.right); 398 399 if (replacement != null) { 400 replacement.parent = p.parent; 401 if (p.parent == null){ 402 setRootWrapperRoot(rootWrapper, replacement); 403 } 404 else if (p == p.parent.left) 405 replaceParentLeft(p, replacement); 406 else 407 replaceParentRight(p, replacement); 408 409 p.left = p.right = p.parent = null; 410 411 if (p.color == BLACK) 412 return replacement; 413 } else if (p.parent == null) { setRootWrapperRoot(rootWrapper, null); 415 } else { if (p.color == BLACK) 417 fixAfterDeletion(rootWrapper, p); 418 if (p.parent != null) { 419 if (p == p.parent.left) 420 p.parent.left = null; 421 else if (p == p.parent.right) 422 p.parent.right = null; 423 p.parent = null; 424 } 425 } 426 return null; 427 } 428 protected void replaceParentLeft(RBTreeNode p, RBTreeNode replacement){ 429 p.parent.left = replacement; 430 } 431 432 protected void replaceParentRight(RBTreeNode p, RBTreeNode replacement){ 433 p.parent.right = replacement; 434 } 435 436 public void invokeFixAfterDeletion(RootWrapper rootWrapper, RBTreeNode x) { 437 if(x != null) 438 fixAfterDeletion(rootWrapper, x); 439 } 440 441 442 private void fixAfterDeletion(RootWrapper rootWrapper, RBTreeNode x) { 443 while (x != rootWrapper.getRoot() && colorOf(x) == BLACK) { 444 if (x == leftOf(parentOf(x))) { 445 RBTreeNode sib = rightOf(parentOf(x)); 446 447 if (colorOf(sib) == RED) { 448 setColor(sib, BLACK); 449 setColor(parentOf(x), RED); 450 rotateLeft(rootWrapper, parentOf(x)); 451 sib = rightOf(parentOf(x)); 452 } 453 454 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { 455 setColor(sib, RED); 456 x = parentOf(x); 457 } else { 458 if (colorOf(rightOf(sib)) == BLACK) { 459 setColor(leftOf(sib), BLACK); 460 setColor(sib, RED); 461 rotateRight(rootWrapper, sib); 462 sib = rightOf(parentOf(x)); 463 } 464 setColor(sib, colorOf(parentOf(x))); 465 setColor(parentOf(x), BLACK); 466 setColor(rightOf(sib), BLACK); 467 rotateLeft(rootWrapper, parentOf(x)); 468 x = rootWrapper.getRoot(); 469 } 470 } else { RBTreeNode sib = leftOf(parentOf(x)); 472 473 if (colorOf(sib) == RED) { 474 setColor(sib, BLACK); 475 setColor(parentOf(x), RED); 476 rotateRight(rootWrapper, parentOf(x)); 477 sib = leftOf(parentOf(x)); 478 } 479 480 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { 481 setColor(sib, RED); 482 x = parentOf(x); 483 } else { 484 if (colorOf(leftOf(sib)) == BLACK) { 485 setColor(rightOf(sib), BLACK); 486 setColor(sib, RED); 487 rotateLeft(rootWrapper, sib); 488 sib = leftOf(parentOf(x)); 489 } 490 setColor(sib, colorOf(parentOf(x))); 491 setColor(parentOf(x), BLACK); 492 setColor(leftOf(sib), BLACK); 493 rotateRight(rootWrapper, parentOf(x)); 494 x = rootWrapper.getRoot(); 495 } 496 } 497 } 498 setColor(x, BLACK); 499 } 500 501 504 private void swapPosition(RootWrapper rootWrapper, RBTreeNode x, RBTreeNode y) { 505 preSwapPosition(rootWrapper, x, y); 506 RBTreeNode px = x.parent, lx = x.left, rx = x.right; 507 RBTreeNode py = y.parent, ly = y.left, ry = y.right; 508 boolean xWasLeftChild = px != null && x == px.left; 509 boolean yWasLeftChild = py != null && y == py.left; 510 511 if (x == py) { x.parent = y; 513 if (yWasLeftChild) { 514 y.left = x; 515 y.right = rx; 516 } else { 517 y.right = x; 518 y.left = lx; 519 } 520 } else { 521 x.parent = py; 522 if (py != null) { 523 if (yWasLeftChild) 524 py.left = x; 525 else 526 py.right = x; 527 } 528 y.left = lx; 529 y.right = rx; 530 } 531 532 if (y == px) { y.parent = x; 534 if (xWasLeftChild) { 535 x.left = y; 536 x.right = ry; 537 } else { 538 x.right = y; 539 x.left = ly; 540 } 541 } else { 542 y.parent = px; 543 if (px != null) { 544 if (xWasLeftChild) 545 px.left = y; 546 else 547 px.right = y; 548 } 549 x.left = ly; 550 x.right = ry; 551 } 552 553 if (x.left != null) 554 x.left.parent = x; 555 if (x.right != null) 556 x.right.parent = x; 557 if (y.left != null) 558 y.left.parent = y; 559 if (y.right != null) 560 y.right.parent = y; 561 562 boolean c = x.color; 563 x.color = y.color; 564 y.color = c; 565 566 if (rootWrapper.getRoot() == x) 567 setRootWrapperRoot(rootWrapper, y); 568 else if (rootWrapper.getRoot() == y) 569 setRootWrapperRoot(rootWrapper, x); 570 postSwapPosition(rootWrapper); 571 } 572 573 576 private RBTreeNode successor(RBTreeNode t) { 577 if (t == null) 578 return null; 579 else if (t.right != null) { 580 RBTreeNode p = t.right; 581 while (p.left != null) 582 p = p.left; 583 return p; 584 } else { 585 RBTreeNode p = t.parent; 586 RBTreeNode ch = t; 587 while (p != null && ch == p.right) { 588 ch = p; 589 p = p.parent; 590 } 591 return p; 592 } 593 } 594 595 protected void put(RootWrapper rootWrapper, Object key){ 596 RBTreeNode x = putWithoutFix(rootWrapper, key); 597 invokeFixAfterInsertion(rootWrapper, x); 598 } 599 600 608 609 public RBTreeNode putWithoutFix(RootWrapper rootWrapper, Object key){ 610 RBTreeNode t = rootWrapper.getRoot(); 611 if (t == null) { 612 rootWrapper.root = createRBTreeNode(key, null); 613 return rootWrapper.getRoot(); } 615 while (true) { 616 int cmp = compare(rootWrapper, key, t.key); 617 if (cmp == 0) { 618 return null; 619 } else if (cmp < 0) { 620 if (t.left != null) { 621 t = t.left; 622 } else { 623 t.left = createRBTreeNode(key, t); 624 return t.left; 625 } 626 } else { if (t.right != null) { 628 t = t.right; 629 } else { 630 t.right = createRBTreeNode(key, t); 631 return t.right; 632 } 633 } 634 } 635 } 636 637 protected void setRootWrapperRoot(RootWrapper rootWrapper, RBTreeNode node){ 638 rootWrapper.setRoot(node); 639 } 640 641 public void breakTree(RootWrapper mainRootWrapper, Object obj, RootWrapper rootWrapperLeft, RootWrapper rootWrapperRight){ 642 RBTreeNode root = mainRootWrapper.getRoot(); 643 if( root == null ){ 644 return; 645 } 646 Object rootKey = root.getKey(); 647 Object leftNodeKey = null; 648 Object rightNodeKey = null; 649 RBTreeNode leftNode = root.left; 650 RBTreeNode rightNode = root.right; 651 if(leftNode != null){ 652 leftNodeKey = leftNode.getKey(); 653 } 654 if(rightNode != null){ 655 rightNodeKey = rightNode.key; 656 } 657 int cmp = compare(rootKey, obj); 658 if(cmp == 0){ if(leftNode == null && rightNode == null){ return; 661 } 662 RootWrapper tempLeft = new RootWrapper(); RootWrapper tempRight = new RootWrapper(); 665 boolean joinWithLeft = true; 666 boolean joinWithRight = true; 667 if(rootWrapperLeft.getRoot() == null){ setRootWrapperRoot(rootWrapperLeft, leftNode); 669 joinWithLeft = false; 670 } 671 else if(leftNode != null){ setRootWrapperRoot(tempLeft, leftNode); 673 } 674 if(rootWrapperRight.getRoot() == null){ setRootWrapperRoot(rootWrapperRight, rightNode); 676 joinWithRight = false; 677 } 678 else if(rightNode != null){ setRootWrapperRoot(tempRight, rightNode); 680 } 681 682 if(joinWithLeft){ 683 rootWrapperLeft.setRoot(joinTrees(rootWrapperLeft, tempLeft).getRoot()); 684 } 685 if(joinWithRight){ 686 rootWrapperRight.setRoot(joinTrees(rootWrapperRight, tempRight).getRoot()); 687 } 688 return; 689 } 690 else if( cmp > 0){ if(leftNode == null && rightNode == null){ 692 if(rootWrapperRight.getRoot() == null){ 693 setRootWrapperRoot(rootWrapperRight, root); 694 } 695 else { 696 makeLinksNull(root); 697 put(rootWrapperRight, rootKey); 698 } 699 return; 700 } 701 if(rootWrapperRight.getRoot() == null){ if(rightNode != null){ 703 setRootWrapperRoot(rootWrapperRight, rightNode); 704 makeLinksNull(root); 705 put(rootWrapperRight, rootKey); 706 } 707 else{ 708 root.left = null; 709 setRootWrapperRoot(rootWrapperRight, root); 710 } 711 } 712 else{ if(rightNode == null){ Object tempRootRight = rootWrapperRight.getRoot().getKey(); 715 makeLinksNull(root); 716 put(rootWrapperRight, rootKey); 717 } 718 else{ 719 RootWrapper tempRight = new RootWrapper(rightNode); 720 makeLinksNull(root); 721 put(tempRight, rootKey); 722 723 Object rootWrapperRightTempRoot = rootWrapperRight.getRoot().getKey(); 724 rootWrapperRight.setRoot(joinTrees(tempRight, rootWrapperRight).getRoot()); 725 726 } 727 } 728 if(leftNode == null){ 729 return; 730 } 731 setRootWrapperRoot(mainRootWrapper, leftNode); 732 breakTree(mainRootWrapper, obj, rootWrapperLeft, rootWrapperRight); 733 return; 734 } 735 else{ if(leftNode == null && rightNode == null){ 737 if(rootWrapperLeft.getRoot() == null){ 738 setRootWrapperRoot(rootWrapperLeft, root); 739 } 740 else { 741 makeLinksNull(root); 742 put(rootWrapperLeft, rootKey); 743 } 744 return; 745 } 746 if(rootWrapperLeft.getRoot() == null){ if(leftNode != null){ 748 setRootWrapperRoot(rootWrapperLeft, leftNode); 749 makeLinksNull(root); 750 put(rootWrapperLeft, rootKey); 751 } 752 else{ 753 root.right = null; 754 setRootWrapperRoot(rootWrapperLeft, root); 755 } 756 } 757 else{ if(leftNode == null){ Object tempRootLeft = rootWrapperLeft.getRoot().getKey(); 760 makeLinksNull(root); 761 put(rootWrapperLeft, rootKey); 762 } 763 else{ 764 RootWrapper tempLeft = new RootWrapper(leftNode); 765 makeLinksNull(root); 766 put(tempLeft, rootKey); 767 768 Object rootWrapperLeftTempRoot = rootWrapperLeft.getRoot().getKey(); 769 rootWrapperLeft.setRoot(joinTrees(tempLeft, rootWrapperLeft).getRoot()); 770 } 771 } 772 if(rightNode == null){ 773 return; 774 } 775 setRootWrapperRoot(mainRootWrapper, rightNode); 776 breakTree(mainRootWrapper, obj, rootWrapperLeft, rootWrapperRight); 777 return; 778 } 779 } 780 781 782 783 public RootWrapper getRootWrapper(Object locationId){ 784 if(locationId == null ){ 785 ; 786 throw new IllegalArgumentException ("<<<<<<<<<<<<<<<can't pass null to getRoot>>>>>>>>>>>"); 787 } 788 if(rootOfRootWrapperList == null){ 789 return null; 790 } 791 RBTreeNode root = rootOfRootWrapperList.getRoot(); 792 while (root != null) { 793 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 794 if (canContain(rootWrapper, locationId)){ 795 return rootWrapper; 796 } 797 int cmp = compare(locationId, rootWrapper.getRoot().getKey()); 798 if (cmp < 0) 799 root = root.left; 800 else 801 root = root.right; 802 } 803 return null; 804 } 805 806 public Object getCommonAncestor(RootWrapper rootWrapper, Object locationId1, Object locationId2){ 807 int cmp = compare(rootWrapper, locationId1, locationId2); 808 if(cmp == 0){ 809 return locationId1; 810 } 811 Object result = findCommonRootKey(rootWrapper.getRoot(), locationId1, locationId2); 812 return result; 813 } 814 815 private Object findCommonRootKey(RBTreeNode root, Object locationId1, Object locationId2){ 816 Object rootLocationId = root.getKey(); 817 int cmp1 = compare(rootLocationId, locationId1 ); 818 int cmp2 = compare(rootLocationId, locationId2 ); 819 if(cmp1 == 0){ 820 return locationId1; 821 } 822 else if(cmp2 == 0){ 823 return locationId2; 824 } 825 if((cmp1 < 0 ) && ( cmp2 < 0 )){ 826 Object result = findCommonRootKey(root.getRight(), locationId1, locationId2); 827 return result; 828 } 829 if((cmp1 > 0 ) && ( cmp2 > 0 )){ 830 Object result = findCommonRootKey(root.getLeft(), locationId1, locationId2); 831 return result; 832 } 833 return rootLocationId; 834 } 835 836 public RootWrapper getNextRootWrapper(RootWrapper rootWrapper){ 837 if(rootOfRootWrapperList == null){ 838 return null; 839 } 840 RBTreeNode nextNode = getNextNode(rootOfRootWrapperList, rootWrapper); 841 RootWrapper result; 842 if(nextNode == null) 843 result = null; 844 else 845 result = (RootWrapper)(nextNode.getKey()); 846 return result; 847 } 848 849 public RootWrapper getPreviousRootWrapper(RootWrapper rootWrapper){ 850 if(rootOfRootWrapperList == null){ 851 return null; 852 } 853 RBTreeNode previousNode = getPrecedingNode(rootOfRootWrapperList, rootWrapper); 854 RootWrapper result; 855 if(previousNode == null) 856 result = null; 857 else 858 result = (RootWrapper)(previousNode.getKey()); 859 return result; 860 } 861 862 public RootWrapper getCeilRootWrapper(Object locationId){ 863 if(rootOfRootWrapperList == null){ 864 return null; 865 } 866 RBTreeNode root = rootOfRootWrapperList.getRoot(); 867 if (root==null){ 868 return null; 869 } 870 while (true) { 871 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 872 if (canContain(rootWrapper, locationId)){ 873 return rootWrapper; 874 } 875 int cmp = compare(locationId, rootWrapper.getRoot().getKey()); 876 if (cmp < 0) { 877 if (root.left != null) 878 root = root.left; 879 else{ 880 return rootWrapper; 881 } 882 } else { 883 if (root.right != null) { 884 root = root.right; 885 } else { 886 RBTreeNode parent = root.parent; 887 RBTreeNode ch = root; 888 while (parent != null && ch == parent.right) { 889 ch = parent; 890 parent = parent.parent; 891 } 892 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey(); 893 return rootWrapper; 894 } 895 } 896 } 897 } 898 899 public RootWrapper getNextRootWrapperOfKey(Object locationId){ 900 if(rootOfRootWrapperList == null){ 901 return null; 902 } 903 RBTreeNode root = rootOfRootWrapperList.getRoot(); 904 if (root==null){ 905 return null; 906 } 907 while (true) { 908 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 909 int cmp = compare(locationId, rootWrapper.getRoot().getKey()); 910 if (cmp < 0) { 911 if (root.left != null) 912 root = root.left; 913 else{ 914 return rootWrapper; 915 } 916 } else { 917 if (root.right != null) { 918 root = root.right; 919 } else { 920 RBTreeNode parent = root.parent; 921 RBTreeNode ch = root; 922 while (parent != null && ch == parent.right) { 923 ch = parent; 924 parent = parent.parent; 925 } 926 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey(); 927 return rootWrapper; 928 } 929 } 930 } 931 } 932 933 public RootWrapper getFloorRootWrapper(Object locationId){ 934 if(rootOfRootWrapperList == null){ 935 return null; 936 } 937 RBTreeNode root = rootOfRootWrapperList.getRoot(); 938 if (root == null){ 939 return null; 940 } 941 942 while (true) { 943 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 944 if (canContain(rootWrapper, locationId)){ 945 return rootWrapper; 946 } 947 int cmp = compare(locationId, rootWrapper.getRoot().getKey()); 948 if (cmp > 0) { 949 if (root.right != null) 950 root = root.right; 951 else{ 952 rootWrapper = (RootWrapper)root.getKey(); 953 return rootWrapper; 954 } 955 } else { 956 if (root.left != null) { 957 root = root.left; 958 } else { 959 RBTreeNode parent = root.parent; 960 RBTreeNode ch = root; 961 while (parent != null && ch == parent.left) { 962 ch = parent; 963 parent = parent.parent; 964 } 965 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey(); 966 return rootWrapper; 967 } 968 } 969 } 970 } 971 972 public RootWrapper getPreviousRootWrapperOfKey(Object locationId){ 973 if(rootOfRootWrapperList == null){ 974 return null; 975 } 976 RBTreeNode root = rootOfRootWrapperList.getRoot(); 977 if (root == null){ 978 return null; 979 } 980 981 while (true) { 982 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 983 int cmp = compare(locationId, rootWrapper.getRoot().getKey()); 984 if (cmp > 0) { 985 if (root.right != null) 986 root = root.right; 987 else{ 988 rootWrapper = (RootWrapper)root.getKey(); 989 return rootWrapper; 990 } 991 } else { 992 if (root.left != null) { 993 root = root.left; 994 } else { 995 RBTreeNode parent = root.parent; 996 RBTreeNode ch = root; 997 while (parent != null && ch == parent.left) { 998 ch = parent; 999 parent = parent.parent; 1000 } 1001 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey(); 1002 return rootWrapper; 1003 } 1004 } 1005 } 1006 } 1007 1008 public RootWrapper getFirstRootWrapper(){ 1009 if(rootOfRootWrapperList == null){ 1010 return null; 1011 } 1012 RootWrapper result = (RootWrapper)firstKey(rootOfRootWrapperList); 1013 return result; 1014 } 1015 1016 public RootWrapper getLastRootWrapper(){ 1017 if(rootOfRootWrapperList == null){ 1018 return null; 1019 } 1020 RootWrapper result = (RootWrapper)lastKey(rootOfRootWrapperList); 1021 return result; 1022 } 1023 1024 public void removeRootWrappersWithIn(Object locationIdFrom, Object locationIdTo){ 1025 if(rootOfRootWrapperList == null){ 1026 return; 1027 } 1028 int cmp = compare(locationIdFrom, locationIdTo); 1029 if(cmp == 0) return; 1030 if(cmp > 0){ 1031 Object temp = locationIdFrom; 1032 locationIdFrom = locationIdTo; 1033 locationIdTo = temp; 1034 } 1035 boolean removing = true; 1036 while(removing){ 1037 removing = removeNodeInBetween(rootOfRootWrapperList.getRoot(), locationIdFrom, locationIdTo); 1038 } 1039 } 1040 1041 private boolean removeNodeInBetween(RBTreeNode root, Object locationIdFrom, Object locationIdTo){ 1042 if(root == null){ 1043 return false; 1044 } 1045 RootWrapper rootWrapper = (RootWrapper)root.getKey(); 1046 int cmp1 = compare(locationIdFrom, rootWrapper.getRoot().getKey()); 1047 int cmp2 = compare(locationIdTo, rootWrapper.getRoot().getKey()); 1048 if( (cmp1 < 0 && cmp2 > 0) ){ 1049 removeFromRootWrapperList(rootWrapper); 1050 return true; 1051 } 1052 if (cmp1 < 0 && cmp2 < 0) 1053 root = root.left; 1054 else if(cmp1 > 0 && cmp2 > 0) 1055 root = root.right; 1056 return removeNodeInBetween(root, locationIdFrom, locationIdTo); 1057 } 1058 1059 public void show(){ 1060 if (rootOfRootWrapperList.getRoot() != null) 1061 show(rootOfRootWrapperList.getRoot()); 1062 else 1063 ; 1064 } 1065 1066 private void show(RBTreeNode root){ 1067 if (root.left != null) 1068 show(root.left); 1069 ( (RootWrapper) root.key).show(); 1070 if (root.right != null) 1071 show(root.right); 1072 } 1073 1074 protected int getNumberOfEntries(){ 1075 if(rootOfRootWrapperList.getRoot() != null) 1076 return getNumberOfEntriesInWrapper(rootOfRootWrapperList.getRoot(), 0); 1077 return 0; 1078 } 1079 1080 private int getNumberOfEntriesInWrapper(RBTreeNode root, int number){ 1081 1082 int numberOfEntries = getNumberOfEntries(((RootWrapper)root.key).getRoot(), 0); 1083 number += numberOfEntries; 1084 1085 int numberInLeft = 0; 1086 int numberInRight = 0; 1087 1088 1089 if(root.left != null) numberInLeft = getNumberOfEntriesInWrapper(root.left, number); 1090 if(root.right != null) numberInRight = getNumberOfEntriesInWrapper(root.right, number); 1091{} int toReturn = numberOfEntries + numberInLeft + numberInRight; 1093 return toReturn; 1094 } 1095 1096 1097 1104 1105 1115 1116 private int getNumberOfEntries(RBTreeNode root, int number){ 1117 number++; 1118 int numberInLeft = 0; 1119 int numberInRight = 0; 1120 1121 if(root.left != null) numberInLeft = getNumberOfEntries(root.left, number); 1122 if(root.right != null) numberInRight = getNumberOfEntries(root.right, number); 1123{} int toReturn = 1 + numberInLeft + numberInRight; 1125 return toReturn; 1126 } 1127 public Object getCeilKey(Object key){ 1128 RootWrapper rootWrapper = getRootWrapper(key); 1129 if(rootWrapper != null) 1130 return getCeilNode(rootWrapper, key).getKey(); 1131 rootWrapper = getCeilRootWrapper(key); 1132 if(rootWrapper == null) 1133 return null; 1134 return firstKey(rootWrapper); 1135 } 1136 1137 public Object getFloorKey(Object key){ 1138 RootWrapper rootWrapper = getRootWrapper(key); 1139 if(rootWrapper != null) 1140 getFloorNode(rootWrapper, key).getKey(); 1141 rootWrapper = getFloorRootWrapper(key); 1142 if(rootWrapper == null) 1143 return null; 1144 return lastKey(rootWrapper); 1145 } 1146 public RootWrapper joinTrees(RootWrapper rootWrapper1, Object obj, RootWrapper rootWrapper2){ 1147 if(rootWrapper1 == null || rootWrapper2 == null) 1148 throw new InternalError ("One or the RootWrapper is null"); 1149 1150 if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null){ 1151 put(rootWrapper2, obj); 1152 return rootWrapper2; 1153 } 1154 if(rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null){ 1155 put(rootWrapper1, obj); 1156 return rootWrapper1; 1157 } 1158 if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null){ 1159 put(rootWrapper1, obj); 1160 return rootWrapper1; 1161 } 1162 int blackHeight1 = rootWrapper1.getBlackHeight(); 1163 int blackHeight2 = rootWrapper2.getBlackHeight(); 1164 1165 if(blackHeight1 == blackHeight2){ 1166 RootWrapper result = new RootWrapper(); 1167 put(result, obj); 1168 RBTreeNode node = result.getRoot(); 1169 RBTreeNode root1 = rootWrapper1.getRoot(); 1170 RBTreeNode root2 = rootWrapper2.getRoot(); 1171 root1.parent = node; 1172 root2.parent = node; 1173 if(compareRootWrappers(rootWrapper1, rootWrapper2) < 0){ 1174 node.left = root1; 1175 node.right = root2; 1176 } 1177 else{ 1178 node.left = root2; 1179 node.right = root1; 1180 } 1181 return result; 1182 } 1183 if(blackHeight1 < blackHeight2){ 1184 RootWrapper temp = rootWrapper1; 1185 rootWrapper1 = rootWrapper2; 1186 rootWrapper2 = temp; 1187 } 1188 1189 int cmp = compareRootWrappers(rootWrapper1, rootWrapper2); 1190 RootWrapper result; 1191 if(cmp >= 0){ 1192 result = joinToLeft(rootWrapper1, rootWrapper2, obj); 1193 } 1194 else{ 1195 result = joinToRight(rootWrapper1, rootWrapper2, obj); 1196 } 1197 return result; 1198 } 1199 1200 protected int compareRootWrappers(RootWrapper p, RootWrapper q){ 1201 if(p == q){ 1202 return 0; 1203 } 1204 int result = compare(p.getRoot().getKey(), q.getRoot().getKey()); 1205 return result; 1206 } 1207 1208 private RootWrapper joinToLeft(RootWrapper mainRootWrapper, RootWrapper rootWrapper1, Object obj){ 1209 int blackHeight1 = rootWrapper1.getBlackHeight(); 1210 1211 int blackHeight2 = mainRootWrapper.getBlackHeight(); 1212 1213 if(blackHeight2 < blackHeight1) 1214 throw new InternalError ("blackHeight2 can't be less than blackHeight1 " + blackHeight1 + " , " + blackHeight2); 1215 if(blackHeight1 == 0){ 1216 put(mainRootWrapper, obj); 1217 return mainRootWrapper; 1218 } 1219 RBTreeNode node = mainRootWrapper.getRoot(); 1220 while(node != null){ 1221 if((getBlackHeight(node) == blackHeight1) && node.getColor()) 1222 break; 1223 node = node.left; 1224 } 1225 if(node == null){ 1226 throw new InternalError ("node can't be null."); 1227 } 1228 RBTreeNode parentNode = node.parent; 1229 RBTreeNode root1 = rootWrapper1.root; 1230 RBTreeNode subTreeRoot = (RBTreeNode)createRBTreeNode(obj, null); 1231 1232 1233 subTreeRoot.left = root1; 1234 root1.parent = subTreeRoot; 1235 1236 subTreeRoot.right = node; 1237 node.parent = subTreeRoot; 1238 1239 if(parentNode == null){ 1240 RootWrapper subTree = new RootWrapper(subTreeRoot); 1241 return subTree; 1242 } 1243 parentNode.left = subTreeRoot; 1244 subTreeRoot.parent = parentNode; 1245 1246 invokeFixAfterInsertion(mainRootWrapper, subTreeRoot); 1247 return mainRootWrapper; 1248 } 1249 1250 private RootWrapper joinToRight(RootWrapper mainRootWrapper, RootWrapper rootWrapper2, Object obj){ 1251 1252 int blackHeight1 = mainRootWrapper.getBlackHeight(); 1253 int blackHeight2 = getBlackHeight(rootWrapper2.getRoot()); 1254 1255 if(blackHeight1 < blackHeight2) 1256 throw new InternalError ("blackHeight1 can't be less than blackHeight2 " + blackHeight1 + " , " + blackHeight2); 1257 if(blackHeight2 == 0){ 1258 put(mainRootWrapper, obj); 1259 return mainRootWrapper; 1260 } 1261 1262 RBTreeNode node = (RBTreeNode)mainRootWrapper.getRoot(); 1263 while(node != null){ 1264 if((getBlackHeight(node) == blackHeight2) && node.getColor()) 1265 break; 1266 node = node.right; 1267 } 1268 if(node == null){ 1269 throw new InternalError ("node can't be null."); 1270 } 1271 RBTreeNode parentNode = node.getParent(); 1272 RBTreeNode root2 = rootWrapper2.getRoot(); 1273 RBTreeNode subTreeRoot = createRBTreeNode(obj, null); 1274 subTreeRoot.right = root2; 1275 root2.parent = subTreeRoot; 1276 1277 subTreeRoot.left = node; 1278 node.parent = subTreeRoot; 1279 1280 if(parentNode == null){ 1281 RootWrapper subTree = new RootWrapper(subTreeRoot); 1282 return subTree; 1283 } 1284 subTreeRoot.parent = parentNode; 1285 parentNode.right = subTreeRoot; 1286 1287 invokeFixAfterInsertion(mainRootWrapper, subTreeRoot); 1288 return mainRootWrapper; 1289 } 1290 1291 protected int getBlackHeight(RBTreeNode p){ 1292 int height = 0; 1293 if(p == null) 1294 throw new InternalError ("can't get blackHeight of null."); 1295 if (p != null) 1296 while (p != null){ 1297 if(p.color) height++; 1298 p = p.right; 1299 } 1300 return height; 1301 } 1302 1303 protected boolean isOnlyNode(RootWrapper rootWrapper){ 1304 RBTreeNode root = rootWrapper.getRoot(); 1305 return (root.getLeft() == null && root.getRight() == null); 1306 } 1307 1308 protected boolean mightBeDeleted(RBTreeNode node){ 1309 return (node.getLeft() == null && node.getParent() == null && node.getRight() == null); 1310 } 1311 protected void makeLinksNull(RBTreeNode node){ 1312 node.parent = null; 1313 node.left = null; 1314 node.right = null; 1315 } 1316 1317 private RootWrapper joinTrees(RootWrapper rootWrapper1, RootWrapper rootWrapper2){ 1318 if(rootWrapper1 == null || rootWrapper2 == null) 1319 throw new InternalError ("One or the rootWrapper is null"); 1320 if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null){ 1321 return rootWrapper2; 1322 } 1323 if(rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null){ 1324 return rootWrapper1; 1325 } 1326 if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null){ 1327 return null; 1328 } 1329 if(rootWrapper1.getRoot().getLeft() == null && rootWrapper1.getRoot().getRight() == null){ 1330 put(rootWrapper2, rootWrapper1.getRoot().getKey()); 1331 return rootWrapper2; 1332 } 1333 if(rootWrapper2.getRoot().getLeft() == null && rootWrapper2.getRoot().getRight() == null){ 1334 put(rootWrapper1, rootWrapper2.getRoot().getKey()); 1335 return rootWrapper1; 1336 } 1337 int cmp = compareRootWrappers(rootWrapper1, rootWrapper2); 1338 if(cmp > 0){ 1339 RootWrapper temp = rootWrapper1; 1340 rootWrapper1 = rootWrapper2; 1341 rootWrapper2 = temp; 1342 } 1343 1344 Object obj = firstKey(rootWrapper2); 1345 Object oldRootKey = rootWrapper2.getRoot().getKey(); 1346 if(obj == oldRootKey){ 1347 1348 RBTreeNode rightNode = rootWrapper2.getRoot().getRight(); 1349 if(rightNode != null){ 1350 Object rightNodeKey = rightNode.getKey(); 1351 put(rootWrapper1, obj); 1352 makeLinksNull(rightNode); 1353 put(rootWrapper1, rightNodeKey); 1354 return rootWrapper1; 1355 } 1356 } 1357 1358 remove(rootWrapper2, obj); 1359 1360 if(rootWrapper2.getRoot() == null){ 1361 put(rootWrapper1, obj); 1362 return rootWrapper1; 1363 } 1364 else{ 1365 RootWrapper joinedTree = joinTrees(rootWrapper1, obj, rootWrapper2); 1366 return joinedTree; 1367 } 1368 } 1369} 1370 1371 1372 1449 1450 1451 1452 | Popular Tags |