GetFEM  5.5
dal_bit_vector.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2026 Yves Renard
5 
6  This file is a part of GetFEM
7 
8  GetFEM is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program. If not, see https://www.gnu.org/licenses/.
19 
20  As a special exception, you may use this file as it is a part of a free
21  software library without restriction. Specifically, if other files
22  instantiate templates or use macros or inline functions from this file,
23  or you compile this file and link it with other files to produce an
24  executable, this file does not by itself cause the resulting executable
25  to be covered by the GNU Lesser General Public License. This exception
26  does not however invalidate any other reasons why the executable file
27  might be covered by the GNU Lesser General Public License.
28 
29 ===========================================================================*/
30 
31 
32 #ifndef DAL_BIT_VECTOR_H__
33 #define DAL_BIT_VECTOR_H__
34 
35 
36 /** @file dal_bit_vector.h
37  @author Yves Renard <[email protected]>
38  @date June 01, 1995.
39  @brief Provide a dynamic bit container.
40 
41  Provide a dynamic bit container, which can also be considered as a
42  set of integers.
43 
44  As a convention, the default value of a bit is false. The main
45  member functions are dal::bit_vector::is_in,
46  dal::bit_vector::add, dal::bit_vector::sup. Iterate over the
47  bit_vector with dal::bv_visitor
48 */
49 
50 #include "dal_basic.h"
51 #include <limits.h>
52 #include <bitset>
53 #include <iterator>
54 #include <algorithm>
55 
56 namespace dal {
57 
58  typedef unsigned int bit_support;
59  static const bit_support WD_BIT = bit_support(CHAR_BIT*sizeof(bit_support));
60  static const bit_support WD_MASK = WD_BIT - 1;
61  typedef dynamic_array<bit_support, 4> bit_container;
62 
63  class bit_vector;
64 
65  struct APIDECL bit_reference {
66  typedef size_t size_type;
67 
68  bit_support* p;
69  bit_support mask;
70  size_type ind;
71  bit_vector* bv;
72 
73  bit_reference(bit_support* x, bit_support m, size_type y, bit_vector* z)
74  { p = x; ind = y; bv = z; mask = m; }
75  bit_reference(void) {}
76  operator bool(void) const { return (*p & mask) != 0; }
77  bit_reference& operator = (bool x);
78  bit_reference& operator=(const bit_reference& x)
79  { return *this = bool(x); }
80  bool operator==(const bit_reference& x) const
81  { return bool(*this) == bool(x); }
82  bool operator<(const bit_reference& x) const
83  { return bool(*this) < bool(x); }
84  bool operator>(const bit_reference& x) const
85  { return bool(*this) > bool(x); }
86  bool operator>=(const bit_reference& x) const
87  { return bool(*this) >= bool(x); }
88  void flip(void) { if (bool(*this)) *this = false; else *this = true; }
89  };
90 
91  struct APIDECL bit_iterator {
92  typedef bool value_type;
93  typedef bit_reference reference;
94  typedef bit_reference* pointer;
95  typedef size_t size_type;
96  typedef ptrdiff_t difference_type;
97  typedef std::random_access_iterator_tag iterator_category;
98 
99  size_type ind;
100  bit_support mask;
101  bit_container::iterator p;
102  bit_vector* bv;
103 
104  inline void bump_up()
105  { ind++; if (!(mask <<= 1)) { ++p; mask = 1;} }
106  inline void bump_down()
107  { ind--; if (!(mask >>= 1)) { --p; mask = 1; mask <<= WD_MASK; } }
108 
109  bit_iterator(void) {}
110  bit_iterator(bit_vector &b, size_type i);
111  reference operator*() const
112  { return reference(&(*p), mask, ind, bv); }
113  bit_iterator& operator++() { bump_up(); return *this; }
114  bit_iterator operator++(int)
115  { bit_iterator tmp=*this; bump_up(); return tmp; }
116  bit_iterator& operator--() { bump_down(); return *this; }
117  bit_iterator operator--(int)
118  { bit_iterator tmp = *this; bump_down(); return tmp; }
119  bit_iterator& operator+=(difference_type i);
120  bit_iterator& operator-=(difference_type i)
121  { *this += -i; return *this; }
122  bit_iterator operator+(difference_type i) const
123  { bit_iterator tmp = *this; return tmp += i; }
124  bit_iterator operator-(difference_type i) const
125  { bit_iterator tmp = *this; return tmp -= i; }
126  difference_type operator-(bit_iterator x) const { return ind - x.ind; }
127  reference operator[](difference_type i) { return *(*this + i); }
128  size_type index(void) const { return ind; }
129  bool operator==(const bit_iterator& x) const { return ind == x.ind; }
130  bool operator!=(const bit_iterator& x) const { return ind != x.ind; }
131  bool operator<(bit_iterator x) const { return ind < x.ind; }
132  bool operator>(bit_iterator x) const { return ind > x.ind; }
133  bool operator>=(bit_iterator x) const { return ind >= x.ind; }
134  };
135 
136  struct APIDECL bit_const_iterator {
137  typedef bool value_type;
138  typedef bool reference;
139  typedef const bool* pointer;
140  typedef size_t size_type;
141  typedef ptrdiff_t difference_type;
142  typedef std::random_access_iterator_tag iterator_category;
143 
144  size_type ind;
145  bit_support mask;
146  bit_container::const_iterator p;
147  const bit_vector* bv;
148 
149  inline void bump_up()
150  { ind++; if (!(mask <<= 1)) { ++p; mask = 1;} }
151  inline void bump_down()
152  { ind--; if (!(mask >>= 1)) { --p; mask = 1; mask <<= WD_MASK; } }
153 
154  bit_const_iterator() {}
155  bit_const_iterator(const bit_vector &b, size_type i);
156  bit_const_iterator(const bit_iterator& x)
157  : ind(x.ind), mask(x.mask), p(x.p), bv(x.bv) {}
158  reference operator*() const { return (*p & mask) != 0; }
159  bit_const_iterator& operator++() { bump_up(); return *this; }
160  bit_const_iterator operator++(int)
161  { bit_const_iterator tmp = *this; bump_up(); return tmp; }
162  bit_const_iterator& operator--() { bump_down(); return *this; }
163  bit_const_iterator operator--(int)
164  { bit_const_iterator tmp = *this; bump_down(); return tmp; }
165  bit_const_iterator& operator+=(difference_type i);
166  bit_const_iterator& operator-=(difference_type i)
167  { *this += -i; return *this; }
168  bit_const_iterator operator+(difference_type i) const
169  { bit_const_iterator tmp = *this; return tmp += i; }
170  bit_const_iterator operator-(difference_type i) const
171  { bit_const_iterator tmp = *this; return tmp -= i; }
172  difference_type operator-(bit_const_iterator x) const { return ind-x.ind; }
173  reference operator[](difference_type i) { return *(*this + i); }
174  size_type index(void) const { return ind; }
175  bool operator==(const bit_const_iterator& x) const { return ind == x.ind; }
176  bool operator!=(const bit_const_iterator& x) const { return ind != x.ind; }
177  bool operator<(bit_const_iterator x) const { return ind < x.ind; }
178  bool operator>(bit_const_iterator x) const { return ind > x.ind; }
179  bool operator>=(bit_const_iterator x) const { return ind >= x.ind; }
180  };
181 
182  ///Dynamic bit container.
183  class APIDECL bit_vector : public bit_container {
184  public :
185 
186  typedef bool value_type;
187  typedef size_t size_type;
188  typedef ptrdiff_t difference_type;
189  typedef bool const_reference;
190  typedef const bool* const_pointer;
191  typedef bit_reference reference;
192  typedef bit_reference* pointer;
193  typedef bit_iterator iterator;
194  typedef bit_const_iterator const_iterator;
195 
196  protected :
197 
198  mutable size_type ifirst_true, ilast_true;
199  mutable size_type ifirst_false, ilast_false;
200  mutable size_type icard;
201  mutable bool icard_valid;
202 
203  void fill_false(size_type i1, size_type i2);
204 
205  public :
206 
207  void change_for_true(size_type i) {
208  ifirst_true = std::min(ifirst_true, i);
209  ilast_true = std::max(ilast_true, i);
210  ++icard;
211  }
212  void change_for_false(size_type i) {
213  ifirst_false = std::min(ifirst_false, i);
214  ilast_false = std::max(ilast_false, i);
215  --icard;
216  }
217 
218  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
219  typedef std::reverse_iterator<iterator> reverse_iterator;
220  size_type size(void) const { return std::max(ilast_true, ilast_false)+1;}
221 
222  iterator begin(void) { return iterator(*this, 0); }
223  const_iterator begin(void) const { return const_iterator(*this, 0); }
224  iterator end(void) { return iterator(*this, size()); }
225  const_iterator end(void) const { return const_iterator(*this, size()); }
226 
227  reverse_iterator rbegin(void) { return reverse_iterator(end()); }
228  const_reverse_iterator rbegin(void) const
229  { return const_reverse_iterator(end()); }
230  reverse_iterator rend(void) { return reverse_iterator(begin()); }
231  const_reverse_iterator rend(void) const
232  { return const_reverse_iterator(begin()); }
233 
234  size_type capacity(void) const
235  { return bit_container::capacity() * WD_BIT; }
236  size_type max_size(void) const { return (size_type(-1)); }
237  // bool empty(void) const { return card() == 0; } /* ?? */
238  reference front(void) { return *begin(); }
239  const_reference front(void) const { return *begin(); }
240  reference back(void) { return *(end() - 1); }
241  const_reference back(void) const { return *(end() - 1); }
242 
243 
244  const_reference operator [](size_type ii) const
245  { return (ii >= size()) ? false : *const_iterator(*this, ii); }
246  reference operator [](size_type ii)
247  { if (ii >= size()) fill_false(size(),ii); return *iterator(*this, ii);}
248 
249  void swap(bit_vector &da);
250 
251  void clear(void) {
252  icard = 0; icard_valid = true;
253  ifirst_false = ilast_false = ifirst_true = ilast_true = 0;
254  fill_false(0,0);
255  }
256  void swap(size_type i1, size_type i2) {
257  if (i1 != i2) {
258  reference r1 = (*this)[i1], r2 = (*this)[i2];
259  bool tmp = r1; r1 = r2; r2 = tmp;
260  }
261  }
262  size_type memsize(void) const {
263  return bit_container::memsize() + sizeof(bit_vector)
264  - sizeof(bit_container);
265  }
266  size_type card(void) const;
267  /// index of first non-zero entry (size_type(-1) for an empty bit_vector)
268  size_type first_true(void) const;
269  /// index of first zero entry (size_type(0) for an empty bit_vector)
270  size_type first_false(void) const;
271  /// index of last non-zero entry (size_type(-1) for an empty bit_vector)
272  size_type last_true(void) const;
273  /// index of last zero entry (size_type(0) for an empty bit_vector)
274  size_type last_false(void) const;
275  /// remove all elements found in bv
276  bit_vector &setminus(const bit_vector &bv);
277  bit_vector &operator |=(const bit_vector &bv);
278  bit_vector &operator &=(const bit_vector &bv);
279 
280  bit_vector operator |(const bit_vector &bv) const
281  { bit_vector r(*this); r |= bv; return r; }
282  bit_vector operator &(const bit_vector &bv) const
283  { bit_vector r(*this); r &= bv; return r; }
284  bool operator ==(const bit_vector &bv) const;
285  bool operator !=(const bit_vector &bv) const
286  { return !((*this) == bv); }
287 
288  bit_vector(void) { clear(); }
289  template <size_t N> bit_vector(const std::bitset<N> &bs) {
290  clear();
291  for (size_type i=0; i < bs.size(); ++i) { if (bs[i]) add(i); }
292  }
293 
294  /// merges the integer values of the supplied container into the bit_vector
295  template <typename ICONT> dal::bit_vector& merge_from(const ICONT& c) {
296  for (typename ICONT::const_iterator it = c.begin(); it != c.end(); ++it)
297  add(*it);
298  return *this;
299  }
300  /** merges the integer values of the supplied iterator range into
301  * the bit_vector */
302  template <typename IT> dal::bit_vector& merge_from(IT b, IT e) {
303  while (b != e) { add(*b++); }
304  return *this;
305  }
306  /** return true if the supplied bit_vector is a subset of the current
307  * bit_vector */
308  bool contains(const dal::bit_vector &other) const;
309 
310  public :
311  /// return true if (*this)[i] == true
312  bool is_in(size_type i) const {
313  if (i < ifirst_true || i > ilast_true) return false;
314  else return (((*(const bit_container*)(this))[i / WD_BIT]) &
315  (bit_support(1) << (i & WD_MASK))) ? true : false; }
316  void add(size_type i) { (*this)[i] = true; }
317  /** set the interval [i .. i+nb-1] to true */
318  void add(size_type i, size_type nb);
319  void sup(size_type i) { (*this)[i] = false; } /* deprecated ...*/
320  void del(size_type i) { (*this)[i] = false; }
321  /** set the interval [i .. i+nb-1] to false */
322  void sup(size_type i, size_type nb); /* deprecated ...*/
323  void del(size_type i, size_type nb);
324  int first(void) const { return (card() == 0) ? -1 : int(first_true()); }
325  int last(void) const { return (card() == 0) ? -1 : int(last_true()); }
326  inline int take_first(void)
327  { int res = first(); if (res >= 0) sup(res); return res; }
328  inline int take_last(void)
329  { int res = last(); if (res >= 0) sup(res); return res; }
330  };
331 
332  /**
333  if you are only interested in indexes of true values of a bit_vector
334  (i.e. if you use it as an int set), use bv_visitor instead of
335  bit_vector::const_iterator (much faster)
336 
337  example:
338  @code
339  for (bv_visitor i(v); !i.finished(); ++i) {
340  .... (use i as an unsigned int)
341  }
342  @endcode
343  CAUTION: use bv_visitor_c instead of bv_visitor if the class bv_visitor
344  need to store a copy of the bit_vector
345  (if the original is destroyed just after the creation...)
346  */
347  class APIDECL bv_visitor {
348  typedef dal::bit_vector::size_type size_type;
349  bit_container::const_iterator it;
350  size_type ilast,ind;
351  bit_support v;
352  public:
353  bv_visitor(const dal::bit_vector& b) :
354  it(((const bit_container&)b).begin()+b.first()/WD_BIT),
355  ilast(b.last()+1), ind(b.first()), v(0) {
356  if (ind < ilast) { v = *it; v >>= (ind&WD_MASK); }
357  }
358  bool finished() const { return ind >= ilast; }
359  bool operator++();
360  operator size_type() const { return ind; }
361  };
362 
363  /**
364  bv_visitor with local copy of the bit_vector
365  */
366  class APIDECL bv_visitor_c {
367  bit_vector bv;
368  bv_visitor v; // no inheritance since v must be init after bv
369  public:
370  bv_visitor_c(const dal::bit_vector& b) : bv(b), v(bv) {}
371  bool finished() const { return v.finished(); }
372  bool operator++() { return ++v; }
373  operator dal::bit_vector::size_type() const
374  { return dal::bit_vector::size_type(v); }
375  };
376 
377  /// extract index of first entry in the bit_vector
378  inline int APIDECL &operator << (int &i, bit_vector &s)
379  { i = s.take_first(); return i; }
380  inline const int APIDECL &operator >> (const int &i, bit_vector &s)
381  { s.add(i); return i; }
382 
383  inline size_t APIDECL &operator << (size_t &i, bit_vector &s)
384  { i = s.take_first(); return i; }
385  inline const size_t &operator >> (const size_t &i, bit_vector &s)
386  { s.add(i); return i; }
387 
388  std::ostream APIDECL &operator <<(std::ostream &o, const bit_vector &s);
389 
390  /**Iterator class for bv_iterable and bv_iterable_c.*/
391  template<typename ITERABLE_BV>
392  class const_bv_iterator
393  {
394  typedef dal::bit_vector::size_type size_type;
395 
396  public:
397 
398  typedef std::forward_iterator_tag iterator_category;
399  typedef size_type value_type;
400  typedef size_type difference_type;
401  typedef size_type* pointer;
402  typedef size_type& reference;
403 
404  const_bv_iterator(const ITERABLE_BV* p_iterable, size_type pos)
405  : p_iterable_(const_cast<ITERABLE_BV*>(p_iterable)), pos_(pos)
406  {}
407 
408  bool operator!= (const const_bv_iterator &other) const{
409  return pos_ < other.pos_;
410  }
411 
412  size_type operator *() const{
413  return size_type(*p_iterable_);
414  }
415 
416  //difference of iterators
417  size_type operator-(const const_bv_iterator &other) const{
418  if (pos_ == other.pos_) return 0;
419 
420  auto &vector_this = p_iterable_->v_;
421  auto &vector_other = other.p_iterable_->v_;
422  bv_visitor v_this(vector_this), v_other(vector_other);
423  while (v_this < pos_) ++v_this;
424  while (v_other < other.pos_) ++v_other;
425  auto &v = (pos_ < other.pos_) ? v_this : v_other;
426  auto &v_end = (pos_ >= other.pos_) ? v_this : v_other;
427 
428  size_type count = 0;
429  while(v < v_end) { ++v; ++count;}
430  return count;
431  }
432 
433  const const_bv_iterator &operator++(){
434  ++*p_iterable_;
435  pos_ = *p_iterable_;
436  return *this;
437  }
438 
439  private:
440  ITERABLE_BV *p_iterable_;
441  size_type pos_;
442  };
443 
444 
445  /**
446  Wrapper class to make bit_vector iterable on true values.
447  It enables the use of c++11 range-based loop feature.
448  example:
449  @code
450  for (auto i : bv_iterable(bit_vector)) {
451  .... //(use i as an unsigned int)
452  }
453  */
454  class bv_iterable
455  {
456  public:
457  bv_iterable(const bit_vector &v) : v_(v), visitor_(v){}
458 
459  const_bv_iterator<bv_iterable> begin() const;
460  const_bv_iterator<bv_iterable> end() const;
461  inline bool operator++(){return ++visitor_;};
462  inline operator dal::bit_vector::size_type() const{return visitor_;};
463 
464  private:
465  const bit_vector& v_;
466  bv_visitor visitor_;
467  friend class const_bv_iterator<bv_iterable>;
468  };
469 
470  /***Same as bv_iterable class except the bit_vector is copied locally.*/
471  class bv_iterable_c
472  {
473  public:
474  bv_iterable_c(const bit_vector &v) : v_(v), visitor_(v_){}
475  const_bv_iterator<bv_iterable_c> begin() const;
476  const_bv_iterator<bv_iterable_c> end() const;
477  inline bool operator++(){return ++visitor_;};
478  inline operator dal::bit_vector::size_type() const{return visitor_;};
479 
480  private:
481  bit_vector v_;
482  bv_visitor visitor_;
483  friend class const_bv_iterator<bv_iterable_c>;
484  };
485 
486 }
487 
488 #endif /* DAL_BIT_VECTOR_H__ */
dal_basic.h
Dynamic array class.
gmm::clear
void clear(L &l)
clear (fill with zeros) a vector or matrix.
Definition: gmm_blas.h:58
gmm::add
void add(const L1 &l1, L2 &l2)
*‍/
Definition: gmm_blas.h:1275
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:755
bgeot::operator+
rational_fraction< T > operator+(const polynomial< T > &P, const rational_fraction< T > &Q)
Add Q to P.
Definition: bgeot_poly.h:748
bgeot::operator==
bool operator==(const pconvex_structure &p1, const pconvex_structure &p2)
Stored objects must be compared by keys, because there is a possibility that they are duplicated in s...
Definition: bgeot_convex_structure.cc:110
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:48
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:28