KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > daffodilwoods > rbtreesizesequence > utils > rbtree > SegmentedRedBlackTree


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.utils.rbtree;
19
20 import java.util.TreeSet JavaDoc;
21 import java.util.ArrayList JavaDoc;
22 import java.util.Comparator JavaDoc;
23 import java.util.Iterator JavaDoc;
24
25 public class SegmentedRedBlackTree {
26
27         private static final boolean BLACK = true;
28         private static final boolean RED = false;
29
30         private static final boolean LEFT = true;
31         private static final boolean RIGHT = false;
32
33         protected RootWrapper rootOfRootWrapperList; //
34
protected Comparator JavaDoc comparator; // comparator for keys in trees
35

36         public SegmentedRedBlackTree() {
37                 rootOfRootWrapperList = new RootWrapper();
38         }
39
40         public SegmentedRedBlackTree(Comparator JavaDoc c) {
41                 comparator = c;
42         }
43
44         protected void addRootWrapperToList(RootWrapper rootWrapper){
45         put(rootOfRootWrapperList, rootWrapper);
46         }
47
48         protected void removeFromRootWrapperList(RootWrapper rootWrapper){
49                         remove(rootOfRootWrapperList, rootWrapper, false);
50         }
51
52         protected RBTreeNode createRBTreeNode(Object JavaDoc key, RBTreeNode parent){
53                 return new RBTreeNode(key, parent);
54         }
55
56         protected void preSwapPosition(RootWrapper rootWrapper, RBTreeNode x, RBTreeNode y){
57         }
58
59         protected void postSwapPosition(RootWrapper rootWrapper){
60         }
61
62         public boolean canContain(RootWrapper rootWrapper, Object JavaDoc key){
63                         boolean result =
64                                 ( compare(firstKey(rootWrapper), key) <= 0 )
65                                                                         &&
66                                 ( compare(lastKey(rootWrapper), key) >= 0 );
67                         return result;
68         }
69
70         private int compare(RootWrapper rootWrapper, Object JavaDoc obj1, Object JavaDoc obj2){
71                 if(obj1 == obj2) return 0;
72                 if(obj1 instanceof RootWrapper && obj2 instanceof RootWrapper)
73                         return compare(((RootWrapper)obj1).getRoot().getKey(), ((RootWrapper)obj2).getRoot().getKey());
74                 return compare(obj1, obj2);
75         }
76
77         protected int compare(Object JavaDoc obj1, Object JavaDoc obj2){
78                 if(obj1 == obj2) return 0;
79                 if(obj1 instanceof RootWrapper && obj2 instanceof RootWrapper)
80                         return compare(((RootWrapper)obj1).getRoot().getKey(), ((RootWrapper)obj2).getRoot().getKey());
81                 return (comparator==null ? ((Comparable JavaDoc)obj1).compareTo(obj2) :
82                                  comparator.compare(obj1, obj2));
83         }
84
85         public boolean containsKey(RootWrapper rootWrapper, Object JavaDoc key){
86                 return getNode(rootWrapper, key) != null;
87         }
88
89         public RBTreeNode getNode(RootWrapper rootWrapper, Object JavaDoc key){
90                 RBTreeNode root = rootWrapper.getRoot();
91                 while (root != null) {
92                         int cmp = compare(rootWrapper, key, root.key);
93                         if (cmp == 0)
94                                 return root;
95                         else if (cmp < 0)
96                                 root = root.left;
97                         else
98                                 root = root.right;
99                 }
100                 return null;
101         }
102
103         public Comparator JavaDoc getComparator(){
104                 return comparator;
105         }
106
107         public Object JavaDoc firstKey(RootWrapper rootWrapper){
108                 return rootWrapper == null ? null : getKey(firstNode(rootWrapper));
109         }
110
111         public Object JavaDoc lastKey(RootWrapper rootWrapper){
112
113                 return rootWrapper == null ? null : getKey(lastNode(rootWrapper));
114         }
115
116         public Object JavaDoc getKey(RBTreeNode node){
117                 if (node==null)
118                         return null;
119                 return node.key;
120         }
121
122         protected RBTreeNode firstNode(RootWrapper rootWrapper) {
123                 RBTreeNode root = rootWrapper.getRoot();
124                 if (root != null)
125                         while (root.left != null)
126                                 root = root.left;
127                 return root;
128         }
129
130         protected RBTreeNode lastNode(RootWrapper rootWrapper) {
131                 RBTreeNode root = rootWrapper.getRoot();
132                 if (root != null)
133                         while (root.right != null)
134                                 root = root.right;
135                 return root;
136         }
137
138         public RBTreeNode getCeilNode(RootWrapper rootWrapper, Object JavaDoc key) {
139                 RBTreeNode root = rootWrapper.getRoot();
140                 if (root==null){
141                         return null;
142                 }
143
144                 while (true) {
145                         int cmp = compare(rootWrapper, key, root.key);
146                         if (cmp == 0) {
147                                 return root;
148                         } else if (cmp < 0) {
149                                 if (root.left != null)
150                                         root = root.left;
151                                 else{
152                                         return root;
153                                 }
154                         } else {
155                                 if (root.right != null) {
156                                         root = root.right;
157                                 } else {
158                                         RBTreeNode parent = root.parent;
159                                         RBTreeNode ch = root;
160                                         while (parent != null && ch == parent.right) {
161                                                 ch = parent;
162                                                 parent = parent.parent;
163                                         }
164                                         return parent;
165                                 }
166                         }
167                 }
168         }
169
170         public RBTreeNode getFloorNode(RootWrapper rootWrapper, Object JavaDoc key) {
171               RBTreeNode root = rootWrapper.getRoot();
172                 if (root==null){
173                         return null;
174                 }
175                 while (true) {
176                         int cmp = compare(rootWrapper, key, root.key);
177                         if (cmp == 0) {
178                                 return root;
179                         } else if (cmp > 0) {
180                                 if (root.right != null)
181                                         root = root.right;
182                                 else{
183                                         return root;
184                                 }
185                         } else {
186                                 if (root.left != null) {
187                                         root = root.left;
188                                 } else {
189                                         RBTreeNode parent = root.parent;
190                                         RBTreeNode ch = root;
191                                         while (parent != null && ch == parent.left) {
192                                                 ch = parent;
193                                                 parent = parent.parent;
194                                         }
195                                         return parent;
196                                 }
197                         }
198                 }
199         }
200
201         public RBTreeNode getNextNode(RootWrapper rootWrapper, Object JavaDoc key) {
202                 RBTreeNode root = rootWrapper.getRoot();
203                 if (root==null)
204                         return null;
205
206                 while (true) {
207                         int cmp = compare(rootWrapper, key, root.key);
208                         if (cmp < 0) {
209                                 if (root.left != null)
210                                         root = root.left;
211                                 else
212                                         return root;
213                         } else {
214                                 if (root.right != null) {
215                                         root = root.right;
216                                 } else {
217                                         RBTreeNode parent = root.parent;
218                                         RBTreeNode ch = root;
219                                         while (parent != null && ch == parent.right) {
220                                                 ch = parent;
221                                                 parent = parent.parent;
222                                         }
223                                         return parent;
224                                 }
225                         }
226                 }
227         }
228
229         public RBTreeNode getPrecedingNode(RootWrapper rootWrapper, Object JavaDoc key) {
230                 RBTreeNode root = rootWrapper.getRoot();
231                 if (root==null)
232                         return null;
233
234                 while (true) {
235                         int cmp = compare(rootWrapper, key, root.key);
236                         if (cmp > 0) {
237                                 if (root.right != null)
238                                         root = root.right;
239                                 else
240                                         return root;
241                         } else {
242                                 if (root.left != null) {
243                                         root = root.left;
244                                 } else {
245                                         RBTreeNode parent = root.parent;
246                                         RBTreeNode ch = root;
247                                         while (parent != null && ch == parent.left) {
248                                                 ch = parent;
249                                                 parent = parent.parent;
250                                         }
251                                         return parent;
252                                 }
253                         }
254                 }
255         }
256
257         public void invokeFixAfterInsertion(RootWrapper rootWrapper, RBTreeNode x) {
258                 if(x != null)
259                         fixAfterInsertion(rootWrapper, x);
260         }
261
262
263         /** From CLR **/
264         private void fixAfterInsertion(RootWrapper rootWrapper, RBTreeNode x) {
265                 x.color = RED;
266                 while (x != null && x != rootWrapper.getRoot() && x.parent.color == RED) {
267                         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
268                                 RBTreeNode y = rightOf(parentOf(parentOf(x)));
269                                 if (colorOf(y) == RED) {
270                                         setColor(parentOf(x), BLACK);
271                                         setColor(y, BLACK);
272                                         setColor(parentOf(parentOf(x)), RED);
273                                         x = parentOf(parentOf(x));
274                                 } else {
275                                         if (x == rightOf(parentOf(x))) {
276                                                 x = parentOf(x);
277                                                 rotateLeft(rootWrapper, x);
278                                         }
279                                         setColor(parentOf(x), BLACK);
280                                         setColor(parentOf(parentOf(x)), RED);
281                                         if (parentOf(parentOf(x)) != null)
282                                                 rotateRight(rootWrapper, parentOf(parentOf(x)));
283                                 }
284                         } else {
285                                 RBTreeNode y = leftOf(parentOf(parentOf(x)));
286                                 if (colorOf(y) == RED) {
287                                         setColor(parentOf(x), BLACK);
288                                         setColor(y, BLACK);
289                                         setColor(parentOf(parentOf(x)), RED);
290                                         x = parentOf(parentOf(x));
291                                 } else {
292                                         if (x == leftOf(parentOf(x))) {
293                                                 x = parentOf(x);
294                                                 rotateRight(rootWrapper, x);
295                                         }
296                                         setColor(parentOf(x), BLACK);
297                                         setColor(parentOf(parentOf(x)), RED);
298                                         if (parentOf(parentOf(x)) != null)
299                                                 rotateLeft(rootWrapper, parentOf(parentOf(x)));
300                                 }
301                         }
302                 }
303                 rootWrapper.getRoot().color = BLACK;
304         }
305
306         /** From CLR **/
307         protected void rotateLeft(RootWrapper rootWrapper, RBTreeNode p) {
308                 RBTreeNode r = p.right;
309                 p.right = r.left;
310                 if (r.left != null)
311                         r.left.parent = p;
312                 r.parent = p.parent;
313                 if (p.parent == null)
314                         setRootWrapperRoot(rootWrapper, r);
315                 else if (p.parent.left == p)
316                         p.parent.left = r;
317                 else
318                         p.parent.right = r;
319                 r.left = p;
320                 p.parent = r;
321         }
322
323         /** From CLR **/
324         protected void rotateRight(RootWrapper rootWrapper, RBTreeNode p) {
325
326                 RBTreeNode l = p.left;
327                 p.left = l.right;
328                 if (l.right != null) l.right.parent = p;
329                         l.parent = p.parent;
330                 if (p.parent == null)
331                         setRootWrapperRoot(rootWrapper, l);
332                 else if (p.parent.right == p)
333                         p.parent.right = l;
334                 else p.parent.left = l;
335                         l.right = p;
336                 p.parent = l;
337         }
338
339         /**
340          * Balancing operations.
341          *
342          * Implementations of rebalancings during insertion and deletion are
343          * slightly different than the CLR version. Rather than using dummy
344          * nilnodes, we use a set of accessors that deal properly with null. They
345          * are used to avoid messiness surrounding nullness checks in the main
346          * algorithms.
347          */

