dune-common  2.2.1
bitsetvector.hh
Go to the documentation of this file.
1 #ifndef DUNE_BLOCK_BITFIELD_HH
2 #define DUNE_BLOCK_BITFIELD_HH
3 
8 #include <vector>
9 #include <bitset>
10 #include <iostream>
11 #include <algorithm>
12 
15 
16 namespace Dune {
17 
18  template <int block_size, class Alloc> class BitSetVector;
19  template <int block_size, class Alloc> class BitSetVectorReference;
20 
31  template <int block_size, class Alloc>
33  {
34  protected:
35 
37  friend class Dune::BitSetVector<block_size, Alloc>;
38 
40  blockBitField(blockBitField),
41  block_number(block_number)
42  {};
43 
46 
47  public:
48 
49  typedef std::bitset<block_size> bitset;
50 
51  // bitset interface typedefs
52  typedef typename std::vector<bool, Alloc>::const_reference reference;
53  typedef typename std::vector<bool, Alloc>::const_reference const_reference;
54  typedef size_t size_type;
55 
58  {
59  bitset b = *this;
60  b <<= n;
61  return b;
62  }
63 
66  {
67  bitset b = *this;
68  b >>= n;
69  return b;
70  }
71 
73  bitset operator~() const
74  {
75  bitset b = *this;
76  b.flip();
77  return b;
78  }
79 
81  size_type size() const
82  {
83  return block_size;
84  }
85 
87  size_type count() const
88  {
89  size_type n = 0;
90  for(size_type i=0; i<block_size; ++i)
91  n += getBit(i);
92  return n;
93  }
94 
96  bool any() const
97  {
98  return count();
99  }
100 
102  bool none() const
103  {
104  return ! any();
105  }
106 
108  bool test(size_type n) const
109  {
110  return getBit(n);
111  }
112 
114  {
115  return getBit(i);
116  }
117 
119  operator bitset() const
120  {
121  return blockBitField.getRepr(block_number);
122  }
123 
125  bool operator== (const bitset& bs) const
126  {
127  return equals(bs);
128  }
129 
132  {
133  return equals(bs);
134  }
135 
137  bool operator!= (const bitset& bs) const
138  {
139  return ! equals(bs);
140  }
141 
144  {
145  return ! equals(bs);
146  }
147 
154  friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
155  {
156  s << "(";
157  for(int i=0; i<block_size; ++i)
158  s << v[i];
159  s << ")";
160  return s;
161  }
162 
163  protected:
166 
168  {
169  return blockBitField.getBit(block_number,i);
170  }
171 
172  template<class BS>
173  bool equals(const BS & bs) const
174  {
175  bool eq = true;
176  for(int i=0; i<block_size; ++i)
177  eq &= (getBit(i) == bs[i]);
178  return eq;
179  }
180 
181  private:
186  void operator & ();
187 
188  friend class BitSetVectorReference<block_size, Alloc>;
189  };
190 
203  template <int block_size, class Alloc>
204  class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
205  {
206  protected:
207 
209  friend class Dune::BitSetVector<block_size, Alloc>;
210 
212 
214  BitSetVectorConstReference(blockBitField, block_number),
215  blockBitField(blockBitField)
216  {};
217 
218  public:
219  typedef std::bitset<block_size> bitset;
220 
224  typedef typename std::vector<bool, Alloc>::reference reference;
226  typedef typename std::vector<bool, Alloc>::const_reference const_reference;
228 
230  typedef size_t size_type;
231 
234  {
235  for(int i=0; i<block_size; ++i)
236  getBit(i) = b;
237  return (*this);
238  }
239 
242  {
243  for(int i=0; i<block_size; ++i)
244  getBit(i) = b.test(i);
245  return (*this);
246  }
247 
250  {
251  for(int i=0; i<block_size; ++i)
252  getBit(i) = b.test(i);
253  return (*this);
254  }
255 
258  {
259  for(int i=0; i<block_size; ++i)
260  getBit(i) = b.test(i);
261  return (*this);
262  }
263 
266  {
267  for (size_type i=0; i<block_size; i++)
268  getBit(i) = (test(i) & x.test(i));
269  return *this;
270  }
271 
274  {
275  for (size_type i=0; i<block_size; i++)
276  getBit(i) = (test(i) & x.test(i));
277  return *this;
278  }
279 
282  {
283  for (size_type i=0; i<block_size; i++)
284  getBit(i) = (test(i) | x.test(i));
285  return *this;
286  }
287 
290  {
291  for (size_type i=0; i<block_size; i++)
292  getBit(i) = (test(i) | x.test(i));
293  return *this;
294  }
295 
298  {
299  for (size_type i=0; i<block_size; i++)
300  getBit(i) = (test(i) ^ x.test(i));
301  return *this;
302  }
303 
306  {
307  for (size_type i=0; i<block_size; i++)
308  getBit(i) = (test(i) ^ x.test(i));
309  return *this;
310  }
311 
314  {
315  for (size_type i=0; i<block_size-n; i++)
316  getBit(i) = test(i+n);
317  return *this;
318  }
319 
322  {
323  for (size_type i=0; i<block_size-n; i++)
324  getBit(i+n) = test(i);
325  return *this;
326  }
327 
328  // Sets every bit.
330  {
331  for (size_type i=0; i<block_size; i++)
332  set(i);
333  return *this;
334  }
335 
338  {
339  for (size_type i=0; i<block_size; i++)
340  flip(i);
341  return *this;
342  }
343 
346  {
347  }
348 
350  BitSetVectorReference& set(size_type n, int val = 1)
351  {
352  getBit(n) = val;
353  return *this;
354  }
355 
358  {
359  set(n, false);
360  return *this;
361  }
362 
365  {
366  getBit(n).flip();
367  return *this;
368  }
369 
371  using BitSetVectorConstReference::operator[];
372 
374  {
375  return getBit(i);
376  }
377 
378  protected:
380 
382 
384  {
385  return blockBitField.getBit(this->block_number,i);
386  }
387  };
388 
392  template<int block_size, class Alloc>
393  struct const_reference< BitSetVectorReference<block_size,Alloc> >
394  {
396  };
397 
398  template<int block_size, class Alloc>
399  struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
400  {
402  };
403 
404  template<int block_size, class Alloc>
405  struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
406  {
408  };
409 
410  template<int block_size, class Alloc>
411  struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
412  {
414  };
415 
419  template <int block_size, class Allocator=std::allocator<bool> >
420  class BitSetVector : private std::vector<bool, Allocator>
421  {
423  typedef std::vector<bool, Allocator> BlocklessBaseClass;
424 
425  public:
428 
430  typedef std::bitset<block_size> value_type;
431 
434 
437 
440 
443 
445  typedef typename std::vector<bool, Allocator>::size_type size_type;
446 
448  typedef Allocator allocator_type;
450 
456 
459  return iterator(*this, 0);
460  }
461 
464  return const_iterator(*this, 0);
465  }
466 
469  return iterator(*this, size());
470  }
471 
473  const_iterator end() const{
474  return const_iterator(*this, size());
475  }
476 
479  BlocklessBaseClass()
480  {}
481 
483  BitSetVector(const BlocklessBaseClass& blocklessBitField) :
484  BlocklessBaseClass(blocklessBitField)
485  {
486  if (blocklessBitField.size()%block_size != 0)
487  DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
488  }
489 
493  explicit BitSetVector(int n) :
494  BlocklessBaseClass(n*block_size)
495  {}
496 
498  BitSetVector(int n, bool v) :
499  BlocklessBaseClass(n*block_size,v)
500  {}
501 
503  void clear()
504  {
506  }
507 
509  void resize(int n, bool v = bool())
510  {
511  BlocklessBaseClass::resize(n*block_size, v);
512  }
513 
515  size_type size() const
516  {
517  return BlocklessBaseClass::size()/block_size;
518  }
519 
521  void setAll() {
522  this->assign(BlocklessBaseClass::size(), true);
523  }
524 
526  void unsetAll() {
527  this->assign(BlocklessBaseClass::size(), false);
528  }
529 
532  {
533  return reference(*this, i);
534  }
535 
538  {
539  return const_reference(*this, i);
540  }
541 
544  {
545  return reference(*this, size()-1);
546  }
547 
550  {
551  return const_reference(*this, size()-1);
552  }
553 
555  size_type count() const
556  {
557  return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
558  }
559 
561  size_type countmasked(int j) const
562  {
563  size_type n = 0;
564  size_type blocks = size();
565  for(size_type i=0; i<blocks; ++i)
566  n += getBit(i,j);
567  return n;
568  }
569 
571  friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
572  {
573  for (size_t i=0; i<v.size(); i++)
574  s << v[i] << " ";
575  return s;
576  }
577 
578  private:
579 
580  // get a prepresentation as value_type
581  value_type getRepr(int i) const
582  {
583  value_type bits;
584  for(int j=0; j<block_size; ++j)
585  bits.set(j, getBit(i,j));
586  return bits;
587  }
588 
589  typename std::vector<bool>::reference getBit(size_type i, size_type j) {
590  return BlocklessBaseClass::operator[](i*block_size+j);
591  }
592 
593  typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
594  return BlocklessBaseClass::operator[](i*block_size+j);
595  }
596 
597  friend class BitSetVectorReference<block_size,Allocator>;
598  friend class BitSetVectorConstReference<block_size,Allocator>;
599  };
600 
601 } // namespace Dune
602 
603 #endif