|
1
16
17
18
19 package com.daffodilwoods.rbtreesizesequence;
20
21 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.RBTreeNode;
22 import com.daffodilwoods.rbtreesizesequence.utils.sizesequenceutility.RBTreeSizeSequenceUtility;
23
24 import java.util.Comparator  ;
25
26
34
35 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.RootWrapper;
36 import com.daffodilwoods.rbtreesizesequence.utils.rbtree.SegmentedRedBlackTree;
37
38 public class RBTreeSimple extends SegmentedRedBlackTree implements SizeSequence {
39
40 protected RBTreeSizeSequenceUser treeSizeSequenceUser;
41 protected int maxOffst;
42 protected boolean addAllowed = true;
43
44 public RBTreeSimple(RBTreeSizeSequenceUser user, int maxOffst) {
45 this.treeSizeSequenceUser = user;
46 this.comparator = user.getComparator();
47 this.maxOffst = maxOffst;
48 }
49
50
51 public void setRBTreeSizeSequenceUser(SizeSequenceUser sizeSequenceUser){
52 this.treeSizeSequenceUser = (RBTreeSizeSequenceUser)sizeSequenceUser;
53 }
54
55 public void add(Object locationIdFrom, int atDistance, Object locationId) {
56 if(!addAllowed){
57 return;
58 }
59 if(locationId == null)
60 throw new IllegalArgumentException ("<<<<<<< locationId to be added shouldn't be null >>>>>>>>");
61 if(locationIdFrom == null){
62 RootWrapper rootWrapper = new RootWrapper();
63 put(rootWrapper, locationId);
64 addRootWrapperToList(rootWrapper);
65 checkForJoinTrees(rootWrapper, locationId);
66 return;
67 }
68 if(compare(locationIdFrom, locationId) == 0){
69 if(atDistance == 0) return;
70 throw new IllegalArgumentException ("Can't add " + locationId + " at distance " + atDistance + " from " + locationIdFrom);
71 }
72
73
74
78
79 RootWrapper rootWrapper = getRootWrapper(locationIdFrom);
80 if(rootWrapper == null){
81 rootWrapper = new RootWrapper();
82 put(rootWrapper, locationIdFrom);
83 put(rootWrapper, locationId);
84 addRootWrapperToList(rootWrapper);
85
86
88
89 checkForJoinTrees(rootWrapper, locationId);
90 return;
91 }
92
93 put(rootWrapper, locationId);
94 checkForJoinTrees(rootWrapper, locationId);
95
96 }
97
98 protected boolean isAtEnd(RootWrapper rootWrapper, Object locationId){
99 boolean result;
100 if(compare(lastKey(rootWrapper), locationId) == 0)
101 result = true;
102 else
103 result = false;
104 return result;
105 }
106
107 protected boolean isAtStart(RootWrapper rootWrapper, Object locationId){
108 boolean result;
109 if(compare(firstKey(rootWrapper), locationId) == 0)
110 result = true;
111 else
112 result = false;
113 return result;
114 }
115
116
117 private boolean checkForJoinTrees(RootWrapper rootWrapper, Object locationId){
118 addAllowed = false;
119 if(isAtEnd(rootWrapper, locationId)){
120 RootWrapper rootWrapperNext = getNextRootWrapper(rootWrapper);
121 if(rootWrapperNext == null){
122 addAllowed = true;
123 return false;
124 }
125 if(treeSizeSequenceUser.canJoin(locationId, firstKey(rootWrapperNext))){
126 boolean bln2 = remove(rootWrapperNext, firstKey(rootWrapperNext));
127 if(!bln2){
128 addAllowed = true;
129 return false;
130 }
131 boolean bln1 = remove(rootWrapper, locationId);
132 if(!bln1){
133 addAllowed = true;
134 return false;
135 }
136
137 RootWrapper joinedTree = joinTrees(rootWrapper, locationId, rootWrapperNext);
138
139 removeFromRootWrapperList(rootWrapper);
140 removeFromRootWrapperList(rootWrapperNext);
141
142 addRootWrapperToList(joinedTree);
143
144 addAllowed = true;
145 return true;
146 }
147 addAllowed = true;
148 return false;
149 }
150 else if(isAtStart(rootWrapper, locationId)){
151 RootWrapper rootWrapperPrevious = getPreviousRootWrapper(rootWrapper);
152 if(rootWrapperPrevious == null){
153 addAllowed = true;
154 return false;
155 }
156
157 if(treeSizeSequenceUser.canJoin(locationId, lastKey(rootWrapperPrevious))){
158 boolean bln2 = remove(rootWrapperPrevious, lastKey(rootWrapperPrevious));
159 if(!bln2){
160 addAllowed = true;
161 return false;
162 }
163 boolean bln1 = remove(rootWrapper, locationId);
164 if(!bln1){
165 addAllowed = true;
166 return false;
167 }
168
169 RootWrapper joinedTree = joinTrees(rootWrapper, locationId, rootWrapperPrevious);
170
171 removeFromRootWrapperList(rootWrapper);
172 removeFromRootWrapperList(rootWrapperPrevious);
173 addRootWrapperToList(joinedTree);
174 addAllowed = true;
175 return true;
176 }
177 addAllowed = true;
178 return false;
179 }
180 addAllowed = true;
181 return false;
182 }
183
184 public void invalidate(Object key){
185 addAllowed = false;
186 try{
187 RootWrapper rootWrapper = getRootWrapper(key);
188 if(rootWrapper == null){
189 return;
190 }
191 removeFromRootWrapperList(rootWrapper);
192 RootWrapper rootWrapperLeft = new RootWrapper();
193 RootWrapper rootWrapperRight = new RootWrapper();
194 breakTree(rootWrapper, key, rootWrapperLeft, rootWrapperRight);
195
196 if(rootWrapperLeft.getRoot() != null){
197 addRootWrapperToList(rootWrapperLeft);
198 }
199 if(rootWrapperRight.getRoot() != null){
200 addRootWrapperToList(rootWrapperRight);
201 }
202 }finally{
203 addAllowed = true;
204 }
205 }
206
207 public synchronized void update(Object oldKey, Object newKey){
208 RootWrapper rootWrapper = getRootWrapper(oldKey);
209
210 RBTreeNode node = (RBTreeNode)getNode(rootWrapper, oldKey);
211
212 RBTreeNode previousNode = getPrecedingNode(rootWrapper, oldKey);
213
214 RBTreeNode nextNode = getNextNode(rootWrapper, oldKey);
215
216
217 if(previousNode != null && nextNode != null && compare(previousNode.getKey(), newKey) < 0 && compare(nextNode.getKey(), newKey) > 0){
218 node.setKey(newKey);
219 return;
220
221 }
222 delete(oldKey);
223 insert(newKey);
224
225 }
226
227 public synchronized void insert(Object locationId){
228 try{
229 RootWrapper rootWrapper = getRootWrapper(locationId);
230
231 if(rootWrapper == null){
232 add(null, 0, locationId);
233 return;
234 }
235
236 RBTreeNode previous = (RBTreeNode)getFloorNode(rootWrapper, locationId);
237
238 RBTreeNode next = (RBTreeNode)getCeilNode(rootWrapper, locationId);
239 if(previous != null && next != null){
240 add(previous.key, 1, locationId);
241 return;
242 }
243
244 if(previous != null){
245 add(previous.key, 1, locationId);
246 }
247 else if(next != null){
248 add(next.key, -1, locationId);
249 }
250 else{
251 add(null, 0, locationId);
252 }
253 }finally{
254 }
255 }
256
257 public synchronized void delete(Object locationId){
258 RootWrapper rootWrapper = getRootWrapper(locationId);
259
260 remove(rootWrapper, locationId);
261
262 }
263
264 public Object getFloorKey(Object locationId){
265 RootWrapper rootWrapper = getFloorRootWrapper(locationId);
266 if(rootWrapper != null)
267 return getFloorNode(rootWrapper, locationId).getKey();
268 return null;
269 }
270
271 public Object getPreviousKey(Object locationId){
272 RootWrapper rootWrapper = getRootWrapper(locationId);
273 if(rootWrapper == null){
274 rootWrapper = getFloorRootWrapper(locationId);
275 return rootWrapper != null ? lastKey(rootWrapper) : null;
276 }
277 else {
278 if(firstKey(rootWrapper) == locationId){
279 RootWrapper previousRootWrapper = getPreviousRootWrapper(rootWrapper);
280 if(previousRootWrapper != null)
281 return lastKey(previousRootWrapper);
282 return null;
283 }
284 RBTreeNode previousNode = getPrecedingNode(rootWrapper, locationId);
285 return previousNode != null ? previousNode.getKey() : null;
286 }
287 }
288
289 public Object getCeilKey(Object locationId){
290 RootWrapper rootWrapper = getCeilRootWrapper(locationId);
291 if(rootWrapper != null)
292 return getCeilNode(rootWrapper, locationId).getKey();
293 return null;
294 }
295
296 public Object getNextKey(Object locationId){
297 RootWrapper rootWrapper = getRootWrapper(locationId);
298 if(rootWrapper == null){
299 rootWrapper = getCeilRootWrapper(locationId);
300 return rootWrapper != null ? firstKey(rootWrapper) : null;
301 }
302 else {
303 if(lastKey(rootWrapper) == locationId){
304 RootWrapper nextRootWrapper = getNextRootWrapper(rootWrapper);
305 if(nextRootWrapper != null)
306 return firstKey(nextRootWrapper);
307 return null;
308 }
309 RBTreeNode nextNode = getNextNode(rootWrapper, locationId);
310 return nextNode != null ? nextNode.getKey() : null;
311 }
312 }
313
314
315 public Object getTreeTopKey(){
316 RootWrapper rootWrapper = getFirstRootWrapper();
317 if(rootWrapper == null)
318 return null;
319 return firstNode(rootWrapper);
320 }
321
322 public Object getTreeBottomKey(){
323 RootWrapper rootWrapper = getLastRootWrapper();
324 if(rootWrapper == null)
325 return null;
326 return lastNode(rootWrapper);
327 }
328
329 public Object getTopKey(){
330 RBTreeNode topKey = (RBTreeNode)getTreeTopKey();
331 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(null, topKey == null ? null : topKey.getKey(), 1));
332 if(distance == 0)
333 return topKey;
334 return getTreeTopKey();
335 }
336
337 public Object getBottomKey(){
338 RBTreeNode bottomKey = (RBTreeNode)getTreeBottomKey();
339 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(null, bottomKey == null ? null : bottomKey.getKey(), -1));
340 if(distance == 0)
341 return bottomKey;
342 return getTreeBottomKey();
343 }
344
345 public Object getObjectAtKey(Object rbTreeNode){
346 return ((RBTreeNode)rbTreeNode).getKey();
347 }
348
349 public Object locateNearestKey(Object key){
350 RootWrapper rootWrapper = getCeilRootWrapper(key);
351 if(rootWrapper != null)
352 return getCeilNode(rootWrapper, key);
353 rootWrapper = getFloorRootWrapper(key);
354 if(rootWrapper == null)
355 return null;
356 return getFloorNode(rootWrapper, key);
357 }
358
359
360
361 private Object getNextOfDeleted(RBTreeNode node){
362 Object key = node.getKey();
363 RootWrapper rootWrapper = getRootWrapper(key);
364 RootWrapper rootWrapperPrev = null;
365 if(rootWrapper == null){
366 rootWrapperPrev = getPreviousRootWrapperOfKey(key);
367 }
368 else{
369 if(isOnlyNode(rootWrapper)){
370 rootWrapperPrev = rootWrapper;
371 }
372 else{
373 RBTreeNode nextNode = getNextNode(getRootWrapper(key), key);
374 if(nextNode != null)
375 return nextNode;
376 rootWrapperPrev = rootWrapper;
377 }
378 }
379 RootWrapper rootWrapperNext = getNextRootWrapperOfKey(key);
380 RBTreeNode nodeFrom = null;
381 RBTreeNode nodeTo = null;
382 if(rootWrapperPrev != null)
383 nodeFrom = lastNode(rootWrapperPrev);
384 if(rootWrapperNext != null)
385 nodeTo = firstNode(rootWrapperNext);
386 Object keyFrom = null;
387 Object keyTo = null;
388 try{
389 keyFrom = nodeFrom.getKey();
390 }catch(NullPointerException e){} try{
392 keyTo = nodeTo.getKey();
393 }catch(NullPointerException e){} int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(keyFrom, keyTo, Integer.MAX_VALUE));
395 return (distance != 0 ? getNextNode(getRootWrapper(key), key) : nodeTo);
396 }
397
398
399 public Object getNext(Object rbTreeNode){
400 RBTreeNode node = (RBTreeNode)rbTreeNode;
401
402 if(mightBeDeleted(node)){
403 return getNextOfDeleted(node);
404 }
405
406
407 RBTreeNode right = (RBTreeNode)node.getRight();
408 if (right != null){
409 while (right.left != null)
410 right = (RBTreeNode)right.left;
411 return right;
412 }
413 else{
414 RBTreeNode parent = (RBTreeNode)node.parent;
415 RBTreeNode ch = node;
416 while (parent != null && ch == parent.right) {
417 ch = parent;
418 parent = (RBTreeNode)parent.parent;
419 }
420 if(parent == null){
421 RootWrapper rootWrapperTemp = getRootWrapper(node.key);
422 if(rootWrapperTemp == null){
423 ;
424 Thread.dumpStack();
425 show();
426 }
427 RootWrapper rootWrapper = getNextRootWrapper(rootWrapperTemp);
428 Object locationIdTo = null;
429 if(rootWrapper != null)
430 locationIdTo = firstKey(rootWrapper);
431 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(node.key, locationIdTo, 1));
432 if(distance != 0)
433 parent = (RBTreeNode)getNext(rbTreeNode);
434 }
435 return parent;
436 }
437 }
438
439
440
441 private Object getPreviousOfDeleted(RBTreeNode node){
442 Object key = node.getKey();
443 RootWrapper rootWrapper = getRootWrapper(key);
444 RootWrapper rootWrapperNext = null;
445 if(rootWrapper == null){
446 rootWrapperNext = getNextRootWrapperOfKey(key);
447 }
448 else{
449 if(isOnlyNode(rootWrapper)){
450 rootWrapperNext = rootWrapper;
451 }
452 else{
453 RBTreeNode precedingNode = getPrecedingNode(getRootWrapper(key), key);
454 if(precedingNode != null)
455 return precedingNode;
456 rootWrapperNext = rootWrapper;
457 }
458 }
459 RootWrapper rootWrapperPrev = getPreviousRootWrapperOfKey(key);
460 RBTreeNode nodeFrom = null;
461 RBTreeNode nodeTo = null;
462 if(rootWrapperNext != null)
463 nodeFrom = firstNode(rootWrapperNext);
464 if(rootWrapperPrev != null)
465 nodeTo = lastNode(rootWrapperPrev);
466 Object keyFrom = null;
467 Object keyTo = null;
468 try{
469 keyFrom = nodeFrom.getKey();
470 }catch(NullPointerException e){} try{
472 keyTo = nodeTo.getKey();
473 }catch(NullPointerException e){} int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(keyFrom, keyTo, Integer.MIN_VALUE));
475 return (distance != 0 ? getPrecedingNode(getRootWrapper(key), key) : nodeTo);
476 }
477
478
479
480 public Object getPrevious(Object rbTreeNode){
481 RBTreeNode node = (RBTreeNode)rbTreeNode;
482
483 if(mightBeDeleted(node)){
484 return getPreviousOfDeleted(node);
485 }
486
487 RBTreeNode left = (RBTreeNode)node.getLeft();
488 if (left != null){
489 while (left.right != null)
490 left = (RBTreeNode)left.right;
491 return left;
492 }
493 else{
494 RBTreeNode parent = (RBTreeNode)node.parent;
495 RBTreeNode ch = node;
496 while (parent != null && ch == parent.left) {
497 ch = parent;
498 parent = (RBTreeNode)parent.parent;
499 }
500 if(parent == null){
501 RootWrapper rootWrapper = getPreviousRootWrapper(getRootWrapper(node.key));
502 Object locationIdTo = null;
503 if(rootWrapper != null)
504 locationIdTo = lastKey(rootWrapper);
505 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(node.key, locationIdTo, -1));
506 if(distance != 0)
507 parent = (RBTreeNode)getPrevious(rbTreeNode);
508 }
509 return parent;
510 }
511 }
512
513
514 private Object getNextOfDeletedWithoutTrace(RBTreeNode node){
515 Object key = node.getKey();
516 RootWrapper rootWrapper = getRootWrapper(key);
517 if(rootWrapper == null || isOnlyNode(rootWrapper)){
518 RootWrapper rootWrapperNext = getNextRootWrapperOfKey(key);
519 return (rootWrapperNext == null ? null : firstNode(rootWrapperNext));
520 }
521 else{
522 return getNextNode(rootWrapper, key);
523 }
524 }
525
526
527
528 public Object getTreeNext(Object rbTreeNode){
529 RBTreeNode node = (RBTreeNode)rbTreeNode;
530 if(mightBeDeleted(node)){
531 return getNextOfDeletedWithoutTrace(node);
532 }
533 RBTreeNode right = (RBTreeNode)node.getRight();
534 if (right != null){
535 while (right.left != null)
536 right = (RBTreeNode)right.left;
537 return right;
538 }
539 else{
540 RBTreeNode parent = (RBTreeNode)node.parent;
541 RBTreeNode ch = node;
542 while (parent != null && ch == parent.right) {
543 ch = parent;
544 parent = (RBTreeNode)parent.parent;
545 }
546 if(parent == null){
547 RootWrapper rootWrapper = getNextRootWrapper(getRootWrapper(node.key));
548 if(rootWrapper != null)
549 parent = (RBTreeNode)firstNode(rootWrapper);
550 }
551 return parent;
552 }
553 }
554
555
556 private Object getPreviousOfDeletedWithoutTrace(RBTreeNode node){
557 Object key = node.getKey();
558 RootWrapper rootWrapper = getRootWrapper(key);
559 if(rootWrapper == null || isOnlyNode(rootWrapper)){
560 RootWrapper rootWrapperPrev = getPreviousRootWrapperOfKey(key);
561 return (rootWrapperPrev == null ? null : lastNode(rootWrapperPrev));
562 }
563 else{
564 return getPrecedingNode(rootWrapper, key);
565 }
566 }
567
568 public Object getTreePrevious(Object rbTreeNode){
569 RBTreeNode node = (RBTreeNode)rbTreeNode;
570 if(mightBeDeleted(node)){
571 return getPreviousOfDeletedWithoutTrace(node);
572 }
573 RBTreeNode left = (RBTreeNode)node.getLeft();
574 if (left != null){
575 while (left.right != null)
576 left = (RBTreeNode)left.right;
577 return left;
578 }
579 else{
580 RBTreeNode parent = (RBTreeNode)node.parent;
581 RBTreeNode ch = node;
582 while (parent != null && ch == parent.left) {
583 ch = parent;
584 parent = (RBTreeNode)parent.parent;
585 }
586 if(parent == null){
587 RootWrapper rootWrapper = getPreviousRootWrapper(getRootWrapper(node.key));
588 if(rootWrapper != null)
589 parent = (RBTreeNode)lastNode(rootWrapper);
590 }
591 return parent;
592 }
593 }
594
595
596
600 public Object getCeil(Object key){
601 RootWrapper rootWrapper = getRootWrapper(key);
602 if(rootWrapper != null){
603 Object toReturn = getCeilNode(rootWrapper, key);
604 return toReturn;
605 }
606 RootWrapper previousRootWrapper = getFloorRootWrapper(key);
607 RootWrapper nextRootWrapper = getCeilRootWrapper(key);
608 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(previousRootWrapper == null ? null : lastKey(previousRootWrapper), nextRootWrapper == null ? null : firstKey(nextRootWrapper), 1));
609 if(distance == 0){
610 if(nextRootWrapper != null)
611 return firstNode(nextRootWrapper);
612 return null;
613 }
614 Object toReturn = getCeil(key);
615 return toReturn;
616 }
617
618
622 public Object getFloor(Object key){
623 RootWrapper rootWrapper = getRootWrapper(key);
624 if(rootWrapper != null){
625 Object toReturn = getFloorNode(rootWrapper, key);
626 return toReturn;
627 }
628 RootWrapper previousRootWrapper = getFloorRootWrapper(key);
629 RootWrapper nextRootWrapper = getCeilRootWrapper(key);
630
631
636
637 int distance = RBTreeSizeSequenceUtility.getFirstInt(treeSizeSequenceUser.traceDistance(nextRootWrapper == null ? null : firstKey(nextRootWrapper), previousRootWrapper == null ? null : lastKey(previousRootWrapper), -1));
638 if(distance == 0){
639 if(previousRootWrapper != null)
640 return lastNode(previousRootWrapper);
641 return null;
642 }
643
644 Object toReturn = getFloor(key);
645 return toReturn;
646 }
647
648 public int getSize(){
649 int toReturn = getNumberOfEntries();
650 return toReturn;
651 }
652
653 public void breakTreeAt(Object obj){
654 addAllowed = false;
655 try{
656 RootWrapper rootWrapper = getRootWrapper(obj);
657 if(rootWrapper == null){
658 return;
659 }
660 removeFromRootWrapperList(rootWrapper);
661 RootWrapper rootWrapperLeft = new RootWrapper();
662 RootWrapper rootWrapperRight = new RootWrapper();
663 breakTree(rootWrapper, obj, rootWrapperLeft, rootWrapperRight);
664
665 if(rootWrapperLeft.getRoot() != null){
666 addRootWrapperToList(rootWrapperLeft);
667 }
668 if(rootWrapperRight.getRoot() != null){
669 addRootWrapperToList(rootWrapperRight);
670 }
671 }finally{
672 addAllowed = true;
673 }
674 }
675
676 public void markInvalid(Object locationIdFrom, Object locationIdTo){
677 int cmp = compare(locationIdFrom, locationIdTo);
678 if(cmp > 0){
679 markInvalid(locationIdTo, locationIdFrom);
680 return;
681 }
682 breakTreeAt(locationIdFrom);
683 breakTreeAt(locationIdTo);
684 removeRootWrappersWithIn(locationIdFrom, locationIdTo);
685 }
686 public void flushData(Object key, boolean direction){
687 Object otherKey;
688 if(direction) {
689 key = getNextKey(key);
690 otherKey = lastKey(getLastRootWrapper());
691 int cmp = compare(key, otherKey);
692 if(key == null || cmp > 0)
693 return;
694 }
695 else {
696 key = getPreviousKey(key);
697 otherKey = firstKey(getFirstRootWrapper());
698 int cmp = compare(key, otherKey);
699 if(key == null || cmp < 0)
700 return;
701 }
702 markInvalid(key, otherKey);
703 }
704 }
705
706 |
Popular Tags |
Java API By Example, From Geeks To Geeks.