6 #include <KrisLibrary/errors.h> 16 typedef map<int,T>::iterator iterator;
17 typedef map<int,T>::const_iterator const_iterator;
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);
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(); }
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; }
44 inline bool IsCacheBuilt()
const {
return hasContainmentCache; }
49 bool hasContainmentCache;
50 vector<iterator> contains;
55 :imin(1),imax(0),hasContainmentCache(
false)
63 hasContainmentCache=
false;
71 if(!isRangeEmpty() && !items.empty())
72 Assert(_imin <= imin && _imax >= imax);
73 if(hasContainmentCache) {
74 FatalError(
"Already have cache set up");
87 if(hasContainmentCache) {
89 FatalError(
"RangeMap<T>::expandRange(): error, item lower than the range bound");
93 contains.resize(item-imin+1,end());
98 if(item < imin) imin=item;
99 else if(item > imax) imax=item;
106 if(hasContainmentCache) {
108 FatalError(
"RangeMap<T>::insert(): error, item lower than the range bound");
112 contains.resize(item-imin+1,
false);
115 iterator it=cacheGet(item);
117 iterator it=items.insert(item);
123 if(item < imin) imin=item;
124 if(item > imax) imax=item;
131 if(!inRange(item))
return;
132 if(hasContainmentCache) {
133 iterator it=cacheGet(item);
136 cacheSet(item,end());
140 items.erase(items.find(item));
147 if(it == end())
return;
148 if(hasContainmentCache) cacheSet(*it,end());
155 if(!inRange(item))
return 0;
156 if(hasContainmentCache) {
157 if(cacheGet(item) != end())
return 1;
160 return items.count(item);
166 if(!inRange(item))
return items.end();
167 if(hasContainmentCache)
168 return cacheGet(item);
170 return items.find(item);
176 if(!inRange(item))
return items.end();
177 if(hasContainmentCache)
178 return cacheGet(item);
180 return items.find(item);
186 if(imax < imin)
return;
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++)
193 hasContainmentCache =
true;
199 hasContainmentCache=
false;
Definition: rayprimitives.h:132
Same as RangeSet, but a map rather than a set. O(1) find as well.
Definition: RangeMap.h:13