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 ago) by gpertea
File size: 36565 byte(s)
Log Message:
added generic storage function type; wip serialization for GIntervalTree

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
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 template<typename T, typename N=int32_t> class IntervalTree {
22 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 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 color_t color;
45 Node * left;
46 Node * right;
47 Node * parent;
48 }; //Node
49
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 : start_node (start_node_),
58 parentIndex (parentIndex_),
59 tryRightBranch (tryRightBranch_) {}
60
61 Node * start_node;
62 size_t parentIndex;
63 bool tryRightBranch;
64 };
65
66 IntervalTree();
67 IntervalTree(FILE* f); //create by deserialization from file
68
69 ~IntervalTree();
70
71 void fileStore(FILE* f); //write the tree into a file
72 //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 GPVec<Node> nodes; //store all the tree nodes for easy de/serialization
95 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 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 {
141 }
142
143 template<typename T, typename N>
144 IntervalTree<T,N>::Node::~Node()
145 {
146 }
147
148 template<typename T, typename N>
149 IntervalTree<T,N>::IntervalTree() : nodes(64, true)
150 {
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 nodes.Add(nil); //index 0
156 nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
157 root = new IntervalTree<T,N>::Node();
158 root->parent = root->left = root->right = nil;
159 root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
160 root->n_idx = nodes.Add(root);
161 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 newNode->n_idx = nodes.Add(newNode);
409 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 //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 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 nodes.Clear(); //this should also free all allocated nodes
577 /*
578 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 */
603 }
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 removed.Push((*i)->value());
799 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 removed.Push((*i)->value());
813 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 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_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 removed.Push((*i)->value());
845 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 enumResultStack.Push(x);
978 recursionNodeStack[currentParent].tryRightBranch=true;
979 }
980 if(x->left->maxHigh >= low) { // implies x != nil
981 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 x = x->left;
987 } else {
988 x = x->right;
989 }
990 stuffToDo = (x != nil);
991 while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
992 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
993
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 enumResultStack.Push(x->value());
1025 recursionNodeStack[currentParent].tryRightBranch=true;
1026 }
1027 if(x->left->maxHigh >= low) { // implies x != nil
1028 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 x = x->left;
1034 } else {
1035 x = x->right;
1036 }
1037 stuffToDo = (x != nil);
1038 while( (!stuffToDo) && (recursionNodeStack.size() > 1) ) {
1039 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1040
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 enumResultStack.Push(x);
1075 recursionNodeStack[currentParent].tryRightBranch=true;
1076 }
1077 if(x->left->maxHigh >= low) { // implies x != nil
1078 recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1079 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 IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1090
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