Dune Core Modules (2.8.0)

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
18
19namespace Dune {
20
21 template <int block_size, class Alloc> class BitSetVector;
22 template <int block_size, class Alloc> class BitSetVectorReference;
23
34 template <int block_size, class Alloc>
36 {
37 protected:
38
40 friend class Dune::BitSetVector<block_size, Alloc>;
41
42 BitSetVectorConstReference(const BitSetVector& blockBitField_, int block_number_) :
43 blockBitField(blockBitField_),
44 block_number(block_number_)
45 {
46 DUNE_ASSERT_BOUNDS(blockBitField_.size() > static_cast<size_t>(block_number_));
47 }
48
51
52 public:
53
54 typedef std::bitset<block_size> bitset;
55
56 // bitset interface typedefs
57 typedef typename std::vector<bool, Alloc>::const_reference reference;
58 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
59 typedef size_t size_type;
60
62 bitset operator<<(size_type n) const
63 {
64 bitset b = *this;
65 b <<= n;
66 return b;
67 }
68
70 bitset operator>>(size_type n) const
71 {
72 bitset b = *this;
73 b >>= n;
74 return b;
75 }
76
78 bitset operator~() const
79 {
80 bitset b = *this;
81 b.flip();
82 return b;
83 }
84
86 size_type size() const
87 {
88 return block_size;
89 }
90
92 size_type count() const
93 {
94 size_type n = 0;
95 for(size_type i=0; i<block_size; ++i)
96 n += getBit(i);
97 return n;
98 }
99
101 bool any() const
102 {
103 return count();
104 }
105
107 bool none() const
108 {
109 return ! any();
110 }
111
113 bool all() const
114 {
115 for(size_type i=0; i<block_size; ++i)
116 if(not test(i))
117 return false;
118 return true;
119 }
120
122 bool test(size_type n) const
123 {
124 return getBit(n);
125 }
126
128 const_reference operator[](size_type i) const
129 {
130 return getBit(i);
131 }
132
134 operator bitset() const
135 {
136 return blockBitField.getRepr(block_number);
137 }
138
140 bool operator== (const bitset& bs) const
141 {
142 return equals(bs);
143 }
144
147 {
148 return equals(bs);
149 }
150
152 bool operator!= (const bitset& bs) const
153 {
154 return ! equals(bs);
155 }
156
159 {
160 return ! equals(bs);
161 }
162
169 friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
170 {
171 s << "(";
172 for(int i=0; i<block_size; ++i)
173 s << v[i];
174 s << ")";
175 return s;
176 }
177
178 protected:
179 const BitSetVector& blockBitField;
180 int block_number;
181
182 const_reference getBit(size_type i) const
183 {
184 return blockBitField.getBit(block_number,i);
185 }
186
187 template<class BS>
188 bool equals(const BS & bs) const
189 {
190 bool eq = true;
191 for(int i=0; i<block_size; ++i)
192 eq &= (getBit(i) == bs[i]);
193 return eq;
194 }
195
196 private:
201 void operator & () = delete;
202
203 friend class BitSetVectorReference<block_size, Alloc>;
204 };
205
218 template <int block_size, class Alloc>
219 class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
220 {
221 protected:
222
224 friend class Dune::BitSetVector<block_size, Alloc>;
225
227
228 BitSetVectorReference(BitSetVector& blockBitField_, int block_number_) :
229 BitSetVectorConstReference(blockBitField_, block_number_),
230 blockBitField(blockBitField_)
231 {}
232
233 public:
234 typedef std::bitset<block_size> bitset;
235
239 typedef typename std::vector<bool, Alloc>::reference reference;
241 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
243
245 typedef size_t size_type;
246
249 {
250 for(int i=0; i<block_size; ++i)
251 getBit(i) = b;
252 return (*this);
253 }
254
257 {
258 for(int i=0; i<block_size; ++i)
259 getBit(i) = b.test(i);
260 return (*this);
261 }
262
265 {
266 for(int i=0; i<block_size; ++i)
267 getBit(i) = b.test(i);
268 return (*this);
269 }
270
273 {
274 for(int i=0; i<block_size; ++i)
275 getBit(i) = b.test(i);
276 return (*this);
277 }
278
281 {
282 for (size_type i=0; i<block_size; i++)
283 getBit(i) = (test(i) & x.test(i));
284 return *this;
285 }
286
289 {
290 for (size_type i=0; i<block_size; i++)
291 getBit(i) = (test(i) & x.test(i));
292 return *this;
293 }
294
297 {
298 for (size_type i=0; i<block_size; i++)
299 getBit(i) = (test(i) | x.test(i));
300 return *this;
301 }
302
305 {
306 for (size_type i=0; i<block_size; i++)
307 getBit(i) = (test(i) | x.test(i));
308 return *this;
309 }
310
313 {
314 for (size_type i=0; i<block_size; i++)
315 getBit(i) = (test(i) ^ x.test(i));
316 return *this;
317 }
318
319 private:
320
321 // For some reason, the following variant of operator^= triggers an ICE or a hanging
322 // compiler on Debian 9 with GCC 6.3 and full optimizations enabled (-O3).
323 // The only way to reliably avoid the issue is by making sure that the compiler does not
324 // see the XOR in the context of the function, so here is a little helper that will normally
325 // be inlined, but not on the broken compiler. This incurs a substantial overhead (a function
326 // call), but until someone else has a better idea, it's the only way to make it work reliably.
327
328 static bool xor_helper(bool a, bool b)
329#if defined(__GNUC__) && ! defined(__clang__) && __GNUC__ == 6 && __GNUC_MINOR__ == 3 && __cplusplus \
330 == 201402L
331 __attribute__((noinline))
332#endif
333 ;
334
335 public:
336
339 {
340 // This uses the helper from above to hoist the actual XOR computation out of the function for
341 // the buggy version of GCC.
342 for (size_type i=0; i<block_size; i++)
343 getBit(i) = xor_helper(test(i),x.test(i));
344 return *this;
345 }
346
349 {
350 for (size_type i=0; i<block_size-n; i++)
351 getBit(i) = test(i+n);
352 return *this;
353 }
354
357 {
358 for (size_type i=0; i<block_size-n; i++)
359 getBit(i+n) = test(i);
360 return *this;
361 }
362
365 {
366 for (size_type i=0; i<block_size; i++)
367 set(i);
368 return *this;
369 }
370
373 {
374 for (size_type i=0; i<block_size; i++)
375 flip(i);
376 return *this;
377 }
378
381 {
382 *this = false;
383 return *this;
384 }
385
387 BitSetVectorReference& set(size_type n, int val = 1)
388 {
389 getBit(n) = val;
390 return *this;
391 }
392
395 {
396 set(n, false);
397 return *this;
398 }
399
402 {
403 getBit(n).flip();
404 return *this;
405 }
406
408 using BitSetVectorConstReference::operator[];
409
411 reference operator[](size_type i)
412 {
413 return getBit(i);
414 }
415
416 protected:
417 BitSetVector& blockBitField;
418
419 using BitSetVectorConstReference::getBit;
420
421 reference getBit(size_type i)
422 {
423 return blockBitField.getBit(this->block_number,i);
424 }
425 };
426
427 // implementation of helper - I put it into the template to avoid having
428 // to compile it in a dedicated compilation unit
429 template<int block_size, class Alloc>
430 bool BitSetVectorReference<block_size,Alloc>::xor_helper(bool a, bool b)
431 {
432 return a ^ b;
433 }
434
438 template<int block_size, class Alloc>
439 struct const_reference< BitSetVectorReference<block_size,Alloc> >
440 {
442 };
443
444 template<int block_size, class Alloc>
445 struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
446 {
448 };
449
450 template<int block_size, class Alloc>
451 struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
452 {
453 typedef BitSetVectorReference<block_size,Alloc> type;
454 };
455
456 template<int block_size, class Alloc>
457 struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
458 {
459 typedef BitSetVectorReference<block_size,Alloc> type;
460 };
461
465 template <int block_size, class Allocator=std::allocator<bool> >
466 class BitSetVector : private std::vector<bool, Allocator>
467 {
469 typedef std::vector<bool, Allocator> BlocklessBaseClass;
470
471 public:
474
476 typedef std::bitset<block_size> value_type;
477
480
483
486
489
491 typedef typename std::vector<bool, Allocator>::size_type size_type;
492
494 typedef Allocator allocator_type;
496
502
505 return iterator(*this, 0);
506 }
507
510 return const_iterator(*this, 0);
511 }
512
515 return iterator(*this, size());
516 }
517
520 return const_iterator(*this, size());
521 }
522
525 BlocklessBaseClass()
526 {}
527
529 BitSetVector(const BlocklessBaseClass& blocklessBitField) :
530 BlocklessBaseClass(blocklessBitField)
531 {
532 if (blocklessBitField.size()%block_size != 0)
533 DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
534 }
535
539 explicit BitSetVector(int n) :
540 BlocklessBaseClass(n*block_size)
541 {}
542
544 BitSetVector(int n, bool v) :
545 BlocklessBaseClass(n*block_size,v)
546 {}
547
549 void clear()
550 {
551 BlocklessBaseClass::clear();
552 }
553
555 void resize(int n, bool v = bool())
556 {
557 BlocklessBaseClass::resize(n*block_size, v);
558 }
559
562 {
563 return BlocklessBaseClass::size()/block_size;
564 }
565
567 void setAll() {
568 this->assign(BlocklessBaseClass::size(), true);
569 }
570
572 void unsetAll() {
573 this->assign(BlocklessBaseClass::size(), false);
574 }
575
578 {
579 return reference(*this, i);
580 }
581
584 {
585 return const_reference(*this, i);
586 }
587
590 {
591 return reference(*this, size()-1);
592 }
593
596 {
597 return const_reference(*this, size()-1);
598 }
599
602 {
603 return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
604 }
605
608 {
609 size_type n = 0;
610 size_type blocks = size();
611 for(size_type i=0; i<blocks; ++i)
612 n += getBit(i,j);
613 return n;
614 }
615
617 friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
618 {
619 for (size_t i=0; i<v.size(); i++)
620 s << v[i] << " ";
621 return s;
622 }
623
624 private:
625
627 value_type getRepr(int i) const
628 {
629 value_type bits;
630 for(int j=0; j<block_size; ++j)
631 bits.set(j, getBit(i,j));
632 return bits;
633 }
634
635 typename std::vector<bool>::reference getBit(size_type i, size_type j) {
636 DUNE_ASSERT_BOUNDS(j < block_size);
638 return BlocklessBaseClass::operator[](i*block_size+j);
639 }
640
641 typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
642 DUNE_ASSERT_BOUNDS(j < block_size);
644 return BlocklessBaseClass::operator[](i*block_size+j);
645 }
646
647 friend class BitSetVectorReference<block_size,Allocator>;
648 friend class BitSetVectorConstReference<block_size,Allocator>;
649 };
650
651} // namespace Dune
652
653#endif
Macro for wrapping boundary checks.
A proxy class that acts as a const reference to a single bitset in a BitSetVector.
Definition: bitsetvector.hh:36
bool operator==(const bitset &bs) const
Equality of reference and std::bitset.
Definition: bitsetvector.hh:140
bool test(size_type n) const
Returns true if bit n is set.
Definition: bitsetvector.hh:122
const_reference operator[](size_type i) const
Return reference to the i-th bit.
Definition: bitsetvector.hh:128
bitset operator<<(size_type n) const
Returns a copy of *this shifted left by n bits.
Definition: bitsetvector.hh:62
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:70
bool operator!=(const bitset &bs) const
Inequality of reference and std::bitset.
Definition: bitsetvector.hh:152
bool all() const
Returns true if all bits are set.
Definition: bitsetvector.hh:113
bitset operator~() const
Returns a copy of *this with all of its bits flipped.
Definition: bitsetvector.hh:78
size_type size() const
Returns block_size.
Definition: bitsetvector.hh:86
size_type count() const
Returns the number of bits that are set.
Definition: bitsetvector.hh:92
bool none() const
Returns true if no bits are set.
Definition: bitsetvector.hh:107
bool any() const
Returns true if any bits are set.
Definition: bitsetvector.hh:101
A proxy class that acts as a mutable reference to a single bitset in a BitSetVector.
Definition: bitsetvector.hh:220
bool test(size_type n) const
Returns true if bit n is set.
Definition: bitsetvector.hh:122
BitSetVectorReference & operator=(const BitSetVectorConstReference &b)
Assignment from BitSetVectorConstReference.
Definition: bitsetvector.hh:264
reference operator[](size_type i)
Return reference to the i-th bit.
Definition: bitsetvector.hh:411
BitSetVectorReference & reset(size_type n)
Clears bit n.
Definition: bitsetvector.hh:394
BitSetVectorReference & operator<<=(size_type n)
Left shift.
Definition: bitsetvector.hh:348
std::vector< bool, Alloc >::const_reference const_reference
A proxy class that acts as a const reference to a single bit.
Definition: bitsetvector.hh:241
BitSetVectorReference & operator=(const BitSetVectorReference &b)
Assignment from BitSetVectorReference.
Definition: bitsetvector.hh:272
BitSetVectorReference & operator&=(const BitSetVectorConstReference &x)
Bitwise and (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:288
size_t size_type
size_type typedef (an unsigned integral type)
Definition: bitsetvector.hh:245
BitSetVectorReference & operator=(const bitset &b)
Assignment from bitset.
Definition: bitsetvector.hh:256
BitSetVectorReference & reset()
Clears every bit.
Definition: bitsetvector.hh:380
BitSetVectorReference & operator|=(const BitSetVectorConstReference &x)
Bitwise inclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:304
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:387
BitSetVectorReference & operator^=(const bitset &x)
Bitwise exclusive or (for bitset).
Definition: bitsetvector.hh:312
std::vector< bool, Alloc >::reference reference
Definition: bitsetvector.hh:239
BitSetVectorReference & operator|=(const bitset &x)
Bitwise inclusive or (for bitset)
Definition: bitsetvector.hh:296
BitSetVectorReference & operator>>=(size_type n)
Right shift.
Definition: bitsetvector.hh:356
BitSetVectorReference & operator^=(const BitSetVectorConstReference &x)
Bitwise exclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:338
BitSetVectorReference & flip(size_type n)
Flips bit n.
Definition: bitsetvector.hh:401
BitSetVectorReference & flip()
Flips the value of every bit.
Definition: bitsetvector.hh:372
BitSetVectorReference & set()
Sets every bit.
Definition: bitsetvector.hh:364
BitSetVectorReference & operator&=(const bitset &x)
Bitwise and (for bitset).
Definition: bitsetvector.hh:280
BitSetVectorReference & operator=(bool b)
Assignment from bool, sets each bit in the bitset to b.
Definition: bitsetvector.hh:248
A dynamic array of blocks of booleans.
Definition: bitsetvector.hh:467
const_reference operator[](int i) const
Return const reference to i-th block.
Definition: bitsetvector.hh:583
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:504
BitSetVectorConstReference< block_size, Allocator > * const_pointer
Const pointer to a small block of bits.
Definition: bitsetvector.hh:488
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition: bitsetvector.hh:519
BitSetVectorReference< block_size, Allocator > reference
Reference to a small block of bits.
Definition: bitsetvector.hh:479
size_type countmasked(int j) const
Returns the number of set bits, while each block is masked with 1<<i.
Definition: bitsetvector.hh:607
BitSetVectorConstReference< block_size, Allocator > const_reference
Const reference to a small block of bits.
Definition: bitsetvector.hh:482
iterator end()
Returns an iterator pointing to the end of the vector.
Definition: bitsetvector.hh:514
size_type count() const
Returns the number of bits that are set.
Definition: bitsetvector.hh:601
BitSetVector()
Default constructor.
Definition: bitsetvector.hh:524
void setAll()
Sets all entries to true
Definition: bitsetvector.hh:567
std::bitset< block_size > value_type
Type of the values stored by the container.
Definition: bitsetvector.hh:476
reference back()
Return reference to last block.
Definition: bitsetvector.hh:589
BitSetVector(const BlocklessBaseClass &blocklessBitField)
Construction from an unblocked bitfield.
Definition: bitsetvector.hh:529
friend std::ostream & operator<<(std::ostream &s, const BitSetVector &v)
Send bitfield to an output stream.
Definition: bitsetvector.hh:617
const_reference back() const
Return const reference to last block.
Definition: bitsetvector.hh:595
void clear()
Erases all of the elements.
Definition: bitsetvector.hh:549
BitSetVectorReference< block_size, Allocator > * pointer
Pointer to a small block of bits.
Definition: bitsetvector.hh:485
reference operator[](int i)
Return reference to i-th block.
Definition: bitsetvector.hh:577
size_type size() const
Return the number of blocks.
Definition: bitsetvector.hh:561
std::vector< bool, Allocator >::size_type size_type
size type
Definition: bitsetvector.hh:491
BitSetVector(int n, bool v)
Constructor which initializes the field with true or false.
Definition: bitsetvector.hh:544
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:509
Dune::GenericIterator< BitSetVector< block_size, Allocator >, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade > iterator
Definition: bitsetvector.hh:499
void resize(int n, bool v=bool())
Resize field.
Definition: bitsetvector.hh:555
Allocator allocator_type
The type of the allocator.
Definition: bitsetvector.hh:494
BitSetVector(int n)
Definition: bitsetvector.hh:539
void unsetAll()
Sets all entries to false
Definition: bitsetvector.hh:572
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:139
Generic class for stl-conforming iterators for container classes with operator[].
Definition: genericiterator.hh:151
Default exception class for range errors.
Definition: exceptions.hh:252
A few common exception classes.
Implements a generic iterator class for writing stl conformant iterators.
#define DUNE_ASSERT_BOUNDS(cond)
If DUNE_CHECK_BOUNDS is defined: check if condition cond holds; otherwise, do nothing.
Definition: boundschecking.hh:28
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
bool eq(const T &first, const T &second, typename EpsilonType< T >::Type epsilon)
test for equality using epsilon
Definition: float_cmp.cc:142
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:400
Dune namespace.
Definition: alignedallocator.hh:11
void assign(T &dst, const T &src, bool mask)
masked Simd assignment (scalar version)
Definition: simd.hh:445
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 (Dec 22, 23:30, 2024)