1 16 17 18 package com.daffodilwoods.rbtreesizesequence; 19 20 import com.daffodilwoods.rbtreesizesequence.utils.sizesequenceutility. 21 RBTreeSizeSequenceUtility; 22 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree; 23 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.RBTreeNode; 24 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.RootWrapper; 25 import java.util.*; 26 27 public class RBTreeSizeSequence 28 extends RBTreeSimple 29 implements SizeSequenceInterface { 30 private Vector distanceListenerVector; 31 32 private Vector invalidRanges; 33 34 public RBTreeSizeSequence(RBTreeSizeSequenceUser treeSizeSequenceUser1, 35 int maxOffst) { 36 super(treeSizeSequenceUser1, maxOffst); 37 } 38 39 public RBTreeSizeSequenceUser getRBTreeSizeSequenceUser() { 40 return treeSizeSequenceUser; 41 } 42 43 public synchronized void removeDistanceListener(DistanceAdapter adp) { 44 if (distanceListenerVector == null) { 45 throw new InternalError ( 46 "why are you removing distanceListener when you have not added one ?"); 47 } 48 adp.setDistanceStatus(Integer.MIN_VALUE); 49 distanceListenerVector.remove(adp); 50 } 51 52 public synchronized void addDistanceListener(DistanceAdapter adp) { 53 if (adp.getDistanceStatus() != Integer.MIN_VALUE) { 54 ; 55 throw new IllegalArgumentException ("adapter's distanceStatus can't be " + 56 adp.getDistanceStatus()); 57 } 58 Object locationId1 = adp.getLocationId1(); 59 Object locationId2 = adp.getLocationId2(); 60 if (distanceListenerVector == null) 61 distanceListenerVector = new Vector(); 62 if (!distanceListenerVector.contains(adp)) { 63 distanceListenerVector.add(adp); 64 } 65 int vrb = getDistance(locationId1, locationId2, true); 66 adp.setDistanceStatus(vrb); 67 if (vrb == Integer.MIN_VALUE) { 68 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_UNKNOWN, 69 Integer.MIN_VALUE, this)); 70 } 71 else { 72 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_KNOWN, vrb, this)); 73 } 74 } 75 76 private void checkFireEvent() { 77 int i; 78 if (distanceListenerVector != null) { 79 int size = distanceListenerVector.size(); 80 for (i = 0; i < size; i++) { 81 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 82 if (adp.getDistanceStatus() != Integer.MIN_VALUE) { 83 continue; 84 } 85 Object locationId1 = adp.getLocationId1(); 86 Object locationId2 = adp.getLocationId2(); 87 int dst = getDistance(locationId1, locationId2, false); 88 if (dst != Integer.MIN_VALUE && dst != adp.getDistanceStatus()) { 89 adp.setDistanceStatus(dst); 90 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_KNOWN, 91 dst, this)); 92 } 93 } 94 } 95 } 96 97 private void fireEventDistanceChanged(Object locationId1, Object locationId2, 98 int change) { 99 int size = distanceListenerVector.size(); 100 for (int i = 0; i < size; i++) { 101 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 102 if (isBetween(adp.getLocationId1(), adp.getLocationId2(), locationId1, false)) { 103 adp.setDistanceStatus(DistanceEvent.DISTANCE_UNKNOWN); 104 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_CHANGED, 105 Integer.MIN_VALUE, this)); 106 } 107 else if (isBetween(adp.getLocationId1(), adp.getLocationId2(), 108 locationId1, false) && 109 isBetween(adp.getLocationId1(), adp.getLocationId2(), 110 locationId2, false)) { 111 adp.setDistanceStatus(DistanceEvent.DISTANCE_CHANGED); 112 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_CHANGED, 113 change, this)); 114 } 115 } 116 } 117 118 private void fireEventDistanceKnown(Object locationId1, Object locationId2, 119 int change) { 120 int size = distanceListenerVector.size(); 121 for (int i = 0; i < size; i++) { 122 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 123 } 124 } 125 126 private void fireEventDistanceUnknown(Object locationId1, Object locationId2, 127 int change) { 128 int size = distanceListenerVector.size(); 129 for (int i = 0; i < size; i++) { 130 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 131 } 132 } 133 134 private void fireDistanceEvent() { 135 if (distanceListenerVector == null) 136 return; 137 int size = distanceListenerVector.size(); 138 for (int i = 0; i < size; i++) { 139 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 140 Object adpLocationId1 = adp.getLocationId1(); 141 Object adpLocationId2 = adp.getLocationId2(); 142 int distance = getDistance(adpLocationId1, adpLocationId2, false); 143 int adpDistanceStatus = adp.getDistanceStatus(); 144 adp.setDistanceStatus(distance); 145 if (adpDistanceStatus == Integer.MIN_VALUE) { 146 if (distance != Integer.MIN_VALUE) { 147 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_KNOWN, 148 distance, this)); 149 } 150 } 151 else { 152 if (distance == Integer.MIN_VALUE) { 153 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_UNKNOWN, 154 distance, this)); 155 } 156 else if (adpDistanceStatus != distance) { 157 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_CHANGED, 158 distance - adpDistanceStatus, this)); 159 } 160 } 161 } 162 } 163 164 private void fireDistanceEventOld(Object locationId1, Object locationId2, 165 int change, int type) { 166 int i; 167 if (distanceListenerVector != null) { 168 int size = distanceListenerVector.size(); 169 for (i = 0; i < size; i++) { 170 DistanceAdapter adp = (DistanceAdapter) distanceListenerVector.get(i); 171 175 if (type == DistanceEvent.DISTANCE_UNKNOWN) { 176 if (isBetween(adp.getLocationId1(), adp.getLocationId1(), locationId1, false)) { 177 adp.setDistanceStatus(DistanceEvent.DISTANCE_UNKNOWN); 178 adp.distanceNotify(new DistanceEvent(type, Integer.MIN_VALUE, this)); 179 } 180 } 181 else if (isBetween(adp.getLocationId1(), adp.getLocationId2(), 182 locationId1, false) && 183 isBetween(adp.getLocationId1(), adp.getLocationId2(), 184 locationId2, false)) { 185 adp.setDistanceStatus(DistanceEvent.DISTANCE_CHANGED); 186 adp.distanceNotify(new DistanceEvent(DistanceEvent.DISTANCE_CHANGED, 187 change, this)); 188 } 189 } 190 } 191 } 192 193 public RBTreeNode createRBTreeNode(Object key, RBTreeNode parent) { 194 return new Entry(key, (Entry) parent, 0); 195 } 196 197 private void preSwapPosition(RBTreeNode p, RBTreeNode q) { 198 Entry x = (Entry) p; 199 Entry y = (Entry) q; 200 int dst = getDistance(y, x); 201 int previousDstX = x.distanceFromParent; 202 x.distanceFromParent = y.distanceFromParent + dst; 203 y.distanceFromParent = previousDstX - dst; 204 ( (Entry) (y.getLeft())).distanceFromParent -= dst; 205 ( (Entry) (y.getRight())).distanceFromParent -= dst; 206 if (x.getRight() != null) 207 ( (Entry) x.getRight()).distanceFromParent += dst; 208 } 209 210 protected void postSwapPosition(RootWrapper rootWrapper, RBTreeNode x, 211 RBTreeNode y) { 212 if (rootWrapper.getRoot() == x) { 213 ( (Entry) y).distanceFromParent = 0; 214 } 215 else if (rootWrapper.getRoot() == y) { 216 ( (Entry) x).distanceFromParent = 0; 217 } 218 } 219 220 public int getDistance(Object locationIdFrom, Object locationIdTo) { 221 int result = getDistance(locationIdFrom, locationIdTo, false); 222 return result; 223 } 224 225 public int getDistance(Object locationIdFrom, Object locationIdTo, 226 boolean force) { 227 if (locationIdFrom == null || locationIdTo == null) { 228 ; 229 throw new IllegalArgumentException ( 230 "<<<<can't pass null to getDistance>>>>>>"); 231 } 232 int cmp = compare(locationIdFrom, locationIdTo); 233 if (cmp == 0) { 234 return 0; 235 } 236 int direction = 1; 237 if (cmp > 0) { 238 Object temp = locationIdFrom; 239 locationIdFrom = locationIdTo; 240 locationIdTo = temp; 241 direction = -1; 242 } 243 244 RootWrapper rootWrapperFrom = getCeilRootWrapper(locationIdFrom); 245 RootWrapper rootWrapperTo = getFloorRootWrapper(locationIdTo); 246 247 if (rootWrapperFrom == null || rootWrapperTo == null || 248 compareRootWrappers(rootWrapperFrom, rootWrapperTo) > 0) { 249 if (force || 250 (treeSizeSequenceUser != null && 251 treeSizeSequenceUser.canJoin(locationIdFrom, locationIdTo))) { 252 int result = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 253 traceDistance(locationIdFrom, locationIdTo, Integer.MAX_VALUE)); 254 return (result * direction); 255 } 256 else { 257 return Integer.MIN_VALUE; 258 } 259 } 260 261 if (rootWrapperFrom == rootWrapperTo) { 262 if (!force) { 263 if (! ( (canContain(rootWrapperFrom, locationIdFrom) || 264 treeSizeSequenceUser.canJoin(locationIdFrom, 265 firstKey(rootWrapperFrom))) 266 && 267 (canContain(rootWrapperFrom, locationIdTo) || 268 treeSizeSequenceUser.canJoin(locationIdTo, 269 lastKey(rootWrapperFrom))))) { 270 return Integer.MIN_VALUE; 271 } 272 } 273 boolean canContainLocationIdFrom = canContain(rootWrapperFrom, 274 locationIdFrom); 275 boolean canContainLocationIdTo = canContain(rootWrapperFrom, locationIdTo); 276 277 if (canContainLocationIdFrom && canContainLocationIdTo) { 278 return getDistance(rootWrapperFrom, locationIdFrom, locationIdTo, force) * 279 direction; 280 } 281 if (!force) 282 return Integer.MIN_VALUE; 283 284 Object from = locationIdFrom; 285 Object to = locationIdTo; 286 boolean fromChanged = false; 287 boolean toChanged = false; 288 289 if (!canContainLocationIdFrom) { 290 from = firstKey(rootWrapperFrom); 291 fromChanged = true; 292 } 293 if (!canContainLocationIdTo) { 294 to = lastKey(rootWrapperFrom); 295 toChanged = true; 296 } 297 298 int result = getDistance(rootWrapperFrom, from, to, force); 299 300 if (fromChanged) { 301 result += 302 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 303 traceDistance(locationIdFrom, 304 from, Integer.MAX_VALUE)); 305 } 306 if (toChanged) { 307 result += 308 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 309 traceDistance(to, 310 locationIdTo, Integer.MAX_VALUE)); 311 } 312 313 return (result * direction); 314 } 315 if (!force) { 316 return Integer.MIN_VALUE; 317 } 318 319 int result = 0; 320 RootWrapper nextRootWrapper = getNextRootWrapper(rootWrapperFrom); 321 while (nextRootWrapper != null && nextRootWrapper != rootWrapperTo) { 322 int rootWrapperSize = getRootWrapperSize(nextRootWrapper); 323 result += rootWrapperSize; 324 nextRootWrapper = getNextRootWrapper(nextRootWrapper); 325 } 326 boolean precedesRootWrapperFrom = false, succeedsRootWrapperTo = false; 327 if (compare(firstKey(rootWrapperFrom), locationIdFrom) <= 0) { Object lk = lastKey(rootWrapperFrom); 329 int d = getDistance(rootWrapperFrom, locationIdFrom, lk, force); 330 result += d; 331 } 332 else { 333 int rootWrapperSize = getRootWrapperSize(rootWrapperFrom); 334 result += rootWrapperSize; 335 precedesRootWrapperFrom = true; 336 } 337 if (compare(lastKey(rootWrapperTo), locationIdTo) >= 0) { Object fk = firstKey(rootWrapperTo); 339 int d = getDistance(rootWrapperTo, fk, locationIdTo, force); 340 result += d; 341 } 342 else { 343 int rootWrapperSize = getRootWrapperSize(rootWrapperTo); 344 result += rootWrapperSize; 345 succeedsRootWrapperTo = true; 346 } 347 348 349 Object firstKeyRootWrapperFrom = firstKey(rootWrapperFrom); 350 Object lastKeyRootWrapperTo = lastKey(rootWrapperTo); 351 if (precedesRootWrapperFrom) { 352 int fromTrace = RBTreeSizeSequenceUtility.getFirstInt( 353 treeSizeSequenceUser.traceDistance(locationIdFrom, 354 firstKeyRootWrapperFrom, 355 Integer.MAX_VALUE)); 356 result += fromTrace; 357 } 358 359 rootWrapperFrom = getRootWrapper(firstKeyRootWrapperFrom); 360 nextRootWrapper = getNextRootWrapper(rootWrapperFrom); 361 362 while (nextRootWrapper != null && nextRootWrapper != rootWrapperTo) { 363 Object nextRootWrapperFirst = firstKey(nextRootWrapper); 364 Object lk = lastKey(rootWrapperFrom); 365 int fromTrace = RBTreeSizeSequenceUtility.getFirstInt( 366 treeSizeSequenceUser.traceDistance(lk, nextRootWrapperFirst, 367 Integer.MAX_VALUE)); 368 result += fromTrace; 369 rootWrapperFrom = getRootWrapper(nextRootWrapperFirst); 370 nextRootWrapper = getNextRootWrapper(rootWrapperFrom); 371 } 372 373 Object firstKey = firstKey(nextRootWrapper); 374 Object lastKey = lastKey(rootWrapperFrom); 375 376 int fromTraceDistance = RBTreeSizeSequenceUtility.getFirstInt( 377 treeSizeSequenceUser.traceDistance(lastKey, firstKey, Integer.MAX_VALUE)); 378 result += fromTraceDistance; 379 if (succeedsRootWrapperTo) { 380 int fromTrace = RBTreeSizeSequenceUtility.getFirstInt( 381 treeSizeSequenceUser.traceDistance(lastKeyRootWrapperTo, locationIdTo, 382 Integer.MAX_VALUE)); 383 result += fromTrace; 384 } 385 386 return (result * direction); 387 } 388 389 private int getDistance(RootWrapper rootWrapper, Object locationIdFrom, 390 Object locationIdTo) { 391 return getDistance(rootWrapper, locationIdFrom, locationIdTo, false); 392 } 393 394 private int getDistance(RootWrapper rootWrapper, Object locationIdFrom, 395 Object locationIdTo, boolean force) { 396 int direction = 1; 397 int cmp = compare(locationIdFrom, locationIdTo); 398 399 if (cmp == 0) { return 0; 401 } 402 if (cmp > 0) { direction = -1; 404 Object temp = locationIdFrom; 405 locationIdFrom = locationIdTo; 406 locationIdTo = temp; 407 } 408 Entry ceilNode = (Entry) getCeilNode(rootWrapper, locationIdFrom); 409 Entry floorNode = (Entry) getFloorNode(rootWrapper, locationIdTo); 410 411 412 int cmp1 = compare(ceilNode.getKey(), floorNode.getKey()); 413 414 if (cmp1 > 0) { 415 ceilNode = (Entry) getFloorNode(rootWrapper, locationIdFrom); 416 floorNode = (Entry) getCeilNode(rootWrapper, locationIdTo); 417 int result = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 418 traceDistance(locationIdFrom, locationIdTo, Integer.MAX_VALUE)); 419 return result; 420 } 421 422 Object commonAncestor = getCommonAncestor(rootWrapper, ceilNode.getKey(), 423 floorNode.getKey()); 424 int result = -getDistanceFromAncestor(rootWrapper, commonAncestor, 425 ceilNode.getKey()) + 426 getDistanceFromAncestor(rootWrapper, commonAncestor, floorNode.getKey()); 427 if (compare(locationIdFrom, ceilNode.getKey()) != 0) { 428 int r = treeSizeSequenceUser.getDistance(locationIdFrom, ceilNode.getKey()); 429 if (r != Integer.MIN_VALUE) { 430 result += r; 431 } 432 else { 433 if (force || 434 (treeSizeSequenceUser != null && 435 treeSizeSequenceUser.canJoin(locationIdFrom, ceilNode.getKey()))) { 436 result += 437 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 438 traceDistance(locationIdFrom, ceilNode.getKey(), 439 Integer.MAX_VALUE)); 440 } 441 else { 442 ; 443 ceilNode = (Entry) getCeilNode(rootWrapper, locationIdFrom); 444 int c = compare(locationIdFrom, ceilNode.getKey()); 445 show(); 446 Thread.dumpStack(); 447 result += 448 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 449 traceDistance(locationIdFrom, ceilNode.getKey(), 450 Integer.MAX_VALUE)); 451 } 452 } 453 } 454 if (compare(floorNode.getKey(), locationIdTo) != 0) { 455 int r = treeSizeSequenceUser.getDistance(floorNode.getKey(), locationIdTo); 456 if (r != Integer.MIN_VALUE) { 457 result += r; 458 } 459 else { 460 if (force || 461 (treeSizeSequenceUser != null && 462 treeSizeSequenceUser.canJoin(floorNode.getKey(), locationIdTo))) { 463 result += 464 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 465 traceDistance(floorNode.getKey(), locationIdTo, Integer.MAX_VALUE)); 466 } 467 else { 468 ; 469 show(); 470 Thread.dumpStack(); 471 result += 472 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 473 traceDistance(floorNode.getKey(), locationIdTo, Integer.MAX_VALUE)); 474 } 475 } 476 } 477 return (result * direction); 478 } 479 480 private int getRootWrapperSize(RootWrapper rootWrapper) { 481 int result = -getDistanceFromAncestor(rootWrapper, 482 getKey(rootWrapper.getRoot()), 483 firstKey(rootWrapper)) + 484 getDistanceFromAncestor(rootWrapper, getKey(rootWrapper.getRoot()), 485 lastKey(rootWrapper)); 486 return result; 487 } 488 489 private int getDistanceFromAncestor(RootWrapper rootWrapper, 490 Object rootLocationId, Object locationId) { 491 int result = 0; 492 Entry start = (Entry) getNode(rootWrapper, locationId); 493 while (! (start.key).equals(rootLocationId)) { 494 result += start.getDistanceFromParent(); 495 start = (Entry) start.getParent(); 496 } 497 return result; 498 } 499 500 private void put(RootWrapper rootWrapper, Object locationIdFrom, int distance, 501 Object key) { 502 if (key == null) 503 throw new IllegalArgumentException ( 504 "<<<< key to put shouldn't be null >>>>>>>>>>>>>>>>>"); 505 if (locationIdFrom != null && compare(locationIdFrom, key) == 0) 506 return; 507 Entry x = (Entry) putWithoutFix(rootWrapper, key); 508 if (x != null && x.getParent() != null) { 509 int distanceFromParent = distance - 510 getDistance(rootWrapper, locationIdFrom, x.getParent().getKey()); 511 x.distanceFromParent = distanceFromParent; 512 invokeFixAfterInsertion(rootWrapper, x); 513 ( (Entry) rootWrapper.root).distanceFromParent = 0; 514 } 515 } 516 517 public void set(Object locationId, int distance) { 518 RootWrapper rootWrapper = getRootWrapper(locationId); 519 if (rootWrapper != null) { 520 ( (Entry) getNode(rootWrapper, locationId)).setDistancFromParent(distance); 521 } 522 else { 523 throw new IllegalArgumentException ("LocationId does not exist in RBTree"); 524 } 525 } 526 527 public int get(Object locationId) { 528 RootWrapper rootWrapper = getRootWrapper(locationId); 529 if (rootWrapper != null) { 530 return ( (Entry) getNode(rootWrapper, locationId)).getDistanceFromParent(); 531 } 532 throw new IllegalArgumentException ("LocationId does not exist in RBTree"); 533 } 534 535 public int getDistanceFromTop(Object locationId) { 536 RootWrapper rootWrapper = getRootWrapper(locationId); 537 if (rootWrapper != null) { 538 return getDistance( ( (Entry) getTopKey()).getKey(), 539 getNode(rootWrapper, locationId).getKey()); 540 } 541 throw new IllegalArgumentException ("LocationId does not exist in RBTree"); 542 } 543 544 public Object getKeyAtDistanceFromTop(int atDistance) { 545 return getKeyAtDistance( ( (Entry) getTopKey()).getKey(), atDistance); 546 } 547 548 public void add(Object locationId, int atDistance) { 549 RootWrapper rootWrapper = getFloorRootWrapper(locationId); 550 if (rootWrapper != null) { 551 add(rootWrapper.getRoot().getKey(), atDistance, locationId); 552 } 553 else { 554 rootWrapper = getCeilRootWrapper(locationId); 555 if (rootWrapper != null) { 556 add(rootWrapper.getRoot().getKey(), -atDistance, locationId); 557 } 558 else { 559 add(null, atDistance, locationId); 560 } 561 } 562 } 563 564 public void add(Object locationIdFrom, int atDistance, Object locationId) { 565 try { 566 if (!addAllowed) { 567 return; 568 } 569 if (locationId == null) 570 throw new IllegalArgumentException ( 571 "<<<<<<< locationId to be added shouldn't be null >>>>>>>>"); 572 if (locationIdFrom == null) { 573 RootWrapper rootWrapper = new RootWrapper(); 574 put(rootWrapper, null, 0, locationId); 575 addRootWrapperToList(rootWrapper); 576 checkForJoinTrees(rootWrapper, locationId); 577 return; 578 } 579 int c = compare(locationIdFrom, locationId); 580 if (c == 0) { 581 if (atDistance == 0)return; 582 throw new IllegalArgumentException ("Can't add " + locationId + 583 " at distance " + atDistance + 584 " from " + locationIdFrom); 585 } 586 587 592 593 RootWrapper rootWrapper = getRootWrapper(locationIdFrom); 594 if (rootWrapper == null) { 595 rootWrapper = new RootWrapper(); 596 put(rootWrapper, null, 0, locationIdFrom); 597 if (atDistance >= maxOffst) 598 put(rootWrapper, locationIdFrom, atDistance, locationId); 599 addRootWrapperToList(rootWrapper); 600 601 603 604 checkForJoinTrees(rootWrapper, locationId); 605 return; 606 } 607 Entry node = (Entry) getCeilNode(rootWrapper, locationIdFrom); 608 if (node == null) { 609 node = (Entry) getFloorNode(rootWrapper, locationIdFrom); 610 if (node == null) 611 throw new InternalError ("P R O B L E M H E R E"); 612 } 613 boolean addPrev = addAllowed; 614 addAllowed = false; 615 atDistance -= getDistance(rootWrapper, locationIdFrom, node.getKey(), true); 616 addAllowed = addPrev; 617 locationIdFrom = node.getKey(); 618 619 if (canContain(rootWrapper, locationId)) { 620 boolean alPrev = addAllowed; 621 addAllowed = false; 622 if (canAdd(rootWrapper, locationId, maxOffst)) 623 put(rootWrapper, locationIdFrom, atDistance, locationId); 624 addAllowed = alPrev; 625 return; 626 } 627 Object keyToRemove; 628 if (atDistance > 0) 629 keyToRemove = lastKey(rootWrapper); 630 else 631 keyToRemove = firstKey(rootWrapper); 632 put(rootWrapper, locationIdFrom, atDistance, locationId); 633 int dst = getDistance(rootWrapper, keyToRemove, locationId); 634 if (Math.abs(dst) < maxOffst) 635 remove(rootWrapper, keyToRemove); 636 637 checkForJoinTrees(rootWrapper, locationId); 638 639 } 640 finally { 641 checkFireEvent(); 642 } 643 } 644 645 private boolean checkForJoinTrees(RootWrapper rootWrapper, Object locationId) { 646 addAllowed = false; 647 648 if (isAtEnd(rootWrapper, locationId)) { 649 RootWrapper rootWrapperNext = getNextRootWrapper(rootWrapper); 650 if (rootWrapperNext == null) { 651 addAllowed = true; 652 return false; 653 } 654 Object firstKeyRootWrapperNext = firstKey(rootWrapperNext); 655 if (treeSizeSequenceUser.canJoin(locationId, firstKeyRootWrapperNext)) { 656 657 Object rootKeyOfRootWrapper = rootWrapper.getRoot().getKey(); 658 int distanceFromRootToLocationIdInRootWrapper = getDistance(rootWrapper, 659 rootKeyOfRootWrapper, locationId); 660 int distanceFromFirstKeyToRootInRootWrapperNext = getDistance( 661 rootWrapperNext, firstKeyRootWrapperNext, 662 rootWrapperNext.getRoot().getKey()); 663 int distanceBetweenRoots = distanceFromRootToLocationIdInRootWrapper + 664 distanceFromFirstKeyToRootInRootWrapperNext; 665 if (compare(locationId, firstKeyRootWrapperNext) != 0) { 666 distanceBetweenRoots += 667 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 668 traceDistance(locationId, firstKeyRootWrapperNext, 669 Integer.MAX_VALUE)); 670 } 671 672 673 if (locationId == rootKeyOfRootWrapper) { 674 RBTreeNode leftNode = rootWrapper.getRoot().getLeft(); 675 if (leftNode != null) { 676 Object leftNodeKey = leftNode.getKey(); 677 int disFromLeftNodeKeyToLocationId = - ( (Entry) leftNode). 678 getDistanceFromParent(); 679 int distanceBetweenLeftNodeKeyToRootOfRoorWrapperNext = 680 distanceBetweenRoots + disFromLeftNodeKeyToLocationId; 681 makeLinksNull(leftNode); 682 put(rootWrapperNext, rootWrapperNext.getRoot().getKey(), 683 -distanceBetweenLeftNodeKeyToRootOfRoorWrapperNext, leftNodeKey); 684 removeFromRootWrapperList(rootWrapper); 685 return true; 686 } 687 } 688 689 remove(rootWrapper, locationId); 690 691 Object newRootKeyOfRootWrapper = rootWrapper.getRoot().getKey(); 692 if (newRootKeyOfRootWrapper == null) { 693 removeFromRootWrapperList(rootWrapper); 694 return true; 695 } 696 697 if (compare(rootKeyOfRootWrapper, newRootKeyOfRootWrapper) != 0) { 698 int distanceBetweenNewAndOldRoot = getDistance(rootWrapper, 699 newRootKeyOfRootWrapper, rootKeyOfRootWrapper); 700 distanceBetweenRoots += distanceBetweenNewAndOldRoot; 701 } 702 703 704 RootWrapper joinedTree = joinTrees(rootWrapper, distanceBetweenRoots, 705 rootWrapperNext); 706 707 removeFromRootWrapperList(rootWrapper); 708 removeFromRootWrapperList(rootWrapperNext); 709 710 addRootWrapperToList(joinedTree); 711 712 addAllowed = true; 713 return true; 714 } 715 addAllowed = true; 716 return false; 717 } 718 else if (isAtStart(rootWrapper, locationId)) { 719 RootWrapper rootWrapperPrevious = getPreviousRootWrapper(rootWrapper); 720 if (rootWrapperPrevious == null) { 721 addAllowed = true; 722 return false; 723 } 724 Object lastKeyRootWrapperPrevious = lastKey(rootWrapperPrevious); 725 if (treeSizeSequenceUser.canJoin(lastKeyRootWrapperPrevious, locationId)) { 726 727 Object rootKeyPreviousRootWrapper = rootWrapperPrevious.getRoot(). 728 getKey(); 729 int distanceFromRootToLastKeyInRootWrapperPrevious = getDistance( 730 rootWrapperPrevious, rootKeyPreviousRootWrapper, 731 lastKeyRootWrapperPrevious); 732 int distanceFromLocationIdToRootInRootWrapper = getDistance(rootWrapper, 733 locationId, rootWrapper.getRoot().getKey()); 734 int distanceBetweenRoots = 735 distanceFromRootToLastKeyInRootWrapperPrevious + 736 distanceFromLocationIdToRootInRootWrapper; 737 738 if (compare(lastKeyRootWrapperPrevious, locationId) != 0) 739 distanceBetweenRoots += 740 RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 741 traceDistance(lastKeyRootWrapperPrevious, locationId, 742 Integer.MAX_VALUE)); 743 744 745 746 if (lastKeyRootWrapperPrevious == rootKeyPreviousRootWrapper) { 747 RBTreeNode leftNode = rootWrapperPrevious.getRoot().getLeft(); 748 if (leftNode != null) { 749 Object leftNodeKey = leftNode.getKey(); 750 int disFromLeftNodeKeyToLastKeyRootWrapperPrevious = - ( (Entry) 751 leftNode).getDistanceFromParent(); 752 int distanceBetweenLeftNodeKeyToRootOfRoorWrapper = 753 distanceBetweenRoots + 754 disFromLeftNodeKeyToLastKeyRootWrapperPrevious; 755 makeLinksNull(leftNode); 756 put(rootWrapper, rootWrapper.getRoot().getKey(), 757 -distanceBetweenLeftNodeKeyToRootOfRoorWrapper, leftNodeKey); 758 removeFromRootWrapperList(rootWrapperPrevious); 759 return true; 760 } 761 } 762 763 remove(rootWrapperPrevious, lastKeyRootWrapperPrevious); 764 765 Object newRootKeyOfRootWrapperPrevious = rootWrapperPrevious.getRoot(). 766 getKey(); 767 if (newRootKeyOfRootWrapperPrevious == null) { 768 removeFromRootWrapperList(rootWrapperPrevious); 769 return true; 770 } 771 772 if (compare(rootKeyPreviousRootWrapper, newRootKeyOfRootWrapperPrevious) != 773 0) { 774 int distanceBetweenNewAndOldRoot = getDistance(rootWrapperPrevious, 775 newRootKeyOfRootWrapperPrevious, rootKeyPreviousRootWrapper); 776 distanceBetweenRoots += distanceBetweenNewAndOldRoot; 777 } 778 779 780 RootWrapper joinedTree = joinTrees(rootWrapperPrevious, 781 distanceBetweenRoots, rootWrapper); 782 783 removeFromRootWrapperList(rootWrapper); 784 removeFromRootWrapperList(rootWrapperPrevious); 785 addRootWrapperToList(joinedTree); 786 addAllowed = true; 787 return true; 788 } 789 addAllowed = true; 790 return false; 791 } 792 addAllowed = true; 793 return false; 794 } 795 796 private boolean checkForJoinTreesOld(RootWrapper rootWrapper, 797 Object locationId) { 798 addAllowed = false; 799 if (isAtEnd(rootWrapper, locationId)) { 800 RootWrapper rootWrapperNext = getNextRootWrapper(rootWrapper); 801 if (rootWrapperNext == null) { 802 addAllowed = true; 803 return false; 804 } 805 if (treeSizeSequenceUser.canJoin(locationId, firstKey(rootWrapperNext))) { 806 boolean bln2 = remove(rootWrapperNext, firstKey(rootWrapperNext)); 807 if (!bln2) { 808 addAllowed = true; 809 return false; 810 } 811 boolean bln1 = remove(rootWrapper, locationId); 812 if (!bln1) { 813 addAllowed = true; 814 return false; 815 } 816 boolean addAlPrev = addAllowed; 817 addAllowed = false; 818 int distance1 = getDistance( (rootWrapper.getRoot().getKey()), 819 locationId, true); int distance2 = getDistance( (rootWrapperNext.getRoot().getKey()), 821 locationId, true); addAllowed = addAlPrev; 823 824 825 RootWrapper joinedTree = joinTrees(rootWrapper, distance1, locationId, 826 rootWrapperNext, distance2); 827 828 removeFromRootWrapperList(rootWrapper); 829 removeFromRootWrapperList(rootWrapperNext); 830 831 addRootWrapperToList(joinedTree); 832 833 addAllowed = true; 834 return true; 835 } 836 addAllowed = true; 837 return false; 838 } 839 else if (isAtStart(rootWrapper, locationId)) { 840 RootWrapper rootWrapperPrevious = getPreviousRootWrapper(rootWrapper); 841 if (rootWrapperPrevious == null) { 842 addAllowed = true; 843 return false; 844 } 845 if (treeSizeSequenceUser.canJoin(locationId, lastKey(rootWrapperPrevious))) { 846 boolean bln2 = remove(rootWrapperPrevious, lastKey(rootWrapperPrevious)); 847 if (!bln2) { 848 addAllowed = true; 849 return false; 850 } 851 boolean bln1 = remove(rootWrapper, locationId); 852 if (!bln1) { 853 addAllowed = true; 854 return false; 855 } 856 int distance1 = getDistance( (rootWrapper.getRoot().getKey()), 857 locationId, true); 858 int distance2 = getDistance( (rootWrapperPrevious.getRoot().getKey()), 859 locationId, true); 860 861 RootWrapper joinedTree = joinTrees(rootWrapper, distance1, locationId, 862 rootWrapperPrevious, distance2); 863 864 removeFromRootWrapperList(rootWrapper); 865 removeFromRootWrapperList(rootWrapperPrevious); 866 addRootWrapperToList(joinedTree); 867 addAllowed = true; 868 return true; 869 } 870 addAllowed = true; 871 return false; 872 } 873 addAllowed = true; 874 return false; 875 } 876 877 public boolean canAdd(RootWrapper rootWrapper, Object locationIdToBeAdded, 878 int maxOffst) { 879 if (maxOffst == 0) 880 return true; 881 Entry nodeFloor = (Entry) getFloorNode(rootWrapper, locationIdToBeAdded); 882 Entry nodeCeil = (Entry) getCeilNode(rootWrapper, locationIdToBeAdded); 883 884 int dis1 = getDistance(rootWrapper, nodeFloor.key, locationIdToBeAdded, true); 885 int dis2 = getDistance(rootWrapper, locationIdToBeAdded, nodeCeil.key, true); 886 if (Math.abs(dis1) < maxOffst || Math.abs(dis2) < maxOffst) { 887 return false; 888 } 889 return true; 890 } 891 892 893 public void rotateLeft(RootWrapper rootWrapper, RBTreeNode node) { 894 Entry p = (Entry) node; 895 Entry r = (Entry) p.right; 896 int temp = r.distanceFromParent; 897 p.right = r.left; 898 899 if (r.left != null) { 900 ( (Entry) (r.left)).distanceFromParent += r.distanceFromParent; 901 r.left.parent = p; 902 } 903 r.parent = p.parent; 904 if (p.parent == null) { 905 setRootWrapperRoot(rootWrapper, r); 906 } 907 else if (compare( (p.parent.left).getKey(), p.getKey()) == 0) { 908 r.distanceFromParent += p.distanceFromParent; 909 p.parent.left = r; 910 } 911 else { 912 r.distanceFromParent += p.distanceFromParent; 913 p.parent.right = r; 914 } 915 r.left = p; 916 p.distanceFromParent = -temp; 917 p.parent = r; 918 } 919 920 921 public void rotateRight(RootWrapper rootWrapper, RBTreeNode node) { 922 Entry p = (Entry) node; 923 Entry l = (Entry) p.left; 924 int temp = l.distanceFromParent; 925 p.left = l.right; 926 if (l.right != null) { 927 ( (Entry) (l.right)).distanceFromParent += l.distanceFromParent; 928 l.right.parent = p; 929 } 930 l.parent = p.parent; 931 if (p.parent == null) { 932 setRootWrapperRoot(rootWrapper, l); 933 } 934 else if (compare( (p.parent.right).getKey(), p.getKey()) == 0) { 935 l.distanceFromParent += p.distanceFromParent; 936 p.parent.right = l; 937 } 938 else { 939 l.distanceFromParent += p.distanceFromParent; 940 p.parent.left = l; 941 } 942 l.right = p; 943 p.distanceFromParent = -temp; 944 p.parent = l; 945 } 946 947 public void preSwapPosition(RootWrapper rootWrapper, RBTreeNode x1, 948 RBTreeNode y1) { 949 Entry x = (Entry) x1; 950 Entry y = (Entry) y1; 951 int previousDstX = x.distanceFromParent; 952 if (compare(x.getParent().getKey(), y.getKey()) == 0) { 953 x.distanceFromParent += y.distanceFromParent; 954 ( (Entry) y.left).distanceFromParent -= previousDstX; 955 if (x.right != null) 956 ( (Entry) (x.right)).distanceFromParent += previousDstX; 957 y.distanceFromParent = -previousDstX; 958 return; 959 } 960 int dst = getDistance(rootWrapper, y.getKey(), x.getKey()); 961 x.distanceFromParent = y.distanceFromParent + dst; 962 y.distanceFromParent = previousDstX - dst; 963 ( (Entry) (y.left)).distanceFromParent -= dst; 964 ( (Entry) (y.right)).distanceFromParent -= dst; 965 if (x.right != null) 966 ( (Entry) (x.right)).distanceFromParent += dst; 967 } 968 969 public void postSwapPosition(RootWrapper rootWrapper) { 970 ( (Entry) (rootWrapper.root)).distanceFromParent = 0; 971 } 972 973 public LocationInformation getLocationInformation(LocationInformation 974 locationInformation) { 975 return getLocationInformation(locationInformation.locationId, 976 locationInformation.distance); 977 } 978 979 public LocationInformation getLocationInformation(Object locationId, 980 int distance) { 981 LocationInformation result; 982 if (distance == 0) { 983 result = new LocationInformation(locationId, distance); 984 return result; 985 } 986 RootWrapper rootWrapper = getRootWrapper(locationId); 987 if (rootWrapper == null) { 988 if (distance > 0) { 989 RootWrapper rootWrapperCeil = getCeilRootWrapper(locationId); 990 if (rootWrapperCeil == null) { 991 treeSizeSequenceUser.traceDistance(locationId, null, distance); 992 if (getRootWrapper(locationId) == null) 993 result = new LocationInformation(locationId, 0); 994 else 995 result = getLocationInformation(locationId, distance); 996 return result; 997 } 998 else { treeSizeSequenceUser.traceDistance(locationId, 1000 firstKey(rootWrapperCeil), 1001 distance); 1002 if (getRootWrapper(locationId) == null) 1003 result = new LocationInformation(locationId, 0); 1004 else 1005 result = getLocationInformation(locationId, distance); 1006 return result; 1007 } 1008 } 1009 else { RootWrapper rootWrapperFloor = getFloorRootWrapper(locationId); 1011 if (rootWrapperFloor == null) { 1012 treeSizeSequenceUser.traceDistance(locationId, null, distance); 1013 if (getRootWrapper(locationId) == null) 1014 result = new LocationInformation(locationId, 0); 1015 else 1016 result = getLocationInformation(locationId, distance); 1017 return result; 1018 } 1019 else { 1020 treeSizeSequenceUser.traceDistance(locationId, 1021 lastKey(rootWrapperFloor), 1022 distance); 1023 if (getRootWrapper(locationId) == null) 1024 result = new LocationInformation(locationId, 0); 1025 else 1026 result = getLocationInformation(locationId, distance); 1027 return result; 1028 } 1029 } 1030 } 1031 result = getLocationInformation(rootWrapper, locationId, distance); 1032 ensureResultCorrect(rootWrapper, result, distance, locationId); 1033 return result; 1034 } 1035 1036 private void ensureResultCorrect(RootWrapper rootWrapper, 1037 LocationInformation result, int distance, 1038 Object askedFor) { 1039 if (compare(result.getLocationId(), firstKey(rootWrapper)) == 0) 1040 return; 1041 if (result.getDistance() > distance) { 1042 show(); 1043 throw new InternalError ("ERROR IN GET LOCATION INFORMATION got " + 1044 result + " checking at distance " + distance + 1045 " askedFor = " + askedFor); 1046 } 1047 } 1048 1049 private LocationInformation getLocationInformation(RootWrapper rootWrapper, 1050 Object locationId, int distance) { 1051 LocationInformation locationInformation = null; 1052 boolean addAlPrev = addAllowed; 1053 addAllowed = false; 1054 int distanceFromRoot = getDistance(rootWrapper, 1055 rootWrapper.getRoot().getKey(), 1056 locationId, true); 1057 addAllowed = addAlPrev; 1058 locationInformation = getFinalLocationInformation( (Entry) rootWrapper. 1059 getRoot(), (distance + distanceFromRoot), (Entry) rootWrapper.getRoot(), 1060 -1, distance); 1061 return locationInformation; 1062 } 1063 1064 private LocationInformation getFinalLocationInformation(Entry root, 1065 int distance, Entry node, int minDistance, int distanceAsked) { 1066 LocationInformation locationInformation = null; 1067 if (distance >= 0 && (distance < minDistance || minDistance < 0)) { 1068 node = root; 1069 minDistance = distance; 1070 } 1071 if (root.getLeft() == null && root.getRight() == null) { 1072 if (minDistance < 0) 1073 locationInformation = new LocationInformation(root.key, 1074 (distanceAsked - distance)); 1075 else 1076 locationInformation = new LocationInformation(node.key, 1077 (distanceAsked - minDistance)); 1078 return locationInformation; 1079 } 1080 if (distance < 0 && root.left != null) 1081 return getFinalLocationInformation( (Entry) root.getLeft(), 1082 distance - 1083 ( (Entry) (root.left)).distanceFromParent, 1084 node, minDistance, distanceAsked); 1085 else if (distance > 0 && root.right != null) 1086 return getFinalLocationInformation( (Entry) root.right, 1087 distance - 1088 ( (Entry) (root.right)).distanceFromParent, 1089 node, minDistance, distanceAsked); 1090 if (minDistance < 0) 1091 locationInformation = new LocationInformation(root.key, 1092 (distanceAsked - distance)); 1093 else 1094 locationInformation = new LocationInformation(node.key, 1095 (distanceAsked - minDistance)); 1096 return locationInformation; 1097 } 1098 1099 public void updateSegment(RootWrapper rootWrapper, Object locationIdFrom, 1100 Object locationIdTo, int delta) { 1101 Entry previous = (Entry) getFloorNode(rootWrapper, locationIdFrom); 1102 Entry next = (Entry) getCeilNode(rootWrapper, locationIdTo); 1103 removeNodesWithIn(rootWrapper, previous.key, next.key); 1104 adjustDistance(rootWrapper, locationIdFrom, locationIdTo, delta); 1105 } 1106 1107 public void updateSegment(Object locationIdFrom, Object locationIdTo, 1108 int delta) { 1109 if (locationIdFrom == null || locationIdTo == null) 1110 throw new IllegalArgumentException ("Check For >>>>> locationIdFrom = " + 1111 locationIdFrom + 1112 " & locationIdTo = " + locationIdTo); 1113 try { 1114 if (delta == Integer.MIN_VALUE || delta == 0) { 1115 ; 1116 Thread.dumpStack(); 1117 return; 1118 } 1119 if (compare(locationIdFrom, locationIdTo) > 0) { 1120 Object temp = locationIdFrom; 1121 locationIdFrom = locationIdTo; 1122 locationIdTo = temp; 1123 delta = -delta; 1124 } 1125 RootWrapper rootWrapper1 = getRootWrapper(locationIdFrom); 1126 RootWrapper rootWrapper2 = getRootWrapper(locationIdTo); 1127 1128 if (rootWrapper1 != rootWrapper2) { 1129 ; 1130 Thread.dumpStack(); 1131 return; 1132 } 1133 updateSegment(rootWrapper1, locationIdFrom, locationIdTo, delta); 1134 fireDistanceEvent(); 1135 1136 } 1137 finally { } 1138 } 1139 1140 public void adjustDistance(RootWrapper rootWrapper, Object locationIdFrom, 1141 Object locationIdTo, int delta) { 1142 adjustDistanceFromParent( (Entry) rootWrapper.getRoot(), locationIdFrom, 1143 locationIdTo, delta); 1144 } 1145 1146 private void adjustDistanceFromParent(Entry root, Object locationIdFrom, 1147 Object locationIdTo, int delta) { 1148 Entry node = null; 1149 int cmp1 = compare(locationIdFrom, root.key); 1150 int cmp2 = compare(locationIdTo, root.key); 1151 boolean left = true; 1152 if ( (cmp1 <= 0 && cmp2 <= 0)) { node = (Entry) root.left; 1154 } 1155 else if ( (cmp1 >= 0) && (cmp2 >= 0)) { left = false; 1157 node = (Entry) root.right; 1158 } 1159 if (node != null) { 1160 if (isBetween(locationIdFrom, locationIdTo, root, node)) { 1161 if (left) 1162 node.distanceFromParent -= delta; 1163 else 1164 node.distanceFromParent += delta; 1165 } 1166 adjustDistanceFromParent(node, locationIdFrom, locationIdTo, delta); 1167 } 1168 } 1169 1170 private boolean isBetween(Object locationId1, Object locationId2, Entry node1, 1171 Entry node2) { 1172 int cmp11 = compare(node1.key, locationId1); 1173 int cmp12 = compare(node1.key, locationId2); 1174 int cmp21 = compare(node2.key, locationId1); 1175 int cmp22 = compare(node2.key, locationId2); 1176 1177 1178 boolean result = ( (cmp11 <= 0 && cmp12 <= 0 && cmp21 >= 0 && cmp22 >= 0) 1179 || 1180 (cmp21 <= 0 && cmp22 <= 0 && cmp11 >= 0 && cmp12 >= 0) 1181 ); 1182 return result; 1183 } 1184 1185 public int refreshSegment(Object locationIdFrom, Object locationIdTo) { 1186 int result = 0; 1187 int swap = 1; 1188 if (compare(locationIdFrom, locationIdTo) > 0) { 1189 Object temp = locationIdFrom; 1190 locationIdFrom = locationIdTo; 1191 locationIdTo = temp; 1192 swap = -1; 1193 } 1194 1195 RootWrapper rootWrapperFrom = getRootWrapper(locationIdFrom); 1196 RootWrapper rootWrapperTo = getRootWrapper(locationIdTo); 1197 boolean isLocationIdFromThere = false; 1198 boolean isLocationIdToThere = false; 1199 if (rootWrapperFrom != null) 1200 isLocationIdFromThere = containsKey(rootWrapperFrom, locationIdFrom); 1201 if (rootWrapperTo != null) 1202 isLocationIdToThere = containsKey(rootWrapperTo, locationIdTo); 1203 1204 1205 1212 Object precedingKey = null; 1213 if (rootWrapperFrom != null) { 1214 Entry precedingNode = (Entry) getPrecedingNode(rootWrapperFrom, 1215 locationIdFrom); 1216 precedingKey = precedingNode != null ? precedingNode.getKey() : null; 1217 } 1218 int distanceFromPrecedingKeyToLocationIdFrom = precedingKey != null ? 1219 getDistance(precedingKey, locationIdFrom, true) : 0; 1220 Object nextKey = null; 1221 if (rootWrapperTo != null) { 1222 Entry nextNode = (Entry) getNextNode(rootWrapperTo, locationIdTo); 1223 nextKey = nextNode != null ? nextNode.getKey() : null; 1224 } 1225 int distanceFromNextKeyToLocationIdTo = nextKey != null ? 1226 getDistance(nextKey, locationIdTo, true) : 0; 1227 1228 if (rootWrapperFrom != null) 1229 breakTreeAt(locationIdFrom); 1230 if (rootWrapperTo != null) 1231 breakTreeAt(locationIdTo); 1232 1233 1234 if (isLocationIdFromThere) 1235 add(precedingKey, distanceFromPrecedingKeyToLocationIdFrom, 1236 locationIdFrom); 1237 if (isLocationIdToThere) 1238 add(nextKey, distanceFromNextKeyToLocationIdTo, locationIdTo); 1239 1240 1241 RootWrapper nextRootWrapper = getNextRootWrapperOfKey(locationIdFrom); 1242 RootWrapper previousRootWrapper = getPreviousRootWrapperOfKey(locationIdTo); 1243 if (nextRootWrapper != null && previousRootWrapper != null) { 1244 int cmp = compare(nextRootWrapper, previousRootWrapper); 1245 if (cmp < 0) { 1246 while (nextRootWrapper != previousRootWrapper && nextRootWrapper != null) { 1247 removeFromRootWrapperList(nextRootWrapper); 1248 nextRootWrapper = getNextRootWrapper(nextRootWrapper); 1249 } 1250 } 1251 else if (cmp == 0) 1252 removeFromRootWrapperList(nextRootWrapper); 1253 } 1254 1255 result = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser. 1256 traceDistance(locationIdFrom, locationIdTo, Integer.MAX_VALUE)) * swap; 1257 fireDistanceEvent(); 1258 return result; 1259 } 1260 1261 public int refreshSegmentOld(Object locationIdFrom, Object locationIdTo) { 1262 int result = 0; 1263 try { 1264 if (compare(locationIdFrom, locationIdTo) > 0) { 1265 Object temp = locationIdFrom; 1266 locationIdFrom = locationIdTo; 1267 locationIdTo = temp; 1268 } 1269 RootWrapper floorRootWrapper = getFloorRootWrapper(locationIdFrom); 1270 RootWrapper ceilRootWrapper = getCeilRootWrapper(locationIdTo); 1271 1272 if (floorRootWrapper == null && ceilRootWrapper == null) { 1273 if (getFirstRootWrapper() != null) { 1274 ; 1275 result = Integer.MIN_VALUE; 1276 return Integer.MIN_VALUE; 1277 } 1278 treeSizeSequenceUser.traceDistance(locationIdFrom, locationIdTo, 1279 Integer.MAX_VALUE); 1280 result = Integer.MIN_VALUE; 1281 return Integer.MIN_VALUE; 1282 } 1283 if (floorRootWrapper == null) { 1284 Object firstCeilRootWrapper = firstKey(ceilRootWrapper); 1285 if (compare(firstCeilRootWrapper, locationIdTo) != 0) { 1286 breakTreeAt(locationIdTo); 1287 removeFromRootWrapperList(getRootWrapper(firstCeilRootWrapper)); 1288 fireDistanceEvent(); 1289 result = Integer.MIN_VALUE; 1290 return Integer.MIN_VALUE; 1291 } 1292 treeSizeSequenceUser.traceDistance(locationIdFrom, locationIdTo, 1293 Integer.MAX_VALUE); 1294 result = Integer.MIN_VALUE; 1295 return Integer.MIN_VALUE; 1296 } 1297 if (ceilRootWrapper == null) { 1298 Object lastFloorRootWrapper = lastKey(floorRootWrapper); 1299 if (compare(lastFloorRootWrapper, locationIdFrom) != 0) { 1300 breakTreeAt(locationIdFrom); 1301 removeFromRootWrapperList(getRootWrapper(lastFloorRootWrapper)); 1302 fireDistanceEvent(); 1303 result = Integer.MIN_VALUE; 1304 return Integer.MIN_VALUE; 1305 } 1306 treeSizeSequenceUser.traceDistance(locationIdFrom, locationIdTo, 1307 Integer.MAX_VALUE); 1308 result = Integer.MIN_VALUE; 1309 return Integer.MIN_VALUE; 1310 } 1311 1312 if (floorRootWrapper != ceilRootWrapper) { 1313 1314 breakTreeAt(locationIdFrom); 1315 breakTreeAt(locationIdTo); 1316 RootWrapper rootWrapperOfLocationIdFrom = getCeilRootWrapper( 1317 locationIdFrom); 1318 RootWrapper rootWrapperOfLocationIdTo = getCeilRootWrapper(locationIdTo); 1319 1320 while (rootWrapperOfLocationIdFrom != rootWrapperOfLocationIdTo && 1321 rootWrapperOfLocationIdTo != null) { 1322 removeFromRootWrapperList(rootWrapperOfLocationIdFrom); 1323 rootWrapperOfLocationIdFrom = getNextRootWrapper( 1324 rootWrapperOfLocationIdFrom); 1325 } 1326 fireDistanceEvent(); 1327 1348 return Integer.MIN_VALUE; 1349 } 1350 result = refreshSegment(floorRootWrapper, locationIdFrom, locationIdTo); 1351 fireDistanceEvent(); 1352 return result; 1353 } 1354 finally { } 1355 } 1356 1357 private int refreshSegment(RootWrapper rootWrapper, Object locationIdFrom, 1358 Object locationIdTo) { 1359 Entry previous = (Entry) getFloorNode(rootWrapper, locationIdFrom); 1360 Entry next = (Entry) getCeilNode(rootWrapper, locationIdTo); 1361 int originalDistance = getDistance(rootWrapper, previous.key, next.key, false); 1362 removeNodesWithIn(rootWrapper, previous.key, next.key); 1363 boolean addAlPrev = addAllowed; 1364 addAllowed = false; 1365 int newDistance = RBTreeSizeSequenceUtility.getFirstInt( 1366 treeSizeSequenceUser.traceDistance(previous.getKey(), next.getKey(), 1367 Integer.MAX_VALUE)); 1368 addAllowed = addAlPrev; 1369 int delta = (newDistance - originalDistance); 1370 adjustDistance(rootWrapper, previous.getKey(), next.getKey(), delta); 1371 return delta; 1372 } 1373 1374 private ArrayList nodeList; 1375 private void removeNodesWithIn(RootWrapper rootWrapper, Object locationIdFrom, 1376 Object locationIdTo) { 1377 collectNodesWithIn(rootWrapper.getRoot(), locationIdFrom, locationIdTo); 1378 for (int i = 0; i < nodeList.size(); i++) { 1379 Object toRemove = nodeList.get(i); 1380 remove(rootWrapper, toRemove); 1381 } 1382 nodeList = null; 1383 } 1384 1385 private void collectNodesWithIn(RBTreeNode root, Object locationIdFrom, 1386 Object locationIdTo) { 1387 if (nodeList == null) 1388 nodeList = new ArrayList(); 1389 if (isBetween(locationIdFrom, locationIdTo, root.getKey())) 1390 nodeList.add(root.getKey()); 1391 if (root.getLeft() != null) 1392 collectNodesWithIn(root.getLeft(), locationIdFrom, locationIdTo); 1393 if (root.getRight() != null) 1394 collectNodesWithIn(root.getRight(), locationIdFrom, locationIdTo); 1395 } 1396 1397 private boolean isBetween(Object locationId1, Object locationId2, Object obj) { 1398 return isBetween(locationId1, locationId2, obj, true); 1399 } 1400 1401 private boolean isBetween(Object locationId1, Object locationId2, Object obj, 1402 boolean exactlyInBetween) { 1403 int cmp = compare(locationId1, locationId2); 1404 if (cmp > 0) { 1405 Object temp = locationId1; 1406 locationId1 = locationId2; 1407 locationId2 = temp; 1408 } 1409 int cmp1 = compare(locationId1, obj); 1410 int cmp2 = compare(locationId2, obj); 1411 boolean result; 1412 if (exactlyInBetween) 1413 result = (cmp1 < 0 && cmp2 > 0); 1414 else 1415 result = (cmp1 <= 0 && cmp2 >= 0); 1416 return result; 1417 } 1418 1419 public long checkDistance(Object locationIdFrom, Object locationIdTo, 1420 int upto) { 1421 int cmp = compare(locationIdFrom, locationIdTo); 1422 if (cmp > 0) { 1423 return checkDistance(locationIdTo, locationIdFrom, -upto); 1424 } 1425 RootWrapper rootWrapperFrom = getRootWrapper(locationIdFrom); 1426 RootWrapper rootWrapperTo = getRootWrapper(locationIdTo); 1427 1428 if (rootWrapperFrom != null && rootWrapperTo != null && 1429 rootWrapperFrom == rootWrapperTo) { 1430 return checkDistance(rootWrapperFrom, locationIdFrom, locationIdTo, upto); 1431 } 1432 1433 if (rootWrapperFrom == null) 1434 rootWrapperFrom = makeNewTree(locationIdFrom); 1435 int currentDistance = 0; 1436 Object locationIdLastF = lastKey(rootWrapperFrom); 1437 RootWrapper rootWrapperNext = getNextRootWrapper(rootWrapperFrom); 1438 Object locationIdFirstN = null; 1439 cmp = -1; 1440 if (rootWrapperNext != null) { 1441 locationIdFirstN = firstKey(rootWrapperNext); 1442 cmp = compare(locationIdFirstN, locationIdTo); 1443 } 1444 long longDistance = 0; 1445 RootWrapper rootWrapperPrevious = null; 1446 int distance = 0; 1447 int fnl = 0; 1448 while (cmp < 0) { 1449 if (locationIdFirstN != null) { 1450 longDistance = treeSizeSequenceUser.traceDistance(locationIdLastF, 1451 locationIdFirstN, (upto - currentDistance)); 1452 distance = RBTreeSizeSequenceUtility.getFirstInt(longDistance); 1453 currentDistance += distance; 1454 fnl = RBTreeSizeSequenceUtility.getSecondInt(longDistance); 1455 if (fnl != 1) 1456 return RBTreeSizeSequenceUtility.getLong(currentDistance, fnl); 1457 rootWrapperPrevious = rootWrapperNext; 1458 rootWrapperNext = getNextRootWrapper(rootWrapperNext); 1459 } 1460 if (rootWrapperNext == null) { 1461 longDistance = treeSizeSequenceUser.traceDistance( ( ( 1462 rootWrapperPrevious != null) ? lastKey(rootWrapperPrevious) : 1463 lastKey(rootWrapperFrom)), locationIdTo, (upto - currentDistance)); 1464 distance = RBTreeSizeSequenceUtility.getFirstInt(longDistance); 1465 currentDistance += distance; 1466 fnl = RBTreeSizeSequenceUtility.getSecondInt(longDistance); 1467 return RBTreeSizeSequenceUtility.getLong(distance, fnl); 1468 } 1469 locationIdFirstN = firstKey(rootWrapperNext); 1470 locationIdLastF = lastKey(rootWrapperFrom); 1471 cmp = compare(locationIdFirstN, locationIdTo); 1472 } 1473 longDistance = treeSizeSequenceUser.traceDistance( ( (rootWrapperPrevious != null) ? 1474 lastKey(rootWrapperPrevious) : lastKey(rootWrapperFrom)), locationIdTo, 1475 (upto - currentDistance)); 1476 distance = RBTreeSizeSequenceUtility.getFirstInt(longDistance); 1477 currentDistance += distance; 1478 fnl = RBTreeSizeSequenceUtility.getSecondInt(longDistance); 1479 return RBTreeSizeSequenceUtility.getLong(distance, fnl); 1480 } 1481 1482 private RootWrapper makeNewTree(Object locationId) { 1483 RootWrapper temp; 1484 if ( (temp = getRootWrapper(locationId)) != null) 1485 throw new InternalError ("Should not make tree cpdng to " + locationId + 1486 " as it is present in " + temp); 1487 RootWrapper rootWrapper = new RootWrapper(); 1488 put(rootWrapper, null, Integer.MIN_VALUE, locationId); 1489 addRootWrapperToList(rootWrapper); 1490 return rootWrapper; 1491 } 1492 1493 private long checkDistance(RootWrapper rootWrapper, Object locationIdFrom, 1494 Object locationIdTo, int upto) { 1495 int cmp = compare(locationIdFrom, locationIdTo); 1496 if (cmp > 0) { 1497 return checkDistance(rootWrapper, locationIdTo, locationIdFrom, -upto); 1498 } 1499 Entry entryFrom = (Entry) getNode(rootWrapper, locationIdFrom); 1500 Entry entryTo = (Entry) getNode(rootWrapper, locationIdTo); 1501 if (entryFrom == null) 1502 entryFrom = (Entry) getCeilNode(rootWrapper, locationIdFrom); 1503 if (entryFrom == null) { 1504 show(); 1505 throw new InternalError ("ERROR FINDING CEIL-ENTRY OF " + locationIdFrom); 1506 } 1507 int currentDistance = getDistance(rootWrapper, locationIdFrom, 1508 entryFrom.key); 1509 if (currentDistance > upto) 1510 return RBTreeSizeSequenceUtility.getLong(currentDistance, 0); 1511 1512 if (entryTo == null) 1513 entryTo = (Entry) getFloorNode(rootWrapper, locationIdTo); 1514 if (entryTo == null) { 1515 show(); 1516 throw new InternalError ("ERROR FINDING FLOOR-ENTRY OF " + locationIdTo); 1517 } 1518 currentDistance += getDistance(rootWrapper, entryTo.key, locationIdTo); 1519 if (currentDistance > upto) 1520 return RBTreeSizeSequenceUtility.getLong(currentDistance, 0); 1521 currentDistance += getDistance(rootWrapper, entryFrom.key, entryTo.key); 1522 return RBTreeSizeSequenceUtility.getLong(currentDistance, 1); 1523 } 1524 1525 public void markInvalid(Object locationIdFrom, Object locationIdTo) { 1526 super.markInvalid(locationIdFrom, locationIdTo); 1527 fireDistanceEvent(); 1528 } 1529 1530 private RootWrapper joinTrees(RootWrapper rootWrapper1, 1531 int distanceBetweenRoots, 1532 RootWrapper rootWrapper2) { 1533 if (rootWrapper1 == null || rootWrapper2 == null) 1534 throw new InternalError ("One or the rootWrapper is null"); 1535 if (rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null) { 1536 return rootWrapper2; 1537 } 1538 if (rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null) { 1539 return rootWrapper1; 1540 } 1541 if (rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null) { 1542 return null; 1543 } 1544 if (rootWrapper1.getRoot().getLeft() == null && 1545 rootWrapper1.getRoot().getRight() == null) { 1546 put(rootWrapper2, rootWrapper2.getRoot().getKey(), -distanceBetweenRoots, 1547 rootWrapper1.getRoot().getKey()); 1548 return rootWrapper2; 1549 } 1550 if (rootWrapper2.getRoot().getLeft() == null && 1551 rootWrapper2.getRoot().getRight() == null) { 1552 put(rootWrapper1, rootWrapper1.getRoot().getKey(), distanceBetweenRoots, 1553 rootWrapper2.getRoot().getKey()); 1554 return rootWrapper1; 1555 } 1556 int cmp = compareRootWrappers(rootWrapper1, rootWrapper2); 1557 if (cmp > 0) { 1558 RootWrapper temp = rootWrapper1; 1559 rootWrapper1 = rootWrapper2; 1560 rootWrapper2 = temp; 1561 distanceBetweenRoots = -distanceBetweenRoots; 1562 } 1563 1564 Object obj = firstKey(rootWrapper2); 1565 Object oldRootKey = rootWrapper2.getRoot().getKey(); 1566 if (obj == oldRootKey) { 1567 1568 RBTreeNode rightNode = rootWrapper2.getRoot().getRight(); 1569 if (rightNode != null) { 1570 Object rightNodeKey = rightNode.getKey(); 1571 int disFromObjToRightNodeKey = ( (Entry) rightNode). 1572 getDistanceFromParent(); 1573 put(rootWrapper1, rootWrapper1.getRoot().getKey(), distanceBetweenRoots, 1574 obj); 1575 makeLinksNull(rightNode); 1576 put(rootWrapper1, obj, disFromObjToRightNodeKey, rightNodeKey); 1577 return rootWrapper1; 1578 } 1579 } 1580 int disFromRootToFirst = getDistance(rootWrapper2, oldRootKey, obj); 1582 remove(rootWrapper2, obj); 1583 1584 int distanceFromRootOfRootWrapper1 = distanceBetweenRoots + 1585 disFromRootToFirst; if (rootWrapper2.getRoot() == null) { 1587 put(rootWrapper1, rootWrapper1.getRoot().getKey(), 1588 distanceFromRootOfRootWrapper1, obj); 1589 return rootWrapper1; 1590 } 1591 else { 1592 int dis = getDistance(rootWrapper2, rootWrapper2.getRoot().getKey(), 1593 oldRootKey); int distanceFromRootOfRootWrapper2 = dis + disFromRootToFirst; RootWrapper joinedTree = joinTrees(rootWrapper1, 1596 distanceFromRootOfRootWrapper1, obj, 1597 rootWrapper2, 1598 distanceFromRootOfRootWrapper2); 1599 return joinedTree; 1600 } 1601 } 1602 1603 private RootWrapper joinTrees(RootWrapper rootWrapper1, 1604 int distanceFromRootOfRootWrapper1, Object obj, 1605 RootWrapper rootWrapper2, 1606 int distanceFromRootOfRootWrapper2) { 1607 if (rootWrapper1 == null || rootWrapper2 == null) 1608 throw new InternalError ("One or the RootWrapper is null"); 1609 1610 if (rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null) { 1611 put(rootWrapper2, rootWrapper2.getRoot().getKey(), 1612 distanceFromRootOfRootWrapper2, obj); 1613 return rootWrapper2; 1614 } 1615 if (rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null) { 1616 put(rootWrapper1, rootWrapper1.getRoot().getKey(), 1617 distanceFromRootOfRootWrapper1, obj); 1618 return rootWrapper1; 1619 } 1620 if (rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null) { 1621 put(rootWrapper1, null, 0, obj); 1622 return rootWrapper1; 1623 } 1624 int blackHeight1 = rootWrapper1.getBlackHeight(); 1625 int blackHeight2 = rootWrapper2.getBlackHeight(); 1626 1627 if (blackHeight1 == blackHeight2) { 1628 RootWrapper result = new RootWrapper(); 1629 put(result, null, 0, obj); 1630 Entry node = (Entry) result.getRoot(); 1631 Entry root1 = (Entry) rootWrapper1.getRoot(); 1632 Entry root2 = (Entry) rootWrapper2.getRoot(); 1633 root1.parent = node; 1634 root2.parent = node; 1635 root1.distanceFromParent = -distanceFromRootOfRootWrapper1; 1636 root2.distanceFromParent = -distanceFromRootOfRootWrapper2; 1637 if (compareRootWrappers(rootWrapper1, rootWrapper2) < 0) { 1638 node.left = root1; 1639 node.right = root2; 1640 } 1641 else { 1642 node.left = root2; 1643 node.right = root1; 1644 } 1645 return result; 1646 } 1647 if (blackHeight1 < blackHeight2) { 1648 RootWrapper temp = rootWrapper1; 1649 rootWrapper1 = rootWrapper2; 1650 rootWrapper2 = temp; 1651 int temp1 = distanceFromRootOfRootWrapper1; 1652 distanceFromRootOfRootWrapper1 = distanceFromRootOfRootWrapper2; 1653 distanceFromRootOfRootWrapper2 = temp1; 1654 } 1655 1656 ( (Entry) rootWrapper2.root).distanceFromParent = - 1657 distanceFromRootOfRootWrapper2; 1658 int cmp = compareRootWrappers(rootWrapper1, rootWrapper2); 1659 RootWrapper result; 1660 if (cmp >= 0) { 1661 result = joinToLeft(rootWrapper1, rootWrapper2, obj, 1662 distanceFromRootOfRootWrapper1); 1663 } 1664 else { 1665 result = joinToRight(rootWrapper1, rootWrapper2, obj, 1666 distanceFromRootOfRootWrapper1); 1667 } 1668 return result; 1669 } 1670 1671 private RootWrapper joinToLeft(RootWrapper mainRootWrapper, 1672 RootWrapper rootWrapper1, Object obj, 1673 int distanceFromRoot) { 1674 int blackHeight1 = rootWrapper1.getBlackHeight(); 1675 1676 int blackHeight2 = mainRootWrapper.getBlackHeight(); 1677 1678 if (blackHeight2 < blackHeight1) 1679 throw new InternalError ("blackHeight2 can't be less than blackHeight1 " + 1680 blackHeight1 + " , " + blackHeight2); 1681 if (blackHeight1 == 0) { 1682 put(mainRootWrapper, mainRootWrapper.getRoot().getKey(), distanceFromRoot, 1683 obj); 1684 return mainRootWrapper; 1685 } 1686 Entry node = (Entry) mainRootWrapper.getRoot(); 1687 while (node != null) { 1688 if ( (getBlackHeight(node) == blackHeight1) && node.getColor()) 1689 break; 1690 node = (Entry) node.left; 1691 } 1692 if (node == null) { 1693 throw new InternalError ("node can't be null."); 1694 } 1695 Entry parentNode = (Entry) node.parent; 1696 Entry root1 = (Entry) rootWrapper1.root; 1697 Entry subTreeRoot = (Entry) createRBTreeNode(obj, null); 1698 1699 1700 subTreeRoot.left = root1; 1701 root1.parent = subTreeRoot; 1702 1703 node.distanceFromParent = -distanceFromRoot + 1704 getDistance(mainRootWrapper, mainRootWrapper.getRoot().getKey(), 1705 node.getKey()); 1706 1707 subTreeRoot.right = node; 1708 node.parent = subTreeRoot; 1709 1710 if (parentNode == null) { 1711 RootWrapper subTree = new RootWrapper(subTreeRoot); 1712 return subTree; 1713 } 1714 subTreeRoot.distanceFromParent = distanceFromRoot - 1715 getDistance(mainRootWrapper, mainRootWrapper.getRoot().getKey(), 1716 parentNode.getKey()); 1717 parentNode.left = subTreeRoot; 1718 subTreeRoot.parent = parentNode; 1719 1720 invokeFixAfterInsertion(mainRootWrapper, subTreeRoot); 1721 return mainRootWrapper; 1722 } 1723 1724 private RootWrapper joinToRight(RootWrapper mainRootWrapper, 1725 RootWrapper rootWrapper2, Object obj, 1726 int distanceFromRoot) { 1727 1728 int blackHeight1 = mainRootWrapper.getBlackHeight(); 1729 int blackHeight2 = getBlackHeight(rootWrapper2.getRoot()); 1730 1731 if (blackHeight1 < blackHeight2) 1732 throw new InternalError ("blackHeight1 can't be less than blackHeight2 " + 1733 blackHeight1 + " , " + blackHeight2); 1734 if (blackHeight2 == 0) { 1735 put(mainRootWrapper, mainRootWrapper.getRoot().getKey(), distanceFromRoot, 1736 obj); 1737 return mainRootWrapper; 1738 } 1739 1740 Entry node = (Entry) mainRootWrapper.getRoot(); 1741 while (node != null) { 1742 if ( (getBlackHeight(node) == blackHeight2) && node.getColor()) 1743 break; 1744 node = (Entry) node.right; 1745 } 1746 if (node == null) { 1747 throw new InternalError ("node can't be null."); 1748 } 1749 Entry parentNode = (Entry) node.getParent(); 1750 Entry root2 = (Entry) rootWrapper2.getRoot(); 1751 Entry subTreeRoot = (Entry) createRBTreeNode(obj, null); 1752 subTreeRoot.right = root2; 1753 root2.parent = subTreeRoot; 1754 1755 node.distanceFromParent = -distanceFromRoot + 1756 getDistance(mainRootWrapper, mainRootWrapper.getRoot().getKey(), 1757 node.getKey()); 1758 subTreeRoot.left = node; 1759 node.parent = subTreeRoot; 1760 1761 if (parentNode == null) { 1762 RootWrapper subTree = new RootWrapper(subTreeRoot); 1763 return subTree; 1764 } 1765 subTreeRoot.distanceFromParent = distanceFromRoot - 1766 getDistance(mainRootWrapper, mainRootWrapper.getRoot().getKey(), 1767 parentNode.getKey()); 1768 subTreeRoot.parent = parentNode; 1769 parentNode.right = subTreeRoot; 1770 1771 invokeFixAfterInsertion(mainRootWrapper, subTreeRoot); 1772 return mainRootWrapper; 1773 } 1774 1775 public void breakTreeAt(Object obj) { 1776 addAllowed = false; 1777 try { 1778 RootWrapper rootWrapper = getRootWrapper(obj); 1779 if (rootWrapper == null) { 1780 return; 1781 } 1782 removeFromRootWrapperList(rootWrapper); 1783 RootWrapper rootWrapperLeft = new RootWrapper(); 1784 RootWrapper rootWrapperRight = new RootWrapper(); 1785 breakTree(rootWrapper, obj, rootWrapperLeft, 0, rootWrapperRight, 0); 1786 1787 if (rootWrapperLeft.getRoot() != null) { 1788 addRootWrapperToList(rootWrapperLeft); 1789 } 1790 if (rootWrapperRight.getRoot() != null) { 1791 addRootWrapperToList(rootWrapperRight); 1792 } 1793 } 1794 finally { 1795 addAllowed = true; 1796 } 1797 1800 } 1801 1802 public void breakTree(RootWrapper mainRootWrapper, Object obj, 1803 RootWrapper rootWrapperLeft, int distanceFromLeftRoot, 1804 RootWrapper rootWrapperRight, int distanceFromRightRoot) { 1805 Entry root = (Entry) mainRootWrapper.getRoot(); 1806 if (root == null) { 1807 return; 1808 } 1809 Object rootKey = root.getKey(); 1810 int leftNodeDFP = 0; 1811 int rightNodeDFP = 0; 1812 Object leftNodeKey = null; 1813 Object rightNodeKey = null; 1814 Entry leftNode = (Entry) root.left; 1815 Entry rightNode = (Entry) root.right; 1816 if (leftNode != null) { 1817 leftNodeDFP = leftNode.distanceFromParent; 1818 leftNodeKey = leftNode.getKey(); 1819 } 1820 if (rightNode != null) { 1821 rightNodeDFP = rightNode.distanceFromParent; 1822 rightNodeKey = rightNode.key; 1823 } 1824 int cmp = compare(rootKey, obj); 1825 if (cmp == 0) { if (leftNode == null && rightNode == null) { return; 1828 } 1829 RootWrapper tempLeft = new RootWrapper(); RootWrapper tempRight = new RootWrapper(); 1832 boolean joinWithLeft = true; 1833 boolean joinWithRight = true; 1834 if (rootWrapperLeft.getRoot() == null) { setRootWrapperRoot(rootWrapperLeft, leftNode); 1836 joinWithLeft = false; 1837 } 1838 else if (leftNode != null) { setRootWrapperRoot(tempLeft, leftNode); 1840 } 1841 if (rootWrapperRight.getRoot() == null) { setRootWrapperRoot(rootWrapperRight, rightNode); 1843 joinWithRight = false; 1844 } 1845 else if (rightNode != null) { setRootWrapperRoot(tempRight, rightNode); 1847 } 1848 1849 if (joinWithLeft) { 1850 int distanceBetweenRoots = distanceFromLeftRoot + leftNodeDFP; 1851 rootWrapperLeft.setRoot(joinTrees(rootWrapperLeft, distanceBetweenRoots, 1852 tempLeft).getRoot()); 1853 } 1854 if (joinWithRight) { 1855 int distanceBetweenRoots = distanceFromRightRoot + rightNodeDFP; 1856 rootWrapperRight.setRoot(joinTrees(rootWrapperRight, 1857 distanceBetweenRoots, tempRight). 1858 getRoot()); 1859 } 1860 return; 1861 } 1862 else if (cmp > 0) { if (leftNode == null && rightNode == null) { 1864 if (rootWrapperRight.getRoot() == null) { 1865 setRootWrapperRoot(rootWrapperRight, root); 1866 } 1867 else { 1868 makeLinksNull(root); 1869 put(rootWrapperRight, rootWrapperRight.getRoot().getKey(), 1870 distanceFromRightRoot, rootKey); 1871 } 1872 return; 1873 } 1874 if (rootWrapperRight.getRoot() == null) { if (rightNode != null) { 1876 setRootWrapperRoot(rootWrapperRight, rightNode); 1877 makeLinksNull(root); 1878 put(rootWrapperRight, rootWrapperRight.getRoot().getKey(), 1879 -rightNodeDFP, rootKey); 1880 int disFromOldRoot = getDistance(rootWrapperRight, 1881 rootWrapperRight.getRoot().getKey(), 1882 rightNodeKey); 1883 distanceFromRightRoot = disFromOldRoot - rightNodeDFP + leftNodeDFP; 1884 } 1885 else { 1886 root.left = null; 1887 setRootWrapperRoot(rootWrapperRight, root); 1888 } 1889 } 1890 else { if (rightNode == null) { Object tempRootRight = rootWrapperRight.getRoot().getKey(); 1893 makeLinksNull(root); 1894 put(rootWrapperRight, tempRootRight, distanceFromRightRoot, rootKey); 1895 int disFromOldRoot = getDistance(rootWrapperRight, 1896 rootWrapperRight.getRoot().getKey(), 1897 tempRootRight); 1898 distanceFromRightRoot += disFromOldRoot + leftNodeDFP; 1899 } 1900 else { 1901 RootWrapper tempRight = new RootWrapper(rightNode); 1902 ( (Entry) tempRight.root).setDistancFromParent(0); 1903 makeLinksNull(root); 1904 put(tempRight, rightNodeKey, -rightNodeDFP, rootKey); 1905 1906 Object rootWrapperRightTempRoot = rootWrapperRight.getRoot().getKey(); 1907 int distanceBetweenRoots = distanceFromRightRoot - 1908 getDistance(tempRight, tempRight.getRoot().getKey(), rootKey); 1909 rootWrapperRight.setRoot(joinTrees(tempRight, -distanceBetweenRoots, 1910 rootWrapperRight).getRoot()); 1911 1912 int disRtTree = getDistance(rootWrapperRight, 1913 rootWrapperRight.getRoot().getKey(), 1914 rootWrapperRightTempRoot); 1915 distanceFromRightRoot += disRtTree + leftNodeDFP; 1916 } 1917 } 1918 if (leftNode == null) { 1919 return; 1920 } 1921 if (rootWrapperLeft.getRoot() != null) 1922 distanceFromLeftRoot += leftNodeDFP; 1923 setRootWrapperRoot(mainRootWrapper, leftNode); 1924 breakTree(mainRootWrapper, obj, rootWrapperLeft, distanceFromLeftRoot, 1925 rootWrapperRight, distanceFromRightRoot); 1926 return; 1927 } 1928 else { if (leftNode == null && rightNode == null) { 1930 if (rootWrapperLeft.getRoot() == null) { 1931 setRootWrapperRoot(rootWrapperLeft, root); 1932 } 1933 else { 1934 makeLinksNull(root); 1935 put(rootWrapperLeft, rootWrapperLeft.getRoot().getKey(), 1936 distanceFromLeftRoot, rootKey); 1937 } 1938 return; 1939 } 1940 if (rootWrapperLeft.getRoot() == null) { if (leftNode != null) { 1942 setRootWrapperRoot(rootWrapperLeft, leftNode); 1943 makeLinksNull(root); 1944 put(rootWrapperLeft, rootWrapperLeft.getRoot().getKey(), -leftNodeDFP, 1945 rootKey); 1946 int disFromOldRoot = getDistance(rootWrapperLeft, 1947 rootWrapperLeft.getRoot().getKey(), 1948 leftNodeKey); 1949 distanceFromLeftRoot = disFromOldRoot + rightNodeDFP - leftNodeDFP; 1950 } 1951 else { 1952 root.right = null; 1953 setRootWrapperRoot(rootWrapperLeft, root); 1954 } 1955 } 1956 else { if (leftNode == null) { Object tempRootLeft = rootWrapperLeft.getRoot().getKey(); 1959 makeLinksNull(root); 1960 put(rootWrapperLeft, tempRootLeft, distanceFromLeftRoot, rootKey); 1961 int disFromOldRoot = getDistance(rootWrapperLeft, 1962 rootWrapperLeft.getRoot().getKey(), 1963 tempRootLeft); 1964 distanceFromLeftRoot += disFromOldRoot + rightNodeDFP; 1965 } 1966 else { 1967 RootWrapper tempLeft = new RootWrapper(leftNode); 1968 ( (Entry) tempLeft.root).setDistancFromParent(0); 1969 makeLinksNull(root); 1970 put(tempLeft, leftNodeKey, -leftNodeDFP, rootKey); 1971 1972 Object rootWrapperLeftTempRoot = rootWrapperLeft.getRoot().getKey(); 1973 int distanceBetweenRoots = distanceFromLeftRoot - 1974 getDistance(tempLeft, tempLeft.getRoot().getKey(), rootKey); 1975 rootWrapperLeft.setRoot(joinTrees(tempLeft, -distanceBetweenRoots, 1976 rootWrapperLeft).getRoot()); 1977 int disLfTree = getDistance(rootWrapperLeft, 1978 rootWrapperLeft.getRoot().getKey(), 1979 rootWrapperLeftTempRoot); 1980 distanceFromLeftRoot += disLfTree + rightNodeDFP; 1981 } 1982 } 1983 if (rightNode == null) { 1984 return; 1985 } 1986 if (rootWrapperRight.getRoot() != null) 1987 distanceFromRightRoot += rightNodeDFP; 1988 setRootWrapperRoot(mainRootWrapper, rightNode); 1989 breakTree(mainRootWrapper, obj, rootWrapperLeft, distanceFromLeftRoot, 1990 rootWrapperRight, distanceFromRightRoot); 1991 return; 1992 } 1993 } 1994 1995 public void setRootWrapperRoot(RootWrapper rootWrapper, RBTreeNode node) { 1996 if (node != null) 1997 ( (Entry) node).distanceFromParent = 0; 1998 rootWrapper.setRoot(node); 1999 } 2000 2001 public void replaceParentLeft(RBTreeNode p, RBTreeNode replacement) { 2002 p.parent.left = replacement; 2003 ( (Entry) (p.parent.left)).distanceFromParent += ( (Entry) p). 2004 distanceFromParent; 2005 } 2006 2007 public void replaceParentRight(RBTreeNode p, RBTreeNode replacement) { 2008 p.parent.right = replacement; 2009 ( (Entry) (p.parent.right)).distanceFromParent += ( (Entry) p). 2010 distanceFromParent; 2011 } 2012 2013 public boolean isSizeSequenceValid() { 2014 int numberOfEntries = getNumberOfEntries(); 2015 if (numberOfEntries == 1) 2016 return true; 2017 return false; 2018 } 2019 2020 public void callMethod() { 2021 } 2022 2023 public void show() { 2024 super.show(); 2025 } 2026 2027 2028 public Object getKeyAtDistance(Object key, int distance) { 2029 return getLocationInformation(key, distance).getLocationId(); 2030 } 2031 2032 public synchronized void delete(Object locationId) { 2033 RootWrapper rootWrapper = getRootWrapper(locationId); 2034 2035 RBTreeNode previousNode = getPrecedingNode(rootWrapper, locationId); 2036 2037 RBTreeNode nextNode = getNextNode(rootWrapper, locationId); 2038 2039 remove(rootWrapper, locationId); 2040 2041 if (previousNode != null && nextNode != null) 2042 adjustDistance(rootWrapper, previousNode.getKey(), nextNode.getKey(), -1); 2043 2044 } 2045 2046 public synchronized void insert(Object locationId) { 2047 try { 2048 RootWrapper rootWrapper = getRootWrapper(locationId); 2049 if (rootWrapper == null) { 2050 add(null, 0, locationId); 2051 return; 2052 } 2053 2054 RBTreeNode previous = (RBTreeNode) getFloorNode(rootWrapper, locationId); 2055 2056 RBTreeNode next = (RBTreeNode) getCeilNode(rootWrapper, locationId); 2057 if (previous != null && next != null) { 2058 adjustDistance(rootWrapper, previous.key, next.key, 1); 2059 add(previous.key, 1, locationId); 2060 return; 2061 } 2062 2063 if (previous != null) { 2064 add(previous.key, 1, locationId); 2065 } 2066 else if (next != null) { 2067 add(next.key, -1, locationId); 2068 } 2069 else { 2070 add(null, 0, locationId); 2071 } 2072 } 2073 finally { 2074 } 2075 } 2076 2077 public void showSequentially() { 2078 if (rootOfRootWrapperList.getRoot() != null) 2079 show(rootOfRootWrapperList.getRoot()); 2080 else 2081 ; 2082 } 2083 2084 private void showTree(RBTreeNode root) { 2085 if (root.left != null) showTree(root.left); 2086 RBTreeNode next = (RBTreeNode) getNext(root); 2087 int dis = 0; 2088 if (next != null) { 2089 dis = getDistance(root.getKey(), next.getKey(), false); 2090 } 2091 if (root.right != null) showTree(root.right); 2092 } 2093 2094 private void show(RBTreeNode root) { 2095 if (root.left != null) show(root.left); 2096 if (root.key instanceof RootWrapper) { 2097 RBTreeNode r = ( (RootWrapper) root.getKey()).getRoot(); 2098 if (r.getKey() instanceof RootWrapper) 2099 show(r); 2100 else { 2101 ; 2102 showTree(r); 2103 } 2104 } 2105 else 2106 ; 2107 if (root.right != null) show(root.right); 2108 } 2109 2110} 2111 | Popular Tags |