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 User Rev File contents
1 gpertea 2 #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 gpertea 171 IntervalTreeNode::IntervalTreeNode():key(0),high(0),maxHigh(0){}
24     IntervalTreeNode::IntervalTreeNode(Interval * newInterval)
25 gpertea 2 : storedInterval (newInterval) ,
26 gpertea 171 key(newInterval->GetLowPoint()),
27     high(newInterval->GetHighPoint()) ,
28 gpertea 2 maxHigh(high) {}
29     IntervalTreeNode::~IntervalTreeNode(){}
30     Interval::Interval(){}
31     Interval::~Interval(){}
32     void Interval::Print() const {}
33    
34     IntervalTree::IntervalTree()
35     {
36 gpertea 171 currentParent=NULL;
37 gpertea 2 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 gpertea 171
43 gpertea 2 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 gpertea 171 recursionNodeStack = (it_recursion_node *)
52 gpertea 2 malloc(recursionNodeStackSize*sizeof(it_recursion_node));
53     recursionNodeStackTop = 1;
54     recursionNodeStack[0].start_node = NULL;
55 gpertea 171
56 gpertea 2 }
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 gpertea 171
78 gpertea 2 /* 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 gpertea 171 y->parent=x->parent;
95    
96 gpertea 2 /* 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 gpertea 171 y->maxHigh=MAX(x->maxHigh,GMAX(y->right->maxHigh,y->high));
108 gpertea 2 #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 gpertea 171
197 gpertea 2 z->left=z->right=nil;
198     y=root;
199     x=root->left;
200     while( x != nil) {
201     y=x;
202 gpertea 171 if ( x->key > z->key) {
203 gpertea 2 x=x->left;
204     } else { /* x->key <= z->key */
205     x=x->right;
206     }
207     }
208     z->parent=y;
209     if ( (y == root) ||
210 gpertea 171 (y->key > z->key) ) {
211 gpertea 2 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 gpertea 171 }
295 gpertea 2 } 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 gpertea 171 }
313 gpertea 2 }
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 gpertea 171
341 gpertea 2 IntervalTreeNode * IntervalTree::GetSuccessorOf(IntervalTreeNode * x) const
342 gpertea 171 {
343 gpertea 2 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 gpertea 171 while(x == y->left) {
385     if (y == root) return(nil);
386 gpertea 2 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 gpertea 171
423 gpertea 2 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 gpertea 171 if ( (!w->right->red) && (!w->left->red) ) {
509 gpertea 2 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 gpertea 171 if ( (!w->right->red) && (!w->left->red) ) {
533 gpertea 2 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 gpertea 171
601 gpertea 2 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 gpertea 171 z->parent->left=y;
608 gpertea 2 } else {
609     z->parent->right=y;
610     }
611 gpertea 171 FixUpMaxHigh(x->parent);
612 gpertea 2 if (!(y->red)) {
613     y->red = z->red;
614     DeleteFixUp(x);
615     } else
616 gpertea 171 y->red = z->red;
617 gpertea 2 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 gpertea 171 TemplateStack<void *> * IntervalTree::Enumerate(int low,
700 gpertea 2 int high) {
701     TemplateStack<void *> * enumResultStack;
702     IntervalTreeNode* x=root->left;
703     int stuffToDo = (x != nil);
704 gpertea 171
705 gpertea 2 // 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 gpertea 171 if(x->left->maxHigh >= low) { // implies x != nil
720 gpertea 2 if ( recursionNodeStackTop == recursionNodeStackSize ) {
721     recursionNodeStackSize *= 2;
722 gpertea 171 recursionNodeStack = (it_recursion_node *)
723 gpertea 2 realloc(recursionNodeStack,
724     recursionNodeStackSize * sizeof(it_recursion_node));
725 gpertea 171 if (recursionNodeStack == NULL)
726 gpertea 2 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 gpertea 171 return(enumResultStack);
751 gpertea 2 }
752    
753    
754 gpertea 171
755     int IntervalTree::CheckMaxHighFieldsHelper(IntervalTreeNode * y,
756 gpertea 2 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 gpertea 171
772 gpertea 2 /* 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     }