KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > daffodilwoods > rbtreesizesequence > RBTreeSizeSequence


1 /**
2 * Copyright (c) 2003 Daffodil Software Ltd., India all rights reserved.
3 * This library is free software; you can redistribute it and/or modify
4 * it under the terms of version 2.1 of the GNU Lesser General Public License as
5 * published by the Free Software Foundation.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU Lesser General Public License for more details.
11 *
12 * You should have received a copy of the GNU Lesser General Public License
13 * along with this library; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15 */

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 JavaDoc(
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 JavaDoc("adapter's distanceStatus can't be " +
56                                          adp.getDistanceStatus());
57     }
58     Object JavaDoc locationId1 = adp.getLocationId1();
59     Object JavaDoc 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 JavaDoc locationId1 = adp.getLocationId1();
86         Object JavaDoc 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 JavaDoc locationId1, Object JavaDoc 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 JavaDoc locationId1, Object JavaDoc 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 JavaDoc locationId1, Object JavaDoc 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 JavaDoc adpLocationId1 = adp.getLocationId1();
141       Object JavaDoc 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 JavaDoc locationId1, Object JavaDoc 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         /**
172          * if locationId1 and locationId2 lie in between locationIds represented by adapter,
173          * we have to fire distanceNotifyEvent.
174          * */

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 JavaDoc 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 JavaDoc locationIdFrom, Object JavaDoc locationIdTo) {
221     int result = getDistance(locationIdFrom, locationIdTo, false);
222     return result;
223   }
224
225   public int getDistance(Object JavaDoc locationIdFrom, Object JavaDoc locationIdTo,
226                          boolean force) {
227     if (locationIdFrom == null || locationIdTo == null) {
228          ;
229       throw new IllegalArgumentException JavaDoc(
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 JavaDoc 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 JavaDoc from = locationIdFrom;
285       Object JavaDoc 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) { // locationIdFrom is within rootWrapperFrom
328
Object JavaDoc 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) { // locationIdTo is within rootWrapperTo
338
Object JavaDoc 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 JavaDoc firstKeyRootWrapperFrom = firstKey(rootWrapperFrom);
350     Object JavaDoc 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 JavaDoc nextRootWrapperFirst = firstKey(nextRootWrapper);
364       Object JavaDoc 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 JavaDoc firstKey = firstKey(nextRootWrapper);
374     Object JavaDoc 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 JavaDoc locationIdFrom,
390                           Object JavaDoc locationIdTo) {
391     return getDistance(rootWrapper, locationIdFrom, locationIdTo, false);
392   }
393
394   private int getDistance(RootWrapper rootWrapper, Object JavaDoc locationIdFrom,
395                           Object JavaDoc locationIdTo, boolean force) {
396     int direction = 1;
397     int cmp = compare(locationIdFrom, locationIdTo);
398
399     if (cmp == 0) { //locationIdFrom & locationIdTo are same
400
return 0;
401     }
402     if (cmp > 0) { //locationIdFrom is in the right side of locationIdTo
403
direction = -1;
404       Object JavaDoc 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 JavaDoc 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 JavaDoc rootLocationId, Object JavaDoc 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 JavaDoc locationIdFrom, int distance,
501                    Object JavaDoc key) {
502     if (key == null)
503       throw new IllegalArgumentException JavaDoc(
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 JavaDoc 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 JavaDoc("LocationId does not exist in RBTree");
524     }
525   }
526
527   public int get(Object JavaDoc locationId) {
528     RootWrapper rootWrapper = getRootWrapper(locationId);
529     if (rootWrapper != null) {
530       return ( (Entry) getNode(rootWrapper, locationId)).getDistanceFromParent();
531     }
532     throw new IllegalArgumentException JavaDoc("LocationId does not exist in RBTree");
533   }
534
535   public int getDistanceFromTop(Object JavaDoc 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 JavaDoc("LocationId does not exist in RBTree");
542   }
543
544   public Object JavaDoc getKeyAtDistanceFromTop(int atDistance) {
545     return getKeyAtDistance( ( (Entry) getTopKey()).getKey(), atDistance);
546   }
547
548   public void add(Object JavaDoc 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 JavaDoc locationIdFrom, int atDistance, Object JavaDoc locationId) {
565     try {
566       if (!addAllowed) {
567         return;
568       }
569       if (locationId == null)
570         throw new IllegalArgumentException JavaDoc(
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 JavaDoc("Can't add " + locationId +
583                                            " at distance " + atDistance +
584                                            " from " + locationIdFrom);
585       }
586
587       /* Find the rootWrapper for which subLocationIdFrom is present
588        if not such rootWrapper is there then make a new rootWrapper for that
589        Call the put(...) for that rootWrapper with the same parameters
590        Check for maxOffSet
591        call remove if maxOffSet condition is not satisfied*/

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         /* when new tset is formed which is not the only tset in the map,
602             we have to check the possibility of joining the series...*/

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 JavaDoc("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 JavaDoc 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 JavaDoc 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 JavaDoc firstKeyRootWrapperNext = firstKey(rootWrapperNext);
655       if (treeSizeSequenceUser.canJoin(locationId, firstKeyRootWrapperNext)) {
656
657         Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc lastKeyRootWrapperPrevious = lastKey(rootWrapperPrevious);
725       if (treeSizeSequenceUser.canJoin(lastKeyRootWrapperPrevious, locationId)) {
726
727         Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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); //AB
820
int distance2 = getDistance( (rootWrapperNext.getRoot().getKey()),
821                                     locationId, true); //CB
822
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 JavaDoc 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   /** From CLR **/
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   /** From CLR **/
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 JavaDoc 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 { // rootWrapperCeil != null
999
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 { // distance <= 0
1010
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 JavaDoc askedFor) {
1039    if (compare(result.getLocationId(), firstKey(rootWrapper)) == 0)
1040      return;
1041    if (result.getDistance() > distance) {
1042      show();
1043      throw new InternalError JavaDoc("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 JavaDoc 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 JavaDoc locationIdFrom,
1100                            Object JavaDoc 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 JavaDoc locationIdFrom, Object JavaDoc locationIdTo,
1108                            int delta) {
1109    if (locationIdFrom == null || locationIdTo == null)
1110      throw new IllegalArgumentException JavaDoc("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 JavaDoc 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 { /*callSizeChange(delta);*/}
1138  }
1139
1140  public void adjustDistance(RootWrapper rootWrapper, Object JavaDoc locationIdFrom,
1141                             Object JavaDoc locationIdTo, int delta) {
1142    adjustDistanceFromParent( (Entry) rootWrapper.getRoot(), locationIdFrom,
1143                             locationIdTo, delta);
1144  }
1145
1146  private void adjustDistanceFromParent(Entry root, Object JavaDoc locationIdFrom,
1147                                        Object JavaDoc 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)) { // both locationIds are to the left of the node
1153
node = (Entry) root.left;
1154    }
1155    else if ( (cmp1 >= 0) && (cmp2 >= 0)) { // both locationIds are to the right of the node
1156
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 JavaDoc locationId1, Object JavaDoc 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 JavaDoc locationIdFrom, Object JavaDoc locationIdTo) {
1186    int result = 0;
1187    int swap = 1;
1188    if (compare(locationIdFrom, locationIdTo) > 0) {
1189      Object JavaDoc 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    /* if(rootWrapperFrom == rootWrapperTo){
1206     result = refreshSegment(rootWrapperFrom, locationIdFrom, locationIdTo) * swap;
1207                        D.setReturnValue(D.o(result));
1208                        fireDistanceEvent();
1209                        return result;
1210                    }
1211     */

1212    Object JavaDoc 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 JavaDoc 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 JavaDoc locationIdFrom, Object JavaDoc locationIdTo) {
1262    int result = 0;
1263    try {
1264      if (compare(locationIdFrom, locationIdTo) > 0) {
1265        Object JavaDoc 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 JavaDoc 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 JavaDoc 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        /* RootWrapper nextRootWrapper = getNextRootWrapper(floorRootWrapper);
1328         if(compareRootWrappers(ceilRootWrapper, nextRootWrapper) != 0){
1329         ;
1330                        result = Integer.MIN_VALUE;
1331                        D.setReturnValue("Integer.MIN_VALUE");
1332                        return Integer.MIN_VALUE;
1333                    }
1334         if(compare(lastKey(floorRootWrapper), locationIdFrom) != 0){
1335         ;
1336                        result = Integer.MIN_VALUE;
1337                        D.setReturnValue("Integer.MIN_VALUE");
1338                        return Integer.MIN_VALUE;
1339                    }
1340                    if(compare(firstKey(ceilRootWrapper), locationIdTo) != 0){
1341         ;
1342                        result = Integer.MIN_VALUE;
1343                        D.setReturnValue("Integer.MIN_VALUE");
1344                        return Integer.MIN_VALUE;
1345                    }
1346                    treeSizeSequenceUser.traceDistance(locationIdFrom, locationIdTo, Integer.MAX_VALUE);
1347                    result = Integer.MIN_VALUE;*/

1348        return Integer.MIN_VALUE;
1349      }
1350      result = refreshSegment(floorRootWrapper, locationIdFrom, locationIdTo);
1351      fireDistanceEvent();
1352      return result;
1353    }
1354    finally { /*callSizeChange(result);*/}
1355  }
1356
1357  private int refreshSegment(RootWrapper rootWrapper, Object JavaDoc locationIdFrom,
1358                             Object JavaDoc 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 JavaDoc locationIdFrom,
1376                                 Object JavaDoc locationIdTo) {
1377    collectNodesWithIn(rootWrapper.getRoot(), locationIdFrom, locationIdTo);
1378    for (int i = 0; i < nodeList.size(); i++) {
1379      Object JavaDoc toRemove = nodeList.get(i);
1380      remove(rootWrapper, toRemove);
1381    }
1382    nodeList = null;
1383  }
1384
1385  private void collectNodesWithIn(RBTreeNode root, Object JavaDoc locationIdFrom,
1386                                  Object JavaDoc 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 JavaDoc locationId1, Object JavaDoc locationId2, Object JavaDoc obj) {
1398    return isBetween(locationId1, locationId2, obj, true);
1399  }
1400
1401  private boolean isBetween(Object JavaDoc locationId1, Object JavaDoc locationId2, Object JavaDoc obj,
1402                            boolean exactlyInBetween) {
1403    int cmp = compare(locationId1, locationId2);
1404    if (cmp > 0) {
1405      Object JavaDoc 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 JavaDoc locationIdFrom, Object JavaDoc 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 JavaDoc locationIdLastF = lastKey(rootWrapperFrom);
1437    RootWrapper rootWrapperNext = getNextRootWrapper(rootWrapperFrom);
1438    Object JavaDoc 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 JavaDoc locationId) {
1483    RootWrapper temp;
1484    if ( (temp = getRootWrapper(locationId)) != null)
1485      throw new InternalError JavaDoc("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 JavaDoc locationIdFrom,
1494                             Object JavaDoc 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 JavaDoc("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 JavaDoc("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 JavaDoc locationIdFrom, Object JavaDoc 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 JavaDoc("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 JavaDoc obj = firstKey(rootWrapper2);
1565    Object JavaDoc oldRootKey = rootWrapper2.getRoot().getKey();
1566    if (obj == oldRootKey) {
1567
1568      RBTreeNode rightNode = rootWrapper2.getRoot().getRight();
1569      if (rightNode != null) {
1570        Object JavaDoc 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); // BA
1581

1582    remove(rootWrapper2, obj);
1583
1584    int distanceFromRootOfRootWrapper1 = distanceBetweenRoots +
1585        disFromRootToFirst; //CA
1586
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); //DB
1594
int distanceFromRootOfRootWrapper2 = dis + disFromRootToFirst; //DA
1595
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 JavaDoc obj,
1605                                RootWrapper rootWrapper2,
1606                                int distanceFromRootOfRootWrapper2) {
1607    if (rootWrapper1 == null || rootWrapper2 == null)
1608      throw new InternalError JavaDoc("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 JavaDoc obj,
1673                                 int distanceFromRoot) {
1674    int blackHeight1 = rootWrapper1.getBlackHeight();
1675
1676    int blackHeight2 = mainRootWrapper.getBlackHeight();
1677
1678    if (blackHeight2 < blackHeight1)
1679      throw new InternalError JavaDoc("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 JavaDoc("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 JavaDoc 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 JavaDoc("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 JavaDoc("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 JavaDoc 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    /**
1798     * will be called after markinvalid
1799     * */

1800  }
1801
1802  public void breakTree(RootWrapper mainRootWrapper, Object JavaDoc 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 JavaDoc rootKey = root.getKey();
1810    int leftNodeDFP = 0;
1811    int rightNodeDFP = 0;
1812    Object JavaDoc leftNodeKey = null;
1813    Object JavaDoc 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) { // root is the break point.............
1826
if (leftNode == null && rightNode == null) { // left & right both nodes to the rootNode are null................
1827
return;
1828      }
1829      RootWrapper tempLeft = new RootWrapper(); // tempLeft is made.......
1830
RootWrapper tempRight = new RootWrapper(); // tempRight is made........
1831

1832      boolean joinWithLeft = true;
1833      boolean joinWithRight = true;
1834      if (rootWrapperLeft.getRoot() == null) { // rootWrapperLeft yet not made....................
1835
setRootWrapperRoot(rootWrapperLeft, leftNode);
1836        joinWithLeft = false;
1837      }
1838      else if (leftNode != null) { // rootWrapperLeft is there, as well some nodes are there to the left side of the rootNode...................
1839
setRootWrapperRoot(tempLeft, leftNode);
1840      }
1841      if (rootWrapperRight.getRoot() == null) { // rootWrapperRight yet not made....................
1842
setRootWrapperRoot(rootWrapperRight, rightNode);
1843        joinWithRight = false;
1844      }
1845      else if (rightNode != null) { // rootWrapperRight is there, as well some nodes are there to the right side of the rootNode...................
1846
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) { // obj is in left side............
1863
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) { // rootWrapperRight yet not made............
1875
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 { // rootWrapperRight is already there...............
1891
if (rightNode == null) { // no tempRight will be made..............
1892
Object JavaDoc 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 JavaDoc 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 { // obj is in the right side.............
1929
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) { // rootWrapperLeft yet not made............
1941
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 { // rootWrapperLeft is already there...............
1957
if (leftNode == null) { // no tempLeft will be made..............
1958
Object JavaDoc 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 JavaDoc 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 JavaDoc getKeyAtDistance(Object JavaDoc key, int distance) {
2029    return getLocationInformation(key, distance).getLocationId();
2030  }
2031
2032  public synchronized void delete(Object JavaDoc 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 JavaDoc 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