348
349         private static boolean colorOf(RBTreeNode p) {
350                 return (p == null ? BLACK : p.color);
351         }
352
353         private static RBTreeNode parentOf(RBTreeNode p) {
354                 return (p == null ? null: p.parent);
355         }
356
357         private static void setColor(RBTreeNode p, boolean c) {
358                 if (p != null) p.color = c;
359         }
360
361         private static RBTreeNode leftOf(RBTreeNode p) {
362                 return (p == null)? null: p.left;
363         }
364
365         private static RBTreeNode rightOf(RBTreeNode p) {
366                 return (p == null)? null: p.right;
367         }
368
369         protected boolean remove(RootWrapper rootWrapper, Object JavaDoc key) {
370                 return remove(rootWrapper, key, true);
371         }
372
373
374         private boolean remove(RootWrapper rootWrapper, Object JavaDoc key, boolean removeFromRootWrapperListIfEmpty) {
375
376                 RBTreeNode p = getNode(rootWrapper, key);
377                 if(p != null){
378                         if(removeFromRootWrapperListIfEmpty && compare(p.getKey(), rootWrapper.getRoot().getKey()) == 0 && p.left == null && p.right == null){
379                                 removeFromRootWrapperList(rootWrapper);
380                                 return false;
381                         }
382                         RBTreeNode node = deleteNodeWithoutFix(rootWrapper, p);
383                         invokeFixAfterDeletion(rootWrapper, node);
384                 }
385                 return true;
386         }
387
388         /**
389          * Delete node p, and then rebalance the tree.
390          */

