KrisLibrary  1.0.0
RangeMap.h
1 #ifndef RANGE_MAP_H
2 #define RANGE_MAP_H
3 
4 #include <map>
5 #include <vector>
6 #include <KrisLibrary/errors.h>
7 using namespace std;
8 
12 template<class T>
13 class RangeMap
14 {
15  public:
16  typedef map<int,T>::iterator iterator;
17  typedef map<int,T>::const_iterator const_iterator;
18 
19  RangeMap();
20  void clear();
21  inline bool empty() { return items.empty(); }
22  void setRange(int imin,int imax);
23  void expandRange(int item);
24  void insert(int item,const T& value);
25  void erase(iterator it);
26  void erase(int item);
27  inline iterator begin() { return items.begin(); }
28  inline const_iterator begin() const { return items.begin(); }
29  inline iterator end() { return items.end(); }
30  inline const_iterator end() const { return items.end(); }
31  size_t size() const { return items.size(); }
32  int count(int item);
33  iterator find(int item);
34  const_iterator find(int item) const;
35  inline bool isRangeEmpty() const { return imax < imin; }
36  inline int minimum() const { return imin; }
37  inline int maximum() const { return imax; }
38  inline bool inRange(int item) const { return item >= imin && item <= imax; }
39  inline iterator cacheGet(int item) const { return contains[item-imin]; }
40  inline void cacheSet(int item,iterator it) { contains[item-imin]=it; }
41 
42  void BuildCache();
43  void ClearCache();
44  inline bool IsCacheBuilt() const { return hasContainmentCache; }
45 
46  private:
47  map<int,T> items;
48  int imin,imax;
49  bool hasContainmentCache;
50  vector<iterator> contains;
51 };
52 
53 template <class T>
55  :imin(1),imax(0),hasContainmentCache(false)
56 {}
57 
58 template <class T>
59 void RangeMap<T>::clear()
60 {
61  imin=1;
62  imax=0;
63  hasContainmentCache=false;
64  items.clear();
65  contains.clear();
66 }
67 
68 template <class T>
69 void RangeMap<T>::setRange(int _imin,int _imax)
70 {
71  if(!isRangeEmpty() && !items.empty()) //already has a range
72  Assert(_imin <= imin && _imax >= imax);
73  if(hasContainmentCache) {
74  FatalError("Already have cache set up");
75  }
76  imin=_imin;
77  imax=_imax;
78 }
79 
80 template <class T>
81 void RangeMap<T>::expandRange(int item)
82 {
83  if(isRangeEmpty()) { //has no range
84  imin = imax = item;
85  return;
86  }
87  if(hasContainmentCache) {
88  if(item < imin) {
89  FatalError("RangeMap<T>::expandRange(): error, item lower than the range bound");
90  }
91  if(item > imax) {
92  //issue a warning, perhaps?
93  contains.resize(item-imin+1,end());
94  imax = item;
95  }
96  }
97  else {
98  if(item < imin) imin=item;
99  else if(item > imax) imax=item;
100  }
101 }
102 
103 template <class T>
104 void RangeMap<T>::insert(int item)
105 {
106  if(hasContainmentCache) {
107  if(item < imin) {
108  FatalError("RangeMap<T>::insert(): error, item lower than the range bound");
109  }
110  if(item > imax) {
111  //issue a warning, perhaps?
112  contains.resize(item-imin+1,false);
113  imax = item;
114  }
115  iterator it=cacheGet(item);
116  if(it == end()) {
117  iterator it=items.insert(item);
118  cacheSet(item,it);
119  }
120  }
121  else {
122  items.insert(item);
123  if(item < imin) imin=item;
124  if(item > imax) imax=item;
125  }
126 }
127 
128 template <class T>
129 void RangeMap<T>::erase(int item)
130 {
131  if(!inRange(item)) return;
132  if(hasContainmentCache) {
133  iterator it=cacheGet(item);
134  if(it != end()) {
135  items.erase(it);
136  cacheSet(item,end());
137  }
138  }
139  else {
140  items.erase(items.find(item));
141  }
142 }
143 
144 template <class T>
145 void RangeMap<T>::erase(iterator it)
146 {
147  if(it == end()) return;
148  if(hasContainmentCache) cacheSet(*it,end());
149  items.erase(it);
150 }
151 
152 template <class T>
153 int RangeMap<T>::count(int item)
154 {
155  if(!inRange(item)) return 0;
156  if(hasContainmentCache) {
157  if(cacheGet(item) != end()) return 1;
158  return 0;
159  }
160  return items.count(item);
161 }
162 
163 template <class T>
164 RangeMap<T>::iterator RangeMap<T>::find(int item)
165 {
166  if(!inRange(item)) return items.end();
167  if(hasContainmentCache)
168  return cacheGet(item);
169  else
170  return items.find(item);
171 }
172 
173 template <class T>
174 RangeMap<T>::const_iterator RangeMap<T>::find(int item) const
175 {
176  if(!inRange(item)) return items.end();
177  if(hasContainmentCache)
178  return cacheGet(item);
179  else
180  return items.find(item);
181 }
182 
183 template <class T>
185 {
186  if(imax < imin) return; //no items
187  if(hasContainmentCache) return;
188  Assert(imax >= imin);
189  contains.resize(imax-imin+1);
190  fill(contains.begin(),contains.end(),items.end());
191  for(iterator i=items.begin();i!=items.end();i++)
192  cacheSet(*i,i);
193  hasContainmentCache = true;
194 }
195 
196 template <class T>
198 {
199  hasContainmentCache=false;
200  contains.clear();
201 }
202 
203 #endif
Definition: rayprimitives.h:132
Same as RangeSet, but a map rather than a set. O(1) find as well.
Definition: RangeMap.h:13