ECSTASY
All in the name
Loading...
Searching...
No Matches
util::BitSet Class Reference

Mimics the API of std::bitset but with the dynamic properties of std::vector<bool> More...

#include <BitSet.hpp>

Collaboration diagram for util::BitSet:

Classes

class  Reference
 

Public Member Functions

 BitSet (std::size_t initialSize=0)
 
 BitSet (std::string_view bitString)
 Constructs a bitset from a strings of zeroes and ones.
 
constexpr std::size_t size () const noexcept
 
BIT_SET_CONSTEXPR bool test (std::size_t pos) const noexcept
 
BIT_SET_CONSTEXPR bool operator[] (std::size_t pos) const noexcept
 
BIT_SET_CONSTEXPR BitSetset (std::size_t pos, bool value=true) noexcept
 
BitSetsetAll (bool value=true) noexcept
 Sets all bits to the given value.
 
constexpr Reference operator[] (std::size_t pos) noexcept
 
bool operator== (BitSet const &other) const noexcept
 
bool operator!= (BitSet const &other) const noexcept
 
BitSetflip () noexcept
 Flips all the bits in the set.
 
BitSet operator~ () const
 
BitSet operator& (BitSet const &other) const
 Performs a bitwise AND with this set and other.
 
BitSet operator| (BitSet const &other) const
 Performs a bitwise OR with this set and other.
 
BitSet operator^ (BitSet const &other) const
 Performs a bitwise XOR with this set and other.
 
BitSetoperator&= (BitSet const &other) noexcept
 Performs a bitwise AND with this set and other in place.
 
BitSetoperator|= (BitSet const &other) noexcept
 Performs a bitwise OR with this set and other in place.
 
BitSetoperator^= (BitSet const &other) noexcept
 Performs a bitwise XOR with this set and other in place.
 
BitSetinplaceAnd (BitSet const &other) noexcept
 Performs a bitwise AND with this set and other in place without resizing this.
 
BitSetinplaceOr (BitSet const &other) noexcept
 Performs a bitwise OR with this set and other in place without resizing this.
 
BitSetinplaceXor (BitSet const &other) noexcept
 Performs a bitwise XOR with this set and other in place without resizing this.
 
void resize (std::size_t size)
 Changes the number of bits stored in this set.
 
void resizeSentinel (std::size_t size, bool sentinelValue)
 Changes the number of bits stored in this set, and sets the final bit past size to the value of sentinelValue.
 
BitSetpush (bool value)
 Adds the given bit to the end of the set.
 
bool pop ()
 Removes one bit from the end of the set.
 
BIT_SET_CONSTEXPR std::size_t firstSet (std::size_t start=0) const
 Finds the first set bit in the set, starting from (and including) start.
 
BIT_SET_CONSTEXPR std::size_t lastSet () const
 Finds the last set bit in the set.
 
BIT_SET_CONSTEXPR std::size_t firstUnset (std::size_t start=0) const
 Finds the first unset bit in the set, starting from (and including) start.
 
BIT_SET_CONSTEXPR std::size_t lastUnset () const
 Finds the last unset bit in the set.
 

Private Member Functions

void normalize () noexcept
 Unset the trailing bits.
 
void _resize (std::size_t size)
 Resize without normalizing.
 

Static Private Member Functions

static constexpr std::uint64_t mask (std::size_t pos)
 
static constexpr std::size_t getStoreWordCount (std::size_t bitCount)
 

Private Attributes

std::size_t _size
 
std::vector< std::uint64_t_store
 
friend Reference
 

Friends

class BitSetTester
 Used by unit tests to access BitSet internals.
 

Detailed Description

Mimics the API of std::bitset but with the dynamic properties of std::vector<bool>

Definition at line 35 of file BitSet.hpp.

Constructor & Destructor Documentation

◆ BitSet() [1/2]

util::BitSet::BitSet ( std::size_t  initialSize = 0)
Parameters
initialSizeAn initial number of bits, all set to zero.

Definition at line 24 of file BitSet.cpp.

24 : _size(initialSize), _store(getStoreWordCount(initialSize))
25 {
26 }
static constexpr std::size_t getStoreWordCount(std::size_t bitCount)
Definition BitSet.hpp:319
std::size_t _size
Definition BitSet.hpp:309
std::vector< std::uint64_t > _store
Definition BitSet.hpp:310

