Update copyright to LGPL on all files
[dyninst.git] / common / h / IntervalTree.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #if !defined(INTERVAL_TREE_H)
33 #define INTERVAL_TREE_H
34
35 #include <assert.h>
36 #include <stdio.h>
37
38 template <class K, class V>
39 class IntervalTree {
40  private:
41
42     typedef enum { TREE_RED, TREE_BLACK } color_t;
43     typedef std::pair<K, K> Range;
44
45     /** tree implementation structure. Used to implement the RB tree */
46     typedef struct entry {
47         // Stores a range [lB...uB)
48         K lB; // Lower bound
49         K uB; // Upper bound (soft)
50         V value;
51         color_t color;  /* color of the node */
52         struct entry* left; /* left child */
53         struct entry* right; /* right child */
54         struct entry* parent; /* parent of the node */
55
56         /** constructor for structure */
57         entry() 
58             : color(TREE_BLACK),left(NULL),right(NULL),parent(NULL) {}
59
60         /** constructor used for non-nil elements 
61          * @param e nil entry
62          */       
63         entry(entry* e) //constructor with nil entry 
64             : color(TREE_RED), left(e), right(e), parent(NULL) {}
65
66         /** constructor
67          * @param d data element
68          * @param e nill entry 
69          */
70         entry(K lB_, K uB_, V value_, entry* e) 
71             : lB(lB_), uB(uB_), value(value_), color(TREE_RED), left(e),
72             right(e), parent(NULL) {}
73
74         /** constructor 
75          * @param e the entry structure that will be copied 
76          */
77         entry(const entry& e) : lB(e.lB), uB(e.uB),value(e.value),color(e.color),
78             left(NULL),right(NULL),parent(NULL) {}
79     } entry;
80
81     /** pointer to define the nil element of the tree NULL is not used
82      * since some operations need sentinel nil which may have non-nil
83      * parent.
84      */
85     entry* nil;
86
87     /** size of the tree */
88     int setSize;
89
90     /** pointer to the tree structure */
91     entry* setData;
92
93     // method that implements left rotation used by RB tree for balanced
94     // tree construction and keeps the RBtree properties.
95     void leftRotate(entry* pivot) {
96         if(!pivot || (pivot == nil)) return;
97         entry* y = pivot->right;
98         if(y == nil) return;
99         pivot->right = y->left;
100         if(y->left != nil) y->left->parent = pivot;
101         y->parent = pivot->parent;
102         if(!pivot->parent) setData = y;
103         else if(pivot == pivot->parent->left)
104             pivot->parent->left = y;
105         else
106             pivot->parent->right = y;
107         y->left = pivot;
108         pivot->parent = y;
109     }
110
111     // method that implements right rotattion used by RB tree for balanced
112     // tree construction and keeps the RBtree properties.
113     void rightRotate(entry* pivot) {
114         if(!pivot || (pivot == nil)) return;
115         entry* x = pivot->left;
116         if(x == nil) return;
117         pivot->left = x->right;
118         if(x->right != nil) x->right->parent = pivot;
119         x->parent = pivot->parent;
120         if(!pivot->parent) setData = x;
121         else if(pivot == pivot->parent->left)
122             pivot->parent->left = x;
123         else
124             pivot->parent->right = x;
125         x->right = pivot;
126         pivot->parent = x;
127     }
128
129     // method that modifies the tree structure after deletion for keeping
130     // the RBtree properties.
131     void deleteFixup(entry* x) {
132         while((x != setData) && 
133               (x->color == TREE_BLACK)) {            
134             if(x == x->parent->left){
135                 entry* w = x->parent->right;
136                 if(w->color == TREE_RED){
137                     w->color = TREE_BLACK;
138                     x->parent->color = TREE_RED;
139                     leftRotate(x->parent);
140                     w = x->parent->right;
141                 }
142                 if((w->left->color == TREE_BLACK) &&
143                    (w->right->color == TREE_BLACK)){
144                     w->color = TREE_RED;
145                     x = x->parent;
146                 }
147                 else{
148                     if(w->right->color == TREE_BLACK){
149                         w->left->color = TREE_BLACK;
150                         w->color = TREE_RED;
151                         rightRotate(w);
152                         w = x->parent->right;
153                     }
154                     w->color = x->parent->color;
155                     x->parent->color = TREE_BLACK;
156                     w->right->color = TREE_BLACK;
157                     leftRotate(x->parent);
158                     x = setData;
159                 }
160             }
161             else{
162                 entry* w = x->parent->left;
163                 if(w->color == TREE_RED){
164                     w->color = TREE_BLACK;
165                     x->parent->color = TREE_RED;
166                     rightRotate(x->parent);
167                     w = x->parent->left;
168                 }
169                 if((w->right->color == TREE_BLACK) &&
170                    (w->left->color == TREE_BLACK)){
171                     w->color = TREE_RED;
172                     x = x->parent;
173                 }
174                 else{
175                     if(w->left->color == TREE_BLACK){
176                         w->right->color = TREE_BLACK;
177                         w->color = TREE_RED;
178                         leftRotate(w);
179                         w = x->parent->left;
180                     }
181                     w->color = x->parent->color;
182                     x->parent->color = TREE_BLACK;
183                     w->left->color = TREE_BLACK;
184                     rightRotate(x->parent);
185                     x = setData;
186                 }
187             }
188         }
189         x->color = TREE_BLACK;
190     }
191     // insertion to a binary search tree. It returns the new element pointer
192     // that is inserted. If element is already there it returns NULL
193     entry* treeInsert(K lB, K uB, V value) {
194         entry* y = NULL;
195         entry* x = setData;
196         while(x != nil){
197             y = x;
198             if (lB < x->lB) 
199                 x = x->left;
200             else if(lB > x->lB)
201                 x = x->right;
202             else 
203                 // Found it...
204                 return NULL;
205         }       
206         entry* z = new entry(lB, uB, value, nil);
207         z->parent = y;
208         if(!y) {
209             setData = z;
210         }
211         else {
212             if (lB < y->lB)
213                 y->left = z;
214             else if (lB > y->lB)
215                 y->right = z;
216         }
217         setSize++;
218         return z;
219     }
220     
221     // finds the elemnts in the tree that will be replaced with the element
222     // being deleted in the  deletion. That is the element with the largest
223     // smallest value than the element being deleted. 
224     entry* treeSuccessor(entry* x) const {
225         if(!x || (x == nil))
226                 return NULL;
227         if(x->right != nil){
228                 entry* z = x->right;
229                 while(z->left != nil) z = z->left;
230                 return z;
231         }
232         entry* y = x->parent;
233         while(y && (x == y->right)){
234                 x = y;
235                 y = y->parent;
236         }
237         return y;
238     }
239
240     // method that returns the entry pointer for the element that is searched
241     //for. If the entry is not found then it retuns NULL
242     entry* find_internal(K key) const {
243         entry* x = setData;
244         while(x != nil){
245             if (key < x->lB) {
246                 x = x->left;
247             }
248             else if (key > x->lB) {
249                 x = x->right;
250             }
251             else
252                 return x;
253         }       
254         return NULL;
255     }
256
257     // Vector version of above
258     // infix traverse of the RB tree. It traverses the tree in ascending order
259     void traverse(std::vector<std::pair<Range, V> > &all, entry*node) const {
260         if(node == nil)
261             return;
262         if(node->left != nil)
263             traverse(all,node->left);
264         all.push_back(std::make_pair(std::make_pair(node->lB, node->uB), node->value));
265         if(node->right != nil)
266             traverse(all,node->right);
267     }
268
269     // deletes the tree structure for deconstructor.
270     void destroy(entry* node) {
271         if(!node || (node == nil))
272                 return;
273         if(node->left != nil)
274                 destroy(node->left);
275         if(node->right != nil)
276                 destroy(node->right);
277         delete node;
278     }
279
280     entry *precessor_int(K key) const {
281         entry *x = setData;
282         entry *last = nil;
283         while (x != nil) {
284             assert(x != NULL);
285             if (x->lB == key) {
286                 return x;
287             }
288             else if (key < x->lB) {
289                 x = x->left;
290             }
291             else { // key > x->lB
292                 last = x;
293                 x = x->right;
294             }
295         }
296         if (x == nil) {
297             // Ran out of tree to search... get the parent
298             assert(last != NULL);
299             if (last != nil) {
300                 return last;
301             }
302             else return NULL;
303         }
304         // Should never hit here
305         assert(0);
306         return NULL;
307     }
308
309
310   public:
311
312     /** constructor. The default comparison structure is used */
313     IntervalTree() : setSize(0) { 
314         nil = new entry;
315         setData = nil;
316     }
317
318     
319     /** destructor which deletes all tree structure and allocated entries */
320     ~IntervalTree() {
321         destroy(setData);
322         delete nil;
323     }
324
325     /** returns the cardinality of the tree , number of elements */
326     int size() const { return setSize; }
327     
328     /** returns true if tree is empty */
329     bool empty() const { return (setData == nil); }
330
331     /** inserts the element in the tree 
332      * @param 1 element that will be inserted
333      */
334     void insert(K lB, K uB, V value) {
335         // See if we can simply expand an existing range
336         entry *q = precessor_int(lB);
337         if (q &&
338             (q->value == value) &&
339             (q->uB >= lB) &&
340             (q->uB <= uB)) {
341             // Expand q. By definition (non-overlapping
342             // intervals) this will not cause the
343             // tree to unbalance.
344             q->uB = uB;
345             return;
346         }
347
348         entry* x = treeInsert(lB, uB, value);
349         if(!x) {
350             // We're done.
351             return;
352         }
353         x->color = TREE_RED;
354         while((x != setData) && (x->parent->color == TREE_RED)){
355             if(x->parent == x->parent->parent->left){
356                 entry* y = x->parent->parent->right;
357                 if(y->color == TREE_RED){
358                     x->parent->color = TREE_BLACK;
359                     y->color = TREE_BLACK;
360                     x->parent->parent->color = TREE_RED;
361                     x = x->parent->parent;
362                 }
363                 else{
364                     if(x == x->parent->right){
365                         x = x->parent;
366                         leftRotate(x);
367                     }
368                     x->parent->color = TREE_BLACK;
369                     x->parent->parent->color = TREE_RED;
370                     rightRotate(x->parent->parent);
371                 }
372             }
373             else{
374                 entry* y = x->parent->parent->left;
375                 if(y->color == TREE_RED){
376                     x->parent->color = TREE_BLACK;
377                     y->color = TREE_BLACK;
378                     x->parent->parent->color = TREE_RED;
379                     x = x->parent->parent;
380                 }
381                 else{
382                     if(x == x->parent->left){
383                         x = x->parent;
384                         rightRotate(x);
385                     }
386                     x->parent->color = TREE_BLACK;
387                     x->parent->parent->color = TREE_RED;
388                     leftRotate(x->parent->parent);
389                 }
390             }
391         }
392         setData->color = TREE_BLACK;
393     }
394     
395     /** removes the element in the tree 
396      * @param 1 element that will be removed  
397      */
398     void remove(K lB) {
399         entry* z = find_internal(lB);
400         if(!z)
401             return;
402         if (z->lB != lB)
403             return;
404         
405         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
406         entry* x=(y->left != nil) ? y->left : y->right;
407         x->parent = y->parent;
408         if(!y->parent) {
409             setData = x;
410         }
411         else if(y == y->parent->left)
412             y->parent->left = x;
413         else
414             y->parent->right = x;
415         if(y != z) {
416             z->value = y->value;
417             z->lB = y->lB;
418         }
419         if(y->color == TREE_BLACK)
420             deleteFixup(x);
421         setSize--;
422         delete y;
423     }
424     
425     /** returns true if the argument is member of the IntervalTree
426      * @param e the element that will be searched for
427      */
428     bool find(K key, V &value) const {
429         V val;
430         K lowerBound;
431         K upperBound;
432         if (!precessor(key, lowerBound, upperBound, val))
433             return false;
434         // Check to see if the range works
435         if (key < lowerBound) {
436             return false;
437         }
438         else if (key >= upperBound) {
439             return false;
440         }
441         value = val;
442         return true;
443     }
444
445     /** Returns the largest value less than or equal to the
446      * lB given
447      */
448     bool precessor(K key, K &lB, K &uB, V &value) const {   
449         entry *x = precessor_int(key);
450         if (x) {
451             lB = x->lB;
452             uB = x->uB;
453             value = x->value;
454             return true;
455         }
456         return false;
457     }
458
459     // And vector-style
460     bool elements(std::vector<std::pair<Range, V> > &buffer) const {
461         if(setData == nil) return false;
462         traverse(buffer,setData);       
463         return true;
464     }
465
466     // Remove all entries in the tree
467     void clear() {
468         if (setData == nil) return;
469         destroy(setData);
470         setData = nil;
471         setSize = 0;
472     }
473 };
474
475 #endif