Dune Core Modules (2.4.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
18namespace 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
41 BitSetVectorConstReference(const BitSetVector& blockBitField_, int block_number_) :
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
59 bitset operator<<(size_type n) const
60 {
61 bitset b = *this;
62 b <<= n;
63 return b;
64 }
65
67 bitset operator>>(size_type n) const
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:
166 const BitSetVector& blockBitField;
167 int block_number;
168
169 const_reference getBit(size_type i) const
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
215 BitSetVectorReference(BitSetVector& blockBitField_, int block_number_) :
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:
380 BitSetVector& blockBitField;
381
382 using BitSetVectorConstReference::getBit;
383
384 reference getBit(size_type i)
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 {
408 typedef BitSetVectorReference<block_size,Alloc> type;
409 };
410
411 template<int block_size, class Alloc>
412 struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
413 {
414 typedef BitSetVectorReference<block_size,Alloc> type;
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
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 {
506 BlocklessBaseClass::clear();
507 }
508
510 void resize(int n, bool v = bool())
511 {
512 BlocklessBaseClass::resize(n*block_size, v);
513 }
514
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
557 {
558 return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
559 }
560
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
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
A proxy class that acts as a const reference to a single bitset in a BitSetVector.
Definition: bitsetvector.hh:35
bool operator==(const bitset &bs) const
Equality of reference and std::bitset.
Definition: bitsetvector.hh:127
bool test(size_type n) const
Returns true if bit n is set.
Definition: bitsetvector.hh:110
bitset operator<<(size_type n) const
Returns a copy of *this shifted left by n bits.
Definition: bitsetvector.hh:59
BitSetVectorConstReference & operator=(const BitSetVectorConstReference &b)
hide assignment operator
bitset operator>>(size_type n) const
Returns a copy of *this shifted right by n bits.
Definition: bitsetvector.hh:67
bool operator!=(const bitset &bs) const
Inequality of reference and std::bitset.
Definition: bitsetvector.hh:139
bitset operator~() const
Returns a copy of *this with all of its bits flipped.
Definition: bitsetvector.hh:75
size_type size() const
Returns block_size.
Definition: bitsetvector.hh:83
size_type count() const
Returns the number of bits that are set.
Definition: bitsetvector.hh:89
bool none() const
Returns true if no bits are set.
Definition: bitsetvector.hh:104
bool any() const
Returns true if any bits are set.
Definition: bitsetvector.hh:98
A proxy class that acts as a mutable reference to a single bitset in a BitSetVector.
Definition: bitsetvector.hh:207
bool test(size_type n) const
Returns true if bit n is set.
Definition: bitsetvector.hh:110
BitSetVectorReference & operator=(const BitSetVectorConstReference &b)
Assignment from BitSetVectorConstReference.
Definition: bitsetvector.hh:251
BitSetVectorReference & reset(size_type n)
Clears bit n.
Definition: bitsetvector.hh:358
BitSetVectorReference & operator<<=(size_type n)
Left shift.
Definition: bitsetvector.hh:315
std::vector< bool, Alloc >::const_reference const_reference
A proxy class that acts as a const reference to a single bit.
Definition: bitsetvector.hh:228
BitSetVectorReference & operator=(const BitSetVectorReference &b)
Assignment from BitSetVectorReference.
Definition: bitsetvector.hh:259
BitSetVectorReference & operator&=(const BitSetVectorConstReference &x)
Bitwise and (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:275
size_t size_type
size_type typedef (an unsigned integral type)
Definition: bitsetvector.hh:232
BitSetVectorReference & operator=(const bitset &b)
Assignment from bitset.
Definition: bitsetvector.hh:243
BitSetVectorReference & reset()
Clears every bit.
Definition: bitsetvector.hh:347
BitSetVectorReference & operator|=(const BitSetVectorConstReference &x)
Bitwise inclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:291
BitSetVectorReference & set(size_type n, int val=1)
Sets bit n if val is nonzero, and clears bit n if val is zero.
Definition: bitsetvector.hh:351
BitSetVectorReference & operator^=(const bitset &x)
Bitwise exclusive or (for bitset).
Definition: bitsetvector.hh:299
std::vector< bool, Alloc >::reference reference
Definition: bitsetvector.hh:226
BitSetVectorReference & operator|=(const bitset &x)
Bitwise inclusive or (for bitset)
Definition: bitsetvector.hh:283
BitSetVectorReference & operator>>=(size_type n)
Right shift.
Definition: bitsetvector.hh:323
BitSetVectorReference & operator^=(const BitSetVectorConstReference &x)
Bitwise exclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:307
BitSetVectorReference & flip(size_type n)
Flips bit n.
Definition: bitsetvector.hh:365
BitSetVectorReference & flip()
Flips the value of every bit.
Definition: bitsetvector.hh:339
BitSetVectorReference & operator&=(const bitset &x)
Bitwise and (for bitset).
Definition: bitsetvector.hh:267
BitSetVectorReference & operator=(bool b)
Assignment from bool, sets each bit in the bitset to b.
Definition: bitsetvector.hh:235
A dynamic array of blocks of booleans.
Definition: bitsetvector.hh:422
const_reference operator[](int i) const
Return const reference to i-th block.
Definition: bitsetvector.hh:538
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:459
BitSetVectorConstReference< block_size, Allocator > * const_pointer
Const pointer to a small block of bits.
Definition: bitsetvector.hh:443
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition: bitsetvector.hh:474
BitSetVectorReference< block_size, Allocator > reference
Reference to a small block of bits.
Definition: bitsetvector.hh:434
size_type countmasked(int j) const
Returns the number of set bits, while each block is masked with 1<<i.
Definition: bitsetvector.hh:562
BitSetVectorConstReference< block_size, Allocator > const_reference
Const reference to a small block of bits.
Definition: bitsetvector.hh:437
iterator end()
Returns an iterator pointing to the end of the vector.
Definition: bitsetvector.hh:469
size_type count() const
Returns the number of bits that are set.
Definition: bitsetvector.hh:556
BitSetVector()
Default constructor.
Definition: bitsetvector.hh:479
void setAll()
Sets all entries to true
Definition: bitsetvector.hh:522
std::bitset< block_size > value_type
Type of the values stored by the container.
Definition: bitsetvector.hh:431
reference back()
Return reference to last block.
Definition: bitsetvector.hh:544
BitSetVector(const BlocklessBaseClass &blocklessBitField)
Construction from an unblocked bitfield.
Definition: bitsetvector.hh:484
friend std::ostream & operator<<(std::ostream &s, const BitSetVector &v)
Send bitfield to an output stream.
Definition: bitsetvector.hh:572
const_reference back() const
Return const reference to last block.
Definition: bitsetvector.hh:550
void clear()
Erases all of the elements.
Definition: bitsetvector.hh:504
BitSetVectorReference< block_size, Allocator > * pointer
Pointer to a small block of bits.
Definition: bitsetvector.hh:440
reference operator[](int i)
Return reference to i-th block.
Definition: bitsetvector.hh:532
size_type size() const
Return the number of blocks.
Definition: bitsetvector.hh:516
std::vector< bool, Allocator >::size_type size_type
size type
Definition: bitsetvector.hh:446
BitSetVector(int n, bool v)
Constructor which initializes the field with true or false.
Definition: bitsetvector.hh:499
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:464
Dune::GenericIterator< BitSetVector< block_size, Allocator >, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade > iterator
Definition: bitsetvector.hh:454
void resize(int n, bool v=bool())
Resize field.
Definition: bitsetvector.hh:510
Allocator allocator_type
The type of the allocator.
Definition: bitsetvector.hh:449
BitSetVector(int n)
Definition: bitsetvector.hh:494
void unsetAll()
Sets all entries to false
Definition: bitsetvector.hh:527
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:141
Generic class for stl-conforming iterators for container classes with operator[].
Definition: genericiterator.hh:151
Default exception class for range errors.
Definition: exceptions.hh:279
A few common exception classes.
Implements a generic iterator class for writing stl conformant iterators.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:243
bool eq(const T &first, const T &second, typename EpsilonType< T >::Type epsilon)
test for equality using epsilon
Definition: float_cmp.cc:118
Dune namespace.
Definition: alignment.hh:10
Get the 'const' version of a reference to a mutable object.
Definition: genericiterator.hh:85
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 21, 23:30, 2024)