32 #ifndef PLANCK_CRANGESET_H 33 #define PLANCK_CRANGESET_H 79 typedef std::vector<T> rtype;
84 bool operator()(
const T &a,
const T &b)
99 bool singleVal()
const 101 if (idx==ref.r.size()-1)
102 return (ref.r[idx]>=0);
104 return ((ref.r[idx]^ref.r[idx+1])>=0);
108 RsIter(
const crangeset &ref_) : idx(0), extra(
false), ref(ref_), val(0)
114 bool atEnd()
const {
return idx>=ref.r.size(); }
119 RsIter &operator++ ()
126 if (!atEnd()) val=abs(ref.r[idx]);
138 if (!atEnd()) val=abs(ref.r[idx]);
143 void advance_up_to(T goal)
155 {
return (ref.r[idx]>=0)^extra; }
165 IvIter(
const crangeset &ref_) : rsi(ref_)
167 if (rsi.atEnd())
return;
172 bool atEnd()
const {
return rsi.atEnd(); }
173 T ivbegin()
const {
return b; }
174 T ivend()
const {
return e; }
175 tdiff ivlen()
const {
return e-b; }
176 IvIter &operator++ ()
179 if (rsi.atEnd())
return *
this;
194 RsOutputIter(
crangeset &ref_) : val(T(0)), val_set(
false), ref(ref_)
196 RsOutputIter &operator*() {
return *
this; }
197 RsOutputIter &operator++ () {
return *
this; }
198 RsOutputIter &operator++ (
int) {
return *
this; }
199 RsOutputIter &operator= (
const T &v)
214 return tdiff(std::upper_bound(r.begin(),r.end(),val,abscomp())
221 const double fct1 = 1.;
222 const double fct2 = 1.;
223 tsize slo = sza<szb ? sza : szb,
224 shi = sza<szb ? szb : sza;
225 double cost1 = fct1 * (sza+szb);
226 double cost2 = fct2 * slo * std::max(1,
ilog2(shi));
227 return (cost1<=cost2) ? 1 : (slo==sza) ? 2 : 3;
231 bool flip_a,
bool flip_b)
234 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
236 RsOutputIter io(res);
237 bool runa = !ia.atEnd(), runb = !ib.atEnd();
240 T va = runa ? *ia : T(0),
241 vb = runb ? *ib : T(0);
242 bool adv_a = runa && (!runb || (va<=vb)),
243 adv_b = runb && (!runa || (vb<=va));
244 if (adv_a) { state_a=!state_a; ++ia; runa = !ia.atEnd(); }
245 if (adv_b) { state_b=!state_b; ++ib; runb = !ib.atEnd(); }
246 if ((state_a||state_b)!=state_res)
247 { *io++ = (adv_a ? va : vb); state_res = !state_res; }
252 bool flip_a,
bool flip_b)
255 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
257 RsOutputIter io(res);
258 bool runa = !ia.atEnd(), runb = !ib.atEnd();
261 T va = runa ? *ia : T(0);
267 ib.advance_up_to (va);
268 state_b=!(flip_b^ib.onoff());
271 T vb = runb ? *ib : T(0);
272 bool adv_a = runa && (!runb || (va<=vb)),
273 adv_b = runb && (!runa || (vb<=va));
274 if (adv_a) { state_a=!state_a; ++ia; runa = !ia.atEnd(); }
275 if (adv_b) { state_b=!state_b; ++ib; runb = !ib.atEnd(); }
276 if ((state_a||state_b)!=state_res)
277 { *io++ = (adv_a ? va : vb); state_res = !state_res; }
282 bool flip_a,
bool flip_b)
289 int strat =
strategy (a.r.size(), b.r.size());
290 return (strat==1) ? generalUnion1(a,b,flip_a,flip_b) :
291 ((strat==2) ? generalUnion2(a,b,flip_a,flip_b)
292 : generalUnion2(b,a,flip_b,flip_a));
297 bool state_a=
false, state_b=
false, state_res=state_a||state_b;
299 RsOutputIter io(res);
300 bool runa = !ia.atEnd(), runb = !ib.atEnd();
303 T va = runa ? *ia : T(0),
304 vb = runb ? *ib : T(0);
305 bool adv_a = runa && (!runb || (va<=vb)),
306 adv_b = runb && (!runa || (vb<=va));
307 if (adv_a) { state_a=!state_a; ++ia; runa = !ia.atEnd(); }
308 if (adv_b) { state_b=!state_b; ++ib; runb = !ib.atEnd(); }
309 if ((state_a^state_b)!=state_res)
310 { *io++ = (adv_a ? va : vb); state_res = !state_res; }
316 bool flip_a,
bool flip_b)
318 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
320 bool runa = !ia.atEnd(), runb = !ib.atEnd();
324 T va = runa ? *ia : T(0),
325 vb = runb ? *ib : T(0);
326 bool adv_a = runa && (!runb || (va<=vb)),
327 adv_b = runb && (!runa || (vb<=va));
328 if (adv_a) { state_a=!state_a; ++ia; runa = !ia.atEnd(); }
329 if (adv_b) { state_b=!state_b; ++ib; runb = !ib.atEnd(); }
330 if ((state_a||state_b)!=state_res)
336 bool flip_a,
bool flip_b)
338 bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
340 bool runa = !ia.atEnd(), runb = !ib.atEnd();
343 T va = runa ? *ia : T(0);
349 ib.advance_up_to (va);
350 state_b=!(flip_b^ib.onoff());
353 T vb = runb ? *ib : T(0);
354 bool adv_a = runa && (!runb || (va<=vb)),
355 adv_b = runb && (!runa || (vb<=va));
356 if (adv_a) { state_a=!state_a; ++ia; runa = !ia.atEnd(); }
357 if (adv_b) { state_b=!state_b; ++ib; runb = !ib.atEnd(); }
358 if ((state_a||state_b)!=state_res)
365 bool flip_a,
bool flip_b)
368 return flip_a ?
true : b.r.empty();
370 return flip_b ?
true : a.r.empty();
371 int strat =
strategy (a.r.size(), b.r.size());
372 return (strat==1) ? generalAllOrNothing1(a,b,flip_a,flip_b) :
373 ((strat==2) ? generalAllOrNothing2(a,b,flip_a,flip_b)
374 : generalAllOrNothing2(b,a,flip_b,flip_a));
379 bool empty()
const {
return r.empty(); }
380 const rtype &data()
const {
return r; }
381 void checkConsistency()
const 384 if (r.size()==0)
return;
385 planck_assert(r[0]>=0,
"incorrect first element in range set");
386 for (
tsize i=1; i<r.size(); ++i)
387 planck_assert(abs(r[i])>abs(r[i-1]+1),
"inconsistent entries");
389 void setData (
const rtype &inp)
402 le=(r.back()<0) ? -r.back() : r.back()+1;
406 if ((v1>le+1)||(r.back()>0))
409 if (v2-v1>1) r.push_back(-v2);
418 if (r.back()>=0) lastbegin= r.back();
419 else if (r[r.size()-2]<0) lastbegin = -r[r.size()-2]+1;
420 else lastbegin = r[r.size()-2];
424 T endval=max(abs(r.back()),v2);
428 if (endval>r.back()+1) r.push_back(-endval);
440 while (!iter.atEnd())
442 append(iter.ivbegin(),iter.ivend());
451 while (!iter.atEnd())
452 {res+=iter.ivlen(); ++iter;}
457 {
return generalUnion (*
this,other,
false,
false); }
459 {
return generalUnion (*
this,other,
true,
true); }
461 {
return generalUnion (*
this,other,
true,
false); }
463 {
return generalXor (*
this,other); }
468 {
return r==other.r; }
475 if (res<0)
return false;
478 if (res==
tdiff(r.size())-1)
return false;
479 if (r[res+1]>=0)
return false;
480 return ((a>-r[res])&&(b<=-r[res+1]));
483 if ((res==
tdiff(r.size())-1) || (r[res+1]>=0))
484 return ((a==r[res])&&(b==a+1));
492 if (res<0)
return false;
495 if (res==
tdiff(r.size())-1)
return false;
496 if (r[res+1]>=0)
return false;
499 if ((res<
tdiff(r.size())-1) && (r[res+1]<0))
506 {
return generalAllOrNothing(*
this,other,
false,
true); }
513 if (empty())
return false;
515 if (res<
tdiff(r.size())-1)
516 if (b>abs(r[res+1]))
return true;
519 if (res==-1)
return false;
520 if (res==
tdiff(r.size())-1)
524 return (a==r[res]) || (r[res+1]<0);
525 return (r[res+1]<0) && (b>-r[res]+1);
531 {
return !generalAllOrNothing(*
this,other,
true,
true); }
534 template<
typename T>
inline std::ostream &operator<< (std::ostream &os,
539 while (!iter.atEnd())
541 os <<
"["<<iter.ivbegin()<<
";"<<iter.ivend()<<
"[ ";
void append(const T &v1, const T &v2)
bool overlaps(T a, T b) const
bool contains(const crangeset &other) const
static int strategy(tsize sza, tsize szb)
bool overlaps(const crangeset &other) const
tdiff iiv(const T &val) const
bool operator==(const crangeset &other) const
bool contains(T a, T b) const
#define planck_assert(testval, msg)
void append(const crangeset &other)