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 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     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