Add reverse iterators and an updateValue function to IntervalTree.
[dyninst.git] / common / src / 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   c_r_iter rbegin() { return tree_.rbegin(); }
58   c_r_iter rend() { return tree_.rend(); }
59   const_iterator begin() const { return tree_.begin(); }
60   const_iterator end() const { return tree_.end(); }
61
62   int size() const { return tree_.size(); }
63   bool empty() const { return tree_.empty(); }
64   void insert(K lb, K ub, V v) {
65     tree_[lb] = std::make_pair(ub, v);
66   }
67
68   void remove(K lb) {
69      erase(lb);
70   }
71
72   void erase(K lb) {
73      tree_.erase(lb);
74   }
75
76   bool find(K key, V &value) const {
77     K lb = 0;
78     K ub = 0;
79     V val;
80     if (!precessor(key, lb, ub, val))
81       return false;
82     if (key < lb) return false;
83     if (key >= ub) return false;
84     value = val;
85     return true;
86   }
87
88   bool find(K key, K &l, K &u, V &value) const {
89     if (!precessor(key, l, u, value))
90       return false;
91     if (key < l) return false;
92     if (key >= u) return false;
93     return true;
94   }
95
96   bool precessor(K key, K &l, K &u, V &v) const {
97     Entry e;
98     if (!precessor(key, e)) {
99       return false;
100     }
101     l = lb(e);
102     u = ub(e);
103     v = value(e);
104     return true;
105   }
106
107   bool precessor(K key, Entry &e) const {
108     if (tree_.empty()) return false;
109     c_iter iter = tree_.lower_bound(key);
110     if ((iter == tree_.end()) ||
111         (iter->first != key)) {
112       if (iter == tree_.begin()) {
113         return false;
114       }
115       --iter;
116     }
117     if (iter->first > key) return false;
118
119     lb(e) = iter->first;
120     ub(e) = iter->second.first;
121     value(e) = iter->second.second;
122
123     assert(lb(e) <= key);
124     if (ub(e) <= key) return false;
125     return true;
126   }
127   void elements(std::vector<Entry> &buffer) const {
128     buffer.clear();
129     for (c_iter iter = tree_.begin();
130          iter != tree_.end(); ++iter) {
131       Entry e;
132       lb(e) = iter->first;
133       ub(e) = iter->second.first;
134       value(e) = iter->second.second;
135       buffer.push_back(e);
136     }
137   }
138
139   K lowest() const { 
140     if (tree_.empty()) return 0;
141     c_iter iter = tree_.begin();
142     return iter->first;
143   }
144
145   K highest() const { 
146     if (tree_.empty()) return 0;
147     c_r_iter iter = tree_.rbegin();
148     return iter->second.first;
149   }
150
151   void clear() { tree_.clear(); }
152
153   bool empty() { return tree_.empty(); }
154
155   bool update(K lb, K newUB) {
156      Iter iter = tree_.find(lb);
157      if (iter == tree_.end()) return false;
158      iter->second.first = newUB;
159      return true;
160   }
161
162   bool updateValue(K lb, V newVal) {
163       Iter iter = tree_.find(lb);
164       if (iter == tree_.end()) return false;
165       iter->second.second = newVal;
166       return true;
167   }
168
169  private:
170   
171   static V &value(Entry &e) { return e.second; }
172   static K &lb(Entry &e) { return e.first.first; }
173   static K &ub(Entry &e) { return e.first.second; }
174
175   Tree tree_;
176 };
177 #endif