32 #ifndef PLANCK_RANGESET_H 33 #define PLANCK_RANGESET_H 47 typedef std::vector<T> rtype;
48 typedef typename rtype::iterator iterator;
49 typedef typename rtype::const_iterator c_iterator;
54 tdiff iiv (
const T &val)
const 55 {
return tdiff(std::upper_bound(r.begin(),r.end(),val)-r.begin())-1; }
57 void addRemove (T a, T b,
tdiff v)
59 tdiff pos1=iiv(a), pos2=iiv(b);
60 if ((pos1>=0) && (r[pos1]==a)) --pos1;
62 bool insert_a = (pos1&1)==v;
63 bool insert_b = (pos2&1)==v;
64 tdiff rmstart=pos1+1+(insert_a ? 1 : 0);
65 tdiff rmend =pos2-(insert_b ? 1 : 0);
69 if (insert_a && insert_b && (pos1+1>pos2))
71 r.insert(r.begin()+pos1+1,2,a);
76 if (insert_a) r[pos1+1]=a;
77 if (insert_b) r[pos2]=b;
78 r.erase(r.begin()+rmstart,r.begin()+rmend+1);
85 const double fct1 = 1.;
86 const double fct2 = 1.;
87 tsize slo = sza<szb ? sza : szb,
88 shi = sza<szb ? szb : sza;
89 double cost1 = fct1 * (sza+szb);
90 double cost2 = fct2 * slo * std::max(1,
ilog2(shi));
91 return (cost1<=cost2) ? 1 : (slo==sza) ? 2 : 3;
95 bool flip_a,
bool flip_b)
97 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
98 tsize ia=0, ea=a.r.size(), ib=0, eb=b.r.size();
99 bool runa = ia!=ea, runb = ib!=eb;
102 T va = runa ? a.r[ia] : T(0),
103 vb = runb ? b.r[ib] : T(0);
104 bool adv_a = runa && (!runb || (va<=vb)),
105 adv_b = runb && (!runa || (vb<=va));
106 if (adv_a) { state_a=!state_a; ++ia; runa = ia!=ea; }
107 if (adv_b) { state_b=!state_b; ++ib; runb = ib!=eb; }
108 if ((state_a||state_b)!=state_res)
109 { r.push_back(adv_a ? va : vb); state_res = !state_res; }
113 bool flip_a,
bool flip_b)
115 tdiff iva = flip_a ? 0 : -1;
119 tdiff ivb = (iva==-1) ? -1 : b.iiv(a.r[iva]);
120 bool state_b = flip_b^((ivb&1)==0);
121 if ((iva>-1) && (!state_b)) r.push_back(a.r[iva]);
122 while((ivb<bsz-1)&&((iva==asz-1)||(b.r[ivb+1]<a.r[iva+1])))
123 { ++ivb; state_b=!state_b; r.push_back(b.r[ivb]); }
124 if ((iva<asz-1)&&(!state_b)) r.push_back(a.r[iva+1]);
129 bool flip_a,
bool flip_b)
131 planck_assert((
this!=&a)&&(
this!=&b),
"cannot overwrite the rangeset");
134 if (flip_a)
clear();
else *
this=b;
139 if (flip_b)
clear();
else *
this=a;
145 (strat==1) ? generalUnion1(a,b,flip_a,flip_b) :
146 ((strat==2) ? generalUnion2(a,b,flip_a,flip_b)
147 : generalUnion2(b,a,flip_b,flip_a));
152 bool state_a=
false, state_b=
false, state_res=state_a||state_b;
153 tsize ia=0, ea=a.r.size(), ib=0, eb=b.r.size();
154 bool runa = ia!=ea, runb = ib!=eb;
157 T va = runa ? a.r[ia] : T(0),
158 vb = runb ? b.r[ib] : T(0);
159 bool adv_a = runa && (!runb || (va<=vb)),
160 adv_b = runb && (!runa || (vb<=va));
161 if (adv_a) { state_a=!state_a; ++ia; runa = ia!=ea; }
162 if (adv_b) { state_b=!state_b; ++ib; runb = ib!=eb; }
163 if ((state_a^state_b)!=state_res)
164 { r.push_back(adv_a ? va : vb); state_res = !state_res; }
169 bool flip_a,
bool flip_b)
171 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
172 tsize ia=0, ea=a.r.size(), ib=0, eb=b.r.size();
173 bool runa = ia!=ea, runb = ib!=eb;
176 T va = runa ? a.r[ia] : T(0),
177 vb = runb ? b.r[ib] : T(0);
178 bool adv_a = runa && (!runb || (va<=vb)),
179 adv_b = runb && (!runa || (vb<=va));
180 if (adv_a) { state_a=!state_a; ++ia; runa = ia!=ea; }
181 if (adv_b) { state_b=!state_b; ++ib; runb = ib!=eb; }
182 if ((state_a||state_b)!=state_res)
188 bool flip_a,
bool flip_b)
190 tdiff iva = flip_a ? 0 : -1;
195 {
if ((!flip_b)||(b.r[0]<a.r[0]))
return false; }
197 {
if ((!flip_b)||(b.r[bsz-1]>a.r[asz-1]))
return false; }
200 tdiff ivb=b.iiv(a.r[iva]);
201 if ((ivb!=bsz-1)&&(b.r[ivb+1]<a.r[iva+1]))
return false;
202 if (flip_b==((ivb&1)==0))
return false;
209 bool flip_a,
bool flip_b)
212 return flip_a ?
true : b.r.empty();
214 return flip_b ?
true : a.r.empty();
216 return (strat==1) ? generalAllOrNothing1(a,b,flip_a,flip_b) :
217 ((strat==2) ? generalAllOrNothing2(a,b,flip_a,flip_b)
218 : generalAllOrNothing2(b,a,flip_b,flip_a));
229 bool empty()
const {
return r.empty(); }
231 const rtype &
data()
const {
return r; }
232 void checkConsistency()
const 235 for (
tsize i=1; i<r.size(); ++i)
238 void setData (
const rtype &inp)
256 if ((!r.empty()) && (v1<=r.back()))
259 if (v2>r.back()) r.back()=v2;
262 { r.push_back(v1); r.push_back(v2); }
279 void add(
const T &v1,
const T &v2)
282 if (r.empty() || (v1>=r[r.size()-2]))
append(v1,v2);
290 void remove(
const T &v1,
const T &v2)
293 if (r.empty())
return;
294 if ((v2<=r[0])||(v1>=r.back()))
return;
295 if ((v1<=r[0]) && (v2>=r.back())) { r.clear();
return; }
299 void remove(
const T &v) {
remove(v,v+1); }
304 if (r.empty())
return;
305 if ((b<=r[0]) || (a>=r.back())) { r.clear();
return; }
306 if ((a<=r[0]) && (b>=r.back()))
return;
309 if ((pos2>=0) && (r[pos2]==b)) --pos2;
310 bool insert_b = (pos2&1)==0;
311 r.erase(r.begin()+pos2+1,r.end());
312 if (insert_b) r.push_back(b);
315 bool insert_a = (pos1&1)==0;
316 if (insert_a) r[pos1--]=a;
318 r.erase(r.begin(),r.begin()+pos1+1);
325 for (
tsize i=0; i<r.size(); i+=2)
336 for (
tsize i=0; i<r.size(); i+=2)
337 for (T m(r[i]); m<r[i+1]; ++m)
354 res.generalUnion (*
this,other,
false,
false);
361 res.generalUnion (*
this,other,
true,
true);
368 res.generalUnion (*
this,other,
true,
false);
376 res.generalXor (*
this,other);
385 return (res&1) ? -1 : res>>1;
391 {
return r==other.r; }
398 if (res&1)
return false;
399 return (b<=r[res+1]);
404 {
return !(iiv(v)&1); }
408 {
return generalAllOrNothing(*
this,other,
false,
true); }
414 if ((res&1)==0)
return true;
415 if (res==
tdiff(r.size())-1)
return false;
421 {
return !generalAllOrNothing(*
this,other,
true,
true); }
424 template<
typename T>
inline std::ostream &
operator<< (std::ostream &os,
bool operator==(const rangeset &other) const
bool contains(const rangeset &other) const
bool contains(T a, T b) const
rangeset op_xor(const rangeset &other) const
const rtype & data() const
rangeset op_and(const rangeset &other) const
std::ostream & operator<<(std::ostream &os, const pointing &p)
void toVector(std::vector< T > &res) const
bool overlaps(const rangeset &other) const
void intersect(const T &a, const T &b)
std::vector< T > toVector() const
tdiff findInterval(const T &v) const
bool overlaps(T a, T b) const
void append(const T &v1, const T &v2)
void add(const T &v1, const T &v2)
rangeset op_or(const rangeset &other) const
const T & ivbegin(tdiff i) const
#define planck_assert(testval, msg)
void append(const rangeset &other)
const T & ivend(tdiff i) const
rangeset op_andnot(const rangeset &other) const