ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.cpp
Revision: 2
Committed: Mon Mar 22 22:03:27 2010 UTC (9 years, 3 months ago) by gpertea
File size: 23783 byte(s)
Log Message:
added my gclib source files

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