LevelS C++ support library  3.50
rangeset.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 rangeset.h
26  * Class for storing sets of ranges of integer numbers
27  *
28  * Copyright (C) 2011-2017 Max-Planck-Society
29  * \author Martin Reinecke
30  */
31 
32 #ifndef PLANCK_RANGESET_H
33 #define PLANCK_RANGESET_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 /*! Class for storing sets of ranges of integer numbers */
44 template<typename T> class rangeset
45  {
46  private:
47  typedef std::vector<T> rtype;
48  typedef typename rtype::iterator iterator;
49  typedef typename rtype::const_iterator c_iterator;
50  rtype r;
51 
52  /*! Returns the index of the last number in \c r which is <= \a val.
53  If \a val is smaller than all numbers in \c r, returns -1. */
54  tdiff iiv (const T &val) const
55  { return tdiff(std::upper_bound(r.begin(),r.end(),val)-r.begin())-1; }
56 
57  void addRemove (T a, T b, tdiff v)
58  {
59  tdiff pos1=iiv(a), pos2=iiv(b);
60  if ((pos1>=0) && (r[pos1]==a)) --pos1;
61  // first to delete is at pos1+1; last is at pos2
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);
66 
67  planck_assert((rmend-rmstart)&1,"cannot happen");
68 
69  if (insert_a && insert_b && (pos1+1>pos2)) // insert
70  {
71  r.insert(r.begin()+pos1+1,2,a);
72  r[pos1+2]=b;
73  }
74  else
75  {
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);
79  }
80  }
81 
82  /*! Estimate a good strategy for set operations involving two rangesets. */
83  static int strategy (tsize sza, tsize szb)
84  {
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;
92  }
93 
94  void generalUnion1 (const rangeset &a, const rangeset &b,
95  bool flip_a, bool flip_b)
96  {
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;
100  while(runa||runb)
101  {
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; }
110  }
111  }
112  void generalUnion2 (const rangeset &a, const rangeset &b,
113  bool flip_a, bool flip_b)
114  {
115  tdiff iva = flip_a ? 0 : -1;
116  tdiff asz=tdiff(a.r.size()), bsz=tdiff(b.r.size());
117  while (iva<asz)
118  {
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]);
125  iva+=2;
126  }
127  }
128  void generalUnion (const rangeset &a, const rangeset &b,
129  bool flip_a, bool flip_b)
130  {
131  planck_assert((this!=&a)&&(this!=&b), "cannot overwrite the rangeset");
132  if (a.r.empty())
133  {
134  if (flip_a) clear(); else *this=b;
135  return;
136  }
137  if (b.r.empty())
138  {
139  if (flip_b) clear(); else *this=a;
140  return;
141  }
142 
143  clear();
144  int strat = strategy (a.nranges(), b.nranges());
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));
148  }
149  void generalXor (const rangeset &a, const rangeset &b)
150  {
151  clear();
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;
155  while(runa||runb)
156  {
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; }
165  }
166  }
167 
168  static bool generalAllOrNothing1 (const rangeset &a, const rangeset &b,
169  bool flip_a, bool flip_b)
170  {
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;
174  while(runa||runb)
175  {
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)
183  return false;
184  }
185  return true;
186  }
187  static bool generalAllOrNothing2 (const rangeset &a, const rangeset &b,
188  bool flip_a, bool flip_b)
189  {
190  tdiff iva = flip_a ? 0 : -1;
191  tdiff asz=tdiff(a.r.size()), bsz=tdiff(b.r.size());
192  while (iva<asz)
193  {
194  if (iva==-1) // implies that flip_a==false
195  { if ((!flip_b)||(b.r[0]<a.r[0])) return false; }
196  else if (iva==asz-1) // implies that flip_a==false
197  { if ((!flip_b)||(b.r[bsz-1]>a.r[asz-1])) return false; }
198  else
199  {
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;
203  }
204  iva+=2;
205  }
206  return true;
207  }
208  static bool generalAllOrNothing (const rangeset &a, const rangeset &b,
209  bool flip_a, bool flip_b)
210  {
211  if (a.r.empty())
212  return flip_a ? true : b.r.empty();
213  if (b.r.empty())
214  return flip_b ? true : a.r.empty();
215  int strat = strategy (a.nranges(), b.nranges());
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));
219  }
220 
221  public:
222  /*! Removes all rangeset entries. */
223  void clear() { r.clear(); }
224  /*! Reserves space for \a n ranges. */
225  void reserve(tsize n) { r.reserve(2*n); }
226  /*! Returns the current number of ranges. */
227  tsize nranges() const { return r.size()>>1; }
228  tsize size() const { return nranges(); }
229  bool empty() const { return r.empty(); }
230  /*! Returns the current vector of ranges. */
231  const rtype &data() const { return r; }
232  void checkConsistency() const
233  {
234  planck_assert((r.size()&1)==0,"invalid number of entries");
235  for (tsize i=1; i<r.size(); ++i)
236  planck_assert(r[i]>r[i-1],"inconsistent entries");
237  }
238  void setData (const rtype &inp)
239  {
240  r=inp;
241  checkConsistency();
242  }
243 
244  /*! Returns the first value of range \a i. */
245  const T &ivbegin (tdiff i) const { return r[2*i]; }
246  /*! Returns the one-past-last value of range \a i. */
247  const T &ivend (tdiff i) const { return r[2*i+1]; }
248  /*! Returns the length of range \a i. */
249  T ivlen (tdiff i) const { return r[2*i+1]-r[2*i]; }
250 
251  /*! Appends \a [v1;v2[ to the rangeset. \a v1 must be larger
252  than the minimum of the last range in the rangeset. */
253  void append(const T &v1, const T &v2)
254  {
255  if (v2<=v1) return;
256  if ((!r.empty()) && (v1<=r.back()))
257  {
258  planck_assert (v1>=r[r.size()-2],"bad append operation");
259  if (v2>r.back()) r.back()=v2;
260  }
261  else
262  { r.push_back(v1); r.push_back(v2); }
263  }
264  /*! Appends \a [v;v+1[ to the rangeset. \a v must be larger
265  than the minimum of the last range in the rangeset. */
266  void append(const T &v)
267  { append(v,v+1); }
268 
269  /*! Appends \a other to the rangeset. All values in \a other must be larger
270  than the minimum of the last range in the rangeset. */
271  void append (const rangeset &other)
272  {
273  for (tsize j=0; j<other.nranges(); ++j)
274  append(other.ivbegin(j),other.ivend(j));
275  }
276 
277  /*! After this operation, the rangeset contains the union of itself
278  with \a [v1;v2[. */
279  void add(const T &v1, const T &v2)
280  {
281  if (v2<=v1) return;
282  if (r.empty() || (v1>=r[r.size()-2])) append(v1,v2);
283  addRemove(v1,v2,1);
284  }
285  /*! After this operation, the rangeset contains the union of itself
286  with \a [v;v+1[. */
287  void add(const T &v) { add(v,v+1); }
288 
289  /*! Removes all values within \a [v1;v2[ from the rangeset. */
290  void remove(const T &v1, const T &v2)
291  {
292  if (v2<=v1) return;
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; }
296  addRemove(v1,v2,0);
297  }
298  /*! Removes the value \a v from the rangeset. */
299  void remove(const T &v) { remove(v,v+1); }
300 
301  /*! Removes all values not within \a [a;b[ from the rangeset. */
302  void intersect (const T &a, const T &b)
303  {
304  if (r.empty()) return; // nothing to remove
305  if ((b<=r[0]) || (a>=r.back())) { r.clear(); return; } // no overlap
306  if ((a<=r[0]) && (b>=r.back())) return; // full rangeset in interval
307 
308  tdiff pos2=iiv(b);
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);
313 
314  tdiff pos1=iiv(a);
315  bool insert_a = (pos1&1)==0;
316  if (insert_a) r[pos1--]=a;
317  if (pos1>=0)
318  r.erase(r.begin(),r.begin()+pos1+1);
319  }
320 
321  /*! Returns the total number of elements in the rangeset. */
322  T nval() const
323  {
324  T result=T(0);
325  for (tsize i=0; i<r.size(); i+=2)
326  result+=r[i+1]-r[i];
327  return result;
328  }
329 
330  /*! After this operation, \a res contains all elements of the rangeset
331  in ascending order. */
332  void toVector (std::vector<T> &res) const
333  {
334  res.clear();
335  res.reserve(nval());
336  for (tsize i=0; i<r.size(); i+=2)
337  for (T m(r[i]); m<r[i+1]; ++m)
338  res.push_back(m);
339  }
340 
341  /*! Returns a vector containing all elements of the rangeset in ascending
342  order. */
343  std::vector<T> toVector() const
344  {
345  std::vector<T> res;
346  toVector(res);
347  return res;
348  }
349 
350  /*! Returns the union of this rangeset and \a other. */
351  rangeset op_or (const rangeset &other) const
352  {
353  rangeset res;
354  res.generalUnion (*this,other,false,false);
355  return res;
356  }
357  /*! Returns the intersection of this rangeset and \a other. */
358  rangeset op_and (const rangeset &other) const
359  {
360  rangeset res;
361  res.generalUnion (*this,other,true,true);
362  return res;
363  }
364  /*! Returns the part of this rangeset which is not in \a other. */
365  rangeset op_andnot (const rangeset &other) const
366  {
367  rangeset res;
368  res.generalUnion (*this,other,true,false);
369  return res;
370  }
371  /*! Returns the parts of this rangeset and \a other, which are not in
372  both rangesets. */
373  rangeset op_xor (const rangeset &other) const
374  {
375  rangeset res;
376  res.generalXor (*this,other);
377  return res;
378  }
379 
380  /*! Returns the index of the interval containing \a v; if no such interval
381  exists, -1 is returned. */
382  tdiff findInterval (const T &v) const
383  {
384  tdiff res = iiv(v);
385  return (res&1) ? -1 : res>>1;
386  }
387 
388  /*! Returns \a true if the rangeset is identical to \a other, else \a false.
389  */
390  bool operator== (const rangeset &other) const
391  { return r==other.r; }
392 
393  /*! Returns \a true if the rangeset contains all values in the range
394  \a [a;b[, else \a false. */
395  bool contains (T a,T b) const
396  {
397  tdiff res=iiv(a);
398  if (res&1) return false;
399  return (b<=r[res+1]);
400  }
401  /*! Returns \a true if the rangeset contains the value \a v,
402  else \a false. */
403  bool contains (T v) const
404  { return !(iiv(v)&1); }
405  /*! Returns \a true if the rangeset contains all values stored in \a other,
406  else \a false. */
407  bool contains (const rangeset &other) const
408  { return generalAllOrNothing(*this,other,false,true); }
409  /** Returns true if any of the numbers [a;b[ are contained in the set,
410  else false. */
411  bool overlaps (T a,T b) const
412  {
413  tdiff res=iiv(a);
414  if ((res&1)==0) return true;
415  if (res==tdiff(r.size())-1) return false; // beyond the end of the set
416  return (r[res+1]<b);
417  }
418  /** Returns true if there is overlap between the set and "other",
419  else false. */
420  bool overlaps (const rangeset &other) const
421  { return !generalAllOrNothing(*this,other,true,true); }
422  };
423 
424 template<typename T> inline std::ostream &operator<< (std::ostream &os,
425  const rangeset<T> &rs)
426  {
427  os << "{ ";
428  for (tsize i=0; i<rs.nranges(); ++i)
429  os << "["<<rs.ivbegin(i)<<";"<<rs.ivend(i)<<"[ ";
430  return os << "}";
431  }
432 
433 #endif
T nval() const
Definition: rangeset.h:322
bool operator==(const rangeset &other) const
Definition: rangeset.h:390
bool contains(const rangeset &other) const
Definition: rangeset.h:407
void append(const T &v)
Definition: rangeset.h:266
void reserve(tsize n)
Definition: rangeset.h:225
bool contains(T a, T b) const
Definition: rangeset.h:395
void add(const T &v)
Definition: rangeset.h:287
T ivlen(tdiff i) const
Definition: rangeset.h:249
rangeset op_xor(const rangeset &other) const
Definition: rangeset.h:373
const rtype & data() const
Definition: rangeset.h:231
rangeset op_and(const rangeset &other) const
Definition: rangeset.h:358
std::ostream & operator<<(std::ostream &os, const pointing &p)
void toVector(std::vector< T > &res) const
Definition: rangeset.h:332
tsize nranges() const
Definition: rangeset.h:227
bool overlaps(const rangeset &other) const
Definition: rangeset.h:420
void intersect(const T &a, const T &b)
Definition: rangeset.h:302
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
std::vector< T > toVector() const
Definition: rangeset.h:343
bool contains(T v) const
Definition: rangeset.h:403
tdiff findInterval(const T &v) const
Definition: rangeset.h:382
bool overlaps(T a, T b) const
Definition: rangeset.h:411
void append(const T &v1, const T &v2)
Definition: rangeset.h:253
void add(const T &v1, const T &v2)
Definition: rangeset.h:279
rangeset op_or(const rangeset &other) const
Definition: rangeset.h:351
const T & ivbegin(tdiff i) const
Definition: rangeset.h:245
#define planck_assert(testval, msg)
void clear()
Definition: rangeset.h:223
void append(const rangeset &other)
Definition: rangeset.h:271
const T & ivend(tdiff i) const
Definition: rangeset.h:247
rangeset op_andnot(const rangeset &other) const
Definition: rangeset.h:365

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