LevelS C++ support library  3.50
crangeset.h
Go to the documentation of this file.
1 /*
2  * This file is part of libcxxsupport.
3  *
4  * libcxxsupport is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * libcxxsupport is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with libcxxsupport; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /*
20  * libcxxsupport is being developed at the Max-Planck-Institut fuer Astrophysik
21  * and financially supported by the Deutsches Zentrum fuer Luft- und Raumfahrt
22  * (DLR).
23  */
24 
25 /*! \file crangeset.h
26  * Class for storing sets of ranges of integer numbers
27  *
28  * Copyright (C) 2015 Max-Planck-Society
29  * \author Martin Reinecke
30  */
31 
32 #ifndef PLANCK_CRANGESET_H
33 #define PLANCK_CRANGESET_H
34 
35 #include <algorithm>
36 #include <vector>
37 #include <utility>
38 #include <iostream>
39 #include "datatypes.h"
40 #include "error_handling.h"
41 #include "math_utils.h"
42 
43 /*
44 compact rangeset (CRS)
45 
46 The underlying type T must be signed.
47 BUT: All "on" ranges must lie entirely in N_0.
48 
49 A nonnegative number indicates the start of an "on" range at this number.
50 A negative number indicates the start of an "off" range at the absolute value
51 of this number.
52 
53 All numbers r are sorted in a way that |r_i| < |r_{i+1}|.
54 
55 If two consecutive numbers are both nonnegative or negative, it means that the
56 interval between them contains in fact _two_ ranges: one of length 1 and the
57 other filling the remainder.
58 
59 Consequences:
60 
61 - The first number in CRS must be nonnegative
62 - numbers r_i and r_{i+1} in the CRS have the property
63  |r_{i+1}| > |r_i| + 1 (because of the special treatment of short intervals)
64 
65 Example:
66 The range set
67 [5;7[; [10;15[; [16;22[; [23;24[; [25;30[; [35;36[; [40;45[
68 
69 would be encoded as
70 5 -7 10 -15 -22 -24 -30 35 40 -45
71 */
72 
73 /*! Class for storing sets of ranges of integer numbers
74  T must be a signed integer type, but all numbers entered into the range set
75  must be nonnegative! */
76 template<typename T> class crangeset
77  {
78  private:
79  typedef std::vector<T> rtype;
80  rtype r;
81 
82  struct abscomp
83  {
84  bool operator()(const T &a, const T &b)
85  {
86  using namespace std;
87  return abs(a)<abs(b);
88  }
89  };
90 
91  class RsIter
92  {
93  private:
94  tsize idx;
95  bool extra;
96  const crangeset &ref;
97  T val;
98 
99  bool singleVal() const
100  {
101  if (idx==ref.r.size()-1)
102  return (ref.r[idx]>=0);
103  else
104  return ((ref.r[idx]^ref.r[idx+1])>=0);
105  }
106 
107  public:
108  RsIter(const crangeset &ref_) : idx(0), extra(false), ref(ref_), val(0)
109  {
110  using namespace std;
111  if (!atEnd())
112  val=abs(ref.r[0]);
113  }
114  bool atEnd() const { return idx>=ref.r.size(); }
115  T operator*() const
116  {
117  return val;
118  }
119  RsIter &operator++ ()
120  {
121  using namespace std;
122  if (extra)
123  {
124  ++idx;
125  extra=false;
126  if (!atEnd()) val=abs(ref.r[idx]);
127  }
128  else
129  {
130  if (singleVal())
131  {
132  extra=true;
133  ++val;
134  }
135  else
136  {
137  ++idx;
138  if (!atEnd()) val=abs(ref.r[idx]);
139  }
140  }
141  return *this;
142  }
143  void advance_up_to(T goal)
144  {
145  using namespace std;
146  tdiff idx2=ref.iiv(goal-1);
147  if (idx2>tdiff(idx))
148  {
149  idx=idx2;
150  extra=false;
151  val=abs(ref.r[idx]);
152  }
153  }
154  bool onoff() const
155  { return (ref.r[idx]>=0)^extra; }
156  };
157  public:
158  class IvIter
159  {
160  private:
161  RsIter rsi;
162  T b,e;
163 
164  public:
165  IvIter(const crangeset &ref_) : rsi(ref_)
166  {
167  if (rsi.atEnd()) return;
168  b=*rsi;
169  ++rsi;
170  e=*rsi;
171  }
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++ ()
177  {
178  ++rsi;
179  if (rsi.atEnd()) return *this;
180  b=*rsi;
181  ++rsi;
182  e=*rsi;
183  return *this;
184  }
185  };
186  class RsOutputIter
187  {
188  private:
189  T val;
190  bool val_set;
191  crangeset &ref;
192 
193  public:
194  RsOutputIter(crangeset &ref_) : val(T(0)), val_set(false), ref(ref_)
195  { ref.clear(); }
196  RsOutputIter &operator*() { return *this; }
197  RsOutputIter &operator++ () { return *this; }
198  RsOutputIter &operator++ (int) { return *this; }
199  RsOutputIter &operator= (const T &v)
200  {
201  if (val_set)
202  ref.append(val,v);
203  else
204  val=v;
205  val_set=!val_set;
206  return *this;
207  }
208  };
209  /*! Returns the index of the last number in \c r whose absolute value
210  is <= \a val
211  If \a val is smaller than all absolute values in \c r, returns -1. */
212  tdiff iiv (const T &val) const
213  {
214  return tdiff(std::upper_bound(r.begin(),r.end(),val,abscomp())
215  -r.begin())-1;
216  }
217 
218  /*! Estimate a good strategy for set operations involving two rangesets. */
219  static int strategy (tsize sza, tsize szb)
220  {
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;
228  }
229 
230  static crangeset generalUnion1 (const crangeset &a, const crangeset &b,
231  bool flip_a, bool flip_b)
232  {
233  crangeset res;
234  bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
235  RsIter ia(a), ib(b);
236  RsOutputIter io(res);
237  bool runa = !ia.atEnd(), runb = !ib.atEnd();
238  while(runa||runb)
239  {
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; }
248  }
249  return res;
250  }
251  static crangeset generalUnion2 (const crangeset &a, const crangeset &b,
252  bool flip_a, bool flip_b)
253  {
254  crangeset res;
255  bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
256  RsIter ia(a), ib(b);
257  RsOutputIter io(res);
258  bool runa = !ia.atEnd(), runb = !ib.atEnd();
259  while(runa||runb)
260  {
261  T va = runa ? *ia : T(0);
262  if (state_a && runb) // changes in b are irrelevant while state_a is true
263  {
264  if (!runa) break; // we are at the end
265  if (*ib<va)
266  {
267  ib.advance_up_to (va);
268  state_b=!(flip_b^ib.onoff());
269  }
270  }
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; }
278  }
279  return res;
280  }
281  static crangeset generalUnion (const crangeset &a, const crangeset &b,
282  bool flip_a, bool flip_b)
283  {
284  if (a.r.empty())
285  return flip_a ? crangeset() : b;
286  if (b.r.empty())
287  return flip_b ? crangeset() : a;
288 
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));
293  }
294  static crangeset generalXor (const crangeset &a, const crangeset &b)
295  {
296  crangeset res;
297  bool state_a=false, state_b=false, state_res=state_a||state_b;
298  RsIter ia(a), ib(b);
299  RsOutputIter io(res);
300  bool runa = !ia.atEnd(), runb = !ib.atEnd();
301  while(runa||runb)
302  {
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; }
311  }
312  return res;
313  }
314 
315  static bool generalAllOrNothing1 (const crangeset &a, const crangeset &b,
316  bool flip_a, bool flip_b)
317  {
318  bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
319  RsIter ia(a), ib(b);
320  bool runa = !ia.atEnd(), runb = !ib.atEnd();
321  while(runa||runb)
322  {
323  using namespace std;
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)
331  return false;
332  }
333  return true;
334  }
335  static bool generalAllOrNothing2 (const crangeset &a, const crangeset &b,
336  bool flip_a, bool flip_b)
337  {
338  bool state_a=flip_a, state_b=flip_b, state_res=state_a||state_b;
339  RsIter ia(a), ib(b);
340  bool runa = !ia.atEnd(), runb = !ib.atEnd();
341  while(runa||runb)
342  {
343  T va = runa ? *ia : T(0);
344  if (state_a && runb) // changes in b are irrelevant while state_a is true
345  {
346  if (!runa) break; // we are at the end
347  if (*ib<va)
348  {
349  ib.advance_up_to (va);
350  state_b=!(flip_b^ib.onoff());
351  }
352  }
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)
359  return false;
360  }
361  return true;
362  }
363 
364  static bool generalAllOrNothing (const crangeset &a, const crangeset &b,
365  bool flip_a, bool flip_b)
366  {
367  if (a.r.empty())
368  return flip_a ? true : b.r.empty();
369  if (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));
375  }
376  public:
377  /*! Removes all rangeset entries. */
378  void clear() { r.clear(); }
379  bool empty() const { return r.empty(); }
380  const rtype &data() const { return r; }
381  void checkConsistency() const
382  {
383  using namespace std;
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");
388  }
389  void setData (const rtype &inp)
390  {
391  r=inp;
392  checkConsistency();
393  }
394  /*! Appends \a [v1;v2[ to the rangeset. \a v1 must be larger
395  than the minimum of the last range in the rangeset. */
396  void append(const T &v1, const T &v2)
397  {
398  using namespace std;
399  if (v2<=v1) return;
400  T le = -100;
401  if (!empty())
402  le=(r.back()<0) ? -r.back() : r.back()+1;
403 
404  if (v1>le) // clean append
405  {
406  if ((v1>le+1)||(r.back()>0))
407  {
408  r.push_back(v1);
409  if (v2-v1>1) r.push_back(-v2);
410  }
411  else // short off interval
412  r.push_back(-v2);
413  return;
414  }
415  T lastbegin=-200;
416  if (!r.empty())
417  {
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];
421  }
422  planck_assert(v1>=lastbegin,"bad append operation");
423  // merge with the last interval
424  T endval=max(abs(r.back()),v2);
425  if (r.back()<0)
426  r.back()=-endval;
427  else
428  if (endval>r.back()+1) r.push_back(-endval);
429  }
430  /*! Appends \a [v;v+1[ to the rangeset. \a v must be larger
431  than the minimum of the last range in the rangeset. */
432  void append(const T &v)
433  { append(v,v+1); }
434 
435  /*! Appends \a other to the rangeset. All values in \a other must be larger
436  than the minimum of the last range in the rangeset. */
437  void append (const crangeset &other)
438  {
439  typename crangeset<T>::IvIter iter(other);
440  while (!iter.atEnd())
441  {
442  append(iter.ivbegin(),iter.ivend());
443  ++iter;
444  }
445  }
446  /*! Returns the total number of elements in the rangeset. */
447  T nval() const
448  {
449  T res=0;
450  typename crangeset<T>::IvIter iter(*this);
451  while (!iter.atEnd())
452  {res+=iter.ivlen(); ++iter;}
453  return res;
454  }
455 
456  crangeset op_or (const crangeset &other) const
457  { return generalUnion (*this,other,false,false); }
458  crangeset op_and (const crangeset &other) const
459  { return generalUnion (*this,other,true,true); }
460  crangeset op_andnot (const crangeset &other) const
461  { return generalUnion (*this,other,true,false); }
462  crangeset op_xor (const crangeset &other) const
463  { return generalXor (*this,other); }
464 
465  /*! Returns \a true if the rangeset is identical to \a other, else \a false.
466  */
467  bool operator== (const crangeset &other) const
468  { return r==other.r; }
469 
470  /*! Returns \a true if the rangeset contains all values in the range
471  \a [a;b[, else \a false. */
472  bool contains (T a,T b) const
473  {
474  tdiff res=iiv(a);
475  if (res<0) return false;
476  if (r[res]<0)
477  {
478  if (res==tdiff(r.size())-1) return false; // beyond end
479  if (r[res+1]>=0) return false; // long "off" range
480  return ((a>-r[res])&&(b<=-r[res+1])); // mixed range
481  }
482  // r[res]>=0
483  if ((res==tdiff(r.size())-1) || (r[res+1]>=0)) // short interval
484  return ((a==r[res])&&(b==a+1));
485  return b<=-r[res+1];
486  }
487  /*! Returns \a true if the rangeset contains the value \a v,
488  else \a false. */
489  bool contains (T v) const
490  {
491  tdiff res=iiv(v);
492  if (res<0) return false;
493  if (r[res]<0)
494  {
495  if (res==tdiff(r.size())-1) return false; // beyond end
496  if (r[res+1]>=0) return false; // long "off" range
497  return (v>-r[res]); // mixed range
498  }
499  if ((res<tdiff(r.size())-1) && (r[res+1]<0))
500  return true;
501  return (r[res]==v);
502  }
503  /*! Returns \a true if the rangeset contains all values stored in \a other,
504  else \a false. */
505  bool contains (const crangeset &other) const
506  { return generalAllOrNothing(*this,other,false,true); }
507 
508  /** Returns true if any of the numbers [a;b[ are contained in the set,
509  else false. */
510  bool overlaps (T a,T b) const
511  {
512  using namespace std;
513  if (empty()) return false;
514  tdiff res=iiv(a);
515  if (res<tdiff(r.size())-1)
516  if (b>abs(r[res+1])) return true; // at least one switch
517  // now we know that [a;b[ lies entirely inside an interval,
518  // but it may still contain a short sub-interval
519  if (res==-1) return false; // no sub-intervals in that one
520  if (res==tdiff(r.size())-1)
521  return a==r[res]; // only overlaps if r[res]>0 and a==abs(r[res])
522  // we are somewhere in the middle
523  if (r[res]>=0)
524  return (a==r[res]) || (r[res+1]<0);
525  return (r[res+1]<0) && (b>-r[res]+1);
526  }
527 
528  /** Returns true if there is overlap between the set and "other",
529  else false. */
530  bool overlaps (const crangeset &other) const
531  { return !generalAllOrNothing(*this,other,true,true); }
532  };
533 
534 template<typename T> inline std::ostream &operator<< (std::ostream &os,
535  const crangeset<T> &rs)
536  {
537  os << "{ ";
538  typename crangeset<T>::IvIter iter(rs);
539  while (!iter.atEnd())
540  {
541  os << "["<<iter.ivbegin()<<";"<<iter.ivend()<<"[ ";
542  ++iter;
543  }
544  return os << "}";
545  }
546 
547 #endif
void append(const T &v1, const T &v2)
Definition: crangeset.h:396
void append(const T &v)
Definition: crangeset.h:432
bool overlaps(T a, T b) const
Definition: crangeset.h:510
bool contains(const crangeset &other) const
Definition: crangeset.h:505
T nval() const
Definition: crangeset.h:447
void clear()
Definition: crangeset.h:378
static int strategy(tsize sza, tsize szb)
Definition: crangeset.h:219
std::size_t tsize
Definition: datatypes.h:116
int ilog2(I arg)
Definition: math_utils.h:125
std::ptrdiff_t tdiff
Definition: datatypes.h:118
bool overlaps(const crangeset &other) const
Definition: crangeset.h:530
tdiff iiv(const T &val) const
Definition: crangeset.h:212
bool operator==(const crangeset &other) const
Definition: crangeset.h:467
bool contains(T a, T b) const
Definition: crangeset.h:472
#define planck_assert(testval, msg)
void append(const crangeset &other)
Definition: crangeset.h:437
bool contains(T v) const
Definition: crangeset.h:489

Generated on Mon Dec 10 2018 10:24:20 for LevelS C++ support library