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 File contents
1 #ifndef GINTERVALTREE_HH_
2 #define GINTERVALTREE_HH_
3
4 #include <limits>
5 #include "GBase.h"
6 #include "GVec.hh"
7 using namespace std;
8
9 //#include <sstream>
10 //#include <vector>
11 //#include <string>
12 #define DEBUG_ASSERT 1
13 //#define CHECK_INTERVAL_TREE_ASSUMPTIONS 1
14 // 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 template<typename T, typename N=int32_t> class IntervalTree {
25 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 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 color_t color;
48 Node * left;
49 Node * right;
50 Node * parent;
51 }; //Node
52
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 : start_node (start_node_),
61 parentIndex (parentIndex_),
62 tryRightBranch (tryRightBranch_) {}
63
64 Node * start_node;
65 size_t parentIndex;
66 bool tryRightBranch;
67 };
68
69 IntervalTree();
70 IntervalTree(FILE* f, GFLoadProc fLoadFunc=NULL); //create by deserialization from file
71
72 ~IntervalTree();
73
74 void Store(FILE* f, GFStoreProc fStoreFunc=NULL); //write the tree into a file
75 void Load(FILE* f, GFLoadProc fLoadFunc=NULL);
76 //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 GPVec<Node> nodes; //store all the tree nodes for easy de/serialization
99 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 int currentParent;
117 };
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 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 }
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 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 {
158 }
159
160 template<typename T, typename N>
161 IntervalTree<T,N>::Node::~Node()
162 {
163 }
164
165 template<typename T, typename N>
166 IntervalTree<T,N>::IntervalTree() : nodes(64, true)
167 {
168 currentParent = 0;
169 nil = new IntervalTree<T,N>::Node();
170 nil->left = nil->right = nil->parent = nil;
171 nil->color = BLACK;
172 nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
173 nodes.Add(nil); //index 0
174 nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
175 root = new IntervalTree<T,N>::Node();
176 root->parent = root->left = root->right = nil;
177 root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
178 root->n_idx = nodes.Add(root);
179 root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
180 root->color=BLACK;
181
182 /* the following are used for the fetch function */
183 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
184 }
185
186
187 template<typename T, typename N>
188 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 nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
194 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 root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
201 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 }
209
210
211 template<typename T, typename N>
212 void IntervalTree<T,N>::Load(FILE* f, GFLoadProc* fLoadFunc) {
213
214 }
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 if (nil->maxHigh!=numeric_limits<N>::min())
271 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITLeftRotate!\n");
272 #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 if (nil->maxHigh!=numeric_limits<N>::min())
331 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITRightRotate!\n");
332 #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 if (nil->maxHigh!=numeric_limits<N>::min())
378 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsertHelp!\n");
379 #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 newNode->n_idx = nodes.Add(newNode);
438 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 //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 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 if (nil->maxHigh!=numeric_limits<N>::min())
488 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsert\n");
489 #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 nodes.Clear(); //this should also free all allocated nodes
605 /*
606 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 */
631 }
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 if (nil->maxHigh!=numeric_limits<N>::min())
734 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDeleteFixUp\n");
735 #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 y->maxHigh = numeric_limits<N>::min();
780 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 if (nil->maxHigh!=numeric_limits<N>::min())
801 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
802 #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 if (nil->maxHigh!=numeric_limits<N>::min())
812 GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
813 #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 removed.Push((*i)->value());
827 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 removed.Push((*i)->value());
841 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 removed.Push((*i)->value());
855 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 removed.Push((*i)->value());
873 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 if (recursionNodeStack.Count() == 0)
949 GError("Error: recursionStack empty when entering IntervalTree::fetch\n");
950 #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 if (recursionNodeStack.Count() == 0)
982 GError("Error: recursionStack empty when exiting IntervalTree::fetch!\n");
983 #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 if (recursionNodeStack.Count() == 0)
999 GError("Error: recursionStack empty when entering IntervalTree::fetch\n");
1000 #endif
1001 currentParent = 0;
1002
1003 while(stuffToDo) {
1004 if (Overlap(low,high,x->key,x->high_) ) {
1005 enumResultStack.Push(x);
1006 recursionNodeStack[currentParent].tryRightBranch=true;
1007 }
1008 if(x->left->maxHigh >= low) { // implies x != nil
1009 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 x = x->left;
1015 } else {
1016 x = x->right;
1017 }
1018 stuffToDo = (x != nil);
1019 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1020 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1021
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 // if (recursionNodeStack.Count() == 1)
1032 // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1033 #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 // if (recursionNodeStack.Count() == 1)
1046 // GError("Error: recursionStack not empty when entering IntervalTree::fetch_window\n");
1047 #endif
1048 currentParent = 0;
1049
1050 while(stuffToDo) {
1051 if (Contain(low,high,x->key,x->high_) ) {
1052 enumResultStack.Push(x->value());
1053 recursionNodeStack[currentParent].tryRightBranch=true;
1054 }
1055 if(x->left->maxHigh >= low) { // implies x != nil
1056 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 x = x->left;
1062 } else {
1063 x = x->right;
1064 }
1065 stuffToDo = (x != nil);
1066 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1067 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1068
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 // if (recursionNodeStack.Count() == 1)
1079 // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1080 #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 if (recursionNodeStack.Count() == 0)
1096 GError("Error: recursionStack empty when entering IntervalTree::fetch_window_node\n");
1097 #endif
1098 currentParent = 0;
1099
1100 while(stuffToDo) {
1101 if (Contain(low,high,x->key,x->high_) ) {
1102 enumResultStack.Push(x);
1103 recursionNodeStack[currentParent].tryRightBranch=true;
1104 }
1105 if(x->left->maxHigh >= low) { // implies x != nil
1106 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1107 recursionNodeStack.Last().start_node = x;
1108 recursionNodeStack.Last().tryRightBranch = false;
1109 recursionNodeStack.Last().parentIndex = currentParent;
1110 currentParent = recursionNodeStack.Count()-1;
1111 x = x->left;
1112 } else {
1113 x = x->right;
1114 }
1115 stuffToDo = (x != nil);
1116 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
1117 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1118
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 //if (recursionNodeStack.Count() == 1)
1129 // GError("Error: recursionStack not empty when exiting IntervalTree::fetch\n");
1130 #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