◆ BitSet() [2/2]

util::BitSet::BitSet ( std::string_view  bitString)

Constructs a bitset from a strings of zeroes and ones.

The leftmost bit is the most-significant.

Note
bitString must only contain the chars '0' and '1'.

Definition at line 28 of file BitSet.cpp.

28 : BitSet(bitString.size())
29 {
30 for (std::size_t i = 0, s = bitString.size(); i < s; ++i)
31 this->set(i, bitString[s - i - 1] == '1');
32 }
BitSet(std::size_t initialSize=0)
Definition BitSet.cpp:24
BIT_SET_CONSTEXPR BitSet & set(std::size_t pos, bool value=true) noexcept
Definition BitSet.hpp:111
T size(T... args)

Member Function Documentation

◆ _resize()

void util::BitSet::_resize ( std::size_t  size)
private

Resize without normalizing.

Definition at line 161 of file BitSet.cpp.

162 {
163 this->_store.resize(getStoreWordCount(size));
164 this->_size = size;
165 }
constexpr std::size_t size() const noexcept
Definition BitSet.hpp:87
T resize(T... args)

◆ firstSet()

BIT_SET_CONSTEXPR std::size_t util::BitSet::firstSet ( std::size_t  start = 0) const
inline

Finds the first set bit in the set, starting from (and including) start.

Note
The behavior is undefined if the set does not contain a single 'one' bit from start.
Parameters
startThe bit position of where to start the search for a set bit.
Returns
The position of the first set bit.

Definition at line 229 of file BitSet.hpp.

230 {
231 std::uint64_t mask = (~std::uint64_t(0)) << (start & 0b111111);
232 std::size_t word_pos = start >> 6;
233 std::uint64_t word = this->_store[word_pos] & mask;
234
235 while (word == 0) {
236 ++word_pos;
237 word = this->_store[word_pos];
238 }
239 return (word_pos << 6) + static_cast<std::size_t>(std::countr_zero(word));
240 }
static constexpr std::uint64_t mask(std::size_t pos)
Definition BitSet.hpp:313
T countr_zero(T... args)

◆ firstUnset()

BIT_SET_CONSTEXPR std::size_t util::BitSet::firstUnset ( std::size_t  start = 0) const
inline

Finds the first unset bit in the set, starting from (and including) start.

Note
The behavior is undefined if the set does not contain a single 'zero' bit from start.
Parameters
startThe bit position of where to start the search for an unset bit.
Returns
The position of the first unset bit.

Definition at line 272 of file BitSet.hpp.

273 {
274 std::uint64_t mask = (~std::uint64_t(0)) << (start & 0b111111);
275 std::size_t word_pos = start >> 6;
276 std::uint64_t word = this->_store[word_pos] | (~mask);
277
278 while (word == (~std::uint64_t(0))) {
279 ++word_pos;
280 word = this->_store[word_pos];
281 }
282 return (word_pos << 6) + static_cast<std::size_t>(std::countr_one(word));
283 }
T countr_one(T... args)

◆ flip()

BitSet & util::BitSet::flip ( )
noexcept

Flips all the bits in the set.

Returns
this.

Definition at line 52 of file BitSet.cpp.

53 {
54 for (auto &word : this->_store)
55 word = ~word;
56 this->normalize();
57 return *this;
58 }
void normalize() noexcept
Unset the trailing bits.
Definition BitSet.cpp:152

◆ getStoreWordCount()

static constexpr std::size_t util::BitSet::getStoreWordCount ( std::size_t  bitCount)
inlinestaticconstexprprivate
Returns
The number of 64-bit words needed to store bitCount amount of bits.

Definition at line 319 of file BitSet.hpp.

320 {
321 if ((bitCount & (~static_cast<std::size_t>(0b111111))) == bitCount)
322 return bitCount >> 6; // if bitCount is a multiple of 64, return bitCount / 64
323 else
324 return (bitCount >> 6) + 1; // or else, add one word to contain the extra bits
325 }

◆ inplaceAnd()

BitSet & util::BitSet::inplaceAnd ( BitSet const &  other)
noexcept

