ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.hh
Revision: 252
Committed: Sat May 26 00:55:09 2012 UTC (7 years, 4 months ago) by gpertea
File size: 37093 byte(s)
Log Message:
Interval tree updates, wip Store/Load

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