391         public RBTreeNode deleteNodeWithoutFix(RootWrapper rootWrapper, RBTreeNode p) {
392
393                 if (p.left != null && p.right != null) {
394                         RBTreeNode s = successor(p);
395                         swapPosition(rootWrapper, s, p);
396                 }
397                 RBTreeNode replacement = (p.left != null ? p.left : p.right);
398
399                 if (replacement != null) {
400                         replacement.parent = p.parent;
401                         if (p.parent == null){
402                                 setRootWrapperRoot(rootWrapper, replacement);
403                         }
404                         else if (p == p.parent.left)
405                                 replaceParentLeft(p, replacement);
406                         else
407                                 replaceParentRight(p, replacement);
408
409                         p.left = p.right = p.parent = null;
410
411                         if (p.color == BLACK)
412                                 return replacement;
413                 } else if (p.parent == null) { // return if we are the only node.
414
setRootWrapperRoot(rootWrapper, null);
415                 } else { // No children. Use self as phantom replacement and unlink.
416
if (p.color == BLACK)
417                                 fixAfterDeletion(rootWrapper, p);
418                         if (p.parent != null) {
419                                 if (p == p.parent.left)
420                                         p.parent.left = null;
421                                 else if (p == p.parent.right)
422                                         p.parent.right = null;
423                                 p.parent = null;
424                         }
425                 }
426                 return null;
427         }
428         protected void replaceParentLeft(RBTreeNode p, RBTreeNode replacement){
429                 p.parent.left = replacement;
430         }
431
432         protected void replaceParentRight(RBTreeNode p, RBTreeNode replacement){
433                 p.parent.right = replacement;
434         }
435
436         public void invokeFixAfterDeletion(RootWrapper rootWrapper, RBTreeNode x) {
437                 if(x != null)
438                         fixAfterDeletion(rootWrapper, x);
439         }
440
441         /** From CLR **/
442         private void fixAfterDeletion(RootWrapper rootWrapper, RBTreeNode x) {
443                 while (x != rootWrapper.getRoot() && colorOf(x) == BLACK) {
444                         if (x == leftOf(parentOf(x))) {
445                                 RBTreeNode sib = rightOf(parentOf(x));
446
447                                 if (colorOf(sib) == RED) {
448                                         setColor(sib, BLACK);
449                                         setColor(parentOf(x), RED);
450                                         rotateLeft(rootWrapper, parentOf(x));
451                                         sib = rightOf(parentOf(x));
452                                 }
453
454                                 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
455                                         setColor(sib, RED);
456                                         x = parentOf(x);
457                                 } else {
458                                         if (colorOf(rightOf(sib)) == BLACK) {
459                                                 setColor(leftOf(sib), BLACK);
460                                                 setColor(sib, RED);
461                                                 rotateRight(rootWrapper, sib);
462                                                 sib = rightOf(parentOf(x));
463                                         }
464                                         setColor(sib, colorOf(parentOf(x)));
465                                         setColor(parentOf(x), BLACK);
466                                         setColor(rightOf(sib), BLACK);
467                                         rotateLeft(rootWrapper, parentOf(x));
468                                         x = rootWrapper.getRoot();
469                                 }
470                         } else { // symmetric
471
RBTreeNode sib = leftOf(parentOf(x));
472
473                                 if (colorOf(sib) == RED) {
474                                         setColor(sib, BLACK);
475                                         setColor(parentOf(x), RED);
476                                         rotateRight(rootWrapper, parentOf(x));
477                                         sib = leftOf(parentOf(x));
478                                 }
479
480                                 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
481                                         setColor(sib, RED);
482                                         x = parentOf(x);
483                                 } else {
484                                         if (colorOf(leftOf(sib)) == BLACK) {
485                                                 setColor(rightOf(sib), BLACK);
486                                                 setColor(sib, RED);
487                                                 rotateLeft(rootWrapper, sib);
488                                                 sib = leftOf(parentOf(x));
489                                         }
490                                         setColor(sib, colorOf(parentOf(x)));
491                                         setColor(parentOf(x), BLACK);
492                                         setColor(leftOf(sib), BLACK);
493                                         rotateRight(rootWrapper, parentOf(x));
494                                         x = rootWrapper.getRoot();
495                                 }
496                         }
497                 }
498                 setColor(x, BLACK);
499         }
500
501         /**
502          * Swap the linkages of two nodes in a tree.
503          */

504         private void swapPosition(RootWrapper rootWrapper, RBTreeNode x, RBTreeNode y) {
505                 preSwapPosition(rootWrapper, x, y);
506                 RBTreeNode px = x.parent, lx = x.left, rx = x.right;
507                 RBTreeNode py = y.parent, ly = y.left, ry = y.right;
508                 boolean xWasLeftChild = px != null && x == px.left;
509                 boolean yWasLeftChild = py != null && y == py.left;
510
511                 if (x == py) { // x was y's parent
512
x.parent = y;
513                         if (yWasLeftChild) {
514                                 y.left = x;
515                                 y.right = rx;
516                         } else {
517                                 y.right = x;
518                                 y.left = lx;
519                         }
520                 } else {
521                         x.parent = py;
522                         if (py != null) {
523                                 if (yWasLeftChild)
524                                         py.left = x;
525                                 else
526                                         py.right = x;
527                         }
528                         y.left = lx;
529                         y.right = rx;
530                 }
531
532                 if (y == px) { // y was x's parent
533
y.parent = x;
534                         if (xWasLeftChild) {
535                                 x.left = y;
536                                 x.right = ry;
537                         } else {
538                                 x.right = y;
539                                 x.left = ly;
540                         }
541                 } else {
542                         y.parent = px;
543                         if (px != null) {
544                                 if (xWasLeftChild)
545                                         px.left = y;
546                                 else
547                                         px.right = y;
548                         }
549                         x.left = ly;
550                         x.right = ry;
551                 }
552
553                 if (x.left != null)
554                         x.left.parent = x;
555                 if (x.right != null)
556                         x.right.parent = x;
557                 if (y.left != null)
558                         y.left.parent = y;
559                 if (y.right != null)
560                         y.right.parent = y;
561
562                 boolean c = x.color;
563                 x.color = y.color;
564                 y.color = c;
565
566                 if (rootWrapper.getRoot() == x)
567                         setRootWrapperRoot(rootWrapper, y);
568                 else if (rootWrapper.getRoot() == y)
569                         setRootWrapperRoot(rootWrapper, x);
570                 postSwapPosition(rootWrapper);
571         }
572
573         /**
574          * Returns the successor of the specified RBTreeNode, or null if no such.
575          */

576         private RBTreeNode successor(RBTreeNode t) {
577                 if (t == null)
578                         return null;
579                 else if (t.right != null) {
580                         RBTreeNode p = t.right;
581                         while (p.left != null)
582                                 p = p.left;
583                         return p;
584                 } else {
585                         RBTreeNode p = t.parent;
586                         RBTreeNode ch = t;
587                         while (p != null && ch == p.right) {
588                                 ch = p;
589                                 p = p.parent;
590                         }
591                         return p;
592                 }
593         }
594
595         protected void put(RootWrapper rootWrapper, Object JavaDoc key){
596                 RBTreeNode x = putWithoutFix(rootWrapper, key);
597                 invokeFixAfterInsertion(rootWrapper, x);
598         }
599
600         /**
601          *
602          * @param rootWrapper rootWrapper to specify the tree in which key is to be inserted
603          * @param key value to be inserted into the tree,specified with the rootWrapper.
604          *
605          * @return node to which invokeFixAfterInsertion() is to be called
606          *
607          */