Performs a bitwise AND with this set and other in place without resizing this.

Note
this method is not named and because it is restricted.
Returns
this

Definition at line 125 of file BitSet.cpp.

126 {
127 std::size_t s = std::min(this->_store.size(), other._store.size());
128
129 for (std::size_t i = 0; i + 1 < s; ++i)
130 this->_store[i] &= other._store[i];
131 this->_store[s - 1] &= other._store[s - 1] | (~std::uint64_t(0) << (other.size() & 0b111111));
132 this->normalize();
133 return *this;
134 }
T min(T... args)

◆ inplaceOr()

BitSet & util::BitSet::inplaceOr ( BitSet const &  other)
noexcept

Performs a bitwise OR with this set and other in place without resizing this.

Note
this method is not named or because it is restricted.
Returns
this

Definition at line 136 of file BitSet.cpp.

137 {
138 for (std::size_t i = 0, s = std::min(this->_store.size(), other._store.size()); i < s; ++i)
139 this->_store[i] |= other._store[i];
140 this->normalize();
141 return *this;
142 }

◆ inplaceXor()

BitSet & util::BitSet::inplaceXor ( BitSet const &  other)
noexcept

Performs a bitwise XOR with this set and other in place without resizing this.

Note
this method is not named xor because it is restricted.
Returns
this

Definition at line 144 of file BitSet.cpp.

145 {
146 for (std::size_t i = 0, s = std::min(this->_store.size(), other._store.size()); i < s; ++i)
147 this->_store[i] ^= other._store[i];
148 this->normalize();
149 return *this;
150 }

◆ lastSet()

BIT_SET_CONSTEXPR std::size_t util::BitSet::lastSet ( ) const
inline

Finds the last set bit in the set.

Note
If the set does not contain a single 'one' bit, the return value is 0.
Returns
The position of the last set bit.

Definition at line 247 of file BitSet.hpp.

248 {
249 std::uint64_t mask = ~((~std::uint64_t(0)) << (_size & 0b111111));
250 std::size_t word_pos = _size >> 6;
251 std::uint64_t word = this->_store[word_pos] & mask;
252
253 while (word == 0) {
254 // Avoid underflow
255 if (word_pos == 0)
256 break;
257 --word_pos;
258 word = this->_store[word_pos];
259 }
260 if (word == 0)
261 return 0;
262 return (word_pos << 6) + static_cast<std::size_t>(0b111111 - std::countl_zero(word));
263 }
T countl_zero(T... args)

◆ lastUnset()

BIT_SET_CONSTEXPR std::size_t util::BitSet::lastUnset ( ) const
inline

Finds the last unset bit in the set.

Note
If the set does not contain a single 'zero' bit, the return value is 0.
Returns
The position of the last set bit.

Definition at line 290 of file BitSet.hpp.

291 {
292 std::uint64_t mask = ~((~std::uint64_t(0)) << (_size & 0b111111));
293 std::size_t word_pos = _size >> 6;
294 std::uint64_t word = this->_store[word_pos] | (~mask);
295
296 while (word == (~std::uint64_t(0))) {
297 // Avoid underflow
298 if (word_pos == 0)
299 break;
300 --word_pos;
301 word = this->_store[word_pos];
302 }
303 if (word == (~std::uint64_t(0)))
304 return 0;
305 return (word_pos << 6) + static_cast<std::size_t>(0b111111 - std::countl_one(word));
306 }
T countl_one(T... args)

◆ mask()

static constexpr std::uint64_t util::BitSet::mask ( std::size_t  pos)
inlinestaticconstexprprivate
Returns
The bit mask for the requested bit position.

Definition at line 313 of file BitSet.hpp.

314 {
315 return std::uint64_t(1) << (pos & 0b111111);
316 }

◆ normalize()

void util::BitSet::normalize ( )
privatenoexcept

Unset the trailing bits.

Definition at line 152 of file BitSet.cpp.

153 {
154 if ((this->_size & 0b111111) != 0) {
155 std::uint64_t &last = *this->_store.rbegin();
156 uint64_t mask = ~((~std::uint64_t(0)) << (this->_size & 0b111111));
157 last &= mask;
158 }
159 }
T rbegin(T... args)

