dune-common  2.3.1
bitsetvector.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 #ifndef DUNE_BLOCK_BITFIELD_HH
4 #define DUNE_BLOCK_BITFIELD_HH
5 
10 #include <vector>
11 #include <bitset>
12 #include <iostream>
13 #include <algorithm>
14 
17 
18 namespace Dune {
19 
20  template <int block_size, class Alloc> class BitSetVector;
21  template <int block_size, class Alloc> class BitSetVectorReference;
22 
33  template <int block_size, class Alloc>
35  {
36  protected:
37 
39  friend class Dune::BitSetVector<block_size, Alloc>;
40 
42  blockBitField(blockBitField),
43  block_number(block_number)
44  {};
45 
48 
49  public:
50 
51  typedef std::bitset<block_size> bitset;
52 
53  // bitset interface typedefs
54  typedef typename std::vector<bool, Alloc>::const_reference reference;
55  typedef typename std::vector<bool, Alloc>::const_reference const_reference;
56  typedef size_t size_type;
57 
60  {
61  bitset b = *this;
62  b <<= n;
63  return b;
64  }
65 
68  {
69  bitset b = *this;
70  b >>= n;
71  return b;
72  }
73 
75  bitset operator~() const
76  {
77  bitset b = *this;
78  b.flip();
79  return b;
80  }
81 
83  size_type size() const
84  {
85  return block_size;
86  }
87 
89  size_type count() const
90  {
91  size_type n = 0;
92  for(size_type i=0; i<block_size; ++i)
93  n += getBit(i);
94  return n;
95  }
96 
98  bool any() const
99  {
100  return count();
101  }
102 
104  bool none() const
105  {
106  return ! any();
107  }
108 
110  bool test(size_type n) const
111  {
112  return getBit(n);
113  }
114 
116  {
117  return getBit(i);
118  }
119 
121  operator bitset() const
122  {
123  return blockBitField.getRepr(block_number);
124  }
125 
127  bool operator== (const bitset& bs) const
128  {
129  return equals(bs);
130  }
131 
134  {
135  return equals(bs);
136  }
137 
139  bool operator!= (const bitset& bs) const
140  {
141  return ! equals(bs);
142  }
143 
146  {
147  return ! equals(bs);
148  }
149 
156  friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
157  {
158  s << "(";
159  for(int i=0; i<block_size; ++i)
160  s << v[i];
161  s << ")";
162  return s;
163  }
164 
165  protected:
168 
170  {
171  return blockBitField.getBit(block_number,i);
172  }
173 
174  template<class BS>
175  bool equals(const BS & bs) const
176  {
177  bool eq = true;
178  for(int i=0; i<block_size; ++i)
179  eq &= (getBit(i) == bs[i]);
180  return eq;
181  }
182 
183  private:
188  void operator & ();
189 
190  friend class BitSetVectorReference<block_size, Alloc>;
191  };
192 
205  template <int block_size, class Alloc>
206  class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
207  {
208  protected:
209 
211  friend class Dune::BitSetVector<block_size, Alloc>;
212 
214 
216  BitSetVectorConstReference(blockBitField, block_number),
217  blockBitField(blockBitField)
218  {};
219 
220  public:
221  typedef std::bitset<block_size> bitset;
222 
226  typedef typename std::vector<bool, Alloc>::reference reference;
228  typedef typename std::vector<bool, Alloc>::const_reference const_reference;
230 
232  typedef size_t size_type;
233 
236  {
237  for(int i=0; i<block_size; ++i)
238  getBit(i) = b;
239  return (*this);
240  }
241 
244  {
245  for(int i=0; i<block_size; ++i)
246  getBit(i) = b.test(i);
247  return (*this);
248  }
249 
252  {
253  for(int i=0; i<block_size; ++i)
254  getBit(i) = b.test(i);
255  return (*this);
256  }
257 
260  {
261  for(int i=0; i<block_size; ++i)
262  getBit(i) = b.test(i);
263  return (*this);
264  }
265 
268  {
269  for (size_type i=0; i<block_size; i++)
270  getBit(i) = (test(i) & x.test(i));
271  return *this;
272  }
273 
276  {
277  for (size_type i=0; i<block_size; i++)
278  getBit(i) = (test(i) & x.test(i));
279  return *this;
280  }
281 
284  {
285  for (size_type i=0; i<block_size; i++)
286  getBit(i) = (test(i) | x.test(i));
287  return *this;
288  }
289 
292  {
293  for (size_type i=0; i<block_size; i++)
294  getBit(i) = (test(i) | x.test(i));
295  return *this;
296  }
297 
300  {
301  for (size_type i=0; i<block_size; i++)
302  getBit(i) = (test(i) ^ x.test(i));
303  return *this;
304  }
305 
308  {
309  for (size_type i=0; i<block_size; i++)
310  getBit(i) = (test(i) ^ x.test(i));
311  return *this;
312  }
313 
316  {
317  for (size_type i=0; i<block_size-n; i++)
318  getBit(i) = test(i+n);
319  return *this;
320  }
321 
324  {
325  for (size_type i=0; i<block_size-n; i++)
326  getBit(i+n) = test(i);
327  return *this;
328  }
329 
330  // Sets every bit.
332  {
333  for (size_type i=0; i<block_size; i++)
334  set(i);
335  return *this;
336  }
337 
340  {
341  for (size_type i=0; i<block_size; i++)
342  flip(i);
343  return *this;
344  }
345 
348  {}
349 
351  BitSetVectorReference& set(size_type n, int val = 1)
352  {
353  getBit(n) = val;
354  return *this;
355  }
356 
359  {
360  set(n, false);
361  return *this;
362  }
363 
366  {
367  getBit(n).flip();
368  return *this;
369  }
370 
372  using BitSetVectorConstReference::operator[];
373 
375  {
376  return getBit(i);
377  }
378 
379  protected:
381 
383 
385  {
386  return blockBitField.getBit(this->block_number,i);
387  }
388  };
389 
393  template<int block_size, class Alloc>
394  struct const_reference< BitSetVectorReference<block_size,Alloc> >
395  {
397  };
398 
399  template<int block_size, class Alloc>
400  struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
401  {
403  };
404 
405  template<int block_size, class Alloc>
406  struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
407  {
409  };
410 
411  template<int block_size, class Alloc>
412  struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
413  {
415  };
416 
420  template <int block_size, class Allocator=std::allocator<bool> >
421  class BitSetVector : private std::vector<bool, Allocator>
422  {
424  typedef std::vector<bool, Allocator> BlocklessBaseClass;
425 
426  public:
429 
431  typedef std::bitset<block_size> value_type;
432 
435 
438 
441 
444 
446  typedef typename std::vector<bool, Allocator>::size_type size_type;
447 
449  typedef Allocator allocator_type;
451 
457 
460  return iterator(*this, 0);
461  }
462 
465  return const_iterator(*this, 0);
466  }
467 
470  return iterator(*this, size());
471  }
472 
474  const_iterator end() const {
475  return const_iterator(*this, size());
476  }
477 
480  BlocklessBaseClass()
481  {}
482 
484  BitSetVector(const BlocklessBaseClass& blocklessBitField) :
485  BlocklessBaseClass(blocklessBitField)
486  {
487  if (blocklessBitField.size()%block_size != 0)
488  DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
489  }
490 
494  explicit BitSetVector(int n) :
495  BlocklessBaseClass(n*block_size)
496  {}
497 
499  BitSetVector(int n, bool v) :
500  BlocklessBaseClass(n*block_size,v)
501  {}
502 
504  void clear()
505  {
507  }
508 
510  void resize(int n, bool v = bool())
511  {
512  BlocklessBaseClass::resize(n*block_size, v);
513  }
514 
516  size_type size() const
517  {
518  return BlocklessBaseClass::size()/block_size;
519  }
520 
522  void setAll() {
523  this->assign(BlocklessBaseClass::size(), true);
524  }
525 
527  void unsetAll() {
528  this->assign(BlocklessBaseClass::size(), false);
529  }
530 
533  {
534  return reference(*this, i);
535  }
536 
539  {
540  return const_reference(*this, i);
541  }
542 
545  {
546  return reference(*this, size()-1);
547  }
548 
551  {
552  return const_reference(*this, size()-1);
553  }
554 
556  size_type count() const
557  {
558  return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
559  }
560 
562  size_type countmasked(int j) const
563  {
564  size_type n = 0;
565  size_type blocks = size();
566  for(size_type i=0; i<blocks; ++i)
567  n += getBit(i,j);
568  return n;
569  }
570 
572  friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
573  {
574  for (size_t i=0; i<v.size(); i++)
575  s << v[i] << " ";
576  return s;
577  }
578 
579  private:
580 
581  // get a prepresentation as value_type
582  value_type getRepr(int i) const
583  {
584  value_type bits;
585  for(int j=0; j<block_size; ++j)
586  bits.set(j, getBit(i,j));
587  return bits;
588  }
589 
590  typename std::vector<bool>::reference getBit(size_type i, size_type j) {
591  return BlocklessBaseClass::operator[](i*block_size+j);
592  }
593 
594  typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
595  return BlocklessBaseClass::operator[](i*block_size+j);
596  }
597 
598  friend class BitSetVectorReference<block_size,Allocator>;
599  friend class BitSetVectorConstReference<block_size,Allocator>;
600  };
601 
602 } // namespace Dune
603 
604 #endif