1 |
#include "GIntervalTree.h" |
2 |
|
3 |
// If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the |
4 |
// code does a lot of extra checking to make sure certain assumptions |
5 |
// are satisfied. This only needs to be done if you suspect bugs are |
6 |
// present or if you make significant changes and want to make sure |
7 |
// your changes didn't mess anything up. |
8 |
// #define CHECK_INTERVAL_TREE_ASSUMPTIONS 1 |
9 |
|
10 |
|
11 |
//const int MIN_INT=-MAX_INT; |
12 |
|
13 |
// define a function to find the maximum of two objects. |
14 |
//#define GMAX(a, b) ( (a > b) ? a : b ) |
15 |
|
16 |
inline void Assert(int assertion, char* error) { |
17 |
if(!assertion) { |
18 |
printf("Assertion Failed: %s\n",error); |
19 |
exit(1); |
20 |
} |
21 |
} |
22 |
|
23 |
IntervalTreeNode::IntervalTreeNode(){} |
24 |
IntervalTreeNode::IntervalTreeNode(Interval * newInterval) |
25 |
: storedInterval (newInterval) , |
26 |
key(newInterval->GetLowPoint()), |
27 |
high(newInterval->GetHighPoint()) , |
28 |
maxHigh(high) {} |
29 |
IntervalTreeNode::~IntervalTreeNode(){} |
30 |
Interval::Interval(){} |
31 |
Interval::~Interval(){} |
32 |
void Interval::Print() const {} |
33 |
|
34 |
IntervalTree::IntervalTree() |
35 |
{ |
36 |
nil = new IntervalTreeNode; |
37 |
nil->left = nil->right = nil->parent = nil; |
38 |
nil->red = 0; |
39 |
nil->key = nil->high = nil->maxHigh = MIN_INT; |
40 |
nil->storedInterval = NULL; |
41 |
|
42 |
root = new IntervalTreeNode; |
43 |
root->parent = root->left = root->right = nil; |
44 |
root->key = root->high = root->maxHigh = MAX_INT; |
45 |
root->red=0; |
46 |
root->storedInterval = NULL; |
47 |
|
48 |
/* the following are used for the Enumerate function */ |
49 |
recursionNodeStackSize = 128; |
50 |
recursionNodeStack = (it_recursion_node *) |
51 |
malloc(recursionNodeStackSize*sizeof(it_recursion_node)); |
52 |
recursionNodeStackTop = 1; |
53 |
recursionNodeStack[0].start_node = NULL; |
54 |
|
55 |
} |
56 |
|
57 |
/***********************************************************************/ |
58 |
/* FUNCTION: LeftRotate */ |
59 |
/**/ |
60 |
/* INPUTS: the node to rotate on */ |
61 |
/**/ |
62 |
/* OUTPUT: None */ |
63 |
/**/ |
64 |
/* Modifies Input: this, x */ |
65 |
/**/ |
66 |
/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ |
67 |
/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ |
68 |
/* makes the parent of x be to the left of x, x the parent of */ |
69 |
/* its parent before the rotation and fixes other pointers */ |
70 |
/* accordingly. Also updates the maxHigh fields of x and y */ |
71 |
/* after rotation. */ |
72 |
/***********************************************************************/ |
73 |
|
74 |
void IntervalTree::LeftRotate(IntervalTreeNode* x) { |
75 |
IntervalTreeNode* y; |
76 |
|
77 |
/* I originally wrote this function to use the sentinel for */ |
78 |
/* nil to avoid checking for nil. However this introduces a */ |
79 |
/* very subtle bug because sometimes this function modifies */ |
80 |
/* the parent pointer of nil. This can be a problem if a */ |
81 |
/* function which calls LeftRotate also uses the nil sentinel */ |
82 |
/* and expects the nil sentinel's parent pointer to be unchanged */ |
83 |
/* after calling this function. For example, when DeleteFixUP */ |
84 |
/* calls LeftRotate it expects the parent pointer of nil to be */ |
85 |
/* unchanged. */ |
86 |
|
87 |
y=x->right; |
88 |
x->right=y->left; |
89 |
|
90 |
if (y->left != nil) y->left->parent=x; /* used to use sentinel here */ |
91 |
/* and do an unconditional assignment instead of testing for nil */ |
92 |
|
93 |
y->parent=x->parent; |
94 |
|
95 |
/* instead of checking if x->parent is the root as in the book, we */ |
96 |
/* count on the root sentinel to implicitly take care of this case */ |
97 |
if( x == x->parent->left) { |
98 |
x->parent->left=y; |
99 |
} else { |
100 |
x->parent->right=y; |
101 |
} |
102 |
y->left=x; |
103 |
x->parent=y; |
104 |
|
105 |
x->maxHigh=GMAX(x->left->maxHigh,GMAX(x->right->maxHigh,x->high)); |
106 |
y->maxHigh=GMAX(x->maxHigh,GMAX(y->right->maxHigh,y->high)); |
107 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
108 |
CheckAssumptions(); |
109 |
#elif defined(DEBUG_ASSERT) |
110 |
Assert(!nil->red,"nil not red in ITLeftRotate"); |
111 |
Assert((nil->maxHigh=MIN_INT), |
112 |
"nil->maxHigh != MIN_INT in ITLeftRotate"); |
113 |
#endif |
114 |
} |
115 |
|
116 |
|
117 |
/***********************************************************************/ |
118 |
/* FUNCTION: RighttRotate */ |
119 |
/**/ |
120 |
/* INPUTS: node to rotate on */ |
121 |
/**/ |
122 |
/* OUTPUT: None */ |
123 |
/**/ |
124 |
/* Modifies Input?: this, y */ |
125 |
/**/ |
126 |
/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ |
127 |
/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ |
128 |
/* makes the parent of x be to the left of x, x the parent of */ |
129 |
/* its parent before the rotation and fixes other pointers */ |
130 |
/* accordingly. Also updates the maxHigh fields of x and y */ |
131 |
/* after rotation. */ |
132 |
/***********************************************************************/ |
133 |
|
134 |
|
135 |
void IntervalTree::RightRotate(IntervalTreeNode* y) { |
136 |
IntervalTreeNode* x; |
137 |
|
138 |
/* I originally wrote this function to use the sentinel for */ |
139 |
/* nil to avoid checking for nil. However this introduces a */ |
140 |
/* very subtle bug because sometimes this function modifies */ |
141 |
/* the parent pointer of nil. This can be a problem if a */ |
142 |
/* function which calls LeftRotate also uses the nil sentinel */ |
143 |
/* and expects the nil sentinel's parent pointer to be unchanged */ |
144 |
/* after calling this function. For example, when DeleteFixUP */ |
145 |
/* calls LeftRotate it expects the parent pointer of nil to be */ |
146 |
/* unchanged. */ |
147 |
|
148 |
x=y->left; |
149 |
y->left=x->right; |
150 |
|
151 |
if (nil != x->right) x->right->parent=y; /*used to use sentinel here */ |
152 |
/* and do an unconditional assignment instead of testing for nil */ |
153 |
|
154 |
/* instead of checking if x->parent is the root as in the book, we */ |
155 |
/* count on the root sentinel to implicitly take care of this case */ |
156 |
x->parent=y->parent; |
157 |
if( y == y->parent->left) { |
158 |
y->parent->left=x; |
159 |
} else { |
160 |
y->parent->right=x; |
161 |
} |
162 |
x->right=y; |
163 |
y->parent=x; |
164 |
|
165 |
y->maxHigh=GMAX(y->left->maxHigh,GMAX(y->right->maxHigh,y->high)); |
166 |
x->maxHigh=GMAX(x->left->maxHigh,GMAX(y->maxHigh,x->high)); |
167 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
168 |
CheckAssumptions(); |
169 |
#elif defined(DEBUG_ASSERT) |
170 |
Assert(!nil->red,"nil not red in ITRightRotate"); |
171 |
Assert((nil->maxHigh=MIN_INT), |
172 |
"nil->maxHigh != MIN_INT in ITRightRotate"); |
173 |
#endif |
174 |
} |
175 |
|
176 |
/***********************************************************************/ |
177 |
/* FUNCTION: TreeInsertHelp */ |
178 |
/**/ |
179 |
/* INPUTS: z is the node to insert */ |
180 |
/**/ |
181 |
/* OUTPUT: none */ |
182 |
/**/ |
183 |
/* Modifies Input: this, z */ |
184 |
/**/ |
185 |
/* EFFECTS: Inserts z into the tree as if it were a regular binary tree */ |
186 |
/* using the algorithm described in _Introduction_To_Algorithms_ */ |
187 |
/* by Cormen et al. This funciton is only intended to be called */ |
188 |
/* by the InsertTree function and not by the user */ |
189 |
/***********************************************************************/ |
190 |
|
191 |
void IntervalTree::TreeInsertHelp(IntervalTreeNode* z) { |
192 |
/* This function should only be called by InsertITTree (see above) */ |
193 |
IntervalTreeNode* x; |
194 |
IntervalTreeNode* y; |
195 |
|
196 |
z->left=z->right=nil; |
197 |
y=root; |
198 |
x=root->left; |
199 |
while( x != nil) { |
200 |
y=x; |
201 |
if ( x->key > z->key) { |
202 |
x=x->left; |
203 |
} else { /* x->key <= z->key */ |
204 |
x=x->right; |
205 |
} |
206 |
} |
207 |
z->parent=y; |
208 |
if ( (y == root) || |
209 |
(y->key > z->key) ) { |
210 |
y->left=z; |
211 |
} else { |
212 |
y->right=z; |
213 |
} |
214 |
|
215 |
|
216 |
#if defined(DEBUG_ASSERT) |
217 |
Assert(!nil->red,"nil not red in ITTreeInsertHelp"); |
218 |
Assert((nil->maxHigh=MIN_INT), |
219 |
"nil->maxHigh != MIN_INT in ITTreeInsertHelp"); |
220 |
#endif |
221 |
} |
222 |
|
223 |
|
224 |
/***********************************************************************/ |
225 |
/* FUNCTION: FixUpMaxHigh */ |
226 |
/**/ |
227 |
/* INPUTS: x is the node to start from*/ |
228 |
/**/ |
229 |
/* OUTPUT: none */ |
230 |
/**/ |
231 |
/* Modifies Input: this */ |
232 |
/**/ |
233 |
/* EFFECTS: Travels up to the root fixing the maxHigh fields after */ |
234 |
/* an insertion or deletion */ |
235 |
/***********************************************************************/ |
236 |
|
237 |
void IntervalTree::FixUpMaxHigh(IntervalTreeNode * x) { |
238 |
while(x != root) { |
239 |
x->maxHigh=GMAX(x->high,GMAX(x->left->maxHigh,x->right->maxHigh)); |
240 |
x=x->parent; |
241 |
} |
242 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
243 |
CheckAssumptions(); |
244 |
#endif |
245 |
} |
246 |
|
247 |
/* Before calling InsertNode the node x should have its key set */ |
248 |
|
249 |
/***********************************************************************/ |
250 |
/* FUNCTION: InsertNode */ |
251 |
/**/ |
252 |
/* INPUTS: newInterval is the interval to insert*/ |
253 |
/**/ |
254 |
/* OUTPUT: This function returns a pointer to the newly inserted node */ |
255 |
/* which is guarunteed to be valid until this node is deleted. */ |
256 |
/* What this means is if another data structure stores this */ |
257 |
/* pointer then the tree does not need to be searched when this */ |
258 |
/* is to be deleted. */ |
259 |
/**/ |
260 |
/* Modifies Input: tree */ |
261 |
/**/ |
262 |
/* EFFECTS: Creates a node node which contains the appropriate key and */ |
263 |
/* info pointers and inserts it into the tree. */ |
264 |
/***********************************************************************/ |
265 |
|
266 |
IntervalTreeNode * IntervalTree::Insert(Interval * newInterval) |
267 |
{ |
268 |
IntervalTreeNode * y; |
269 |
IntervalTreeNode * x; |
270 |
IntervalTreeNode * newNode; |
271 |
|
272 |
x = new IntervalTreeNode(newInterval); |
273 |
TreeInsertHelp(x); |
274 |
FixUpMaxHigh(x->parent); |
275 |
newNode = x; |
276 |
x->red=1; |
277 |
while(x->parent->red) { /* use sentinel instead of checking for root */ |
278 |
if (x->parent == x->parent->parent->left) { |
279 |
y=x->parent->parent->right; |
280 |
if (y->red) { |
281 |
x->parent->red=0; |
282 |
y->red=0; |
283 |
x->parent->parent->red=1; |
284 |
x=x->parent->parent; |
285 |
} else { |
286 |
if (x == x->parent->right) { |
287 |
x=x->parent; |
288 |
LeftRotate(x); |
289 |
} |
290 |
x->parent->red=0; |
291 |
x->parent->parent->red=1; |
292 |
RightRotate(x->parent->parent); |
293 |
} |
294 |
} else { /* case for x->parent == x->parent->parent->right */ |
295 |
/* this part is just like the section above with */ |
296 |
/* left and right interchanged */ |
297 |
y=x->parent->parent->left; |
298 |
if (y->red) { |
299 |
x->parent->red=0; |
300 |
y->red=0; |
301 |
x->parent->parent->red=1; |
302 |
x=x->parent->parent; |
303 |
} else { |
304 |
if (x == x->parent->left) { |
305 |
x=x->parent; |
306 |
RightRotate(x); |
307 |
} |
308 |
x->parent->red=0; |
309 |
x->parent->parent->red=1; |
310 |
LeftRotate(x->parent->parent); |
311 |
} |
312 |
} |
313 |
} |
314 |
root->left->red=0; |
315 |
return(newNode); |
316 |
|
317 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
318 |
CheckAssumptions(); |
319 |
#elif defined(DEBUG_ASSERT) |
320 |
Assert(!nil->red,"nil not red in ITTreeInsert"); |
321 |
Assert(!root->red,"root not red in ITTreeInsert"); |
322 |
Assert((nil->maxHigh=MIN_INT), |
323 |
"nil->maxHigh != MIN_INT in ITTreeInsert"); |
324 |
#endif |
325 |
} |
326 |
|
327 |
/***********************************************************************/ |
328 |
/* FUNCTION: GetSuccessorOf */ |
329 |
/**/ |
330 |
/* INPUTS: x is the node we want the succesor of */ |
331 |
/**/ |
332 |
/* OUTPUT: This function returns the successor of x or NULL if no */ |
333 |
/* successor exists. */ |
334 |
/**/ |
335 |
/* Modifies Input: none */ |
336 |
/**/ |
337 |
/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ |
338 |
/***********************************************************************/ |
339 |
|
340 |
IntervalTreeNode * IntervalTree::GetSuccessorOf(IntervalTreeNode * x) const |
341 |
{ |
342 |
IntervalTreeNode* y; |
343 |
|
344 |
if (nil != (y = x->right)) { /* assignment to y is intentional */ |
345 |
while(y->left != nil) { /* returns the minium of the right subtree of x */ |
346 |
y=y->left; |
347 |
} |
348 |
return(y); |
349 |
} else { |
350 |
y=x->parent; |
351 |
while(x == y->right) { /* sentinel used instead of checking for nil */ |
352 |
x=y; |
353 |
y=y->parent; |
354 |
} |
355 |
if (y == root) return(nil); |
356 |
return(y); |
357 |
} |
358 |
} |
359 |
|
360 |
/***********************************************************************/ |
361 |
/* FUNCTION: GetPredecessorOf */ |
362 |
/**/ |
363 |
/* INPUTS: x is the node to get predecessor of */ |
364 |
/**/ |
365 |
/* OUTPUT: This function returns the predecessor of x or NULL if no */ |
366 |
/* predecessor exists. */ |
367 |
/**/ |
368 |
/* Modifies Input: none */ |
369 |
/**/ |
370 |
/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ |
371 |
/***********************************************************************/ |
372 |
|
373 |
IntervalTreeNode * IntervalTree::GetPredecessorOf(IntervalTreeNode * x) const { |
374 |
IntervalTreeNode* y; |
375 |
|
376 |
if (nil != (y = x->left)) { /* assignment to y is intentional */ |
377 |
while(y->right != nil) { /* returns the maximum of the left subtree of x */ |
378 |
y=y->right; |
379 |
} |
380 |
return(y); |
381 |
} else { |
382 |
y=x->parent; |
383 |
while(x == y->left) { |
384 |
if (y == root) return(nil); |
385 |
x=y; |
386 |
y=y->parent; |
387 |
} |
388 |
return(y); |
389 |
} |
390 |
} |
391 |
|
392 |
/***********************************************************************/ |
393 |
/* FUNCTION: Print */ |
394 |
/**/ |
395 |
/* INPUTS: none */ |
396 |
/**/ |
397 |
/* OUTPUT: none */ |
398 |
/**/ |
399 |
/* EFFECTS: This function recursively prints the nodes of the tree */ |
400 |
/* inorder. */ |
401 |
/**/ |
402 |
/* Modifies Input: none */ |
403 |
/**/ |
404 |
/* Note: This function should only be called from ITTreePrint */ |
405 |
/***********************************************************************/ |
406 |
|
407 |
void IntervalTreeNode::Print(IntervalTreeNode * nil, |
408 |
IntervalTreeNode * root) const { |
409 |
storedInterval->Print(); |
410 |
printf(", k=%i, h=%i, mH=%i",key,high,maxHigh); |
411 |
printf(" l->key="); |
412 |
if( left == nil) printf("NULL"); else printf("%i",left->key); |
413 |
printf(" r->key="); |
414 |
if( right == nil) printf("NULL"); else printf("%i",right->key); |
415 |
printf(" p->key="); |
416 |
if( parent == root) printf("NULL"); else printf("%i",parent->key); |
417 |
printf(" red=%i\n",red); |
418 |
} |
419 |
|
420 |
void IntervalTree::TreePrintHelper( IntervalTreeNode* x) const { |
421 |
|
422 |
if (x != nil) { |
423 |
TreePrintHelper(x->left); |
424 |
x->Print(nil,root); |
425 |
TreePrintHelper(x->right); |
426 |
} |
427 |
} |
428 |
|
429 |
IntervalTree::~IntervalTree() { |
430 |
IntervalTreeNode * x = root->left; |
431 |
TemplateStack<IntervalTreeNode *> stuffToFree; |
432 |
|
433 |
if (x != nil) { |
434 |
if (x->left != nil) { |
435 |
stuffToFree.Push(x->left); |
436 |
} |
437 |
if (x->right != nil) { |
438 |
stuffToFree.Push(x->right); |
439 |
} |
440 |
// delete x->storedInterval; |
441 |
delete x; |
442 |
while( stuffToFree.NotEmpty() ) { |
443 |
x = stuffToFree.Pop(); |
444 |
if (x->left != nil) { |
445 |
stuffToFree.Push(x->left); |
446 |
} |
447 |
if (x->right != nil) { |
448 |
stuffToFree.Push(x->right); |
449 |
} |
450 |
// delete x->storedInterval; |
451 |
delete x; |
452 |
} |
453 |
} |
454 |
delete nil; |
455 |
delete root; |
456 |
free(recursionNodeStack); |
457 |
} |
458 |
|
459 |
|
460 |
/***********************************************************************/ |
461 |
/* FUNCTION: Print */ |
462 |
/**/ |
463 |
/* INPUTS: none */ |
464 |
/**/ |
465 |
/* OUTPUT: none */ |
466 |
/**/ |
467 |
/* EFFECT: This function recursively prints the nodes of the tree */ |
468 |
/* inorder. */ |
469 |
/**/ |
470 |
/* Modifies Input: none */ |
471 |
/**/ |
472 |
/***********************************************************************/ |
473 |
|
474 |
void IntervalTree::Print() const { |
475 |
TreePrintHelper(root->left); |
476 |
} |
477 |
|
478 |
/***********************************************************************/ |
479 |
/* FUNCTION: DeleteFixUp */ |
480 |
/**/ |
481 |
/* INPUTS: x is the child of the spliced */ |
482 |
/* out node in DeleteNode. */ |
483 |
/**/ |
484 |
/* OUTPUT: none */ |
485 |
/**/ |
486 |
/* EFFECT: Performs rotations and changes colors to restore red-black */ |
487 |
/* properties after a node is deleted */ |
488 |
/**/ |
489 |
/* Modifies Input: this, x */ |
490 |
/**/ |
491 |
/* The algorithm from this function is from _Introduction_To_Algorithms_ */ |
492 |
/***********************************************************************/ |
493 |
|
494 |
void IntervalTree::DeleteFixUp(IntervalTreeNode* x) { |
495 |
IntervalTreeNode * w; |
496 |
IntervalTreeNode * rootLeft = root->left; |
497 |
|
498 |
while( (!x->red) && (rootLeft != x)) { |
499 |
if (x == x->parent->left) { |
500 |
w=x->parent->right; |
501 |
if (w->red) { |
502 |
w->red=0; |
503 |
x->parent->red=1; |
504 |
LeftRotate(x->parent); |
505 |
w=x->parent->right; |
506 |
} |
507 |
if ( (!w->right->red) && (!w->left->red) ) { |
508 |
w->red=1; |
509 |
x=x->parent; |
510 |
} else { |
511 |
if (!w->right->red) { |
512 |
w->left->red=0; |
513 |
w->red=1; |
514 |
RightRotate(w); |
515 |
w=x->parent->right; |
516 |
} |
517 |
w->red=x->parent->red; |
518 |
x->parent->red=0; |
519 |
w->right->red=0; |
520 |
LeftRotate(x->parent); |
521 |
x=rootLeft; /* this is to exit while loop */ |
522 |
} |
523 |
} else { /* the code below is has left and right switched from above */ |
524 |
w=x->parent->left; |
525 |
if (w->red) { |
526 |
w->red=0; |
527 |
x->parent->red=1; |
528 |
RightRotate(x->parent); |
529 |
w=x->parent->left; |
530 |
} |
531 |
if ( (!w->right->red) && (!w->left->red) ) { |
532 |
w->red=1; |
533 |
x=x->parent; |
534 |
} else { |
535 |
if (!w->left->red) { |
536 |
w->right->red=0; |
537 |
w->red=1; |
538 |
LeftRotate(w); |
539 |
w=x->parent->left; |
540 |
} |
541 |
w->red=x->parent->red; |
542 |
x->parent->red=0; |
543 |
w->left->red=0; |
544 |
RightRotate(x->parent); |
545 |
x=rootLeft; /* this is to exit while loop */ |
546 |
} |
547 |
} |
548 |
} |
549 |
x->red=0; |
550 |
|
551 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
552 |
CheckAssumptions(); |
553 |
#elif defined(DEBUG_ASSERT) |
554 |
Assert(!nil->red,"nil not black in ITDeleteFixUp"); |
555 |
Assert((nil->maxHigh=MIN_INT), |
556 |
"nil->maxHigh != MIN_INT in ITDeleteFixUp"); |
557 |
#endif |
558 |
} |
559 |
|
560 |
|
561 |
/***********************************************************************/ |
562 |
/* FUNCTION: DeleteNode */ |
563 |
/**/ |
564 |
/* INPUTS: tree is the tree to delete node z from */ |
565 |
/**/ |
566 |
/* OUTPUT: returns the Interval stored at deleted node */ |
567 |
/**/ |
568 |
/* EFFECT: Deletes z from tree and but don't call destructor */ |
569 |
/* Then calls FixUpMaxHigh to fix maxHigh fields then calls */ |
570 |
/* ITDeleteFixUp to restore red-black properties */ |
571 |
/**/ |
572 |
/* Modifies Input: z */ |
573 |
/**/ |
574 |
/* The algorithm from this function is from _Introduction_To_Algorithms_ */ |
575 |
/***********************************************************************/ |
576 |
|
577 |
Interval * IntervalTree::DeleteNode(IntervalTreeNode * z){ |
578 |
IntervalTreeNode* y; |
579 |
IntervalTreeNode* x; |
580 |
Interval * returnValue = z->storedInterval; |
581 |
|
582 |
y= ((z->left == nil) || (z->right == nil)) ? z : GetSuccessorOf(z); |
583 |
x= (y->left == nil) ? y->right : y->left; |
584 |
if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */ |
585 |
root->left=x; |
586 |
} else { |
587 |
if (y == y->parent->left) { |
588 |
y->parent->left=x; |
589 |
} else { |
590 |
y->parent->right=x; |
591 |
} |
592 |
} |
593 |
if (y != z) { /* y should not be nil in this case */ |
594 |
|
595 |
#ifdef DEBUG_ASSERT |
596 |
Assert( (y!=nil),"y is nil in DeleteNode \n"); |
597 |
#endif |
598 |
/* y is the node to splice out and x is its child */ |
599 |
|
600 |
y->maxHigh = MIN_INT; |
601 |
y->left=z->left; |
602 |
y->right=z->right; |
603 |
y->parent=z->parent; |
604 |
z->left->parent=z->right->parent=y; |
605 |
if (z == z->parent->left) { |
606 |
z->parent->left=y; |
607 |
} else { |
608 |
z->parent->right=y; |
609 |
} |
610 |
FixUpMaxHigh(x->parent); |
611 |
if (!(y->red)) { |
612 |
y->red = z->red; |
613 |
DeleteFixUp(x); |
614 |
} else |
615 |
y->red = z->red; |
616 |
delete z; |
617 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
618 |
CheckAssumptions(); |
619 |
#elif defined(DEBUG_ASSERT) |
620 |
Assert(!nil->red,"nil not black in ITDelete"); |
621 |
Assert((nil->maxHigh=MIN_INT),"nil->maxHigh != MIN_INT in ITDelete"); |
622 |
#endif |
623 |
} else { |
624 |
FixUpMaxHigh(x->parent); |
625 |
if (!(y->red)) DeleteFixUp(x); |
626 |
delete y; |
627 |
#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS |
628 |
CheckAssumptions(); |
629 |
#elif defined(DEBUG_ASSERT) |
630 |
Assert(!nil->red,"nil not black in ITDelete"); |
631 |
Assert((nil->maxHigh=MIN_INT),"nil->maxHigh != MIN_INT in ITDelete"); |
632 |
#endif |
633 |
} |
634 |
return returnValue; |
635 |
} |
636 |
|
637 |
|
638 |
/***********************************************************************/ |
639 |
/* FUNCTION: Overlap */ |
640 |
/**/ |
641 |
/* INPUTS: [a1,a2] and [b1,b2] are the low and high endpoints of two */ |
642 |
/* closed intervals. */ |
643 |
/**/ |
644 |
/* OUTPUT: stack containing pointers to the nodes between [low,high] */ |
645 |
/**/ |
646 |
/* Modifies Input: none */ |
647 |
/**/ |
648 |
/* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */ |
649 |
/***********************************************************************/ |
650 |
|
651 |
int Overlap(int a1, int a2, int b1, int b2) { |
652 |
if (a1 <= b1) { |
653 |
return( (b1 <= a2) ); |
654 |
} else { |
655 |
return( (a1 <= b2) ); |
656 |
} |
657 |
} |
658 |
|
659 |
|
660 |
/***********************************************************************/ |
661 |
/* FUNCTION: Enumerate */ |
662 |
/**/ |
663 |
/* INPUTS: tree is the tree to look for intervals overlapping the */ |
664 |
/* closed interval [low,high] */ |
665 |
/**/ |
666 |
/* OUTPUT: stack containing pointers to the nodes overlapping */ |
667 |
/* [low,high] */ |
668 |
/**/ |
669 |
/* Modifies Input: none */ |
670 |
/**/ |
671 |
/* EFFECT: Returns a stack containing pointers to nodes containing */ |
672 |
/* intervals which overlap [low,high] in O(max(N,k*log(N))) */ |
673 |
/* where N is the number of intervals in the tree and k is */ |
674 |
/* the number of overlapping intervals */ |
675 |
/**/ |
676 |
/* Note: This basic idea for this function comes from the */ |
677 |
/* _Introduction_To_Algorithms_ book by Cormen et al, but */ |
678 |
/* modifications were made to return all overlapping intervals */ |
679 |
/* instead of just the first overlapping interval as in the */ |
680 |
/* book. The natural way to do this would require recursive */ |
681 |
/* calls of a basic search function. I translated the */ |
682 |
/* recursive version into an interative version with a stack */ |
683 |
/* as described below. */ |
684 |
/***********************************************************************/ |
685 |
|
686 |
|
687 |
|
688 |
/* The basic idea for the function below is to take the IntervalSearch */ |
689 |
/* function from the book and modify to find all overlapping intervals */ |
690 |
/* instead of just one. This means that any time we take the left */ |
691 |
/* branch down the tree we must also check the right branch if and only if */ |
692 |
/* we find an overlapping interval in that left branch. Note this is a */ |
693 |
/* recursive condition because if we go left at the root then go left */ |
694 |
/* again at the first left child and find an overlap in the left subtree */ |
695 |
/* of the left child of root we must recursively check the right subtree */ |
696 |
/* of the left child of root as well as the right child of root. */ |
697 |
|
698 |
TemplateStack<void *> * IntervalTree::Enumerate(int low, |
699 |
int high) { |
700 |
TemplateStack<void *> * enumResultStack; |
701 |
IntervalTreeNode* x=root->left; |
702 |
int stuffToDo = (x != nil); |
703 |
|
704 |
// Possible speed up: add min field to prune right searches // |
705 |
|
706 |
#ifdef DEBUG_ASSERT |
707 |
Assert((recursionNodeStackTop == 1), |
708 |
"recursionStack not empty when entering IntervalTree::Enumerate"); |
709 |
#endif |
710 |
currentParent = 0; |
711 |
enumResultStack = new TemplateStack<void *>(4); |
712 |
|
713 |
while(stuffToDo) { |
714 |
if (Overlap(low,high,x->key,x->high) ) { |
715 |
enumResultStack->Push(x->storedInterval); |
716 |
recursionNodeStack[currentParent].tryRightBranch=1; |
717 |
} |
718 |
if(x->left->maxHigh >= low) { // implies x != nil |
719 |
if ( recursionNodeStackTop == recursionNodeStackSize ) { |
720 |
recursionNodeStackSize *= 2; |
721 |
recursionNodeStack = (it_recursion_node *) |
722 |
realloc(recursionNodeStack, |
723 |
recursionNodeStackSize * sizeof(it_recursion_node)); |
724 |
if (recursionNodeStack == NULL) |
725 |
exit(1); |
726 |
} |
727 |
recursionNodeStack[recursionNodeStackTop].start_node = x; |
728 |
recursionNodeStack[recursionNodeStackTop].tryRightBranch = 0; |
729 |
recursionNodeStack[recursionNodeStackTop].parentIndex = currentParent; |
730 |
currentParent = recursionNodeStackTop++; |
731 |
x = x->left; |
732 |
} else { |
733 |
x = x->right; |
734 |
} |
735 |
stuffToDo = (x != nil); |
736 |
while( (!stuffToDo) && (recursionNodeStackTop > 1) ) { |
737 |
if(recursionNodeStack[--recursionNodeStackTop].tryRightBranch) { |
738 |
x=recursionNodeStack[recursionNodeStackTop].start_node->right; |
739 |
currentParent=recursionNodeStack[recursionNodeStackTop].parentIndex; |
740 |
recursionNodeStack[currentParent].tryRightBranch=1; |
741 |
stuffToDo = ( x != nil); |
742 |
} |
743 |
} |
744 |
} |
745 |
#ifdef DEBUG_ASSERT |
746 |
Assert((recursionNodeStackTop == 1), |
747 |
"recursionStack not empty when exiting IntervalTree::Enumerate"); |
748 |
#endif |
749 |
return(enumResultStack); |
750 |
} |
751 |
|
752 |
|
753 |
|
754 |
int IntervalTree::CheckMaxHighFieldsHelper(IntervalTreeNode * y, |
755 |
const int currentHigh, |
756 |
int match) const |
757 |
{ |
758 |
if (y != nil) { |
759 |
match = CheckMaxHighFieldsHelper(y->left,currentHigh,match) ? |
760 |
1 : match; |
761 |
if (y->high == currentHigh) |
762 |
match = 1; |
763 |
match = CheckMaxHighFieldsHelper(y->right,currentHigh,match) ? |
764 |
1 : match; |
765 |
} |
766 |
return match; |
767 |
} |
768 |
|
769 |
|
770 |
|
771 |
/* Make sure the maxHigh fields for everything makes sense. * |
772 |
* If something is wrong, print a warning and exit */ |
773 |
void IntervalTree::CheckMaxHighFields(IntervalTreeNode * x) const { |
774 |
if (x != nil) { |
775 |
CheckMaxHighFields(x->left); |
776 |
if(!(CheckMaxHighFieldsHelper(x,x->maxHigh,0) > 0)) { |
777 |
exit(1); |
778 |
} |
779 |
CheckMaxHighFields(x->right); |
780 |
} |
781 |
} |
782 |
|
783 |
void IntervalTree::CheckAssumptions() const { |
784 |
CheckMaxHighFields(root->left); |
785 |
} |
786 |
|