◆ operator!=()

bool util::BitSet::operator!= ( BitSet const &  other) const
noexcept
Returns
Whether the bit sets are not equal, both sets must have the same size.

Definition at line 47 of file BitSet.cpp.

48 {
49 return this->_store != other._store;
50 }

◆ operator&()

BitSet util::BitSet::operator& ( BitSet const &  other) const

Performs a bitwise AND with this set and other.

Returns
A new result set, its length is that of the smallest input set.

Definition at line 68 of file BitSet.cpp.

69 {
70 BitSet result(std::min(this->_size, other._size));
71
72 for (std::size_t i = 0, s = result._store.size(); i < s; ++i)
73 result._store[i] = this->_store[i] & other._store[i];
74 result.normalize();
75 return result;
76 }

◆ operator&=()

BitSet & util::BitSet::operator&= ( BitSet const &  other)
noexcept

Performs a bitwise AND with this set and other in place.

Returns
this

Definition at line 98 of file BitSet.cpp.

99 {
100 this->_resize(std::min(this->_size, other._size));
101 for (std::size_t i = 0, s = this->_store.size(); i < s; ++i)
102 this->_store[i] &= other._store[i];
103 this->normalize();
104 return *this;
105 }
void _resize(std::size_t size)
Resize without normalizing.
Definition BitSet.cpp:161

◆ operator==()

bool util::BitSet::operator== ( BitSet const &  other) const
noexcept
Returns
Whether the bit sets are equal, both sets must have the same size.

Definition at line 42 of file BitSet.cpp.

43 {
44 return this->_store == other._store;
45 }

◆ operator[]() [1/2]

BIT_SET_CONSTEXPR bool util::BitSet::operator[] ( std::size_t  pos) const
inlinenoexcept
Note
This function does not perform bounds-checking.
Returns
The value of the bit at pos.

Definition at line 103 of file BitSet.hpp.

104 {
105 return this->test(pos);
106 }
BIT_SET_CONSTEXPR bool test(std::size_t pos) const noexcept
Definition BitSet.hpp:95

◆ operator[]() [2/2]

constexpr Reference util::BitSet::operator[] ( std::size_t  pos)
inlineconstexprnoexcept
Note
This function does not perform bounds-checking.
Returns
A reference to the bit at pos.

Definition at line 126 of file BitSet.hpp.

127 {
128 return Reference(*this, pos);
129 }
friend Reference
Definition BitSet.hpp:333

◆ operator^()

BitSet util::BitSet::operator^ ( BitSet const &  other) const

Performs a bitwise XOR with this set and other.

Returns
A new result set, its length is that of the smallest input set.

Definition at line 88 of file BitSet.cpp.

89 {
90 BitSet result(std::min(this->_size, other._size));
91
92 for (std::size_t i = 0, s = result._store.size(); i < s; ++i)
93 result._store[i] = this->_store[i] ^ other._store[i];
94 result.normalize();
95 return result;
96 }

◆ operator^=()

BitSet & util::BitSet::operator^= ( BitSet const &  other)
noexcept

Performs a bitwise XOR with this set and other in place.

Returns
this

Definition at line 116 of file BitSet.cpp.

117 {
118 this->_resize(std::min(this->_size, other._size));
119 for (std::size_t i = 0, s = this->_store.size(); i < s; ++i)
120 this->_store[i] ^= other._store[i];
121 this->normalize();
122 return *this;
123 }

◆ operator|()

BitSet util::BitSet::operator| ( BitSet const &  other) const

Performs a bitwise OR with this set and other.

Returns
A new result set, its length is that of the smallest input set.

Definition at line 78 of file BitSet.cpp.

79 {
80 BitSet result(std::min(this->_size, other._size));
81
82 for (std::size_t i = 0, s = result._store.size(); i < s; ++i)
83 result._store[i] = this->_store[i] | other._store[i];
84 result.normalize();
85 return result;
86 }

◆ operator|=()

BitSet & util::BitSet::operator|= ( BitSet const &  other)
noexcept

Performs a bitwise OR with this set and other in place.

Returns
this

Definition at line 107 of file BitSet.cpp.

