ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.cpp
Revision: 171
Committed: Tue Feb 14 22:36:26 2012 UTC (7 years, 8 months ago) by gpertea
File size: 23779 byte(s)
Log Message:
wip fqtrim

Line File contents
1 #include "GIntervalTree.h"
2
3 // If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the
4 // code does a lot of extra checking to make sure certain assumptions
5 // are satisfied. This only needs to be done if you suspect bugs are
6 // present or if you make significant changes and want to make sure
7 // your changes didn't mess anything up.
8 // #define CHECK_INTERVAL_TREE_ASSUMPTIONS 1
9
10
11 //const int MIN_INT=-MAX_INT;
12
13 // define a function to find the maximum of two objects.
14 //#define GMAX(a, b) ( (a > b) ? a : b )
15
16 inline void Assert(int assertion, char* error) {
17 if(!assertion) {
18 printf("Assertion Failed: %s\n",error);
19 exit(1);
20 }
21 }
22
23 IntervalTreeNode::IntervalTreeNode():key(0),high(0),maxHigh(0){}
24 IntervalTreeNode::IntervalTreeNode(Interval * newInterval)
25 : storedInterval (newInterval) ,
26 key(newInterval->GetLowPoint()),
27 high(newInterval->GetHighPoint()) ,
28 maxHigh(high) {}
29 IntervalTreeNode::~IntervalTreeNode(){}
30 Interval::Interval(){}
31 Interval::~Interval(){}
32 void Interval::Print() const {}
33
34 IntervalTree::IntervalTree()
35 {
36 currentParent=NULL;
37 nil = new IntervalTreeNode;
38 nil->left = nil->right = nil->parent = nil;
39 nil->red = 0;
40 nil->key = nil->high = nil->maxHigh = MIN_INT;
41 nil->storedInterval = NULL;
42
43 root = new IntervalTreeNode;
44 root->parent = root->left = root->right = nil;
45 root->key = root->high = root->maxHigh = MAX_INT;
46 root->red=0;
47 root->storedInterval = NULL;
48
49 /* the following are used for the Enumerate function */
50 recursionNodeStackSize = 128;
51 recursionNodeStack = (it_recursion_node *)
52 malloc(recursionNodeStackSize*sizeof(it_recursion_node));
53 recursionNodeStackTop = 1;
54 recursionNodeStack[0].start_node = NULL;
55
56 }
57
58 /***********************************************************************/
59 /* FUNCTION: LeftRotate */
60 /**/
61 /* INPUTS: the node to rotate on */
62 /**/
63 /* OUTPUT: None */
64 /**/
65 /* Modifies Input: this, x */
66 /**/
67 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
68 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
69 /* makes the parent of x be to the left of x, x the parent of */
70 /* its parent before the rotation and fixes other pointers */
71 /* accordingly. Also updates the maxHigh fields of x and y */
72 /* after rotation. */
73 /***********************************************************************/
74
75 void IntervalTree::LeftRotate(IntervalTreeNode* x) {
76 IntervalTreeNode* y;
77
78 /* I originally wrote this function to use the sentinel for */
79 /* nil to avoid checking for nil. However this introduces a */
80 /* very subtle bug because sometimes this function modifies */
81 /* the parent pointer of nil. This can be a problem if a */
82 /* function which calls LeftRotate also uses the nil sentinel */
83 /* and expects the nil sentinel's parent pointer to be unchanged */
84 /* after calling this function. For example, when DeleteFixUP */
85 /* calls LeftRotate it expects the parent pointer of nil to be */
86 /* unchanged. */
87
88 y=x->right;
89 x->right=y->left;
90
91 if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
92 /* and do an unconditional assignment instead of testing for nil */
93
94 y->parent=x->parent;
95
96 /* instead of checking if x->parent is the root as in the book, we */
97 /* count on the root sentinel to implicitly take care of this case */
98 if( x == x->parent->left) {
99 x->parent->left=y;
100 } else {
101 x->parent->right=y;
102 }
103 y->left=x;
104 x->parent=y;
105
106 x->maxHigh=GMAX(x->left->maxHigh,GMAX(x->right->maxHigh,x->high));
107 y->maxHigh=MAX(x->maxHigh,GMAX(y->right->maxHigh,y->high));
108 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
109 CheckAssumptions();
110 #elif defined(DEBUG_ASSERT)
111 Assert(!nil->red,"nil not red in ITLeftRotate");
112 Assert((nil->maxHigh=MIN_INT),
113 "nil->maxHigh != MIN_INT in ITLeftRotate");
114 #endif
115 }
116
117
118 /***********************************************************************/
119 /* FUNCTION: RighttRotate */
120 /**/
121 /* INPUTS: node to rotate on */
122 /**/
123 /* OUTPUT: None */
124 /**/
125 /* Modifies Input?: this, y */
126 /**/
127 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
128 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
129 /* makes the parent of x be to the left of x, x the parent of */
130 /* its parent before the rotation and fixes other pointers */
131 /* accordingly. Also updates the maxHigh fields of x and y */
132 /* after rotation. */
133 /***********************************************************************/
134
135
136 void IntervalTree::RightRotate(IntervalTreeNode* y) {
137 IntervalTreeNode* x;
138
139 /* I originally wrote this function to use the sentinel for */
140 /* nil to avoid checking for nil. However this introduces a */
141 /* very subtle bug because sometimes this function modifies */
142 /* the parent pointer of nil. This can be a problem if a */
143 /* function which calls LeftRotate also uses the nil sentinel */
144 /* and expects the nil sentinel's parent pointer to be unchanged */
145 /* after calling this function. For example, when DeleteFixUP */
146 /* calls LeftRotate it expects the parent pointer of nil to be */
147 /* unchanged. */
148
149 x=y->left;
150 y->left=x->right;
151
152 if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
153 /* and do an unconditional assignment instead of testing for nil */
154
155 /* instead of checking if x->parent is the root as in the book, we */
156 /* count on the root sentinel to implicitly take care of this case */
157 x->parent=y->parent;
158 if( y == y->parent->left) {
159 y->parent->left=x;
160 } else {
161 y->parent->right=x;
162 }
163 x->right=y;
164 y->parent=x;
165
166 y->maxHigh=GMAX(y->left->maxHigh,GMAX(y->right->maxHigh,y->high));
167 x->maxHigh=GMAX(x->left->maxHigh,GMAX(y->maxHigh,x->high));
168 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
169 CheckAssumptions();
170 #elif defined(DEBUG_ASSERT)
171 Assert(!nil->red,"nil not red in ITRightRotate");
172 Assert((nil->maxHigh=MIN_INT),
173 "nil->maxHigh != MIN_INT in ITRightRotate");
174 #endif
175 }
176
177 /***********************************************************************/
178 /* FUNCTION: TreeInsertHelp */
179 /**/
180 /* INPUTS: z is the node to insert */
181 /**/
182 /* OUTPUT: none */
183 /**/
184 /* Modifies Input: this, z */
185 /**/
186 /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
187 /* using the algorithm described in _Introduction_To_Algorithms_ */
188 /* by Cormen et al. This funciton is only intended to be called */
189 /* by the InsertTree function and not by the user */
190 /***********************************************************************/
191
192 void IntervalTree::TreeInsertHelp(IntervalTreeNode* z) {
193 /* This function should only be called by InsertITTree (see above) */
194 IntervalTreeNode* x;
195 IntervalTreeNode* y;
196
197 z->left=z->right=nil;
198 y=root;
199 x=root->left;
200 while( x != nil) {
201 y=x;
202 if ( x->key > z->key) {
203 x=x->left;
204 } else { /* x->key <= z->key */
205 x=x->right;
206 }
207 }
208 z->parent=y;
209 if ( (y == root) ||
210 (y->key > z->key) ) {
211 y->left=z;
212 } else {
213 y->right=z;
214 }
215
216
217 #if defined(DEBUG_ASSERT)
218 Assert(!nil->red,"nil not red in ITTreeInsertHelp");
219 Assert((nil->maxHigh=MIN_INT),
220 "nil->maxHigh != MIN_INT in ITTreeInsertHelp");
221 #endif
222 }
223
224
225 /***********************************************************************/
226 /* FUNCTION: FixUpMaxHigh */
227 /**/
228 /* INPUTS: x is the node to start from*/
229 /**/
230 /* OUTPUT: none */
231 /**/
232 /* Modifies Input: this */
233 /**/
234 /* EFFECTS: Travels up to the root fixing the maxHigh fields after */
235 /* an insertion or deletion */
236 /***********************************************************************/
237
238 void IntervalTree::FixUpMaxHigh(IntervalTreeNode * x) {
239 while(x != root) {
240 x->maxHigh=GMAX(x->high,GMAX(x->left->maxHigh,x->right->maxHigh));
241 x=x->parent;
242 }
243 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
244 CheckAssumptions();
245 #endif
246 }
247
248 /* Before calling InsertNode the node x should have its key set */
249
250 /***********************************************************************/
251 /* FUNCTION: InsertNode */
252 /**/
253 /* INPUTS: newInterval is the interval to insert*/
254 /**/
255 /* OUTPUT: This function returns a pointer to the newly inserted node */
256 /* which is guarunteed to be valid until this node is deleted. */
257 /* What this means is if another data structure stores this */
258 /* pointer then the tree does not need to be searched when this */
259 /* is to be deleted. */
260 /**/
261 /* Modifies Input: tree */
262 /**/
263 /* EFFECTS: Creates a node node which contains the appropriate key and */
264 /* info pointers and inserts it into the tree. */
265 /***********************************************************************/
266
267 IntervalTreeNode * IntervalTree::Insert(Interval * newInterval)
268 {
269 IntervalTreeNode * y;
270 IntervalTreeNode * x;
271 IntervalTreeNode * newNode;
272
273 x = new IntervalTreeNode(newInterval);
274 TreeInsertHelp(x);
275 FixUpMaxHigh(x->parent);
276 newNode = x;
277 x->red=1;
278 while(x->parent->red) { /* use sentinel instead of checking for root */
279 if (x->parent == x->parent->parent->left) {
280 y=x->parent->parent->right;
281 if (y->red) {
282 x->parent->red=0;
283 y->red=0;
284 x->parent->parent->red=1;
285 x=x->parent->parent;
286 } else {
287 if (x == x->parent->right) {
288 x=x->parent;
289 LeftRotate(x);
290 }
291 x->parent->red=0;
292 x->parent->parent->red=1;
293 RightRotate(x->parent->parent);
294 }
295 } else { /* case for x->parent == x->parent->parent->right */
296 /* this part is just like the section above with */
297 /* left and right interchanged */
298 y=x->parent->parent->left;
299 if (y->red) {
300 x->parent->red=0;
301 y->red=0;
302 x->parent->parent->red=1;
303 x=x->parent->parent;
304 } else {
305 if (x == x->parent->left) {
306 x=x->parent;
307 RightRotate(x);
308 }
309 x->parent->red=0;
310 x->parent->parent->red=1;
311 LeftRotate(x->parent->parent);
312 }
313 }
314 }
315 root->left->red=0;
316 return(newNode);
317
318 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
319 CheckAssumptions();
320 #elif defined(DEBUG_ASSERT)
321 Assert(!nil->red,"nil not red in ITTreeInsert");
322 Assert(!root->red,"root not red in ITTreeInsert");
323 Assert((nil->maxHigh=MIN_INT),
324 "nil->maxHigh != MIN_INT in ITTreeInsert");
325 #endif
326 }
327
328 /***********************************************************************/
329 /* FUNCTION: GetSuccessorOf */
330 /**/
331 /* INPUTS: x is the node we want the succesor of */
332 /**/
333 /* OUTPUT: This function returns the successor of x or NULL if no */
334 /* successor exists. */
335 /**/
336 /* Modifies Input: none */
337 /**/
338 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
339 /***********************************************************************/
340
341 IntervalTreeNode * IntervalTree::GetSuccessorOf(IntervalTreeNode * x) const
342 {
343 IntervalTreeNode* y;
344
345 if (nil != (y = x->right)) { /* assignment to y is intentional */
346 while(y->left != nil) { /* returns the minium of the right subtree of x */
347 y=y->left;
348 }
349 return(y);
350 } else {
351 y=x->parent;
352 while(x == y->right) { /* sentinel used instead of checking for nil */
353 x=y;
354 y=y->parent;
355 }
356 if (y == root) return(nil);
357 return(y);
358 }
359 }
360
361 /***********************************************************************/
362 /* FUNCTION: GetPredecessorOf */
363 /**/
364 /* INPUTS: x is the node to get predecessor of */
365 /**/
366 /* OUTPUT: This function returns the predecessor of x or NULL if no */
367 /* predecessor exists. */
368 /**/
369 /* Modifies Input: none */
370 /**/
371 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
372 /***********************************************************************/
373
374 IntervalTreeNode * IntervalTree::GetPredecessorOf(IntervalTreeNode * x) const {
375 IntervalTreeNode* y;
376
377 if (nil != (y = x->left)) { /* assignment to y is intentional */
378 while(y->right != nil) { /* returns the maximum of the left subtree of x */
379 y=y->right;
380 }
381 return(y);
382 } else {
383 y=x->parent;
384 while(x == y->left) {
385 if (y == root) return(nil);
386 x=y;
387 y=y->parent;
388 }
389 return(y);
390 }
391 }
392
393 /***********************************************************************/
394 /* FUNCTION: Print */
395 /**/
396 /* INPUTS: none */
397 /**/
398 /* OUTPUT: none */
399 /**/
400 /* EFFECTS: This function recursively prints the nodes of the tree */
401 /* inorder. */
402 /**/
403 /* Modifies Input: none */
404 /**/
405 /* Note: This function should only be called from ITTreePrint */
406 /***********************************************************************/
407
408 void IntervalTreeNode::Print(IntervalTreeNode * nil,
409 IntervalTreeNode * root) const {
410 storedInterval->Print();
411 printf(", k=%i, h=%i, mH=%i",key,high,maxHigh);
412 printf(" l->key=");
413 if( left == nil) printf("NULL"); else printf("%i",left->key);
414 printf(" r->key=");
415 if( right == nil) printf("NULL"); else printf("%i",right->key);
416 printf(" p->key=");
417 if( parent == root) printf("NULL"); else printf("%i",parent->key);
418 printf(" red=%i\n",red);
419 }
420
421 void IntervalTree::TreePrintHelper( IntervalTreeNode* x) const {
422
423 if (x != nil) {
424 TreePrintHelper(x->left);
425 x->Print(nil,root);
426 TreePrintHelper(x->right);
427 }
428 }
429
430 IntervalTree::~IntervalTree() {
431 IntervalTreeNode * x = root->left;
432 TemplateStack<IntervalTreeNode *> stuffToFree;
433
434 if (x != nil) {
435 if (x->left != nil) {
436 stuffToFree.Push(x->left);
437 }
438 if (x->right != nil) {
439 stuffToFree.Push(x->right);
440 }
441 // delete x->storedInterval;
442 delete x;
443 while( stuffToFree.NotEmpty() ) {
444 x = stuffToFree.Pop();
445 if (x->left != nil) {
446 stuffToFree.Push(x->left);
447 }
448 if (x->right != nil) {
449 stuffToFree.Push(x->right);
450 }
451 // delete x->storedInterval;
452 delete x;
453 }
454 }
455 delete nil;
456 delete root;
457 free(recursionNodeStack);
458 }
459
460
461 /***********************************************************************/
462 /* FUNCTION: Print */
463 /**/
464 /* INPUTS: none */
465 /**/
466 /* OUTPUT: none */
467 /**/
468 /* EFFECT: This function recursively prints the nodes of the tree */
469 /* inorder. */
470 /**/
471 /* Modifies Input: none */
472 /**/
473 /***********************************************************************/
474
475 void IntervalTree::Print() const {
476 TreePrintHelper(root->left);
477 }
478
479 /***********************************************************************/
480 /* FUNCTION: DeleteFixUp */
481 /**/
482 /* INPUTS: x is the child of the spliced */
483 /* out node in DeleteNode. */
484 /**/
485 /* OUTPUT: none */
486 /**/
487 /* EFFECT: Performs rotations and changes colors to restore red-black */
488 /* properties after a node is deleted */
489 /**/
490 /* Modifies Input: this, x */
491 /**/
492 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
493 /***********************************************************************/
494
495 void IntervalTree::DeleteFixUp(IntervalTreeNode* x) {
496 IntervalTreeNode * w;
497 IntervalTreeNode * rootLeft = root->left;
498
499 while( (!x->red) && (rootLeft != x)) {
500 if (x == x->parent->left) {
501 w=x->parent->right;
502 if (w->red) {
503 w->red=0;
504 x->parent->red=1;
505 LeftRotate(x->parent);
506 w=x->parent->right;
507 }
508 if ( (!w->right->red) && (!w->left->red) ) {
509 w->red=1;
510 x=x->parent;
511 } else {
512 if (!w->right->red) {
513 w->left->red=0;
514 w->red=1;
515 RightRotate(w);
516 w=x->parent->right;
517 }
518 w->red=x->parent->red;
519 x->parent->red=0;
520 w->right->red=0;
521 LeftRotate(x->parent);
522 x=rootLeft; /* this is to exit while loop */
523 }
524 } else { /* the code below is has left and right switched from above */
525 w=x->parent->left;
526 if (w->red) {
527 w->red=0;
528 x->parent->red=1;
529 RightRotate(x->parent);
530 w=x->parent->left;
531 }
532 if ( (!w->right->red) && (!w->left->red) ) {
533 w->red=1;
534 x=x->parent;
535 } else {
536 if (!w->left->red) {
537 w->right->red=0;
538 w->red=1;
539 LeftRotate(w);
540 w=x->parent->left;
541 }
542 w->red=x->parent->red;
543 x->parent->red=0;
544 w->left->red=0;
545 RightRotate(x->parent);
546 x=rootLeft; /* this is to exit while loop */
547 }
548 }
549 }
550 x->red=0;
551
552 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
553 CheckAssumptions();
554 #elif defined(DEBUG_ASSERT)
555 Assert(!nil->red,"nil not black in ITDeleteFixUp");
556 Assert((nil->maxHigh=MIN_INT),
557 "nil->maxHigh != MIN_INT in ITDeleteFixUp");
558 #endif
559 }
560
561
562 /***********************************************************************/
563 /* FUNCTION: DeleteNode */
564 /**/
565 /* INPUTS: tree is the tree to delete node z from */
566 /**/
567 /* OUTPUT: returns the Interval stored at deleted node */
568 /**/
569 /* EFFECT: Deletes z from tree and but don't call destructor */
570 /* Then calls FixUpMaxHigh to fix maxHigh fields then calls */
571 /* ITDeleteFixUp to restore red-black properties */
572 /**/
573 /* Modifies Input: z */
574 /**/
575 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
576 /***********************************************************************/
577
578 Interval * IntervalTree::DeleteNode(IntervalTreeNode * z){
579 IntervalTreeNode* y;
580 IntervalTreeNode* x;
581 Interval * returnValue = z->storedInterval;
582
583 y= ((z->left == nil) || (z->right == nil)) ? z : GetSuccessorOf(z);
584 x= (y->left == nil) ? y->right : y->left;
585 if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
586 root->left=x;
587 } else {
588 if (y == y->parent->left) {
589 y->parent->left=x;
590 } else {
591 y->parent->right=x;
592 }
593 }
594 if (y != z) { /* y should not be nil in this case */
595
596 #ifdef DEBUG_ASSERT
597 Assert( (y!=nil),"y is nil in DeleteNode \n");
598 #endif
599 /* y is the node to splice out and x is its child */
600
601 y->maxHigh = MIN_INT;
602 y->left=z->left;
603 y->right=z->right;
604 y->parent=z->parent;
605 z->left->parent=z->right->parent=y;
606 if (z == z->parent->left) {
607 z->parent->left=y;
608 } else {
609 z->parent->right=y;
610 }
611 FixUpMaxHigh(x->parent);
612 if (!(y->red)) {
613 y->red = z->red;
614 DeleteFixUp(x);
615 } else
616 y->red = z->red;
617 delete z;
618 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
619 CheckAssumptions();
620 #elif defined(DEBUG_ASSERT)
621 Assert(!nil->red,"nil not black in ITDelete");
622 Assert((nil->maxHigh=MIN_INT),"nil->maxHigh != MIN_INT in ITDelete");
623 #endif
624 } else {
625 FixUpMaxHigh(x->parent);
626 if (!(y->red)) DeleteFixUp(x);
627 delete y;
628 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
629 CheckAssumptions();
630 #elif defined(DEBUG_ASSERT)
631 Assert(!nil->red,"nil not black in ITDelete");
632 Assert((nil->maxHigh=MIN_INT),"nil->maxHigh != MIN_INT in ITDelete");
633 #endif
634 }
635 return returnValue;
636 }
637
638
639 /***********************************************************************/
640 /* FUNCTION: Overlap */
641 /**/
642 /* INPUTS: [a1,a2] and [b1,b2] are the low and high endpoints of two */
643 /* closed intervals. */
644 /**/
645 /* OUTPUT: stack containing pointers to the nodes between [low,high] */
646 /**/
647 /* Modifies Input: none */
648 /**/
649 /* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */
650 /***********************************************************************/
651
652 int Overlap(int a1, int a2, int b1, int b2) {
653 if (a1 <= b1) {
654 return( (b1 <= a2) );
655 } else {
656 return( (a1 <= b2) );
657 }
658 }
659
660
661 /***********************************************************************/
662 /* FUNCTION: Enumerate */
663 /**/
664 /* INPUTS: tree is the tree to look for intervals overlapping the */
665 /* closed interval [low,high] */
666 /**/
667 /* OUTPUT: stack containing pointers to the nodes overlapping */
668 /* [low,high] */
669 /**/
670 /* Modifies Input: none */
671 /**/
672 /* EFFECT: Returns a stack containing pointers to nodes containing */
673 /* intervals which overlap [low,high] in O(max(N,k*log(N))) */
674 /* where N is the number of intervals in the tree and k is */
675 /* the number of overlapping intervals */
676 /**/
677 /* Note: This basic idea for this function comes from the */
678 /* _Introduction_To_Algorithms_ book by Cormen et al, but */
679 /* modifications were made to return all overlapping intervals */
680 /* instead of just the first overlapping interval as in the */
681 /* book. The natural way to do this would require recursive */
682 /* calls of a basic search function. I translated the */
683 /* recursive version into an interative version with a stack */
684 /* as described below. */
685 /***********************************************************************/
686
687
688
689 /* The basic idea for the function below is to take the IntervalSearch */
690 /* function from the book and modify to find all overlapping intervals */
691 /* instead of just one. This means that any time we take the left */
692 /* branch down the tree we must also check the right branch if and only if */
693 /* we find an overlapping interval in that left branch. Note this is a */
694 /* recursive condition because if we go left at the root then go left */
695 /* again at the first left child and find an overlap in the left subtree */
696 /* of the left child of root we must recursively check the right subtree */
697 /* of the left child of root as well as the right child of root. */
698
699 TemplateStack<void *> * IntervalTree::Enumerate(int low,
700 int high) {
701 TemplateStack<void *> * enumResultStack;
702 IntervalTreeNode* x=root->left;
703 int stuffToDo = (x != nil);
704
705 // Possible speed up: add min field to prune right searches //
706
707 #ifdef DEBUG_ASSERT
708 Assert((recursionNodeStackTop == 1),
709 "recursionStack not empty when entering IntervalTree::Enumerate");
710 #endif
711 currentParent = 0;
712 enumResultStack = new TemplateStack<void *>(4);
713
714 while(stuffToDo) {
715 if (Overlap(low,high,x->key,x->high) ) {
716 enumResultStack->Push(x->storedInterval);
717 recursionNodeStack[currentParent].tryRightBranch=1;
718 }
719 if(x->left->maxHigh >= low) { // implies x != nil
720 if ( recursionNodeStackTop == recursionNodeStackSize ) {
721 recursionNodeStackSize *= 2;
722 recursionNodeStack = (it_recursion_node *)
723 realloc(recursionNodeStack,
724 recursionNodeStackSize * sizeof(it_recursion_node));
725 if (recursionNodeStack == NULL)
726 exit(1);
727 }
728 recursionNodeStack[recursionNodeStackTop].start_node = x;
729 recursionNodeStack[recursionNodeStackTop].tryRightBranch = 0;
730 recursionNodeStack[recursionNodeStackTop].parentIndex = currentParent;
731 currentParent = recursionNodeStackTop++;
732 x = x->left;
733 } else {
734 x = x->right;
735 }
736 stuffToDo = (x != nil);
737 while( (!stuffToDo) && (recursionNodeStackTop > 1) ) {
738 if(recursionNodeStack[--recursionNodeStackTop].tryRightBranch) {
739 x=recursionNodeStack[recursionNodeStackTop].start_node->right;
740 currentParent=recursionNodeStack[recursionNodeStackTop].parentIndex;
741 recursionNodeStack[currentParent].tryRightBranch=1;
742 stuffToDo = ( x != nil);
743 }
744 }
745 }
746 #ifdef DEBUG_ASSERT
747 Assert((recursionNodeStackTop == 1),
748 "recursionStack not empty when exiting IntervalTree::Enumerate");
749 #endif
750 return(enumResultStack);
751 }
752
753
754
755 int IntervalTree::CheckMaxHighFieldsHelper(IntervalTreeNode * y,
756 const int currentHigh,
757 int match) const
758 {
759 if (y != nil) {
760 match = CheckMaxHighFieldsHelper(y->left,currentHigh,match) ?
761 1 : match;
762 if (y->high == currentHigh)
763 match = 1;
764 match = CheckMaxHighFieldsHelper(y->right,currentHigh,match) ?
765 1 : match;
766 }
767 return match;
768 }
769
770
771
772 /* Make sure the maxHigh fields for everything makes sense. *
773 * If something is wrong, print a warning and exit */
774 void IntervalTree::CheckMaxHighFields(IntervalTreeNode * x) const {
775 if (x != nil) {
776 CheckMaxHighFields(x->left);
777 if(!(CheckMaxHighFieldsHelper(x,x->maxHigh,0) > 0)) {
778 exit(1);
779 }
780 CheckMaxHighFields(x->right);
781 }
782 }
783
784 void IntervalTree::CheckAssumptions() const {
785 CheckMaxHighFields(root->left);
786 }