ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.hh
Revision: 250
Committed: Thu May 24 18:21:10 2012 UTC (7 years, 3 months ago) by gpertea
File size: 36565 byte(s)
Log Message:
added generic storage function type; wip serialization for GIntervalTree

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