DUNE-FEM (unstable)

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 © 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
64 bitset operator<<(size_type n) const
65 {
66 bitset b = *this;
67 b <<= n;
68 return b;
69 }
70
72 bitset operator>>(size_type n) const
73 {
74 bitset b = *this;
75 b >>= n;
76 return b;
77 }
78
80 bitset operator~() const
81 {
82 bitset b = *this;
83 b.flip();
84 return b;
85 }
86
88 size_type size() const
89 {
90 return block_size;
91 }
92
94 size_type count() const
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
130 const_reference operator[](size_type i) const
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:
181 const BitSetVector& blockBitField;
182 int block_number;
183
184 const_reference getBit(size_type i) const
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 return (*this) = bitset(*this) & x;
285 }
286
289 {
290 return (*this) &= bitset(x);
291 }
292
295 {
296 return (*this) = bitset(*this) | x;
297 }
298
301 {
302 return (*this) |= bitset(x);
303 }
304
307 {
308 return (*this) = bitset(*this) ^ x;
309 }
310
313 {
314 return (*this) ^= bitset(x);
315 }
316
319 {
320 return (*this) = bitset(*this) << n;
321 }
322
325 {
326 return (*this) = bitset(*this) >> n;
327 }
328
331 {
332 for (size_type i=0; i<block_size; i++)
333 set(i);
334 return *this;
335 }
336
339 {
340 for (size_type i=0; i<block_size; i++)
341 flip(i);
342 return *this;
343 }
344
347 {
348 *this = false;
349 return *this;
350 }
351
353 BitSetVectorReference& set(size_type n, int val = 1)
354 {
355 getBit(n) = val;
356 return *this;
357 }
358
361 {
362 set(n, false);
363 return *this;
364 }
365
368 {
369 getBit(n).flip();
370 return *this;
371 }
372
374 using BitSetVectorConstReference::operator[];
375
377 reference operator[](size_type i)
378 {
379 return getBit(i);
380 }
381
382 protected:
383 BitSetVector& blockBitField;
384
385 using BitSetVectorConstReference::getBit;
386
387 reference getBit(size_type i)
388 {
389 return blockBitField.getBit(this->block_number,i);
390 }
391 };
392
396 template<int block_size, class Alloc>
397 struct const_reference< BitSetVectorReference<block_size,Alloc> >
398 {
400 };
401
402 template<int block_size, class Alloc>
403 struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
404 {
406 };
407
408 template<int block_size, class Alloc>
409 struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
410 {
411 typedef BitSetVectorReference<block_size,Alloc> type;
412 };
413
414 template<int block_size, class Alloc>
415 struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
416 {
417 typedef BitSetVectorReference<block_size,Alloc> type;
418 };
419
423 template <int block_size, class Allocator=std::allocator<bool> >
424 class BitSetVector : private std::vector<bool, Allocator>
425 {
427 typedef std::vector<bool, Allocator> BlocklessBaseClass;
428
429 public:
432
434 typedef std::bitset<block_size> value_type;
435
438
441
444
447
449 typedef typename std::vector<bool, Allocator>::size_type size_type;
450
452 typedef Allocator allocator_type;
454
460
463 return iterator(*this, 0);
464 }
465
468 return const_iterator(*this, 0);
469 }
470
473 return iterator(*this, size());
474 }
475
478 return const_iterator(*this, size());
479 }
480
483 BlocklessBaseClass()
484 {}
485
487 BitSetVector(const BlocklessBaseClass& blocklessBitField) :
488 BlocklessBaseClass(blocklessBitField)
489 {
490 if (blocklessBitField.size()%block_size != 0)
491 DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
492 }
493
497 explicit BitSetVector(int n) :
498 BlocklessBaseClass(n*block_size)
499 {}
500
502 BitSetVector(int n, bool v) :
503 BlocklessBaseClass(n*block_size,v)
504 {}
505
507 void clear()
508 {
509 BlocklessBaseClass::clear();
510 }
511
513 void resize(int n, bool v = bool())
514 {
515 BlocklessBaseClass::resize(n*block_size, v);
516 }
517
520 {
521 return BlocklessBaseClass::size()/block_size;
522 }
523
525 void setAll() {
526 this->assign(BlocklessBaseClass::size(), true);
527 }
528
530 void unsetAll() {
531 this->assign(BlocklessBaseClass::size(), false);
532 }
533
536 {
537 return reference(*this, i);
538 }
539
542 {
543 return const_reference(*this, i);
544 }
545
548 {
549 return reference(*this, size()-1);
550 }
551
554 {
555 return const_reference(*this, size()-1);
556 }
557
560 {
561 return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
562 }
563
566 {
567 size_type n = 0;
568 size_type blocks = size();
569 for(size_type i=0; i<blocks; ++i)
570 n += getBit(i,j);
571 return n;
572 }
573
575 friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
576 {
577 for (size_t i=0; i<v.size(); i++)
578 s << v[i] << " ";
579 return s;
580 }
581
582 private:
583
585 value_type getRepr(int i) const
586 {
587 value_type bits;
588 for(int j=0; j<block_size; ++j)
589 bits.set(j, getBit(i,j));
590 return bits;
591 }
592
593 typename std::vector<bool>::reference getBit(size_type i, size_type j) {
594 DUNE_ASSERT_BOUNDS(j < block_size);
596 return BlocklessBaseClass::operator[](i*block_size+j);
597 }
598
599 typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
600 DUNE_ASSERT_BOUNDS(j < block_size);
602 return BlocklessBaseClass::operator[](i*block_size+j);
603 }
604
605 friend class BitSetVectorReference<block_size,Allocator>;
606 friend class BitSetVectorConstReference<block_size,Allocator>;
607 };
608
609} // namespace Dune
610
611#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: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
bitset operator>>(size_type n) const
Returns a copy of *this shifted right by n bits.
Definition: bitsetvector.hh:72
bool operator!=(const bitset &bs) const
Inequality of reference and std::bitset.
Definition: bitsetvector.hh:154
bool all() const
Returns true if all bits are set.
Definition: bitsetvector.hh:115
bitset operator~() const
Returns a copy of *this with all of its bits flipped.
Definition: bitsetvector.hh:80
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
BitSetVectorConstReference & operator=(const BitSetVectorConstReference &b)=delete
disable assignment operator
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:377
BitSetVectorReference & reset(size_type n)
Clears bit n.
Definition: bitsetvector.hh:360
BitSetVectorReference & operator<<=(size_type n)
Left shift.
Definition: bitsetvector.hh:318
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
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:247
BitSetVectorReference & operator=(const bitset &b)
Assignment from bitset.
Definition: bitsetvector.hh:258
BitSetVectorReference & reset()
Clears every bit.
Definition: bitsetvector.hh:346
BitSetVectorReference & operator|=(const BitSetVectorConstReference &x)
Bitwise inclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:300
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:353
BitSetVectorReference & operator^=(const bitset &x)
Bitwise exclusive or (for bitset).
Definition: bitsetvector.hh:306
std::vector< bool, Alloc >::reference reference
Definition: bitsetvector.hh:241
BitSetVectorReference & operator|=(const bitset &x)
Bitwise inclusive or (for bitset)
Definition: bitsetvector.hh:294
BitSetVectorReference & operator>>=(size_type n)
Right shift.
Definition: bitsetvector.hh:324
BitSetVectorReference & operator^=(const BitSetVectorConstReference &x)
Bitwise exclusive or (for BitSetVectorConstReference and BitSetVectorReference)
Definition: bitsetvector.hh:312
BitSetVectorReference & flip(size_type n)
Flips bit n.
Definition: bitsetvector.hh:367
BitSetVectorReference & flip()
Flips the value of every bit.
Definition: bitsetvector.hh:338
BitSetVectorReference & set()
Sets every bit.
Definition: bitsetvector.hh:330
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 dynamic array of blocks of booleans.
Definition: bitsetvector.hh:425
const_reference operator[](int i) const
Return const reference to i-th block.
Definition: bitsetvector.hh:541
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:462
BitSetVectorConstReference< block_size, Allocator > * const_pointer
Const pointer to a small block of bits.
Definition: bitsetvector.hh:446
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition: bitsetvector.hh:477
BitSetVectorReference< block_size, Allocator > reference
Reference to a small block of bits.
Definition: bitsetvector.hh:437
size_type countmasked(int j) const
Returns the number of set bits, while each block is masked with 1<<i.
Definition: bitsetvector.hh:565
BitSetVectorConstReference< block_size, Allocator > const_reference
Const reference to a small block of bits.
Definition: bitsetvector.hh:440
iterator end()
Returns an iterator pointing to the end of the vector.
Definition: bitsetvector.hh:472
size_type count() const
Returns the number of bits that are set.
Definition: bitsetvector.hh:559
BitSetVector()
Default constructor.
Definition: bitsetvector.hh:482
void setAll()
Sets all entries to true
Definition: bitsetvector.hh:525
std::bitset< block_size > value_type
Type of the values stored by the container.
Definition: bitsetvector.hh:434
reference back()
Return reference to last block.
Definition: bitsetvector.hh:547
BitSetVector(const BlocklessBaseClass &blocklessBitField)
Construction from an unblocked bitfield.
Definition: bitsetvector.hh:487
friend std::ostream & operator<<(std::ostream &s, const BitSetVector &v)
Send bitfield to an output stream.
Definition: bitsetvector.hh:575
const_reference back() const
Return const reference to last block.
Definition: bitsetvector.hh:553
void clear()
Erases all of the elements.
Definition: bitsetvector.hh:507
BitSetVectorReference< block_size, Allocator > * pointer
Pointer to a small block of bits.
Definition: bitsetvector.hh:443
reference operator[](int i)
Return reference to i-th block.
Definition: bitsetvector.hh:535
size_type size() const
Return the number of blocks.
Definition: bitsetvector.hh:519
std::vector< bool, Allocator >::size_type size_type
size type
Definition: bitsetvector.hh:449
BitSetVector(int n, bool v)
Constructor which initializes the field with true or false.
Definition: bitsetvector.hh:502
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition: bitsetvector.hh:467
Dune::GenericIterator< BitSetVector< block_size, Allocator >, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade > iterator
Definition: bitsetvector.hh:457
void resize(int n, bool v=bool())
Resize field.
Definition: bitsetvector.hh:513
Allocator allocator_type
The type of the allocator.
Definition: bitsetvector.hh:452
BitSetVector(int n)
Definition: bitsetvector.hh:497
void unsetAll()
Sets all entries to false
Definition: bitsetvector.hh:530
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:142
Generic class for stl-conforming iterators for container classes with operator[].
Definition: genericiterator.hh:153
Default exception class for range errors.
Definition: exceptions.hh:254
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:30
#define DUNE_THROW(E, m)
Definition: exceptions.hh:218
bool eq(const T &first, const T &second, typename EpsilonType< T >::Type epsilon)
test for equality using epsilon
Definition: float_cmp.cc:144
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:587
Dune namespace.
Definition: alignedallocator.hh:13
void assign(T &dst, const T &src, bool mask)
masked Simd assignment (scalar version)
Definition: simd.hh:447
Get the 'const' version of a reference to a mutable object.
Definition: genericiterator.hh:87
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)