108 {
109 this->_resize(std::min(this->_size, other._size));
110 for (std::size_t i = 0, s = this->_store.size(); i < s; ++i)
111 this->_store[i] |= other._store[i];
112 this->normalize();
113 return *this;
114 }

◆ operator~()

BitSet util::BitSet::operator~ ( ) const
Returns
A copy of this with all the bits flipped.

Definition at line 60 of file BitSet.cpp.

61 {
62 BitSet copy(*this);
63
64 copy.flip();
65 return copy;
66 }
T copy(T... args)

◆ pop()

bool util::BitSet::pop ( )

Removes one bit from the end of the set.

Note
This function does not perform bounds-checking.
Returns
The value of the removed bit.

Definition at line 182 of file BitSet.cpp.

183 {
184 bool value = this->test(this->_size - 1);
185 this->resize(this->_size - 1);
186 return value;
187 }
void resize(std::size_t size)
Changes the number of bits stored in this set.
Definition BitSet.hpp:199

◆ push()

BitSet & util::BitSet::push ( bool  value)

Adds the given bit to the end of the set.

Definition at line 175 of file BitSet.cpp.

176 {
177 this->resize(this->_size + 1);
178 this->set(this->_size - 1, value);
179 return *this;
180 }

◆ resize()

void util::BitSet::resize ( std::size_t  size)
inline

Changes the number of bits stored in this set.

Parameters
sizeThe new number of bits, may be smaller or greater than the current size, or zero.

Definition at line 199 of file BitSet.hpp.

200 {
201 this->_resize(size);
202 this->normalize();
203 }

◆ resizeSentinel()

void util::BitSet::resizeSentinel ( std::size_t  size,
bool  sentinelValue 
)

Changes the number of bits stored in this set, and sets the final bit past size to the value of sentinelValue.

Parameters
sizeThe new number of non-sentinel bits, may be smaller or greater than the current size, or zero.
sentinelValueThe value of the sentinel bit.

Definition at line 167 of file BitSet.cpp.

168 {
169 if (this->_size > 0)
170 this->set(this->_size - 1, !sentinelValue);
171 this->resize(size + 1);
172 this->set(this->_size - 1, sentinelValue);
173 }

◆ set()

BIT_SET_CONSTEXPR BitSet & util::BitSet::set ( std::size_t  pos,
bool  value = true 
)
inlinenoexcept
Note
This function does not perform bounds-checking.

Assigns a value to the bit at pos.

Definition at line 111 of file BitSet.hpp.

112 {
113 if (value)
114 this->_store[pos >> 6] |= mask(pos);
115 else
116 this->_store[pos >> 6] &= ~mask(pos);
117 return *this;
118 }

◆ setAll()

BitSet & util::BitSet::setAll ( bool  value = true)
noexcept

Sets all bits to the given value.

Definition at line 34 of file BitSet.cpp.

35 {
36 for (auto &word : this->_store)
37 word = value ? ~std::uint64_t(0) : std::uint64_t(0);
38 this->normalize();
39 return *this;
40 }

◆ size()

constexpr std::size_t util::BitSet::size ( ) const
inlineconstexprnoexcept
Returns
The number of bits in the set.

Definition at line 87 of file BitSet.hpp.

88 {
89 return this->_size;
90 }

◆ test()

BIT_SET_CONSTEXPR bool util::BitSet::test ( std::size_t  pos) const
inlinenoexcept
Note
This function does not perform bounds-checking.
Returns
The value of the bit at pos.

Definition at line 95 of file BitSet.hpp.

96 {
97 return (this->_store[pos >> 6] & mask(pos)) != 0;
98 }

Friends And Related Symbol Documentation

◆ BitSetTester

friend class BitSetTester
friend

Used by unit tests to access BitSet internals.

Definition at line 335 of file BitSet.hpp.

Member Data Documentation

◆ _size

std::size_t util::BitSet::_size
private

Definition at line 309 of file BitSet.hpp.

◆ _store

std::vector<std::uint64_t> util::BitSet::_store
private

Definition at line 310 of file BitSet.hpp.

◆ Reference

friend util::BitSet::Reference
private

Definition at line 333 of file BitSet.hpp.


The documentation for this class was generated from the following files: