aboutsummaryrefslogtreecommitdiffstats
path: root/chilbert/BigBitVec.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'chilbert/BigBitVec.hpp')
-rw-r--r--chilbert/BigBitVec.hpp258
1 files changed, 188 insertions, 70 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index 7302880..29d9a5a 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -39,6 +39,50 @@ public:
static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT;
+ /** Mask for a bit that can be incremented like an index.
+ *
+ * This enables fast iteration while setting or resetting bits since it is
+ * internally stored as a mask which avoids repeated index math.
+ */
+ class Mask
+ {
+ public:
+ void operator++()
+ {
+ if ((m_mask <<= 1) == 0) {
+ m_mask = 1;
+ ++m_rack;
+ }
+ }
+
+ void operator--()
+ {
+ if ((m_mask >>= 1) == 0) {
+ m_mask = Rack{1} << (bits_per_rack - 1);
+ --m_rack;
+ }
+ }
+
+ bool operator==(const Mask& mask) const
+ {
+ return m_rack == mask.m_rack && m_mask == mask.m_mask;
+ }
+
+ bool operator!=(const Mask& mask) const { return !operator==(mask); }
+
+ private:
+ friend class CBigBitVec;
+
+ Mask(const size_t index)
+ : m_rack{index / bits_per_rack}
+ , m_mask{Rack{1} << (index - m_rack * bits_per_rack)}
+ {
+ }
+
+ size_t m_rack;
+ Rack m_mask;
+ };
+
explicit CBigBitVec(const size_t bits)
: m_pcRacks{make_racks(num_racks(bits))}
, m_iRacks{bits == 0 ? 0 : num_racks(bits)}
@@ -83,16 +127,11 @@ public:
/// Truncate to a given precision in bits (zero MSBs)
CBigBitVec& truncate(const size_t bits)
{
- assert(bits <= size());
- const Ref ref(bits);
- if (ref.rack >= m_iRacks) {
- return *this;
- }
+ const Mask m = mask(bits);
- // Truncate rack that contains the split point
- m_pcRacks[ref.rack] &= ((Rack{1} << ref.bit) - 1);
+ m_pcRacks[m.m_rack] &= (m.m_mask - 1);
- for (size_t i = ref.rack + 1; i < m_iRacks; ++i) {
+ for (size_t i = m.m_rack + 1; i < m_iRacks; ++i) {
m_pcRacks[i] = 0;
}
@@ -145,50 +184,59 @@ public:
CBigBitVec& operator=(CBigBitVec&& vec) = default;
+ /// Return the value of the bit covered by `mask`
+ bool test(const Mask mask) const
+ {
+ return m_pcRacks[mask.m_rack] & mask.m_mask;
+ }
+
/// Return the value of the `index`th bit
- bool test(const size_t index) const
+ bool test(const size_t index) const { return test(mask(index)); }
+
+ /// Set the bit covered by `mask` to 1
+ CBigBitVec& set(const Mask mask)
{
- assert(index < size());
- const Ref ref(index);
- return testBit(m_pcRacks[ref.rack], ref.bit);
+ m_pcRacks[mask.m_rack] |= mask.m_mask;
+ return *this;
}
/// Set the `index`th bit to 1
- CBigBitVec& set(const size_t index)
+ CBigBitVec& set(const size_t index) { return set(mask(index)); }
+
+ /// Reset the bit covered by `mask` to 0
+ CBigBitVec& reset(const Mask mask)
{
- assert(index < size());
- const Ref ref(index);
- setBit(m_pcRacks[ref.rack], ref.bit);
+ m_pcRacks[mask.m_rack] &= ~mask.m_mask;
return *this;
}
/// Reset the `index`th bit to 0
- CBigBitVec& reset(const size_t index)
+ CBigBitVec& reset(const size_t index) { return reset(mask(index)); }
+
+ /// Set the bit covered by `mask` to `value`
+ CBigBitVec& set(const Mask mask, const bool value)
{
- assert(index < size());
- const Ref ref(index);
- m_pcRacks[ref.rack] &= ~(Rack{1} << ref.bit);
+ auto& rack = m_pcRacks[mask.m_rack];
+ rack ^= (-Rack{value} ^ rack) & mask.m_mask;
return *this;
}
/// Set the `index`th bit to `value`
CBigBitVec& set(const size_t index, const bool value)
{
- assert(index < size());
- const Ref ref(index);
- setBit(m_pcRacks[ref.rack], ref.bit, value);
- return *this;
+ return set(mask(index), value);
}
- /// Flip the value of the `index`th bit
- CBigBitVec& flip(const size_t index)
+ /// Flip the value of the bit covered by `mask`
+ CBigBitVec& flip(const Mask mask)
{
- assert(index < size());
- const Ref ref(index);
- m_pcRacks[ref.rack] ^= (Rack{1} << ref.bit);
+ m_pcRacks[mask.m_rack] ^= mask.m_mask;
return *this;
}
+ /// Flip the value of the `index`th bit
+ CBigBitVec& flip(const size_t index) { return flip(mask(index)); }
+
CBigBitVec& operator&=(const CBigBitVec& vec)
{
for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
@@ -249,40 +297,34 @@ public:
CBigBitVec& operator<<=(const size_t bits)
{
- assert(bits < size());
-
- // No shift?
if (bits == 0) {
return *this;
- }
-
- const Ref ref(bits);
-
- // All racks?
- if (ref.rack >= m_iRacks) {
+ } else if (bits >= size()) {
reset();
return *this;
}
- // Do rack shifts.
- if (ref.rack > 0) {
- for (size_t i = m_iRacks - 1; i >= ref.rack; --i) {
- m_pcRacks[i] = m_pcRacks[i - ref.rack];
+ const Index index{bits};
+
+ if (index.rack > 0) {
+ // Shift entire racks
+ for (size_t i = m_iRacks - 1; i >= index.rack; --i) {
+ m_pcRacks[i] = m_pcRacks[i - index.rack];
}
- for (size_t i = 0; i < ref.rack; ++i) {
+ for (size_t i = 0; i < index.rack; ++i) {
m_pcRacks[i] = 0;
}
}
- // Do bit shifts.
- if (ref.bit > 0) {
- size_t bi = bits_per_rack - ref.bit;
+ if (index.bit > 0) {
+ // Shift bits within racks
+ size_t bi = bits_per_rack - index.bit;
size_t i;
- for (i = m_iRacks - 1; i >= ref.rack + 1; --i) {
- m_pcRacks[i] <<= ref.bit;
+ for (i = m_iRacks - 1; i >= index.rack + 1; --i) {
+ m_pcRacks[i] <<= index.bit;
m_pcRacks[i] |= m_pcRacks[i - 1] >> bi;
}
- m_pcRacks[i] <<= ref.bit;
+ m_pcRacks[i] <<= index.bit;
}
return *this;
@@ -297,41 +339,35 @@ public:
CBigBitVec& operator>>=(const size_t bits)
{
- assert(bits < size());
-
- // No shift?
if (bits == 0) {
return *this;
- }
-
- const Ref ref(bits);
-
- // All racks?
- if (ref.rack >= m_iRacks) {
+ } else if (bits >= size()) {
reset();
return *this;
}
- // Do rack shifts.
- if (ref.rack > 0) {
+ const Index index{bits};
+
+ if (index.rack > 0) {
+ // Shift entire racks
size_t i;
- for (i = 0; i < m_iRacks - ref.rack; ++i) {
- m_pcRacks[i] = m_pcRacks[i + ref.rack];
+ for (i = 0; i < m_iRacks - index.rack; ++i) {
+ m_pcRacks[i] = m_pcRacks[i + index.rack];
}
for (; i < m_iRacks; ++i) {
m_pcRacks[i] = 0;
}
}
- // Do bit shifts.
- if (ref.bit > 0) {
- size_t bi = bits_per_rack - ref.bit;
+ if (index.bit > 0) {
+ // Shift bits within racks
+ size_t bi = bits_per_rack - index.bit;
size_t i;
- for (i = 0; i < m_iRacks - ref.rack - 1; ++i) {
- m_pcRacks[i] >>= ref.bit;
+ for (i = 0; i < m_iRacks - index.rack - 1; ++i) {
+ m_pcRacks[i] >>= index.bit;
m_pcRacks[i] |= m_pcRacks[i + 1] << bi;
}
- m_pcRacks[i] >>= ref.bit;
+ m_pcRacks[i] >>= index.bit;
}
return *this;
@@ -451,10 +487,92 @@ public:
/// Return the number of racks
size_t rackCount() const { return m_iRacks; }
+ template <class BitVec>
+ class iterator_base : public Mask
+ {
+ public:
+ iterator_base& operator++()
+ {
+ Mask::operator++();
+ return *this;
+ }
+
+ iterator_base& operator--()
+ {
+ Mask::operator--();
+ return *this;
+ }
+
+ bool operator==(const iterator_base& iterator_base) const
+ {
+ return m_vec == iterator_base.m_vec &&
+ Mask::operator==(iterator_base);
+ }
+
+ bool operator!=(const iterator_base& iterator_base) const
+ {
+ return !operator==(iterator_base);
+ }
+
+ bool operator*() const { return m_vec->test(*this); }
+
+ protected:
+ iterator_base(BitVec& vec, const size_t index)
+ : Mask{index}
+ , m_vec{&vec}
+ {
+ }
+
+ BitVec* m_vec;
+ };
+
+ class iterator : public iterator_base<CBigBitVec>
+ {
+ public:
+ void set() { m_vec->set(*this); }
+ void reset() { m_vec->reset(*this); }
+
+ private:
+ friend class CBigBitVec;
+
+ iterator(CBigBitVec& vec, const size_t index)
+ : iterator_base{vec, index}
+ {
+ }
+ };
+
+ class const_iterator : public iterator_base<const CBigBitVec>
+ {
+ private:
+ friend class CBigBitVec;
+
+ const_iterator(const CBigBitVec& vec, const size_t index)
+ : iterator_base{vec, index}
+ {
+ }
+ };
+
+ Mask mask(const size_t i = 0) const
+ {
+ assert(i <= size());
+ return Mask{i};
+ }
+
+ iterator begin(const size_t i = 0) { return iterator(*this, i); }
+
+ iterator end() { return iterator(*this, size()); }
+
+ const_iterator begin(const size_t i = 0) const
+ {
+ return const_iterator(*this, i);
+ }
+
+ const_iterator end() const { return const_iterator(*this, size()); }
+
private:
- struct Ref
+ struct Index
{
- Ref(const size_t bits)
+ Index(const size_t bits)
: rack{bits / bits_per_rack}
, bit{bits - rack * bits_per_rack}
{
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-30 23:04:09 +0000