608
609         public RBTreeNode putWithoutFix(RootWrapper rootWrapper, Object JavaDoc key){
610                         RBTreeNode t = rootWrapper.getRoot();
611                         if (t == null) {
612                                 rootWrapper.root = createRBTreeNode(key, null);
613                                 return rootWrapper.getRoot();// new root is created
614
}
615                         while (true) {
616                                 int cmp = compare(rootWrapper, key, t.key);
617                                 if (cmp == 0) {
618                                     return null;
619                                 } else if (cmp < 0) {
620                                         if (t.left != null) {
621                                                 t = t.left;
622                                         } else {
623                                                 t.left = createRBTreeNode(key, t);
624                                                 return t.left;
625                                         }
626                                 } else { // cmp > 0
627
if (t.right != null) {
628                                                 t = t.right;
629                                         } else {
630                                                 t.right = createRBTreeNode(key, t);
631                                                 return t.right;
632                                         }
633                                 }
634                         }
635         }
636
637         protected void setRootWrapperRoot(RootWrapper rootWrapper, RBTreeNode node){
638                 rootWrapper.setRoot(node);
639         }
640
641     public void breakTree(RootWrapper mainRootWrapper, Object JavaDoc obj, RootWrapper rootWrapperLeft, RootWrapper rootWrapperRight){
642         RBTreeNode root = mainRootWrapper.getRoot();
643         if( root == null ){
644             return;
645         }
646         Object JavaDoc rootKey = root.getKey();
647         Object JavaDoc leftNodeKey = null;
648         Object JavaDoc rightNodeKey = null;
649         RBTreeNode leftNode = root.left;
650         RBTreeNode rightNode = root.right;
651         if(leftNode != null){
652             leftNodeKey = leftNode.getKey();
653         }
654         if(rightNode != null){
655             rightNodeKey = rightNode.key;
656         }
657         int cmp = compare(rootKey, obj);
658         if(cmp == 0){// root is the break point.............
659
if(leftNode == null && rightNode == null){// left & right both nodes to the rootNode are null................
660
return;
661             }
662             RootWrapper tempLeft = new RootWrapper();// tempLeft is made.......
663
RootWrapper tempRight = new RootWrapper();// tempRight is made........
664

665             boolean joinWithLeft = true;
666             boolean joinWithRight = true;
667             if(rootWrapperLeft.getRoot() == null){// rootWrapperLeft yet not made....................
668
setRootWrapperRoot(rootWrapperLeft, leftNode);
669                 joinWithLeft = false;
670             }
671             else if(leftNode != null){// rootWrapperLeft is there, as well some nodes are there to the left side of the rootNode...................
672
setRootWrapperRoot(tempLeft, leftNode);
673             }
674             if(rootWrapperRight.getRoot() == null){// rootWrapperRight yet not made....................
675
setRootWrapperRoot(rootWrapperRight, rightNode);
676                 joinWithRight = false;
677             }
678             else if(rightNode != null){// rootWrapperRight is there, as well some nodes are there to the right side of the rootNode...................
679
setRootWrapperRoot(tempRight, rightNode);
680             }
681
682             if(joinWithLeft){
683                 rootWrapperLeft.setRoot(joinTrees(rootWrapperLeft, tempLeft).getRoot());
684             }
685             if(joinWithRight){
686                 rootWrapperRight.setRoot(joinTrees(rootWrapperRight, tempRight).getRoot());
687             }
688             return;
689         }
690         else if( cmp > 0){// obj is in left side............
691
if(leftNode == null && rightNode == null){
692                 if(rootWrapperRight.getRoot() == null){
693                     setRootWrapperRoot(rootWrapperRight, root);
694                 }
695                 else {
696                     makeLinksNull(root);
697                     put(rootWrapperRight, rootKey);
698                 }
699                 return;
700             }
701             if(rootWrapperRight.getRoot() == null){// rootWrapperRight yet not made............
702
if(rightNode != null){
703                     setRootWrapperRoot(rootWrapperRight, rightNode);
704                     makeLinksNull(root);
705                     put(rootWrapperRight, rootKey);
706                 }
707                 else{
708                     root.left = null;
709                     setRootWrapperRoot(rootWrapperRight, root);
710                 }
711             }
712             else{// rootWrapperRight is already there...............
713
if(rightNode == null){// no tempRight will be made..............
714
Object JavaDoc tempRootRight = rootWrapperRight.getRoot().getKey();
715                     makeLinksNull(root);
716                     put(rootWrapperRight, rootKey);
717                 }
718                 else{
719                     RootWrapper tempRight = new RootWrapper(rightNode);
720                     makeLinksNull(root);
721                     put(tempRight, rootKey);
722
723                     Object JavaDoc rootWrapperRightTempRoot = rootWrapperRight.getRoot().getKey();
724                     rootWrapperRight.setRoot(joinTrees(tempRight, rootWrapperRight).getRoot());
725
726                 }
727             }
728             if(leftNode == null){
729                 return;
730             }
731             setRootWrapperRoot(mainRootWrapper, leftNode);
732             breakTree(mainRootWrapper, obj, rootWrapperLeft, rootWrapperRight);
733             return;
734         }
735         else{// obj is in the right side.............
736
if(leftNode == null && rightNode == null){
737                 if(rootWrapperLeft.getRoot() == null){
738                     setRootWrapperRoot(rootWrapperLeft, root);
739                 }
740                 else {
741                     makeLinksNull(root);
742                     put(rootWrapperLeft, rootKey);
743                 }
744                 return;
745             }
746             if(rootWrapperLeft.getRoot() == null){// rootWrapperLeft yet not made............
747
if(leftNode != null){
748                     setRootWrapperRoot(rootWrapperLeft, leftNode);
749                     makeLinksNull(root);
750                     put(rootWrapperLeft, rootKey);
751                 }
752                 else{
753                     root.right = null;
754                     setRootWrapperRoot(rootWrapperLeft, root);
755                 }
756             }
757             else{// rootWrapperLeft is already there...............
758
if(leftNode == null){// no tempLeft will be made..............
759
Object JavaDoc tempRootLeft = rootWrapperLeft.getRoot().getKey();
760                     makeLinksNull(root);
761                     put(rootWrapperLeft, rootKey);
762                 }
763                 else{
764                     RootWrapper tempLeft = new RootWrapper(leftNode);
765                     makeLinksNull(root);
766                     put(tempLeft, rootKey);
767
768                     Object JavaDoc rootWrapperLeftTempRoot = rootWrapperLeft.getRoot().getKey();
769                     rootWrapperLeft.setRoot(joinTrees(tempLeft, rootWrapperLeft).getRoot());
770                 }
771             }
772             if(rightNode == null){
773                 return;
774             }
775             setRootWrapperRoot(mainRootWrapper, rightNode);
776             breakTree(mainRootWrapper, obj, rootWrapperLeft, rootWrapperRight);
777             return;
778         }
779     }
780
781
782
783         public RootWrapper getRootWrapper(Object JavaDoc locationId){
784                         if(locationId == null ){
785          ;
786                                 throw new IllegalArgumentException JavaDoc("<<<<<<<<<<<<<<<can't pass null to getRoot>>>>>>>>>>>");
787                         }
788                         if(rootOfRootWrapperList == null){
789                                 return null;
790                         }
791                         RBTreeNode root = rootOfRootWrapperList.getRoot();
792                         while (root != null) {
793                                 RootWrapper rootWrapper = (RootWrapper)root.getKey();
794                                 if (canContain(rootWrapper, locationId)){
795                                         return rootWrapper;
796                                 }
797                                 int cmp = compare(locationId, rootWrapper.getRoot().getKey());
798                                 if (cmp < 0)
799                                         root = root.left;
800                                 else
801                                         root = root.right;
802                         }
803                         return null;
804         }
805
806         public Object JavaDoc getCommonAncestor(RootWrapper rootWrapper, Object JavaDoc locationId1, Object JavaDoc locationId2){
807                         int cmp = compare(rootWrapper, locationId1, locationId2);
808                         if(cmp == 0){
809                                 return locationId1;
810                         }
811                         Object JavaDoc result = findCommonRootKey(rootWrapper.getRoot(), locationId1, locationId2);
812                         return result;
813         }
814
815         private Object JavaDoc findCommonRootKey(RBTreeNode root, Object JavaDoc locationId1, Object JavaDoc locationId2){
816                         Object JavaDoc rootLocationId = root.getKey();
817                         int cmp1 = compare(rootLocationId, locationId1 );
818                         int cmp2 = compare(rootLocationId, locationId2 );
819                         if(cmp1 == 0){
820                                 return locationId1;
821                         }
822                         else if(cmp2 == 0){
823                                 return locationId2;
824                         }
825                         if((cmp1 < 0 ) && ( cmp2 < 0 )){
826                                 Object JavaDoc result = findCommonRootKey(root.getRight(), locationId1, locationId2);
827                                 return result;
828                         }
829                         if((cmp1 > 0 ) && ( cmp2 > 0 )){
830                                 Object JavaDoc result = findCommonRootKey(root.getLeft(), locationId1, locationId2);
831                                 return result;
832                         }
833                         return rootLocationId;
834         }
835
836         public RootWrapper getNextRootWrapper(RootWrapper rootWrapper){
837                         if(rootOfRootWrapperList == null){
838                                 return null;
839                         }
840                         RBTreeNode nextNode = getNextNode(rootOfRootWrapperList, rootWrapper);
841                         RootWrapper result;
842                         if(nextNode == null)
843                                 result = null;
844                         else
845                                 result = (RootWrapper)(nextNode.getKey());
846                         return result;
847         }
848
849         public RootWrapper getPreviousRootWrapper(RootWrapper rootWrapper){
850                         if(rootOfRootWrapperList == null){
851                                 return null;
852                         }
853                         RBTreeNode previousNode = getPrecedingNode(rootOfRootWrapperList, rootWrapper);
854                         RootWrapper result;
855                         if(previousNode == null)
856                                 result = null;
857                         else
858                                 result = (RootWrapper)(previousNode.getKey());
859                         return result;
860         }
861
862         public RootWrapper getCeilRootWrapper(Object JavaDoc locationId){
863                         if(rootOfRootWrapperList == null){
864                                 return null;
865                         }
866                         RBTreeNode root = rootOfRootWrapperList.getRoot();
867                         if (root==null){
868                                 return null;
869                         }
870                         while (true) {
871                                 RootWrapper rootWrapper = (RootWrapper)root.getKey();
872                                 if (canContain(rootWrapper, locationId)){
873                                         return rootWrapper;
874                                 }
875                                 int cmp = compare(locationId, rootWrapper.getRoot().getKey());
876                                 if (cmp < 0) {
877                                         if (root.left != null)
878                                                 root = root.left;
879                                         else{
880                                                 return rootWrapper;
881                                         }
882                                 } else {
883                                         if (root.right != null) {
884                                                 root = root.right;
885                                         } else {
886                                                 RBTreeNode parent = root.parent;
887                                                 RBTreeNode ch = root;
888                                                 while (parent != null && ch == parent.right) {
889                                                         ch = parent;
890                                                         parent = parent.parent;
891                                                 }
892                                                 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey();
893                                                 return rootWrapper;
894                                         }
895                                 }
896                         }
897         }
898
899         public RootWrapper getNextRootWrapperOfKey(Object JavaDoc locationId){
900                         if(rootOfRootWrapperList == null){
901                                 return null;
902                         }
903                         RBTreeNode root = rootOfRootWrapperList.getRoot();
904                         if (root==null){
905                                 return null;
906                         }
907                         while (true) {
908                                 RootWrapper rootWrapper = (RootWrapper)root.getKey();
909                                 int cmp = compare(locationId, rootWrapper.getRoot().getKey());
910                                 if (cmp < 0) {
911                                         if (root.left != null)
912                                                 root = root.left;
913                                         else{
914                                                 return rootWrapper;
915                                         }
916                                 } else {
917                                         if (root.right != null) {
918                                                 root = root.right;
919                                         } else {
920                                                 RBTreeNode parent = root.parent;
921                                                 RBTreeNode ch = root;
922                                                 while (parent != null && ch == parent.right) {
923                                                         ch = parent;
924                                                         parent = parent.parent;
925                                                 }
926                                                 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey();
927                                                 return rootWrapper;
928                                         }
929                                 }
930                         }
931         }
932
933         public RootWrapper getFloorRootWrapper(Object JavaDoc locationId){
934                         if(rootOfRootWrapperList == null){
935                                 return null;
936                         }
937                         RBTreeNode root = rootOfRootWrapperList.getRoot();
938                         if (root == null){
939                                 return null;
940                         }
941
942                         while (true) {
943                                 RootWrapper rootWrapper = (RootWrapper)root.getKey();
944                                 if (canContain(rootWrapper, locationId)){
945                                         return rootWrapper;
946                                 }
947                                 int cmp = compare(locationId, rootWrapper.getRoot().getKey());
948                                 if (cmp > 0) {
949                                         if (root.right != null)
950                                                 root = root.right;
951                                         else{
952                                                 rootWrapper = (RootWrapper)root.getKey();
953                                                 return rootWrapper;
954                                         }
955                                 } else {
956                                         if (root.left != null) {
957                                                 root = root.left;
958                                         } else {
959                                                 RBTreeNode parent = root.parent;
960                                                 RBTreeNode ch = root;
961                                                 while (parent != null && ch == parent.left) {
962                                                         ch = parent;
963                                                         parent = parent.parent;
964                                                 }
965                                                 rootWrapper = parent == null ? null : (RootWrapper)parent.getKey();
966                                                 return rootWrapper;
967                                         }
968                                 }
969                         }
970         }
971
972         public RootWrapper getPreviousRootWrapperOfKey(Object JavaDoc locationId){
973                         if(rootOfRootWrapperList == null){
974                                 return null;
975                         }
976                         RBTreeNode root = rootOfRootWrapperList.getRoot();
977                         if (root == null){
978                                 return null;
979                         }
980
981                         while (true) {
982                                 RootWrapper rootWrapper = (RootWrapper)root.getKey();
983                                 int cmp = compare(locationId, rootWrapper.getRoot().getKey());
984                                 if (cmp > 0) {
985                                         if (root.right != null)
986                                                 root = root.right;
987                                         else{
988                                                 rootWrapper = (RootWrapper)root.getKey();
989                                                 return rootWrapper;
990                                         }
991                                 } else {
992                                         if (root.left != null) {
993                                                 root = root.left;
994                                         } else {
995                                                 RBTreeNode parent = root.parent;
996                                                 RBTreeNode ch = root;
997                                                 while (parent != null && ch == parent.left) {
998                                                         ch = parent;
999                                                         parent = parent.parent;
1000                                                }
1001                                                rootWrapper = parent == null ? null : (RootWrapper)parent.getKey();
1002                                                return rootWrapper;
1003                                        }
1004                                }
1005                        }
1006        }
1007
1008        public RootWrapper getFirstRootWrapper(){
1009                        if(rootOfRootWrapperList == null){
1010                                return null;
1011                        }
1012                        RootWrapper result = (RootWrapper)firstKey(rootOfRootWrapperList);
1013                        return result;
1014        }
1015
1016        public RootWrapper getLastRootWrapper(){
1017                        if(rootOfRootWrapperList == null){
1018                                return null;
1019                        }
1020                        RootWrapper result = (RootWrapper)lastKey(rootOfRootWrapperList);
1021                        return result;
1022        }
1023
1024        public void removeRootWrappersWithIn(Object JavaDoc locationIdFrom, Object JavaDoc locationIdTo){
1025                        if(rootOfRootWrapperList == null){
1026                                return;
1027                        }
1028                        int cmp = compare(locationIdFrom, locationIdTo);
1029                        if(cmp == 0) return;
1030                        if(cmp > 0){
1031                                Object JavaDoc temp = locationIdFrom;
1032                                locationIdFrom = locationIdTo;
1033                                locationIdTo = temp;
1034                        }
1035                        boolean removing = true;
1036                        while(removing){
1037                                removing = removeNodeInBetween(rootOfRootWrapperList.getRoot(), locationIdFrom, locationIdTo);
1038                        }
1039        }
1040
1041        private boolean removeNodeInBetween(RBTreeNode root, Object JavaDoc locationIdFrom, Object JavaDoc locationIdTo){
1042                if(root == null){
1043                        return false;
1044                }
1045                RootWrapper rootWrapper = (RootWrapper)root.getKey();
1046                int cmp1 = compare(locationIdFrom, rootWrapper.getRoot().getKey());
1047                int cmp2 = compare(locationIdTo, rootWrapper.getRoot().getKey());
1048                if( (cmp1 < 0 && cmp2 > 0) ){
1049                        removeFromRootWrapperList(rootWrapper);
1050                        return true;
1051                }
1052                if (cmp1 < 0 && cmp2 < 0)
1053                        root = root.left;
1054                else if(cmp1 > 0 && cmp2 > 0)
1055                        root = root.right;
1056                return removeNodeInBetween(root, locationIdFrom, locationIdTo);
1057        }
1058
1059        public void show(){
1060            if (rootOfRootWrapperList.getRoot() != null)
1061                show(rootOfRootWrapperList.getRoot());
1062            else
1063         ;
1064        }
1065
1066        private void show(RBTreeNode root){
1067            if (root.left != null)
1068                show(root.left);
1069            ( (RootWrapper) root.key).show();
1070            if (root.right != null)
1071                show(root.right);
1072        }
1073
1074        protected int getNumberOfEntries(){
1075                if(rootOfRootWrapperList.getRoot() != null)
1076                        return getNumberOfEntriesInWrapper(rootOfRootWrapperList.getRoot(), 0);
1077                return 0;
1078        }
1079
1080        private int getNumberOfEntriesInWrapper(RBTreeNode root, int number){
1081
1082            int numberOfEntries = getNumberOfEntries(((RootWrapper)root.key).getRoot(), 0);
1083                number += numberOfEntries;
1084
1085                int numberInLeft = 0;
1086                int numberInRight = 0;
1087
1088
1089                if(root.left != null) numberInLeft = getNumberOfEntriesInWrapper(root.left, number);
1090                if(root.right != null) numberInRight = getNumberOfEntriesInWrapper(root.right, number);
1091{}/// D.outP("numberInLeft", numberInLeft);
1092
int toReturn = numberOfEntries + numberInLeft + numberInRight;
1093                return toReturn;
1094        }
1095
1096
1097        /*protected int getNumberOfEntriesOld(){
1098          if(D.pushCheck("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.getNumberOfEntries"))D.push(this, null);try{
1099                if(rootOfRootWrapperList.getRoot() != null)
1100                        return getNumberOfEntriesOld(rootOfRootWrapperList.getRoot(), 0);
1101                return 0;
1102          }finally{D.pop("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.getNumberOfEntries");}
1103        }*/

