Merge branch 'master' into bgq_ramdisk_io
[dyninst.git] / common / h / IntervalTree.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #if !defined(INTERVAL_TREE_H)
32 #define INTERVAL_TREE_H
33
34 #include <assert.h>
35 #include <stdio.h>
36 #include <vector>
37 #include <map>
38
39 template <class K, class V>
40 class IntervalTree {
41   typedef typename std::map<K, std::pair<K, V> > Tree;
42   typedef typename Tree::const_iterator c_iter;
43   typedef typename Tree::const_reverse_iterator c_r_iter;
44   typedef typename Tree::iterator Iter;
45
46  public:
47   typedef typename std::pair<K, K> Range;
48   typedef typename std::pair<Range, V> Entry;
49   typedef typename Tree::iterator iterator;
50   typedef typename Tree::const_iterator const_iterator;
51
52   IntervalTree() {};
53   ~IntervalTree() {};
54
55   iterator begin() { return tree_.begin(); }
56   iterator end() { return tree_.end(); }
57   const_iterator begin() const { return tree_.begin(); }
58   const_iterator end() const { return tree_.end(); }
59
60   int size() const { return tree_.size(); }
61   bool empty() const { return tree_.empty(); }
62   void insert(K lb, K ub, V v) {
63     tree_[lb] = std::make_pair(ub, v);
64   }
65
66   void remove(K lb) {
67      erase(lb);
68   }
69
70   void erase(K lb) {
71      tree_.erase(lb);
72   }
73
74   bool find(K key, V &value) const {
75     K lb = 0;
76     K ub = 0;
77     V val;
78     if (!precessor(key, lb, ub, val))
79       return false;
80     if (key < lb) return false;
81     if (key >= ub) return false;
82     value = val;
83     return true;
84   }
85
86   bool find(K key, K &l, K &u, V &value) const {
87     if (!precessor(key, l, u, value))
88       return false;
89     if (key < l) return false;
90     if (key >= u) return false;
91     return true;
92   }
93
94   bool precessor(K key, K &l, K &u, V &v) const {
95     Entry e;
96     if (!precessor(key, e)) {
97       return false;
98     }
99     l = lb(e);
100     u = ub(e);
101     v = value(e);
102     return true;
103   }
104
105   bool precessor(K key, Entry &e) const {
106     if (tree_.empty()) return false;
107     c_iter iter = tree_.lower_bound(key);
108     if ((iter == tree_.end()) ||
109         (iter->first != key)) {
110       if (iter == tree_.begin()) {
111         return false;
112       }
113       --iter;
114     }
115     if (iter->first > key) return false;
116
117     lb(e) = iter->first;
118     ub(e) = iter->second.first;
119     value(e) = iter->second.second;
120
121     assert(lb(e) <= key);
122     if (ub(e) <= key) return false;
123     return true;
124   }
125   void elements(std::vector<Entry> &buffer) const {
126     buffer.clear();
127     for (c_iter iter = tree_.begin();
128          iter != tree_.end(); ++iter) {
129       Entry e;
130       lb(e) = iter->first;
131       ub(e) = iter->second.first;
132       value(e) = iter->second.second;
133       buffer.push_back(e);
134     }
135   }
136
137   K lowest() const { 
138     if (tree_.empty()) return 0;
139     c_iter iter = tree_.begin();
140     return iter->first;
141   }
142
143   K highest() const { 
144     if (tree_.empty()) return 0;
145     c_r_iter iter = tree_.rbegin();
146     return iter->second.first;
147   }
148
149   void clear() { tree_.clear(); }
150
151   bool empty() { return tree_.empty(); }
152
153   bool update(K lb, K newUB) {
154      Iter iter = tree_.find(lb);
155      if (iter == tree_.end()) return false;
156      iter->second.first = newUB;
157   }
158
159  private:
160   
161   static V &value(Entry &e) { return e.second; }
162   static K &lb(Entry &e) { return e.first.first; }
163   static K &ub(Entry &e) { return e.first.second; }
164
165   Tree tree_;
166 };
167 #endif