GetFEM  5.4.4
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 <[email protected]>
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  bool operator>(const bit_reference& x) const
86  { return bool(*this) > bool(x); }
87  bool operator>=(const bit_reference& x) const
88  { return bool(*this) >= bool(x); }
89  void flip(void) { if (bool(*this)) *this = false; else *this = true; }
90  };
91 
92  struct APIDECL bit_iterator {
93  typedef bool value_type;
94  typedef bit_reference reference;
95  typedef bit_reference* pointer;
96  typedef size_t size_type;
97  typedef ptrdiff_t difference_type;
98  typedef std::random_access_iterator_tag iterator_category;
99 
100  size_type ind;
101  bit_support mask;
102  bit_container::iterator p;
103  bit_vector* bv;
104 
105  inline void bump_up()
106  { ind++; if (!(mask <<= 1)) { ++p; mask = 1;} }
107  inline void bump_down()
108  { ind--; if (!(mask >>= 1)) { --p; mask = 1; mask <<= WD_MASK; } }
109 
110  bit_iterator(void) {}
111  bit_iterator(bit_vector &b, size_type i);
112  reference operator*() const
113  { return reference(&(*p), mask, ind, bv); }
114  bit_iterator& operator++() { bump_up(); return *this; }
115  bit_iterator operator++(int)
116  { bit_iterator tmp=*this; bump_up(); return tmp; }
117  bit_iterator& operator--() { bump_down(); return *this; }
118  bit_iterator operator--(int)
119  { bit_iterator tmp = *this; bump_down(); return tmp; }
120  bit_iterator& operator+=(difference_type i);
121  bit_iterator& operator-=(difference_type i)
122  { *this += -i; return *this; }
123  bit_iterator operator+(difference_type i) const
124  { bit_iterator tmp = *this; return tmp += i; }
125  bit_iterator operator-(difference_type i) const
126  { bit_iterator tmp = *this; return tmp -= i; }
127  difference_type operator-(bit_iterator x) const { return ind - x.ind; }
128  reference operator[](difference_type i) { return *(*this + i); }
129  size_type index(void) const { return ind; }
130  bool operator==(const bit_iterator& x) const { return ind == x.ind; }
131  bool operator!=(const 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  bool operator>=(bit_iterator x) const { return ind >= x.ind; }
135  };
136 
137  struct APIDECL bit_const_iterator {
138  typedef bool value_type;
139  typedef bool reference;
140  typedef const bool* pointer;
141  typedef size_t size_type;
142  typedef ptrdiff_t difference_type;
143  typedef std::random_access_iterator_tag iterator_category;
144 
145  size_type ind;
146  bit_support mask;
147  bit_container::const_iterator p;
148  const bit_vector* bv;
149 
150  inline void bump_up()
151  { ind++; if (!(mask <<= 1)) { ++p; mask = 1;} }
152  inline void bump_down()
153  { ind--; if (!(mask >>= 1)) { --p; mask = 1; mask <<= WD_MASK; } }
154 
155  bit_const_iterator() {}
156  bit_const_iterator(const bit_vector &b, size_type i);
157  bit_const_iterator(const bit_iterator& x)
158  : ind(x.ind), mask(x.mask), p(x.p), bv(x.bv) {}
159  reference operator*() const { return (*p & mask) != 0; }
160  bit_const_iterator& operator++() { bump_up(); return *this; }
161  bit_const_iterator operator++(int)
162  { bit_const_iterator tmp = *this; bump_up(); return tmp; }
163  bit_const_iterator& operator--() { bump_down(); return *this; }
164  bit_const_iterator operator--(int)
165  { bit_const_iterator tmp = *this; bump_down(); return tmp; }
166  bit_const_iterator& operator+=(difference_type i);
167  bit_const_iterator& operator-=(difference_type i)
168  { *this += -i; return *this; }
169  bit_const_iterator operator+(difference_type i) const
170  { bit_const_iterator tmp = *this; return tmp += i; }
171  bit_const_iterator operator-(difference_type i) const
172  { bit_const_iterator tmp = *this; return tmp -= i; }
173  difference_type operator-(bit_const_iterator x) const { return ind-x.ind; }
174  reference operator[](difference_type i) { return *(*this + i); }
175  size_type index(void) const { return ind; }
176  bool operator==(const bit_const_iterator& x) const { return ind == x.ind; }
177  bool operator!=(const 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  bool operator>=(bit_const_iterator x) const { return ind >= x.ind; }
181  };
182 
183  ///Dynamic bit container.
184  class APIDECL bit_vector : public bit_container {
185  public :
186 
187  typedef bool value_type;
188  typedef size_t size_type;
189  typedef ptrdiff_t difference_type;
190  typedef bool const_reference;
191  typedef const bool* const_pointer;
192  typedef bit_reference reference;
193  typedef bit_reference* pointer;
194  typedef bit_iterator iterator;
195  typedef bit_const_iterator const_iterator;
196 
197  protected :
198 
199  mutable size_type ifirst_true, ilast_true;
200  mutable size_type ifirst_false, ilast_false;
201  mutable size_type icard;
202  mutable bool icard_valid;
203 
204  void fill_false(size_type i1, size_type i2);
205 
206  public :
207 
208  void change_for_true(size_type i) {
209  ifirst_true = std::min(ifirst_true, i);
210  ilast_true = std::max(ilast_true, i);
211  ++icard;
212  }
213  void change_for_false(size_type i) {
214  ifirst_false = std::min(ifirst_false, i);
215  ilast_false = std::max(ilast_false, i);
216  --icard;
217  }
218 
219  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
220  typedef std::reverse_iterator<iterator> reverse_iterator;
221  size_type size(void) const { return std::max(ilast_true, ilast_false)+1;}
222 
223  iterator begin(void) { return iterator(*this, 0); }
224  const_iterator begin(void) const { return const_iterator(*this, 0); }
225  iterator end(void) { return iterator(*this, size()); }
226  const_iterator end(void) const { return const_iterator(*this, size()); }
227 
228  reverse_iterator rbegin(void) { return reverse_iterator(end()); }
229  const_reverse_iterator rbegin(void) const
230  { return const_reverse_iterator(end()); }
231  reverse_iterator rend(void) { return reverse_iterator(begin()); }
232  const_reverse_iterator rend(void) const
233  { return const_reverse_iterator(begin()); }
234 
235  size_type capacity(void) const
236  { return bit_container::capacity() * WD_BIT; }
237  size_type max_size(void) const { return (size_type(-1)); }
238  // bool empty(void) const { return card() == 0; } /* ?? */
239  reference front(void) { return *begin(); }
240  const_reference front(void) const { return *begin(); }
241  reference back(void) { return *(end() - 1); }
242  const_reference back(void) const { return *(end() - 1); }
243 
244 
245  const_reference operator [](size_type ii) const
246  { return (ii >= size()) ? false : *const_iterator(*this, ii); }
247  reference operator [](size_type ii)
248  { if (ii >= size()) fill_false(size(),ii); return *iterator(*this, ii);}
249 
250  void swap(bit_vector &da);
251 
252  void clear(void) {
253  icard = 0; icard_valid = true;
254  ifirst_false = ilast_false = ifirst_true = ilast_true = 0;
255  fill_false(0,0);
256  }
257  void swap(size_type i1, size_type i2) {
258  if (i1 != i2) {
259  reference r1 = (*this)[i1], r2 = (*this)[i2];
260  bool tmp = r1; r1 = r2; r2 = tmp;
261  }
262  }
263  size_type memsize(void) const {
264  return bit_container::memsize() + sizeof(bit_vector)
265  - sizeof(bit_container);
266  }
267  size_type card(void) const;
268  /// index of first non-zero entry (size_type(-1) for an empty bit_vector)
269  size_type first_true(void) const;
270  /// index of first zero entry (size_type(0) for an empty bit_vector)
271  size_type first_false(void) const;
272  /// index of last non-zero entry (size_type(-1) for an empty bit_vector)
273  size_type last_true(void) const;
274  /// index of last zero entry (size_type(0) for an empty bit_vector)
275  size_type last_false(void) const;
276  /// remove all elements found in bv
277  bit_vector &setminus(const bit_vector &bv);
278  bit_vector &operator |=(const bit_vector &bv);
279  bit_vector &operator &=(const bit_vector &bv);
280 
281  bit_vector operator |(const bit_vector &bv) const
282  { bit_vector r(*this); r |= bv; return r; }
283  bit_vector operator &(const bit_vector &bv) const
284  { bit_vector r(*this); r &= bv; return r; }
285  bool operator ==(const bit_vector &bv) const;
286  bool operator !=(const bit_vector &bv) const
287  { return !((*this) == bv); }
288 
289  bit_vector(void) { clear(); }
290  template <size_t N> bit_vector(const std::bitset<N> &bs) {
291  clear();
292  for (size_type i=0; i < bs.size(); ++i) { if (bs[i]) add(i); }
293  }
294 
295  /// merges the integer values of the supplied container into the bit_vector
296  template <typename ICONT> dal::bit_vector& merge_from(const ICONT& c) {
297  for (typename ICONT::const_iterator it = c.begin(); it != c.end(); ++it)
298  add(*it);
299  return *this;
300  }
301  /** merges the integer values of the supplied iterator range into
302  * the bit_vector */
303  template <typename IT> dal::bit_vector& merge_from(IT b, IT e) {
304  while (b != e) { add(*b++); }
305  return *this;
306  }
307  /** return true if the supplied bit_vector is a subset of the current
308  * bit_vector */
309  bool contains(const dal::bit_vector &other) const;
310 
311  public :
312  /// return true if (*this)[i] == true
313  bool is_in(size_type i) const {
314  if (i < ifirst_true || i > ilast_true) return false;
315  else return (((*(const bit_container*)(this))[i / WD_BIT]) &
316  (bit_support(1) << (i & WD_MASK))) ? true : false; }
317  void add(size_type i) { (*this)[i] = true; }
318  /** set the interval [i .. i+nb-1] to true */
319  void add(size_type i, size_type nb);
320  void sup(size_type i) { (*this)[i] = false; } /* deprecated ...*/
321  void del(size_type i) { (*this)[i] = false; }
322  /** set the interval [i .. i+nb-1] to false */
323  void sup(size_type i, size_type nb); /* deprecated ...*/
324  void del(size_type i, size_type nb);
325  int first(void) const { return (card() == 0) ? -1 : int(first_true()); }
326  int last(void) const { return (card() == 0) ? -1 : int(last_true()); }
327  inline int take_first(void)
328  { int res = first(); if (res >= 0) sup(res); return res; }
329  inline int take_last(void)
330  { int res = last(); if (res >= 0) sup(res); return res; }
331  };
332 
333  /**
334  if you are only interested in indexes of true values of a bit_vector
335  (i.e. if you use it as an int set), use bv_visitor instead of
336  bit_vector::const_iterator (much faster)
337 
338  example:
339  @code
340  for (bv_visitor i(v); !i.finished(); ++i) {
341  .... (use i as an unsigned int)
342  }
343  @endcode
344  CAUTION: use bv_visitor_c instead of bv_visitor if the class bv_visitor
345  need to store a copy of the bit_vector
346  (if the original is destroyed just after the creation...)
347  */
348  class APIDECL bv_visitor {
349  typedef dal::bit_vector::size_type size_type;
350  bit_container::const_iterator it;
351  size_type ilast,ind;
352  bit_support v;
353  public:
354  bv_visitor(const dal::bit_vector& b) :
355  it(((const bit_container&)b).begin()+b.first()/WD_BIT),
356  ilast(b.last()+1), ind(b.first()), v(0) {
357  if (ind < ilast) { v = *it; v >>= (ind&WD_MASK); }
358  }
359  bool finished() const { return ind >= ilast; }
360  bool operator++();
361  operator size_type() const { return ind; }
362  };
363 
364  /**
365  bv_visitor with local copy of the bit_vector
366  */
367  class APIDECL bv_visitor_c {
368  bit_vector bv;
369  bv_visitor v; // no inheritance since v must be init after bv
370  public:
371  bv_visitor_c(const dal::bit_vector& b) : bv(b), v(bv) {}
372  bool finished() const { return v.finished(); }
373  bool operator++() { return ++v; }
374  operator dal::bit_vector::size_type() const
375  { return dal::bit_vector::size_type(v); }
376  };
377 
378  /// extract index of first entry in the bit_vector
379  inline int APIDECL &operator << (int &i, bit_vector &s)
380  { i = s.take_first(); return i; }
381  inline const int APIDECL &operator >> (const int &i, bit_vector &s)
382  { s.add(i); return i; }
383 
384  inline size_t APIDECL &operator << (size_t &i, bit_vector &s)
385  { i = s.take_first(); return i; }
386  inline const size_t &operator >> (const size_t &i, bit_vector &s)
387  { s.add(i); return i; }
388 
389  std::ostream APIDECL &operator <<(std::ostream &o, const bit_vector &s);
390 
391  /**Iterator class for bv_iterable and bv_iterable_c.*/
392  template<typename ITERABLE_BV>
393  class const_bv_iterator
394  {
395  typedef dal::bit_vector::size_type size_type;
396 
397  public:
398 
399  typedef std::forward_iterator_tag iterator_category;
400  typedef size_type value_type;
401  typedef size_type difference_type;
402  typedef size_type* pointer;
403  typedef size_type& reference;
404 
405  const_bv_iterator(const ITERABLE_BV* p_iterable, size_type pos)
406  : p_iterable_(const_cast<ITERABLE_BV*>(p_iterable)), pos_(pos)
407  {}
408 
409  bool operator!= (const const_bv_iterator &other) const{
410  return pos_ < other.pos_;
411  }
412 
413  size_type operator *() const{
414  return size_type(*p_iterable_);
415  }
416 
417  //difference of iterators
418  size_type operator-(const const_bv_iterator &other) const{
419  if (pos_ == other.pos_) return 0;
420 
421  auto &vector_this = p_iterable_->v_;
422  auto &vector_other = other.p_iterable_->v_;
423  bv_visitor v_this(vector_this), v_other(vector_other);
424  while (v_this < pos_) ++v_this;
425  while (v_other < other.pos_) ++v_other;
426  auto &v = (pos_ < other.pos_) ? v_this : v_other;
427  auto &v_end = (pos_ >= other.pos_) ? v_this : v_other;
428 
429  size_type count = 0;
430  while(v < v_end) { ++v; ++count;}
431  return count;
432  }
433 
434  const const_bv_iterator &operator++(){
435  ++*p_iterable_;
436  pos_ = *p_iterable_;
437  return *this;
438  }
439 
440  private:
441  ITERABLE_BV *p_iterable_;
442  size_type pos_;
443  };
444 
445 
446  /**
447  Wrapper class to make bit_vector iterable on true values.
448  It enables the use of c++11 range-based loop feature.
449  example:
450  @code
451  for (auto i : bv_iterable(bit_vector)) {
452  .... //(use i as an unsigned int)
453  }
454  */
455  class bv_iterable
456  {
457  public:
458  bv_iterable(const bit_vector &v) : v_(v), visitor_(v){}
459 
460  const_bv_iterator<bv_iterable> begin() const;
461  const_bv_iterator<bv_iterable> end() const;
462  inline bool operator++(){return ++visitor_;};
463  inline operator dal::bit_vector::size_type() const{return visitor_;};
464 
465  private:
466  const bit_vector& v_;
467  bv_visitor visitor_;
468  friend class const_bv_iterator<bv_iterable>;
469  };
470 
471  /***Same as bv_iterable class except the bit_vector is copied locally.*/
472  class bv_iterable_c
473  {
474  public:
475  bv_iterable_c(const bit_vector &v) : v_(v), visitor_(v_){}
476  const_bv_iterator<bv_iterable_c> begin() const;
477  const_bv_iterator<bv_iterable_c> end() const;
478  inline bool operator++(){return ++visitor_;};
479  inline operator dal::bit_vector::size_type() const{return visitor_;};
480 
481  private:
482  bit_vector v_;
483  bv_visitor visitor_;
484  friend class const_bv_iterator<bv_iterable_c>;
485  };
486 
487 }
488 
489 #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:59
gmm::add
void add(const L1 &l1, L2 &l2)
*‍/
Definition: gmm_blas.h:1276
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:756
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::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29