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