1104
1105        /*private int getNumberOfEntriesOld(RBTreeNode root, int number){
1106          if(D.pushCheck("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.getNumberOfEntriesP"))D.push(this, null);try{
1107                number++;
1108                int numberInLeft = 0;
1109                int numberInRight = 0;
1110                if(root.left != null) numberInLeft = getNumberOfEntriesOld(root.left, number);
1111                if(root.right != null) numberInRight = getNumberOfEntriesOld(root.right, number);
1112                return number + numberInLeft + numberInRight;
1113          }finally{D.pop("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.getNumberOfEntriesP");}
1114        }*/

1115
1116        private int getNumberOfEntries(RBTreeNode root, int number){
1117                number++;
1118                int numberInLeft = 0;
1119                int numberInRight = 0;
1120
1121                if(root.left != null) numberInLeft = getNumberOfEntries(root.left, number);
1122                if(root.right != null) numberInRight = getNumberOfEntries(root.right, number);
1123{}/// D.outP("number", number);
1124
int toReturn = 1 + numberInLeft + numberInRight;
1125                return toReturn;
1126        }
1127    public Object JavaDoc getCeilKey(Object JavaDoc key){
1128        RootWrapper rootWrapper = getRootWrapper(key);
1129        if(rootWrapper != null)
1130            return getCeilNode(rootWrapper, key).getKey();
1131        rootWrapper = getCeilRootWrapper(key);
1132        if(rootWrapper == null)
1133            return null;
1134        return firstKey(rootWrapper);
1135    }
1136
1137    public Object JavaDoc getFloorKey(Object JavaDoc key){
1138        RootWrapper rootWrapper = getRootWrapper(key);
1139        if(rootWrapper != null)
1140            getFloorNode(rootWrapper, key).getKey();
1141        rootWrapper = getFloorRootWrapper(key);
1142        if(rootWrapper == null)
1143            return null;
1144        return lastKey(rootWrapper);
1145    }
1146    public RootWrapper joinTrees(RootWrapper rootWrapper1, Object JavaDoc obj, RootWrapper rootWrapper2){
1147            if(rootWrapper1 == null || rootWrapper2 == null)
1148                throw new InternalError JavaDoc("One or the RootWrapper is null");
1149
1150            if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null){
1151                put(rootWrapper2, obj);
1152                return rootWrapper2;
1153            }
1154            if(rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null){
1155                put(rootWrapper1, obj);
1156                return rootWrapper1;
1157            }
1158            if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null){
1159                put(rootWrapper1, obj);
1160                return rootWrapper1;
1161            }
1162            int blackHeight1 = rootWrapper1.getBlackHeight();
1163            int blackHeight2 = rootWrapper2.getBlackHeight();
1164
1165            if(blackHeight1 == blackHeight2){
1166                RootWrapper result = new RootWrapper();
1167                put(result, obj);
1168                RBTreeNode node = result.getRoot();
1169                RBTreeNode root1 = rootWrapper1.getRoot();
1170                RBTreeNode root2 = rootWrapper2.getRoot();
1171                root1.parent = node;
1172                root2.parent = node;
1173                if(compareRootWrappers(rootWrapper1, rootWrapper2) < 0){
1174                    node.left = root1;
1175                    node.right = root2;
1176                }
1177                else{
1178                    node.left = root2;
1179                    node.right = root1;
1180                }
1181                return result;
1182            }
1183            if(blackHeight1 < blackHeight2){
1184                RootWrapper temp = rootWrapper1;
1185                rootWrapper1 = rootWrapper2;
1186                rootWrapper2 = temp;
1187            }
1188
1189            int cmp = compareRootWrappers(rootWrapper1, rootWrapper2);
1190            RootWrapper result;
1191            if(cmp >= 0){
1192                result = joinToLeft(rootWrapper1, rootWrapper2, obj);
1193            }
1194            else{
1195                result = joinToRight(rootWrapper1, rootWrapper2, obj);
1196            }
1197            return result;
1198    }
1199
1200    protected int compareRootWrappers(RootWrapper p, RootWrapper q){
1201            if(p == q){
1202                return 0;
1203            }
1204            int result = compare(p.getRoot().getKey(), q.getRoot().getKey());
1205            return result;
1206    }
1207
1208    private RootWrapper joinToLeft(RootWrapper mainRootWrapper, RootWrapper rootWrapper1, Object JavaDoc obj){
1209            int blackHeight1 = rootWrapper1.getBlackHeight();
1210
1211            int blackHeight2 = mainRootWrapper.getBlackHeight();
1212
1213            if(blackHeight2 < blackHeight1)
1214                throw new InternalError JavaDoc("blackHeight2 can't be less than blackHeight1 " + blackHeight1 + " , " + blackHeight2);
1215            if(blackHeight1 == 0){
1216                put(mainRootWrapper, obj);
1217                return mainRootWrapper;
1218            }
1219            RBTreeNode node = mainRootWrapper.getRoot();
1220            while(node != null){
1221                if((getBlackHeight(node) == blackHeight1) && node.getColor())
1222                    break;
1223                node = node.left;
1224            }
1225            if(node == null){
1226                throw new InternalError JavaDoc("node can't be null.");
1227            }
1228            RBTreeNode parentNode = node.parent;
1229            RBTreeNode root1 = rootWrapper1.root;
1230            RBTreeNode subTreeRoot = (RBTreeNode)createRBTreeNode(obj, null);
1231
1232
1233            subTreeRoot.left = root1;
1234            root1.parent = subTreeRoot;
1235
1236            subTreeRoot.right = node;
1237            node.parent = subTreeRoot;
1238
1239            if(parentNode == null){
1240                RootWrapper subTree = new RootWrapper(subTreeRoot);
1241                return subTree;
1242            }
1243            parentNode.left = subTreeRoot;
1244            subTreeRoot.parent = parentNode;
1245
1246            invokeFixAfterInsertion(mainRootWrapper, subTreeRoot);
1247            return mainRootWrapper;
1248    }
1249
1250    private RootWrapper joinToRight(RootWrapper mainRootWrapper, RootWrapper rootWrapper2, Object JavaDoc obj){
1251
1252            int blackHeight1 = mainRootWrapper.getBlackHeight();
1253            int blackHeight2 = getBlackHeight(rootWrapper2.getRoot());
1254
1255            if(blackHeight1 < blackHeight2)
1256                throw new InternalError JavaDoc("blackHeight1 can't be less than blackHeight2 " + blackHeight1 + " , " + blackHeight2);
1257            if(blackHeight2 == 0){
1258                put(mainRootWrapper, obj);
1259                return mainRootWrapper;
1260            }
1261
1262            RBTreeNode node = (RBTreeNode)mainRootWrapper.getRoot();
1263            while(node != null){
1264                if((getBlackHeight(node) == blackHeight2) && node.getColor())
1265                    break;
1266                node = node.right;
1267            }
1268            if(node == null){
1269                throw new InternalError JavaDoc("node can't be null.");
1270            }
1271            RBTreeNode parentNode = node.getParent();
1272            RBTreeNode root2 = rootWrapper2.getRoot();
1273            RBTreeNode subTreeRoot = createRBTreeNode(obj, null);
1274            subTreeRoot.right = root2;
1275            root2.parent = subTreeRoot;
1276
1277            subTreeRoot.left = node;
1278            node.parent = subTreeRoot;
1279
1280            if(parentNode == null){
1281                RootWrapper subTree = new RootWrapper(subTreeRoot);
1282                return subTree;
1283            }
1284            subTreeRoot.parent = parentNode;
1285            parentNode.right = subTreeRoot;
1286
1287            invokeFixAfterInsertion(mainRootWrapper, subTreeRoot);
1288            return mainRootWrapper;
1289    }
1290
1291    protected int getBlackHeight(RBTreeNode p){
1292        int height = 0;
1293        if(p == null)
1294            throw new InternalError JavaDoc("can't get blackHeight of null.");
1295        if (p != null)
1296            while (p != null){
1297                if(p.color) height++;
1298                p = p.right;
1299            }
1300        return height;
1301    }
1302
1303    protected boolean isOnlyNode(RootWrapper rootWrapper){
1304        RBTreeNode root = rootWrapper.getRoot();
1305        return (root.getLeft() == null && root.getRight() == null);
1306    }
1307
1308    protected boolean mightBeDeleted(RBTreeNode node){
1309        return (node.getLeft() == null && node.getParent() == null && node.getRight() == null);
1310    }
1311    protected void makeLinksNull(RBTreeNode node){
1312        node.parent = null;
1313        node.left = null;
1314        node.right = null;
1315    }
1316
1317      private RootWrapper joinTrees(RootWrapper rootWrapper1, RootWrapper rootWrapper2){
1318              if(rootWrapper1 == null || rootWrapper2 == null)
1319                  throw new InternalError JavaDoc("One or the rootWrapper is null");
1320              if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() != null){
1321                  return rootWrapper2;
1322              }
1323              if(rootWrapper1.getRoot() != null && rootWrapper2.getRoot() == null){
1324                  return rootWrapper1;
1325              }
1326              if(rootWrapper1.getRoot() == null && rootWrapper2.getRoot() == null){
1327                  return null;
1328              }
1329              if(rootWrapper1.getRoot().getLeft() == null && rootWrapper1.getRoot().getRight() == null){
1330                  put(rootWrapper2, rootWrapper1.getRoot().getKey());
1331                  return rootWrapper2;
1332              }
1333              if(rootWrapper2.getRoot().getLeft() == null && rootWrapper2.getRoot().getRight() == null){
1334                  put(rootWrapper1, rootWrapper2.getRoot().getKey());
1335                  return rootWrapper1;
1336              }
1337              int cmp = compareRootWrappers(rootWrapper1, rootWrapper2);
1338              if(cmp > 0){
1339                  RootWrapper temp = rootWrapper1;
1340                  rootWrapper1 = rootWrapper2;
1341                  rootWrapper2 = temp;
1342              }
1343
1344              Object JavaDoc obj = firstKey(rootWrapper2);
1345              Object JavaDoc oldRootKey = rootWrapper2.getRoot().getKey();
1346              if(obj == oldRootKey){
1347
1348                  RBTreeNode rightNode = rootWrapper2.getRoot().getRight();
1349                  if(rightNode != null){
1350                      Object JavaDoc rightNodeKey = rightNode.getKey();
1351                      put(rootWrapper1, obj);
1352                      makeLinksNull(rightNode);
1353                      put(rootWrapper1, rightNodeKey);
1354                      return rootWrapper1;
1355                  }
1356              }
1357
1358              remove(rootWrapper2, obj);
1359
1360              if(rootWrapper2.getRoot() == null){
1361                  put(rootWrapper1, obj);
1362                  return rootWrapper1;
1363              }
1364              else{
1365                  RootWrapper joinedTree = joinTrees(rootWrapper1, obj, rootWrapper2);
1366                  return joinedTree;
1367              }
1368      }
1369}
1370
1371
1372/*
1373    public void breakTreeOld(RootWrapper mainTree, Object obj, RootWrapper leftTree, RootWrapper rightTree){
1374            if(D.pushCheck("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.breakTree")) D.push(this, null); try {
1375                RBTreeNode root = mainTree.getRoot();
1376                if( root == null )
1377                        return;
1378                Object rootKey = root.key;
1379                RBTreeNode leftNode = root.left;
1380                RBTreeNode rightNode = root.right;
1381                int cmp = compare(rootKey, obj);
1382                if( cmp > 0){// obj is in left side...
1383                        if( leftNode == null && rightNode == null){
1384                            if(rightTree.getRoot() == null){
1385                                setRootWrapperRoot(rightTree, root);
1386                            }
1387                            else
1388                                put(rightTree, rootKey);
1389                            return;
1390                        }
1391                        if(rightTree.getRoot() == null){ // rightTree yet not made...............
1392                            setRootWrapperRoot(rightTree, rightNode);
1393                            put(rightTree, rootKey);
1394                        }
1395                        else{////////////// rightTree already there...............
1396                                RootWrapper tempRight = new RootWrapper(rightNode);
1397                                put(tempRight, rootKey);
1398                                Object tempObj = lastKey(tempRight);
1399                                remove(tempRight, tempObj);
1400                                rightTree = joinTrees(rightTree, tempObj, tempRight);
1401                        }
1402                        setRootWrapperRoot(mainTree, leftNode);
1403                        breakTree(mainTree, obj, leftTree, rightTree);
1404                        return;
1405                }else if(cmp < 0){// obj is in right side...
1406                        if( leftNode == null && rightNode == null){
1407                                put(leftTree, rootKey);
1408                                return;
1409                        }
1410                        if(leftTree.getRoot() == null){ //// leftTree yet not made..........
1411                                setRootWrapperRoot(leftTree, leftNode);
1412                                put(leftTree, rootKey);
1413                        }
1414                        else{ /// leftTree already there.......
1415                                RootWrapper tempLeft = new RootWrapper(leftNode);
1416                                put(tempLeft, rootKey);
1417                                Object tempObj = firstKey(tempLeft);
1418                                remove(tempLeft, tempObj);
1419                        }
1420                        setRootWrapperRoot(mainTree, rightNode);
1421                        breakTree(mainTree, obj, leftTree, rightTree);
1422                        return;
1423                }else{ ///// root is the break point .............
1424                        if( leftNode == null && rightNode == null)
1425                                return;
1426                        if(leftTree.getRoot() == null)///left set yet not made.............
1427                                setRootWrapperRoot(leftTree, leftNode);
1428                        else{// left set is there.......
1429                                RootWrapper tempLeft = new RootWrapper(leftNode);
1430                                Object tempObj = firstKey(tempLeft);
1431                                remove(tempLeft, tempObj);
1432                                leftTree = joinTrees(leftTree, tempObj , tempLeft);
1433                        }
1434                        if(rightTree.getRoot() == null){ ///right set yet not made.............
1435                                setRootWrapperRoot(rightTree, rightNode);
1436                        }
1437                        else{ // right set is there.......
1438                                RootWrapper tempRight = new RootWrapper(rightNode);
1439                                Object tempObj = lastKey(tempRight);
1440                                remove(tempRight, tempObj);
1441                                rightTree = joinTrees(rightTree, tempObj, tempRight);
1442                        }
1443                        return;
1444                }
1445            }finally{D.pop("com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree.breakTree");}
1446        }
1447
1448*/

1449
1450
1451
1452
Popular Tags