dune-common 2.9.0
Loading...
Searching...
No Matches
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// SPDX-FileCopyrightInfo: Copyright (C) DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
5#ifndef DUNE_BLOCK_BITFIELD_HH
6#define DUNE_BLOCK_BITFIELD_HH
7
12#include <vector>
13#include <bitset>
14#include <iostream>
15#include <algorithm>
16
20
21namespace Dune {
22
23 template <int block_size, class Alloc> class BitSetVector;
24 template <int block_size, class Alloc> class BitSetVectorReference;
25
36 template <int block_size, class Alloc>
38 {
39 protected:
40
42 friend class Dune::BitSetVector<block_size, Alloc>;
43
44 BitSetVectorConstReference(const BitSetVector& blockBitField_, int block_number_) :
45 blockBitField(blockBitField_),
46 block_number(block_number_)
47 {
48 DUNE_ASSERT_BOUNDS(blockBitField_.size() > static_cast<size_t>(block_number_));
49 }
50
53
54 public:
55
56 typedef std::bitset<block_size> bitset;
57
58 // bitset interface typedefs
59 typedef typename std::vector<bool, Alloc>::const_reference reference;
60 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
61 typedef size_t size_type;
62
65 {
66 bitset b = *this;
67 b <<= n;
68 return b;
69 }
70
73 {
74 bitset b = *this;
75 b >>= n;
76 return b;
77 }
78
81 {
82 bitset b = *this;
83 b.flip();
84 return b;
85 }
86
89 {
90 return block_size;
91 }
92
95 {
96 size_type n = 0;
97 for(size_type i=0; i<block_size; ++i)
98 n += getBit(i);
99 return n;
100 }
101
103 bool any() const
104 {
105 return count();
106 }
107
109 bool none() const
110 {
111 return ! any();
112 }
113
115 bool all() const
116 {
117 for(size_type i=0; i<block_size; ++i)
118 if(not test(i))
119 return false;
120 return true;
121 }
122
124 bool test(size_type n) const
125 {
126 return getBit(n);
127 }
128
131 {
132 return getBit(i);
133 }
134
136 operator bitset() const
137 {
138 return blockBitField.getRepr(block_number);
139 }
140
142 bool operator== (const bitset& bs) const
143 {
144 return equals(bs);
145 }
146
149 {
150 return equals(bs);
151 }
152
154 bool operator!= (const bitset& bs) const
155 {
156 return ! equals(bs);
157 }
158
161 {
162 return ! equals(bs);
163 }
164
171 friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
172 {
173 s << "(";
174 for(int i=0; i<block_size; ++i)
175 s << v[i];
176 s << ")";
177 return s;
178 }
179
180 protected:
183
185 {
186 return blockBitField.getBit(block_number,i);
187 }
188
189 template<class BS>
190 bool equals(const BS & bs) const
191 {
192 bool eq = true;
193 for(int i=0; i<block_size; ++i)
194 eq &= (getBit(i) == bs[i]);
195 return eq;
196 }
197
198 private:
203 void operator & () = delete;
204
205 friend class BitSetVectorReference<block_size, Alloc>;
206 };
207
220 template <int block_size, class Alloc>
221 class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
222 {
223 protected:
224
226 friend class Dune::BitSetVector<block_size, Alloc>;
227
229
230 BitSetVectorReference(BitSetVector& blockBitField_, int block_number_) :
231 BitSetVectorConstReference(blockBitField_, block_number_),
232 blockBitField(blockBitField_)
233 {}
234
235 public:
236 typedef std::bitset<block_size> bitset;
237
241 typedef typename std::vector<bool, Alloc>::reference reference;
243 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
245
247 typedef size_t size_type;
248
251 {
252 for(int i=0; i<block_size; ++i)
253 getBit(i) = b;
254 return (*this);
255 }
256
259 {
260 for(int i=0; i<block_size; ++i)
261 getBit(i) = b.test(i);
262 return (*this);
263 }
264
267 {
268 for(int i=0; i<block_size; ++i)
269 getBit(i) = b.test(i);
270 return (*this);
271 }
272
275 {
276 for(int i=0; i<block_size; ++i)
277 getBit(i) = b.test(i);
278 return (*this);
279 }
280
283 {
284 for (size_type i=0; i<block_size; i++)
285 getBit(i) = (test(i) & x.test(i));
286 return *this;
287 }
288
291 {
292 for (size_type i=0; i<block_size; i++)
293 getBit(i) = (test(i) & x.test(i));
294 return *this;
295 }
296
299 {
300 for (size_type i=0; i<block_size; i++)
301 getBit(i) = (test(i) | x.test(i));
302 return *this;
303 }
304
307 {
308 for (size_type i=0; i<block_size; i++)
309 getBit(i) = (test(i) | x.test(i));
310 return *this;
311 }
312
315 {
316 for (size_type i=0; i<block_size; i++)
317 getBit(i) = (test(i) ^ x.test(i));
318 return *this;
319 }
320
321 private:
322
323 // For some reason, the following variant of operator^= triggers an ICE or a hanging
324 // compiler on Debian 9 with GCC 6.3 and full optimizations enabled (-O3).
325 // The only way to reliably avoid the issue is by making sure that the compiler does not
326 // see the XOR in the context of the function, so here is a little helper that will normally
327 // be inlined, but not on the broken compiler. This incurs a substantial overhead (a function
328 // call), but until someone else has a better idea, it's the only way to make it work reliably.
329
330 static bool xor_helper(bool a, bool b)
331#if defined(__GNUC__) && ! defined(__clang__) && __GNUC__ == 6 && __GNUC_MINOR__ == 3 && __cplusplus \
332 == 201402L
333 __attribute__((noinline))
334#endif
335 ;
336
337 public:
338
341 {
342 // This uses the helper from above to hoist the actual XOR computation out of the function for
343 // the buggy version of GCC.
344 for (size_type i=0; i<block_size; i++)
345 getBit(i) = xor_helper(test(i),x.test(i));
346 return *this;
347 }
348
351 {
352 for (size_type i=0; i<block_size-n; i++)
353 getBit(i) = test(i+n);
354 return *this;
355 }
356
359 {
360 for (size_type i=0; i<block_size-n; i++)
361 getBit(i+n) = test(i);
362 return *this;
363 }
364
367 {
368 for (size_type i=0; i<block_size; i++)
369 set(i);
370 return *this;
371 }
372
375 {
376 for (size_type i=0; i<block_size; i++)
377 flip(i);
378 return *this;
379 }
380
383 {
384 *this = false;
385 return *this;
386 }
387
390 {
391 getBit(n) = val;
392 return *this;
393 }
394
397 {
398 set(n, false);
399 return *this;
400 }
401
404 {
405 getBit(n).flip();
406 return *this;
407 }
408
410 using BitSetVectorConstReference::operator[];
411
414 {
415 return getBit(i);
416 }
417
418 protected:
420
422
424 {
425 return blockBitField.getBit(this->block_number,i);
426 }
427 };
428
429 // implementation of helper - I put it into the template to avoid having
430 // to compile it in a dedicated compilation unit
431 template<int block_size, class Alloc>
432 bool BitSetVectorReference<block_size,Alloc>::xor_helper(bool a, bool b)
433 {
434 return a ^ b;
435 }
436
440 template<int block_size, class Alloc>
445
446 template<int block_size, class Alloc>
451
452 template<int block_size, class Alloc>
457
458 template<int block_size, class Alloc>
463
467 template <int block_size, class Allocator=std::allocator<bool> >
468 class BitSetVector : private std::vector<bool, Allocator>
469 {
471 typedef std::vector<bool, Allocator> BlocklessBaseClass;
472
473 public:
476
478 typedef std::bitset<block_size> value_type;
479
482
485
488
491
493 typedef typename std::vector<bool, Allocator>::size_type size_type;
494
496 typedef Allocator allocator_type;
498
504
507 return iterator(*this, 0);
508 }
509
512 return const_iterator(*this, 0);
513 }
514
517 return iterator(*this, size());
518 }
519
522 return const_iterator(*this, size());
523 }
524
527 BlocklessBaseClass()
528 {}
529
531 BitSetVector(const BlocklessBaseClass& blocklessBitField) :
532 BlocklessBaseClass(blocklessBitField)
533 {
534 if (blocklessBitField.size()%block_size != 0)
535 DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
536 }
537
541 explicit BitSetVector(int n) :
542 BlocklessBaseClass(n*block_size)
543 {}
544
546 BitSetVector(int n, bool v) :
547 BlocklessBaseClass(n*block_size,v)
548 {}
549
551 void clear()
552 {
553 BlocklessBaseClass::clear();
554 }
555
557 void resize(int n, bool v = bool())
558 {
559 BlocklessBaseClass::resize(n*block_size, v);
560 }
561
564 {
565 return BlocklessBaseClass::size()/block_size;
566 }
567
569 void setAll() {
570 this->assign(BlocklessBaseClass::size(), true);
571 }
572
574 void unsetAll() {
575 this->assign(BlocklessBaseClass::size(), false);
576 }
577
580 {
581 return reference(*this, i);
582 }
583
586 {
587 return const_reference(*this, i);
588 }
589
592 {
593 return reference(*this, size()-1);
594 }
595
598 {
599 return const_reference(*this, size()-1);
600 }
601
604 {
605 return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
606 }
607
610 {
611 size_type n = 0;
612 size_type blocks = size();
613 for(size_type i=0; i<blocks; ++i)
614 n += getBit(i,j);
615 return n;
616 }
617
619 friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
620 {
621 for (size_t i=0; i<v.size(); i++)
622 s << v[i] << " ";
623 return s;
624 }
625
626 private:
627
629 value_type getRepr(int i) const
630 {
631 value_type bits;
632 for(int j=0; j<block_size; ++j)
633 bits.set(j, getBit(i,j));
634 return bits;
635 }
636
637 typename std::vector<bool>::reference getBit(size_type i, size_type j) {
638 DUNE_ASSERT_BOUNDS(j < block_size);
640 return BlocklessBaseClass::operator[](i*block_size+j);
641 }
642
643 typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
644 DUNE_ASSERT_BOUNDS(j < block_size);
646 return BlocklessBaseClass::operator[](i*block_size+j);
647 }
648
649 friend class BitSetVectorReference<block_size,Allocator>;
650 friend class BitSetVectorConstReference<block_size,Allocator>;
651 };
652
653} // namespace Dune
654
655#endif
A few common exception classes.
Macro for wrapping boundary checks.
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:30
#define DUNE_THROW(E, m)
Definition exceptions.hh:218
Dune namespace.
Definition alignedallocator.hh:13
void assign(T &dst, const T &src, bool mask)
masked Simd assignment (scalar version)
Definition simd.hh:447
A dynamic array of blocks of booleans.
Definition bitsetvector.hh:469
const_reference operator[](int i) const
Return const reference to i-th block.
Definition bitsetvector.hh:585
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition bitsetvector.hh:506
BitSetVectorConstReference< block_size, Allocator > * const_pointer
Const pointer to a small block of bits.
Definition bitsetvector.hh:490
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition bitsetvector.hh:521
BitSetVectorReference< block_size, Allocator > reference
Reference to a small block of bits.
Definition bitsetvector.hh:481
size_type countmasked(int j) const
Returns the number of set bits, while each block is masked with 1<<i.
Definition bitsetvector.hh:609
BitSetVectorConstReference< block_size, Allocator > const_reference
Const reference to a small block of bits.
Definition bitsetvector.hh:484
iterator end()
Returns an iterator pointing to the end of the vector.
Definition bitsetvector.hh:516
size_type count() const
Returns the number of bits that are set.
Definition bitsetvector.hh:603
BitSetVector()
Default constructor.
Definition bitsetvector.hh:526
void setAll()
Sets all entries to true
Definition bitsetvector.hh:569
Dune::GenericIterator< const BitSetVector< block_size, Allocator >, const value_type, const_reference, std::ptrdiff_t, ForwardIteratorFacade > const_iterator
Definition bitsetvector.hh:502
std::bitset< block_size > value_type
Type of the values stored by the container.
Definition bitsetvector.hh:478
reference back()
Return reference to last block.
Definition bitsetvector.hh:591
BitSetVector(const BlocklessBaseClass &blocklessBitField)
Construction from an unblocked bitfield.
Definition bitsetvector.hh:531
friend std::ostream & operator<<(std::ostream &s, const BitSetVector &v)
Send bitfield to an output stream.
Definition bitsetvector.hh:619
const_reference back() const
Return const reference to last block.
Definition bitsetvector.hh:597
void clear()
Erases all of the elements.
Definition bitsetvector.hh:551
BitSetVectorReference< block_size, Allocator > * pointer
Pointer to a small block of bits.
Definition bitsetvector.hh:487
reference operator[](int i)
Return reference to i-th block.
Definition bitsetvector.hh:579
size_type size() const
Return the number of blocks.
Definition bitsetvector.hh:563
std::vector< bool, Allocator >::size_type size_type
size type
Definition bitsetvector.hh:493
BitSetVector(int n, bool v)
Constructor which initializes the field with true or false.
Definition bitsetvector.hh:546
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition bitsetvector.hh:511
Dune::GenericIterator< BitSetVector< block_size, Allocator >, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade > iterator
Definition bitsetvector.hh:501
void resize(int n, bool v=bool())
Resize field.
Definition bitsetvector.hh:557
Allocator allocator_type
The type of the allocator.
Definition bitsetvector.hh:496
BitSetVector(int n)
Definition bitsetvector.hh:541
void unsetAll()
Sets all entries to false
Definition bitsetvector.hh:574
A proxy class that acts as a mutable reference to a single bitset in a BitSetVector.
Definition bitsetvector.hh:222
bool test(size_type n) const
Returns true if bit n is set.
Definition bitsetvector.hh:124
BitSetVectorReference & operator=(const BitSetVectorConstReference &b)
Assignment from BitSetVectorConstReference.
Definition bitsetvector.hh:266
reference operator[](size_type i)
Return reference to the i-th bit.
Definition bitsetvector.hh:413
BitSetVectorReference & reset(size_type n)
Clears bit n.
Definition bitsetvector.hh:396
BitSetVectorReference & operator<<=(size_type n)
Left shift.
Definition bitsetvector.hh:350
Dune::BitSetVector< block_size, Alloc > BitSetVector
Definition bitsetvector.hh:225
std::vector< bool, Alloc >::const_reference const_reference
A proxy class that acts as a const reference to a single bit.
Definition bitsetvector.hh:243
BitSetVectorReference & operator=(const BitSetVectorReference &b)
Assignment from BitSetVectorReference.
Definition bitsetvector.hh:274
reference getBit(size_type i)
Definition bitsetvector.hh:423
BitSetVectorReference & operator&=(const BitSetVectorConstReference &x)
Bitwise and (for BitSetVectorConstReference and BitSetVectorReference)
Definition bitsetvector.hh:290
BitSetVectorReference(BitSetVector &blockBitField_, int block_number_)
Definition bitsetvector.hh:230
size_t size_type
size_type typedef (an unsigned integral type)
Definition bitsetvector.hh:247
BitSetVectorReference & operator=(const bitset &b)
Assignment from bitset.
Definition bitsetvector.hh:258
Dune::BitSetVectorConstReference< block_size, Alloc > BitSetVectorConstReference
Definition bitsetvector.hh:228
BitSetVectorReference & reset()
Clears every bit.
Definition bitsetvector.hh:382
BitSetVector & blockBitField
Definition bitsetvector.hh:419
BitSetVectorReference & operator|=(const BitSetVectorConstReference &x)
Bitwise inclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition bitsetvector.hh:306
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:389
std::bitset< block_size > bitset
Definition bitsetvector.hh:236
BitSetVectorReference & operator^=(const bitset &x)
Bitwise exclusive or (for bitset).
Definition bitsetvector.hh:314
std::vector< bool, Alloc >::reference reference
Definition bitsetvector.hh:241
BitSetVectorReference & operator|=(const bitset &x)
Bitwise inclusive or (for bitset)
Definition bitsetvector.hh:298
BitSetVectorReference & operator>>=(size_type n)
Right shift.
Definition bitsetvector.hh:358
BitSetVectorReference & operator^=(const BitSetVectorConstReference &x)
Bitwise exclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition bitsetvector.hh:340
BitSetVectorReference & flip(size_type n)
Flips bit n.
Definition bitsetvector.hh:403
BitSetVectorReference & flip()
Flips the value of every bit.
Definition bitsetvector.hh:374
BitSetVectorReference & set()
Sets every bit.
Definition bitsetvector.hh:366
BitSetVectorReference & operator&=(const bitset &x)
Bitwise and (for bitset).
Definition bitsetvector.hh:282
BitSetVectorReference & operator=(bool b)
Assignment from bool, sets each bit in the bitset to b.
Definition bitsetvector.hh:250
A proxy class that acts as a const reference to a single bitset in a BitSetVector.
Definition bitsetvector.hh:38
bool operator==(const bitset &bs) const
Equality of reference and std::bitset.
Definition bitsetvector.hh:142
bool test(size_type n) const
Returns true if bit n is set.
Definition bitsetvector.hh:124
const_reference operator[](size_type i) const
Return reference to the i-th bit.
Definition bitsetvector.hh:130
bitset operator<<(size_type n) const
Returns a copy of *this shifted left by n bits.
Definition bitsetvector.hh:64
BitSetVectorConstReference & operator=(const BitSetVectorConstReference &b)
hide assignment operator
BitSetVectorConstReference(const BitSetVector &blockBitField_, int block_number_)
Definition bitsetvector.hh:44
const BitSetVector & blockBitField
Definition bitsetvector.hh:181
bitset operator>>(size_type n) const
Returns a copy of *this shifted right by n bits.
Definition bitsetvector.hh:72
const_reference getBit(size_type i) const
Definition bitsetvector.hh:184
bool operator!=(const bitset &bs) const
Inequality of reference and std::bitset.
Definition bitsetvector.hh:154
bool equals(const BS &bs) const
Definition bitsetvector.hh:190
Dune::BitSetVector< block_size, Alloc > BitSetVector
Definition bitsetvector.hh:41
std::bitset< block_size > bitset
Definition bitsetvector.hh:56
bool all() const
Returns true if all bits are set.
Definition bitsetvector.hh:115
size_t size_type
Definition bitsetvector.hh:61
bitset operator~() const
Returns a copy of *this with all of its bits flipped.
Definition bitsetvector.hh:80
std::vector< bool, Alloc >::const_reference reference
Definition bitsetvector.hh:59
size_type size() const
Returns block_size.
Definition bitsetvector.hh:88
size_type count() const
Returns the number of bits that are set.
Definition bitsetvector.hh:94
bool none() const
Returns true if no bits are set.
Definition bitsetvector.hh:109
bool any() const
Returns true if any bits are set.
Definition bitsetvector.hh:103
int block_number
Definition bitsetvector.hh:182
std::vector< bool, Alloc >::const_reference const_reference
Definition bitsetvector.hh:60
friend std::ostream & operator<<(std::ostream &s, const BitSetVectorConstReference &v)
Definition bitsetvector.hh:171
BitSetVectorConstReference< block_size, Alloc > type
Definition bitsetvector.hh:443
BitSetVectorConstReference< block_size, Alloc > type
Definition bitsetvector.hh:449
BitSetVectorReference< block_size, Alloc > type
Definition bitsetvector.hh:455
BitSetVectorReference< block_size, Alloc > type
Definition bitsetvector.hh:461
Default exception class for range errors.
Definition exceptions.hh:254
Get the 'const' version of a reference to a mutable object.
Definition genericiterator.hh:87
get the 'mutable' version of a reference to a const object
Definition genericiterator.hh:116
Generic class for stl-conforming iterators for container classes with operator[].
Definition genericiterator.hh:153
Base class for stl conformant forward iterators.
Definition iteratorfacades.hh:141