ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.hh
Revision: 264
Committed: Mon Aug 27 18:21:11 2012 UTC (6 years, 10 months ago) by gpertea
File size: 37464 byte(s)
Log Message:
minor refactoring etc

Line User Rev File contents
1 gpertea 248 #ifndef GINTERVALTREE_HH_
2     #define GINTERVALTREE_HH_
3    
4 gpertea 264 #include <limits>
5 gpertea 248 #include "GBase.h"
6     #include "GVec.hh"
7 gpertea 264 using namespace std;
8    
9 gpertea 248 //#include <sstream>
10     //#include <vector>
11     //#include <string>
12 gpertea 252 #define DEBUG_ASSERT 1
13     //#define CHECK_INTERVAL_TREE_ASSUMPTIONS 1
14 gpertea 248 // This file contains code for
15     // interval trees implemented using red-black-trees as described in
16     // the book _Introduction_To_Algorithms_ by Cormen, Leisserson,
17     // and Rivest.
18    
19     // The low should return the lowest point of the interval and
20     // the high should return the highest point of the interval.
21    
22     // T = type of data associated with each interval is stored in a <T>
23    
24 gpertea 250 template<typename T, typename N=int32_t> class IntervalTree {
25 gpertea 248 public:
26     enum color_t {BLACK, RED};
27    
28     class Node {
29     friend class IntervalTree<T,N>;
30     public:
31     //std::string str(Node *, Node *) const;
32     Node();
33     Node(const T&, N, N);
34     virtual ~Node();
35     N low() const { return key; }
36     N high() const { return high_; }
37     T value() const { return value_; }
38     protected:
39     T value_;
40     N key;
41     N high_;
42     N maxHigh;
43 gpertea 250 int n_idx; //location in IntervalTree::nodes array
44     int left_n_idx; // left node index in nodes array
45     int right_n_idx; // right node index in nodes array
46     int parent_n_idx; //parent node index in nodes array
47 gpertea 248 color_t color;
48     Node * left;
49     Node * right;
50     Node * parent;
51 gpertea 250 }; //Node
52 gpertea 248
53     struct it_recursion_node {
54     /* this structure stores the information needed when we take the */
55     /* right branch in searching for intervals but possibly come back */
56     /* and check the left branch as well. */
57     it_recursion_node(Node *start_node_=NULL,
58     size_t parentIndex_=0,
59     bool tryRightBranch_=false)
60 gpertea 250 : start_node (start_node_),
61     parentIndex (parentIndex_),
62     tryRightBranch (tryRightBranch_) {}
63 gpertea 248
64     Node * start_node;
65     size_t parentIndex;
66     bool tryRightBranch;
67     };
68    
69     IntervalTree();
70 gpertea 252 IntervalTree(FILE* f, GFLoadProc fLoadFunc=NULL); //create by deserialization from file
71 gpertea 250
72 gpertea 248 ~IntervalTree();
73 gpertea 250
74 gpertea 252 void Store(FILE* f, GFStoreProc fStoreFunc=NULL); //write the tree into a file
75     void Load(FILE* f, GFLoadProc fLoadFunc=NULL);
76 gpertea 248 //std::string str() const;
77     void remove(N, N, GVec<T>&);
78     template <class F> void remove(N, N, const F&, GVec<T>&);
79     void remove_window(N, N, GVec<T>&);
80     template <class F> void remove_window(N, N, const F&, GVec<T>&);
81     Node * insert(const T&, N, N);
82     void fetch(N, N, GVec<T>&);
83     void fetch_window(N, N, GVec<T>&);
84     protected:
85     void fetch_node(N, N, GVec<Node*>&);
86     void fetch_window_node(N, N, GVec<Node*>&);
87     T remove(Node *);
88     Node * GetPredecessorOf(Node *) const;
89     Node * GetSuccessorOf(Node *) const;
90     void check() const;
91    
92     /* A sentinel is used for root and for nil. These sentinels are */
93     /* created when ITTreeCreate is caled. root->left should always */
94     /* point to the node which is the root of the tree. nil points to a */
95     /* node which should always be black but has aribtrary children and */
96     /* parent and no key or info. The point of using these sentinels is so */
97     /* that the root and nil nodes do not require special cases in the code */
98 gpertea 250 GPVec<Node> nodes; //store all the tree nodes for easy de/serialization
99 gpertea 248 Node * root;
100     Node * nil;
101    
102     N Overlap(N a1, N a2, N b1, N b2);
103     N Contain(N a1, N a2, N b1, N b2);
104     void LeftRotate(Node *);
105     void RightRotate(Node *);
106     void TreeInsertHelp(Node *);
107     //void TreePrintHelper(Node *, std::stringstream&) const;
108     void FixUpMaxHigh(Node *);
109     void DeleteFixUp(Node *);
110     void CheckMaxHighFields(Node *) const;
111     bool CheckMaxHighFieldsHelper(Node * y,
112     const N currentHigh,
113     bool match) const;
114     private:
115     GVec<IntervalTree<T,N>::it_recursion_node> recursionNodeStack;
116 gpertea 252 int currentParent;
117 gpertea 248 };
118    
119     // If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the
120     // code does a lot of extra checking to make sure certain assumptions
121     // are satisfied. This only needs to be done if you suspect bugs are
122     // present or if you make significant changes and want to make sure
123     // your changes didn't mess anything up.
124     // #define CHECK_INTERVAL_TREE_ASSUMPTIONS 1
125    
126 gpertea 264 template<typename T, typename N> IntervalTree<T,N>::Node::Node()
127     : //value_ (value__),
128     key(numeric_limits<N>::min()),
129     high_(numeric_limits<N>::min()),
130     maxHigh(numeric_limits<N>::min()),
131     n_idx(-1), //location in IntervalTree::nodes array
132     left_n_idx(0), // left node index in nodes array
133     right_n_idx(0), // right node index in nodes array
134     parent_n_idx(0), //parent node index in nodes array
135     color(BLACK),
136     left(NULL),
137     right(NULL),
138     parent(NULL)
139     {
140 gpertea 248 }
141    
142     template<typename T, typename N>
143     IntervalTree<T,N>::Node::Node(const T& value__, N lowPoint, N highPoint)
144     : value_ (value__),
145     key(lowPoint),
146     high_(highPoint),
147 gpertea 250 maxHigh(highPoint),
148     n_idx(-1), //location in IntervalTree::nodes array
149     left_n_idx(0), // left node index in nodes array
150     right_n_idx(0), // right node index in nodes array
151     parent_n_idx(0), //parent node index in nodes array
152     color(BLACK),
153     left(NULL),
154     right(NULL),
155     parent(NULL)
156    
157 gpertea 248 {
158     }
159    
160     template<typename T, typename N>
161     IntervalTree<T,N>::Node::~Node()
162     {
163     }
164    
165     template<typename T, typename N>
166 gpertea 250 IntervalTree<T,N>::IntervalTree() : nodes(64, true)
167 gpertea 248 {
168 gpertea 264 currentParent = 0;
169 gpertea 248 nil = new IntervalTree<T,N>::Node();
170     nil->left = nil->right = nil->parent = nil;
171     nil->color = BLACK;
172 gpertea 264 nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
173 gpertea 250 nodes.Add(nil); //index 0
174     nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
175 gpertea 248 root = new IntervalTree<T,N>::Node();
176     root->parent = root->left = root->right = nil;
177 gpertea 250 root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
178     root->n_idx = nodes.Add(root);
179 gpertea 264 root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
180 gpertea 248 root->color=BLACK;
181    
182     /* the following are used for the fetch function */
183     recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
184     }
185 gpertea 252
186    
187 gpertea 248 template<typename T, typename N>
188 gpertea 252 IntervalTree<T,N>::IntervalTree(FILE* f, GFLoadProc* fLoadFunc): nodes(64, true)
189     {
190     nil = new IntervalTree<T,N>::Node();
191     nil->left = nil->right = nil->parent = nil;
192     nil->color = BLACK;
193 gpertea 264 nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
194 gpertea 252 nodes.Add(nil); //index 0
195     nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
196     root = new IntervalTree<T,N>::Node(); //root is index 1
197     root->parent = root->left = root->right = nil;
198     root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
199     root->n_idx = nodes.Add(root);
200 gpertea 264 root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
201 gpertea 252 root->color=BLACK;
202    
203     // neeeded by the fetch function
204     recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
205    
206     Load(f, fLoadFunc);
207    
208 gpertea 248 }
209    
210 gpertea 252
211 gpertea 248 template<typename T, typename N>
212 gpertea 252 void IntervalTree<T,N>::Load(FILE* f, GFLoadProc* fLoadFunc) {
213    
214 gpertea 248 }
215    
216     /***********************************************************************/
217     /* FUNCTION: LeftRotate */
218     /**/
219     /* INPUTS: the node to rotate on */
220     /**/
221     /* OUTPUT: None */
222     /**/
223     /* Modifies Input: this, x */
224     /**/
225     /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
226     /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
227     /* makes the parent of x be to the left of x, x the parent of */
228     /* its parent before the rotation and fixes other pointers */
229     /* accordingly. Also updates the maxHigh fields of x and y */
230     /* after rotation. */
231     /***********************************************************************/
232    
233     template<typename T, typename N>
234     void IntervalTree<T,N>::LeftRotate(IntervalTree<T,N>::Node* x) {
235     IntervalTree<T,N>::Node* y;
236    
237     /* I originally wrote this function to use the sentinel for */
238     /* nil to avoid checking for nil. However this introduces a */
239     /* very subtle bug because sometimes this function modifies */
240     /* the parent pointer of nil. This can be a problem if a */
241     /* function which calls LeftRotate also uses the nil sentinel */
242     /* and expects the nil sentinel's parent pointer to be unchanged */
243     /* after calling this function. For example, when DeleteFixUP */
244     /* calls LeftRotate it expects the parent pointer of nil to be */
245     /* unchanged. */
246    
247     y=x->right;
248     x->right=y->left;
249    
250     if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
251     /* and do an unconditional assignment instead of testing for nil */
252    
253     y->parent=x->parent;
254    
255     /* instead of checking if x->parent is the root as in the book, we */
256     /* count on the root sentinel to implicitly take care of this case */
257     if( x == x->parent->left) {
258     x->parent->left=y;
259     } else {
260     x->parent->right=y;
261     }
262     y->left=x;
263     x->parent=y;
264    
265     x->maxHigh=GMAX(x->left->maxHigh, (GMAX(x->right->maxHigh,x->high_)));
266     y->maxHigh=GMAX(x->maxHigh, (GMAX(y->right->maxHigh,y->high_)) );
267     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
268     check();
269     #elif defined(DEBUG_ASSERT)
270 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
271     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITLeftRotate!\n");
272 gpertea 248 #endif
273     }
274    
275    
276     /***********************************************************************/
277     /* FUNCTION: RighttRotate */
278     /**/
279     /* INPUTS: node to rotate on */
280     /**/
281     /* OUTPUT: None */
282     /**/
283     /* Modifies Input?: this, y */
284     /**/
285     /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
286     /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
287     /* makes the parent of x be to the left of x, x the parent of */
288     /* its parent before the rotation and fixes other pointers */
289     /* accordingly. Also updates the maxHigh fields of x and y */
290     /* after rotation. */
291     /***********************************************************************/
292    
293    
294     template<typename T, typename N>
295     void IntervalTree<T,N>::RightRotate(IntervalTree<T,N>::Node* y) {
296     IntervalTree<T,N>::Node* x;
297    
298     /* I originally wrote this function to use the sentinel for */
299     /* nil to avoid checking for nil. However this introduces a */
300     /* very subtle bug because sometimes this function modifies */
301     /* the parent pointer of nil. This can be a problem if a */
302     /* function which calls LeftRotate also uses the nil sentinel */
303     /* and expects the nil sentinel's parent pointer to be unchanged */
304     /* after calling this function. For example, when DeleteFixUP */
305     /* calls LeftRotate it expects the parent pointer of nil to be */
306     /* unchanged. */
307    
308     x=y->left;
309     y->left=x->right;
310    
311     if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
312     /* and do an unconditional assignment instead of testing for nil */
313    
314     /* instead of checking if x->parent is the root as in the book, we */
315     /* count on the root sentinel to implicitly take care of this case */
316     x->parent=y->parent;
317     if( y == y->parent->left) {
318     y->parent->left=x;
319     } else {
320     y->parent->right=x;
321     }
322     x->right=y;
323     y->parent=x;
324    
325     y->maxHigh=GMAX(y->left->maxHigh,(GMAX(y->right->maxHigh,y->high_)));
326     x->maxHigh=GMAX(x->left->maxHigh,(GMAX(y->maxHigh,x->high_)));
327     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
328     check();
329     #elif defined(DEBUG_ASSERT)
330 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
331     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITRightRotate!\n");
332 gpertea 248 #endif
333     }
334    
335     /***********************************************************************/
336     /* FUNCTION: TreeInsertHelp */
337     /**/
338     /* INPUTS: z is the node to insert */
339     /**/
340     /* OUTPUT: none */
341     /**/
342     /* Modifies Input: this, z */
343     /**/
344     /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
345     /* using the algorithm described in _Introduction_To_Algorithms_ */
346     /* by Cormen et al. This funciton is only intended to be called */
347     /* by the InsertTree function and not by the user */
348     /***********************************************************************/
349    
350     template<typename T, typename N>
351     void IntervalTree<T,N>::TreeInsertHelp(IntervalTree<T,N>::Node* z) {
352     /* This function should only be called by InsertITTree (see above) */
353     IntervalTree<T,N>::Node* x;
354     IntervalTree<T,N>::Node* y;
355    
356     z->left=z->right=nil;
357     y=root;
358     x=root->left;
359     while( x != nil) {
360     y=x;
361     if ( x->key > z->key) {
362     x=x->left;
363     } else { /* x->key <= z->key */
364     x=x->right;
365     }
366     }
367     z->parent=y;
368     if ( (y == root) ||
369     (y->key > z->key) ) {
370     y->left=z;
371     } else {
372     y->right=z;
373     }
374    
375    
376     #if defined(DEBUG_ASSERT)
377 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
378     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsertHelp!\n");
379 gpertea 248 #endif
380     }
381    
382    
383     /***********************************************************************/
384     /* FUNCTION: FixUpMaxHigh */
385     /**/
386     /* INPUTS: x is the node to start from*/
387     /**/
388     /* OUTPUT: none */
389     /**/
390     /* Modifies Input: this */
391     /**/
392     /* EFFECTS: Travels up to the root fixing the maxHigh fields after */
393     /* an insertion or deletion */
394     /***********************************************************************/
395    
396     template<typename T, typename N>
397     void IntervalTree<T,N>::FixUpMaxHigh(IntervalTree<T,N>::Node * x) {
398     while(x != root) {
399     x->maxHigh=GMAX(x->high_, (GMAX(x->left->maxHigh,x->right->maxHigh)));
400     x=x->parent;
401     }
402     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
403     check();
404     #endif
405     }
406    
407     /* Before calling InsertNode the node x should have its key set */
408    
409     /***********************************************************************/
410     /* FUNCTION: InsertNode */
411     /**/
412     /* INPUTS: newInterval is the interval to insert*/
413     /**/
414     /* OUTPUT: This function returns a pointer to the newly inserted node */
415     /* which is guarunteed to be valid until this node is deleted. */
416     /* What this means is if another data structure stores this */
417     /* pointer then the tree does not need to be searched when this */
418     /* is to be deleted. */
419     /**/
420     /* Modifies Input: tree */
421     /**/
422     /* EFFECTS: Creates a node node which contains the appropriate key and */
423     /* info pointers and inserts it into the tree. */
424     /***********************************************************************/
425    
426     template <typename T, typename N>
427     typename IntervalTree<T,N>::Node* IntervalTree<T,N>::insert(const T& newInterval, N low, N high)
428     {
429     IntervalTree<T,N>::Node * y;
430     IntervalTree<T,N>::Node * x;
431     IntervalTree<T,N>::Node * newNode;
432    
433     x = new IntervalTree<T,N>::Node(newInterval, low, high);
434     TreeInsertHelp(x);
435     FixUpMaxHigh(x->parent);
436     newNode = x;
437 gpertea 250 newNode->n_idx = nodes.Add(newNode);
438 gpertea 248 x->color=RED;
439     while(x->parent->color == RED) { /* use sentinel instead of checking for root */
440     if (x->parent == x->parent->parent->left) {
441     y=x->parent->parent->right;
442     if (y->color == RED) {
443     x->parent->color=BLACK;
444     y->color=BLACK;
445     x->parent->parent->color=RED;
446     x=x->parent->parent;
447     } else {
448     if (x == x->parent->right) {
449     x=x->parent;
450     LeftRotate(x);
451     }
452     x->parent->color=BLACK;
453     x->parent->parent->color=RED;
454     RightRotate(x->parent->parent);
455     }
456     } else { /* case for x->parent == x->parent->parent->right */
457     /* this part is just like the section above with */
458     /* left and right interchanged */
459     y=x->parent->parent->left;
460     if (y->color == RED) {
461     x->parent->color=BLACK;
462     y->color=BLACK;
463     x->parent->parent->color=RED;
464     x=x->parent->parent;
465     } else {
466     if (x == x->parent->left) {
467     x=x->parent;
468     RightRotate(x);
469     }
470     x->parent->color=BLACK;
471     x->parent->parent->color=RED;
472     LeftRotate(x->parent->parent);
473     }
474     }
475     }
476     root->left->color=BLACK;
477 gpertea 250 //update new node link indexes
478     newNode->left_n_idx = newNode->left->n_idx;
479     newNode->right_n_idx = newNode->right->n_idx;
480     newNode->parent_n_idx = newNode->parent->n_idx;
481 gpertea 248 return(newNode);
482    
483     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
484     check();
485     #elif defined(DEBUG_ASSERT)
486     if (root->color != RED) GError("Error: root not red in ITTreeInsert\n");
487 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
488     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsert\n");
489 gpertea 248 #endif
490     }
491    
492     /***********************************************************************/
493     /* FUNCTION: GetSuccessorOf */
494     /**/
495     /* INPUTS: x is the node we want the succesor of */
496     /**/
497     /* OUTPUT: This function returns the successor of x or NULL if no */
498     /* successor exists. */
499     /**/
500     /* Modifies Input: none */
501     /**/
502     /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
503     /***********************************************************************/
504    
505     template<typename T, typename N>
506     typename IntervalTree<T,N>::Node * IntervalTree<T,N>::GetSuccessorOf(IntervalTree<T,N>::Node * x) const
507     {
508     IntervalTree<T,N>::Node* y;
509    
510     if (nil != (y = x->right)) { /* assignment to y is intentional */
511     while(y->left != nil) { /* returns the minium of the right subtree of x */
512     y=y->left;
513     }
514     return(y);
515     } else {
516     y=x->parent;
517     while(x == y->right) { /* sentinel used instead of checking for nil */
518     x=y;
519     y=y->parent;
520     }
521     if (y == root) return(nil);
522     return(y);
523     }
524     }
525    
526     /***********************************************************************/
527     /* FUNCTION: GetPredecessorOf */
528     /**/
529     /* INPUTS: x is the node to get predecessor of */
530     /**/
531     /* OUTPUT: This function returns the predecessor of x or NULL if no */
532     /* predecessor exists. */
533     /**/
534     /* Modifies Input: none */
535     /**/
536     /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
537     /***********************************************************************/
538    
539     template<typename T, typename N>
540     typename IntervalTree<T,N>::Node * IntervalTree<T,N>::GetPredecessorOf(IntervalTree<T,N>::Node * x) const {
541     IntervalTree<T,N>::Node* y;
542    
543     if (nil != (y = x->left)) { /* assignment to y is intentional */
544     while(y->right != nil) { /* returns the maximum of the left subtree of x */
545     y=y->right;
546     }
547     return(y);
548     } else {
549     y=x->parent;
550     while(x == y->left) {
551     if (y == root) return(nil);
552     x=y;
553     y=y->parent;
554     }
555     return(y);
556     }
557     }
558    
559     /***********************************************************************/
560     /* FUNCTION: str */
561     /**/
562     /* INPUTS: none */
563     /**/
564     /* OUTPUT: none */
565     /**/
566     /* EFFECTS: This function recursively prints the nodes of the tree */
567     /* inorder. */
568     /**/
569     /* Modifies Input: none */
570     /**/
571     /* Note: This function should only be called from ITTreePrint */
572     /***********************************************************************/
573     /*
574     template<typename T, typename N>
575     std::string IntervalTree<T,N>::Node::str(IntervalTree<T,N>::Node * nil,
576     IntervalTree<T,N>::Node * root) const {
577     std::stringstream s;
578    
579     s << value_;
580     s << ", k=" << key << ", h=" << high_ << ", mH=" << maxHigh;
581     s << " l->key=";
582     if( left == nil) s << "NULL"; else s << left->key;
583     s << " r->key=";
584     if( right == nil) s << "NULL"; else s << right->key;
585     s << " p->key=";
586     if( parent == root) s << "NULL"; else s << parent->key;
587     s << " color=" << (color == RED ? "RED" : "BLACK") << std::endl;
588     return s.str();
589     }
590    
591    
592     template<typename T, typename N>
593     void IntervalTree<T,N>::TreePrintHelper(IntervalTree<T,N>::Node* x, std::stringstream &s) const {
594     if (x != nil) {
595     TreePrintHelper(x->left, s);
596     s << x->str(nil,root);
597     TreePrintHelper(x->right, s);
598     }
599     }
600     */
601    
602     template<typename T, typename N>
603     IntervalTree<T,N>::~IntervalTree() {
604 gpertea 250 nodes.Clear(); //this should also free all allocated nodes
605     /*
606 gpertea 248 IntervalTree<T,N>::Node * x = root->left;
607     GVec<IntervalTree<T,N>::Node *> stuffToFree;
608    
609     if (x != nil) {
610     if (x->left != nil) {
611     stuffToFree.Push(x->left);
612     }
613     if (x->right != nil) {
614     stuffToFree.Push(x->right);
615     }
616     delete x;
617     while( stuffToFree.notEmpty() ) {
618     x = stuffToFree.Pop();
619     if (x->left != nil) {
620     stuffToFree.Push(x->left);
621     }
622     if (x->right != nil) {
623     stuffToFree.Push(x->right);
624     }
625     delete x;
626     }
627     }
628     delete nil;
629     delete root;
630 gpertea 250 */
631 gpertea 248 }
632    
633    
634     /***********************************************************************/
635     /* FUNCTION: str */
636     /**/
637     /* INPUTS: none */
638     /**/
639     /* OUTPUT: none */
640     /**/
641     /* EFFECT: This function recursively prints the nodes of the tree */
642     /* inorder. */
643     /**/
644     /* Modifies Input: none */
645     /**/
646     /***********************************************************************/
647     /*
648     template<typename T, typename N>
649     std::string IntervalTree<T,N>::str() const {
650     std::stringstream s;
651     TreePrintHelper(root->left, s);
652     return s.str();
653     }
654     */
655     /***********************************************************************/
656     /* FUNCTION: DeleteFixUp */
657     /**/
658     /* INPUTS: x is the child of the spliced */
659     /* out node in remove. */
660     /**/
661     /* OUTPUT: none */
662     /**/
663     /* EFFECT: Performs rotations and changes colors to restore red-black */
664     /* properties after a node is deleted */
665     /**/
666     /* Modifies Input: this, x */
667     /**/
668     /* The algorithm from this function is from _Introduction_To_Algorithms_ */
669     /***********************************************************************/
670    
671     template<typename T,typename N>
672     void IntervalTree<T,N>::DeleteFixUp(IntervalTree<T,N>::Node* x) {
673     IntervalTree<T,N>::Node * w;
674     IntervalTree<T,N>::Node * rootLeft = root->left;
675    
676     while( (x->color == BLACK) && (rootLeft != x)) {
677     if (x == x->parent->left) {
678     w=x->parent->right;
679     if (w->color == RED) {
680     w->color=BLACK;
681     x->parent->color=RED;
682     LeftRotate(x->parent);
683     w=x->parent->right;
684     }
685     if ( (w->right->color == BLACK) && (w->left->color == BLACK) ) {
686     w->color=RED;
687     x=x->parent;
688     } else {
689     if (w->right->color == BLACK) {
690     w->left->color=BLACK;
691     w->color=RED;
692     RightRotate(w);
693     w=x->parent->right;
694     }
695     w->color=x->parent->color;
696     x->parent->color=BLACK;
697     w->right->color=BLACK;
698     LeftRotate(x->parent);
699     x=rootLeft; /* this is to exit while loop */
700     }
701     } else { /* the code below is has left and right switched from above */
702     w=x->parent->left;
703     if (w->color == RED) {
704     w->color=BLACK;
705     x->parent->color=RED;
706     RightRotate(x->parent);
707     w=x->parent->left;
708     }
709     if ( (w->right->color == BLACK) && (w->left->color == BLACK) ) {
710     w->color=RED;
711     x=x->parent;
712     } else {
713     if (w->left->color == BLACK) {
714     w->right->color=BLACK;
715     w->color=RED;
716     LeftRotate(w);
717     w=x->parent->left;
718     }
719     w->color=x->parent->color;
720     x->parent->color=BLACK;
721     w->left->color=BLACK;
722     RightRotate(x->parent);
723     x=rootLeft; /* this is to exit while loop */
724     }
725     }
726     }
727     x->color=BLACK;
728    
729     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
730     check();
731     #elif defined(DEBUG_ASSERT)
732     if (nil->color != BLACK) GError("Error: nil not black in ITDeleteFixUp\n");
733 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
734     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDeleteFixUp\n");
735 gpertea 248 #endif
736     }
737    
738    
739     /***********************************************************************/
740     /* FUNCTION: remove */
741     /**/
742     /* INPUTS: tree is the tree to delete node z from */
743     /**/
744     /* OUTPUT: returns the Interval stored at deleted node */
745     /**/
746     /* EFFECT: Deletes z from tree and but don't call destructor */
747     /* Then calls FixUpMaxHigh to fix maxHigh fields then calls */
748     /* ITDeleteFixUp to restore red-black properties */
749     /**/
750     /* Modifies Input: z */
751     /**/
752     /* The algorithm from this function is from _Introduction_To_Algorithms_ */
753     /***********************************************************************/
754    
755     template<typename T, typename N>
756     T IntervalTree<T,N>::remove(IntervalTree<T,N>::Node * z){
757     IntervalTree<T,N>::Node* y;
758     IntervalTree<T,N>::Node* x;
759     T returnValue = z->value();
760    
761     y= ((z->left == nil) || (z->right == nil)) ? z : GetSuccessorOf(z);
762     x= (y->left == nil) ? y->right : y->left;
763     if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
764     root->left=x;
765     } else {
766     if (y == y->parent->left) {
767     y->parent->left=x;
768     } else {
769     y->parent->right=x;
770     }
771     }
772     if (y != z) { /* y should not be nil in this case */
773    
774     #ifdef DEBUG_ASSERT
775     if (y!=nil) GError("Error: y is nil in remove()!\n");
776     #endif
777     /* y is the node to splice out and x is its child */
778    
779 gpertea 264 y->maxHigh = numeric_limits<N>::min();
780 gpertea 248 y->left=z->left;
781     y->right=z->right;
782     y->parent=z->parent;
783     z->left->parent=z->right->parent=y;
784     if (z == z->parent->left) {
785     z->parent->left=y;
786     } else {
787     z->parent->right=y;
788     }
789     FixUpMaxHigh(x->parent);
790     if (y->color == BLACK) {
791     y->color = z->color;
792     DeleteFixUp(x);
793     } else
794     y->color = z->color;
795     delete z;
796     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
797     check();
798     #elif defined(DEBUG_ASSERT)
799     if (nil->color != BLACK) GError("Error: nil not black in ITDelete\n!");
800 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
801     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
802 gpertea 248 #endif
803     } else {
804     FixUpMaxHigh(x->parent);
805     if (y->color == BLACK) DeleteFixUp(x);
806     delete y;
807     #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
808     check();
809     #elif defined(DEBUG_ASSERT)
810     if (nil->color != BLACK) GError("Error: nil not black in ITDelete\n");
811 gpertea 264 if (nil->maxHigh!=numeric_limits<N>::min())
812     GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
813 gpertea 248 #endif
814     }
815     return returnValue;
816     }
817    
818     template <typename T, typename N>
819     void IntervalTree<T,N>::remove(N low, N high, GVec<T> &removed)
820     {
821     GVec<IntervalTree<T,N>::Node*> got;
822     fetch_node(low, high, got);
823     for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
824     i=got.begin(); i!=got.end(); ++i)
825     {
826 gpertea 250 removed.Push((*i)->value());
827 gpertea 248 remove(*i);
828     }
829     }
830    
831     template <typename T, typename N> template <typename F>
832     void IntervalTree<T,N>::remove(N low, N high, const F &removeFunctor, GVec<T> &removed)
833     {
834     GVec<IntervalTree<T,N>::Node*> got;
835     fetch_node(low, high, got);
836     for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
837     i=got.begin(); i!=got.end(); ++i)
838     {
839     if (removeFunctor((*i)->value(), (*i)->low(), (*i)->high())) {
840 gpertea 250 removed.Push((*i)->value());
841 gpertea 248 remove(*i);
842     }
843     }
844     }
845    
846     template <typename T, typename N>
847     void IntervalTree<T,N>::remove_window(N low, N high, GVec<T> &removed)
848     {
849     GVec<IntervalTree<T,N>::Node*> got;
850     fetch_window_node(low, high, got);
851     for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
852     i=got.begin(); i!=got.end(); ++i)
853     {
854 gpertea 250 removed.Push((*i)->value());
855 gpertea 248 remove(*i);
856     }
857     }
858    
859     template <typename T, typename N> template <typename F>
860     void IntervalTree<T,N>::remove_window(
861     N low,
862     N high,
863     const F& removeFunctor,
864     GVec<T> &removed)
865     {
866     GVec<IntervalTree<T,N>::Node*> got;
867     fetch_window_node(low, high, got);
868     for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
869     i=got.begin(); i!=got.end(); ++i)
870     {
871     if (removeFunctor((*i)->value(), (*i)->low(), (*i)->high())) {
872 gpertea 250 removed.Push((*i)->value());
873 gpertea 248 remove(*i);
874     }
875     }
876     }
877    
878     /***********************************************************************/
879     /* FUNCTION: Overlap */
880     /**/
881     /* INPUTS: [a1,a2) and [b1,b2) are the low and high endpoints of two */
882     /* intervals. */
883     /**/
884     /* OUTPUT: stack containing pointers to the nodes between [low,high) */
885     /**/
886     /* Modifies Input: none */
887     /**/
888     /* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */
889     /***********************************************************************/
890    
891     template<typename T, typename N>
892     N IntervalTree<T,N>::Overlap(N a1, N a2, N b1, N b2) {
893     return a1 <= b2 && b1 <= a2;
894     }
895    
896    
897     template<typename T, typename N>
898     N IntervalTree<T,N>::Contain(N a1, N a2, N b1, N b2) {
899     return a1 <= b1 && b2 <= a2;
900     }
901    
902     /***********************************************************************/
903     /* FUNCTION: fetch */
904     /**/
905     /* INPUTS: tree is the tree to look for intervals overlapping the */
906     /* interval [low,high) */
907     /**/
908     /* OUTPUT: stack containing pointers to the nodes overlapping */
909     /* [low,high) */
910     /**/
911     /* Modifies Input: none */
912     /**/
913     /* EFFECT: Returns a stack containing pointers to nodes containing */
914     /* intervals which overlap [low,high) in O(max(N,k*log(N))) */
915     /* where N is the number of intervals in the tree and k is */
916     /* the number of overlapping intervals */
917     /**/
918     /* Note: This basic idea for this function comes from the */
919     /* _Introduction_To_Algorithms_ book by Cormen et al, but */
920     /* modifications were made to return all overlapping intervals */
921     /* instead of just the first overlapping interval as in the */
922     /* book. The natural way to do this would require recursive */
923     /* calls of a basic search function. I translated the */
924     /* recursive version into an interative version with a stack */
925     /* as described below. */
926     /***********************************************************************/
927    
928    
929    
930     /* The basic idea for the function below is to take the IntervalSearch */
931     /* function from the book and modify to find all overlapping intervals */
932     /* instead of just one. This means that any time we take the left */
933     /* branch down the tree we must also check the right branch if and only if */
934     /* we find an overlapping interval in that left branch. Note this is a */
935     /* recursive condition because if we go left at the root then go left */
936     /* again at the first left child and find an overlap in the left subtree */
937     /* of the left child of root we must recursively check the right subtree */
938     /* of the left child of root as well as the right child of root. */
939    
940     template<typename T, typename N>
941     void IntervalTree<T,N>::fetch(N low, N high, GVec<T> &enumResultStack) {
942     IntervalTree<T,N>::Node* x=root->left;
943     bool stuffToDo = (x != nil);
944    
945     // Possible speed up: add min field to prune right searches //
946    
947     #ifdef DEBUG_ASSERT
948 gpertea 252 if (recursionNodeStack.Count() == 0)
949     GError("Error: recursionStack empty when entering IntervalTree::fetch\n");
950 gpertea 248 #endif
951     currentParent = 0;
952    
953     while(stuffToDo) {
954     if (Overlap(low,high,x->key,x->high_) ) {
955     enumResultStack.Push(x->value());
956     recursionNodeStack[currentParent].tryRightBranch=true;
957     }
958     if(x->left->maxHigh >= low) { // implies x != nil
959     recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
960     recursionNodeStack.Last().start_node = x;
961     recursionNodeStack.Last().tryRightBranch = false;
962     recursionNodeStack.Last().parentIndex = currentParent;
963     currentParent = recursionNodeStack.Count()-1;
964     x = x->left;
965     } else {
966     x = x->right;
967     }
968     stuffToDo = (x != nil);
969     while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
970     IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
971    
972     if(back.tryRightBranch) {
973     x=back.start_node->right;
974     currentParent=back.parentIndex;
975     recursionNodeStack[currentParent].tryRightBranch=true;
976     stuffToDo = ( x != nil);
977     }
978     }
979     }
980     #ifdef DEBUG_ASSERT
981 gpertea 252 if (recursionNodeStack.Count() == 0)
982     GError("Error: recursionStack empty when exiting IntervalTree::fetch!\n");
983 gpertea 248 #endif
984     }
985    
986     template<typename T, typename N>
987     void IntervalTree<T,N>::fetch_node(
988     N low,
989     N high,
990     GVec<typename IntervalTree<T,N>::Node*> &enumResultStack)
991     {
992     IntervalTree<T,N>::Node* x=root->left;
993     bool stuffToDo = (x != nil);
994    
995     // Possible speed up: add min field to prune right searches //
996    
997     #ifdef DEBUG_ASSERT
998 gpertea 252 if (recursionNodeStack.Count() == 0)
999     GError("Error: recursionStack empty when entering IntervalTree::fetch\n");
1000 gpertea 248 #endif
1001     currentParent = 0;
1002    
1003     while(stuffToDo) {
1004     if (Overlap(low,high,x->key,x->high_) ) {
1005 gpertea 250 enumResultStack.Push(x);
1006 gpertea 248 recursionNodeStack[currentParent].tryRightBranch=true;
1007     }
1008     if(x->left->maxHigh >= low) { // implies x != nil
1009 gpertea 250 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1010     recursionNodeStack.Last().start_node = x;
1011     recursionNodeStack.Last().tryRightBranch = false;
1012     recursionNodeStack.Last().parentIndex = currentParent;
1013     currentParent = recursionNodeStack.Count()-1;
1014 gpertea 248 x = x->left;
1015     } else {
1016     x = x->right;
1017     }
1018     stuffToDo = (x != nil);
1019 gpertea 250 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1020     IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1021 gpertea 248
1022     if(back.tryRightBranch) {
1023     x=back.start_node->right;
1024     currentParent=back.parentIndex;
1025     recursionNodeStack[currentParent].tryRightBranch=true;
1026     stuffToDo = ( x != nil);
1027     }
1028     }
1029     }
1030     #ifdef DEBUG_ASSERT
1031 gpertea 252 // if (recursionNodeStack.Count() == 1)
1032     // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1033 gpertea 248 #endif
1034     }
1035    
1036     template<typename T, typename N>
1037     void IntervalTree<T,N>::fetch_window(N low, N high, GVec<T> &enumResultStack)
1038     {
1039     IntervalTree<T,N>::Node* x=root->left;
1040     bool stuffToDo = (x != nil);
1041    
1042     // Possible speed up: add min field to prune right searches //
1043    
1044     #ifdef DEBUG_ASSERT
1045 gpertea 252 // if (recursionNodeStack.Count() == 1)
1046     // GError("Error: recursionStack not empty when entering IntervalTree::fetch_window\n");
1047 gpertea 248 #endif
1048     currentParent = 0;
1049    
1050     while(stuffToDo) {
1051     if (Contain(low,high,x->key,x->high_) ) {
1052 gpertea 250 enumResultStack.Push(x->value());
1053 gpertea 248 recursionNodeStack[currentParent].tryRightBranch=true;
1054     }
1055     if(x->left->maxHigh >= low) { // implies x != nil
1056 gpertea 250 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1057     recursionNodeStack.Last().start_node = x;
1058     recursionNodeStack.Last().tryRightBranch = false;
1059     recursionNodeStack.Last().parentIndex = currentParent;
1060     currentParent = recursionNodeStack.Count()-1;
1061 gpertea 248 x = x->left;
1062     } else {
1063     x = x->right;
1064     }
1065     stuffToDo = (x != nil);
1066 gpertea 252 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1067 gpertea 250 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1068 gpertea 248
1069     if(back.tryRightBranch) {
1070     x=back.start_node->right;
1071     currentParent=back.parentIndex;
1072     recursionNodeStack[currentParent].tryRightBranch=true;
1073     stuffToDo = ( x != nil);
1074     }
1075     }
1076     }
1077     #ifdef DEBUG_ASSERT
1078 gpertea 252 // if (recursionNodeStack.Count() == 1)
1079     // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1080 gpertea 248 #endif
1081     }
1082    
1083     template<typename T, typename N>
1084     void IntervalTree<T,N>::fetch_window_node(
1085     N low,
1086     N high,
1087     GVec<typename IntervalTree<T,N>::Node*> &enumResultStack)
1088     {
1089     IntervalTree<T,N>::Node* x=root->left;
1090     bool stuffToDo = (x != nil);
1091    
1092     // Possible speed up: add min field to prune right searches //
1093    
1094     #ifdef DEBUG_ASSERT
1095 gpertea 252 if (recursionNodeStack.Count() == 0)
1096     GError("Error: recursionStack empty when entering IntervalTree::fetch_window_node\n");
1097 gpertea 248 #endif
1098     currentParent = 0;
1099    
1100     while(stuffToDo) {
1101     if (Contain(low,high,x->key,x->high_) ) {
1102 gpertea 250 enumResultStack.Push(x);
1103 gpertea 248 recursionNodeStack[currentParent].tryRightBranch=true;
1104     }
1105     if(x->left->maxHigh >= low) { // implies x != nil
1106 gpertea 250 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1107 gpertea 248 recursionNodeStack.Last().start_node = x;
1108     recursionNodeStack.Last().tryRightBranch = false;
1109     recursionNodeStack.Last().parentIndex = currentParent;
1110 gpertea 252 currentParent = recursionNodeStack.Count()-1;
1111 gpertea 248 x = x->left;
1112     } else {
1113     x = x->right;
1114     }
1115     stuffToDo = (x != nil);
1116 gpertea 252 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1117 gpertea 250 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1118 gpertea 248
1119     if(back.tryRightBranch) {
1120     x=back.start_node->right;
1121     currentParent=back.parentIndex;
1122     recursionNodeStack[currentParent].tryRightBranch=true;
1123     stuffToDo = ( x != nil);
1124     }
1125     }
1126     }
1127     #ifdef DEBUG_ASSERT
1128 gpertea 252 //if (recursionNodeStack.Count() == 1)
1129     // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1130 gpertea 248 #endif
1131     }
1132    
1133     template<typename T, typename N>
1134     bool IntervalTree<T,N>::CheckMaxHighFieldsHelper(IntervalTree<T,N>::Node * y,
1135     const N currentHigh,
1136     bool match) const
1137     {
1138     if (y != nil) {
1139     match = CheckMaxHighFieldsHelper(y->left,currentHigh,match) ?
1140     true : match;
1141     if (y->high_ == currentHigh)
1142     match = true;
1143     match = CheckMaxHighFieldsHelper(y->right,currentHigh,match) ?
1144     true : match;
1145     }
1146     return match;
1147     }
1148    
1149    
1150     /* Make sure the maxHigh fields for everything makes sense. *
1151     * If something is wrong, print a warning and exit */
1152     template<typename T, typename N>
1153     void IntervalTree<T,N>::CheckMaxHighFields(IntervalTree<T,N>::Node * x) const {
1154     if (x != nil) {
1155     CheckMaxHighFields(x->left);
1156     if(!(CheckMaxHighFieldsHelper(x,x->maxHigh,false) > 0)) {
1157     //assert(0);
1158     GError("Error: CheckMaxHighFields error\n");
1159     }
1160     CheckMaxHighFields(x->right);
1161     }
1162     }
1163    
1164     template<typename T, typename N>
1165     void IntervalTree<T,N>::check() const {
1166     CheckMaxHighFields(root->left);
1167     }
1168    
1169     #endif