summaryrefslogtreecommitdiff
path: root/Runtime/Utilities/dynamic_bitset.h
diff options
context:
space:
mode:
Diffstat (limited to 'Runtime/Utilities/dynamic_bitset.h')
-rw-r--r--Runtime/Utilities/dynamic_bitset.h1144
1 files changed, 1144 insertions, 0 deletions
diff --git a/Runtime/Utilities/dynamic_bitset.h b/Runtime/Utilities/dynamic_bitset.h
new file mode 100644
index 0000000..7dadb2c
--- /dev/null
+++ b/Runtime/Utilities/dynamic_bitset.h
@@ -0,0 +1,1144 @@
+#ifndef DYNAMIC_BITSET_H
+#define DYNAMIC_BITSET_H
+// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
+//
+// Permission to copy, use, modify, sell and distribute this software
+// is granted provided this copyright notice appears in all
+// copies. This software is provided "as is" without express or
+// implied warranty, and with no claim as to its suitability for any
+// purpose.
+
+// With optimizations, bug fixes, and improvements by Gennaro Prota.
+
+// See http://www.boost.org/libs/dynamic_bitset for documentation.
+
+// -------------------------------------
+// CHANGE LOG:
+//
+// - corrected workaround for Dinkum lib's allocate() [GP]
+// - changed macro test for old iostreams [GP]
+// - removed #include <vector> for now. [JGS]
+// - Added __GNUC__ to compilers that cannot handle the constructor from basic_string. [JGS]
+// - corrected to_block_range [GP]
+// - corrected from_block_range [GP]
+// - Removed __GNUC__ from compilers that cannot handle the constructor
+// from basic_string and added the workaround suggested by GP. [JGS]
+// - Removed __BORLANDC__ from the #if around the basic_string
+// constructor. Luckily the fix by GP for g++ also fixes Borland. [JGS]
+
+#include <cassert>
+#include <string>
+#include <cstring> // for memset, memcpy, memcmp, etc.
+#include <algorithm> // for std::swap, std::min, std::copy, std::fill
+#include <memory> // for std::swap, std::min, std::copy, std::fill
+#include <stdlib.h>
+#include "LogAssert.h"
+
+namespace std
+{
+ typedef ::size_t size_t;
+}
+// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
+//
+// Permission to copy, use, modify, sell and distribute this software
+// is granted provided this copyright notice appears in all
+// copies. This software is provided "as is" without express or
+// implied warranty, and with no claim as to its suitability for any
+// purpose.
+
+// With optimizations by Gennaro Prota.
+
+ class dynamic_bitset_base
+ {
+ typedef std::size_t size_type;
+ public:
+#if defined(LINUX) && (defined (__LP64__) || defined(_AMD64_))
+ typedef unsigned int Block;
+#else
+ typedef unsigned long Block;
+#endif
+ enum { bits_per_block = 8 * sizeof(Block) };
+
+ dynamic_bitset_base()
+ : m_bits(0), m_num_bits(0), m_num_blocks(0) { }
+
+ dynamic_bitset_base(size_type num_bits) :
+ m_num_bits(num_bits),
+ m_num_blocks(calc_num_blocks(num_bits))
+ {
+ if (m_num_blocks != 0)
+ {
+ m_bits = new Block[m_num_blocks];
+ memset(m_bits, 0, m_num_blocks * sizeof(Block)); // G.P.S. ask to Jeremy
+ }
+ else
+ m_bits = 0;
+ }
+ ~dynamic_bitset_base() {
+ delete []m_bits;;
+ }
+
+ Block* m_bits;
+ size_type m_num_bits;
+ size_type m_num_blocks;
+
+ static size_type word(size_type bit) { return bit / bits_per_block; } // [gps]
+ static size_type offset(size_type bit){ return bit % bits_per_block; } // [gps]
+ static Block mask1(size_type bit) { return Block(1) << offset(bit); }
+ static Block mask0(size_type bit) { return ~(Block(1) << offset(bit)); }
+ static size_type calc_num_blocks(size_type num_bits)
+ { return (num_bits + bits_per_block - 1) / bits_per_block; }
+ };
+
+
+ // ------- count table implementation --------------
+
+ typedef unsigned char byte_t;
+
+ template <bool bogus = true>
+ struct bitcount {
+ typedef byte_t element_type;
+ static const byte_t table[];
+
+ };
+ //typedef count<true> table_t;
+
+
+ // the table: wrapped in a class template, so
+ // that it is only instantiated if/when needed
+ //
+ template <bool bogus>
+ const byte_t bitcount<bogus>::table[] =
+ {
+ // Automatically generated by GPTableGen.exe v.1.0
+ //
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+ };
+
+
+ // -------------------------------------------------------
+ template <typename BlockInputIterator>
+ std::size_t initial_num_blocks(BlockInputIterator first,
+ BlockInputIterator last)
+ {
+ std::size_t n = 0;
+ while (first != last)
+ ++first, ++n;
+ return n;
+ }
+
+class dynamic_bitset : public dynamic_bitset_base
+{
+ public:
+
+ typedef Block block_type;
+ typedef std::size_t size_type;
+ enum { bits_per_block = 8 * sizeof(Block) };
+
+ // reference to a bit
+ class reference
+ {
+ friend class dynamic_bitset;
+ dynamic_bitset* bs;
+ size_type bit;
+ reference(); // intentionally not implemented
+ reference(dynamic_bitset& bs_, size_type bit_) : bs(&bs_), bit(bit_){ }
+ public:
+ reference& operator=(bool value) // for b[i] = x
+ {
+ if (value)
+ bs->set(bit);
+ else
+ bs->reset(bit);
+ return *this;
+ }
+ reference& operator|=(bool value) // for b[i] |= x
+ {
+ if (value)
+ bs->set(bit);
+ return *this;
+ }
+ reference& operator&=(bool value) // for b[i] &= x
+ {
+ if (! (value && bs->test(bit)))
+ bs->reset(bit);
+ return *this;
+ }
+ reference& operator^=(bool value) // for b[i] ^= x
+ {
+ bs->set(bit, bs->test(bit) ^ value);
+ return *this;
+ }
+ reference& operator-=(bool value) // for b[i] -= x
+ {
+ if (!value)
+ bs->reset(bit);
+ return *this;
+ }
+ reference& operator=(const reference& j) // for b[i] = b[j]
+ {
+ if (j.bs->test(j.bit))
+ bs->set(bit);
+ else
+ bs->reset(bit);
+ return *this;
+ }
+ reference& operator|=(const reference& j) // for b[i] |= b[j]
+ {
+ if (j.bs->test(j.bit))
+ bs->set(bit);
+ return *this;
+ }
+ reference& operator&=(const reference& j) // for b[i] &= b[j]
+ {
+ if (! (j.bs->test(j.bit) && bs->test(bit)))
+ bs->reset(bit);
+ return *this;
+ }
+ reference& operator^=(const reference& j) // for b[i] ^= b[j]
+ {
+ bs->set(bit, bs->test(bit) ^ j.bs->test(j.bit));
+ return *this;
+ }
+ reference& operator-=(const reference& j) // for b[i] -= b[j]
+ {
+ if (!j.bs->test(j.bit))
+ bs->reset(bit);
+ return *this;
+ }
+ bool operator~() const // flips the bit
+ {
+ return ! bs->test(bit);
+ }
+ operator bool() const // for x = b[i]
+ {
+ return bs->test(bit);
+ }
+ reference& flip() // for b[i].flip();
+ {
+ bs->flip(bit);
+ return *this;
+ }
+ };
+ typedef bool const_reference;
+
+ dynamic_bitset ();
+ explicit
+ dynamic_bitset(size_type num_bits, unsigned long value = 0);
+
+ // The parenthesis around std::basic_string<CharT, Traits, Alloc>::npos
+ // in the code below are to avoid a g++ 3.2 bug and a Borland bug. -JGS
+ template <typename String>
+ explicit
+ dynamic_bitset(const String& s,
+ typename String::size_type pos = 0,
+ typename String::size_type n
+ = (String::npos))
+ : dynamic_bitset_base
+ (std::min(n, s.size() - pos))
+ {
+ // Locate sub string
+ AssertIf (pos > s.length());
+ from_string(s, pos, std::min(n, s.size() - pos));
+ }
+
+ // The first bit in *first is the least significant bit, and the
+ // last bit in the block just before *last is the most significant bit.
+ template <typename BlockInputIterator>
+ dynamic_bitset(BlockInputIterator first, BlockInputIterator last)
+ : dynamic_bitset_base
+ (initial_num_blocks(first, last)
+ * bits_per_block)
+ {
+ if (first != last) {
+ if (this->m_num_bits == 0) { // dealing with input iterators
+ this->append(first, last);
+ } else {
+ // dealing with forward iterators, memory has been allocated
+ for (std::size_t i = 0; first != last; ++first, ++i)
+ set_block_(i, *first);
+ }
+ }
+ }
+
+
+ // copy constructor
+ dynamic_bitset(const dynamic_bitset& b);
+
+ void swap(dynamic_bitset& b);
+
+ dynamic_bitset& operator=(const dynamic_bitset& b);
+
+ // size changing operations
+ void resize(size_type num_bits, bool value = false);
+ void clear();
+ void push_back(bool bit);
+ void append(Block block);
+
+ // This is declared inside the class to avoid compiler bugs.
+ template <typename BlockInputIterator>
+ void append(BlockInputIterator first, BlockInputIterator last)
+ {
+ if (first != last) {
+ std::size_t nblocks = initial_num_blocks(first, last);
+ if (nblocks == 0) { // dealing with input iterators
+ for (; first != last; ++first)
+ append(*first);
+ } else { // dealing with forward iterators
+ if (size() % bits_per_block == 0) {
+ std::size_t old_nblocks = this->m_num_blocks;
+ resize(size() + nblocks * bits_per_block);
+ for (std::size_t i = old_nblocks; first != last; ++first)
+ set_block_(i++, *first);
+ } else {
+ // probably should optimize this,
+ // but I'm sick of bit twiddling
+ for (; first != last; ++first)
+ append(*first);
+ }
+ }
+ }
+ }
+
+
+ // bitset operations
+ dynamic_bitset& operator&=(const dynamic_bitset& b);
+ dynamic_bitset& operator|=(const dynamic_bitset& b);
+ dynamic_bitset& operator^=(const dynamic_bitset& b);
+ dynamic_bitset& operator-=(const dynamic_bitset& b);
+ dynamic_bitset& operator<<=(size_type n);
+ dynamic_bitset& operator>>=(size_type n);
+ dynamic_bitset operator<<(size_type n) const;
+ dynamic_bitset operator>>(size_type n) const;
+
+ // basic bit operations
+ dynamic_bitset& set(size_type n, bool val = true);
+ dynamic_bitset& set();
+ dynamic_bitset& reset(size_type n);
+ dynamic_bitset& reset();
+ dynamic_bitset& flip(size_type n);
+ dynamic_bitset& flip();
+ bool test(size_type n) const;
+ bool any() const;
+ bool none() const;
+ dynamic_bitset operator~() const;
+ size_type count() const;
+
+ // subscript
+ reference operator[](size_type pos) { return reference(*this, pos); }
+ bool operator[](size_type pos) const
+ {
+ #if UNITY_EDITOR
+ if (pos < this->m_num_bits)
+ return test_(pos);
+ else
+ {
+ ErrorString("dynamic_bitset.test bit out of bounds");
+ return false;
+ }
+ #else
+ AssertIf(pos >= this->m_num_bits);
+ return test_(pos);
+ #endif
+ }
+
+ unsigned long to_ulong() const;
+
+ size_type size() const;
+ size_type num_blocks() const;
+
+ bool is_subset_of(const dynamic_bitset& a) const;
+ bool is_proper_subset_of(const dynamic_bitset& a) const;
+
+ void m_zero_unused_bits();
+
+
+private:
+ void set_(size_type bit);
+ bool set_(size_type bit, bool val);
+ void reset_(size_type bit);
+ bool test_(size_type bit) const;
+ void set_block_(size_type blocknum, Block b);
+
+public:
+
+ // This is templated on the whole String instead of just CharT,
+ // Traits, Alloc to avoid compiler bugs.
+ template <typename String>
+ void from_string(const String& s, typename String::size_type pos,
+ typename String::size_type rlen)
+ {
+ reset(); // bugfix [gps]
+ size_type const tot = std::min (rlen, s.length()); // bugfix [gps]
+
+ // Assumes string contains only 0's and 1's
+ for (size_type i = 0; i < tot; ++i) {
+ if (s[pos + tot - i - 1] == '1') {
+ set_(i);
+ } else {
+ AssertIf(s[pos + tot - i - 1] != '0');
+ }
+ }
+ }
+
+};
+
+// Global Functions:
+
+// comparison
+inline bool operator!=(const dynamic_bitset& a,
+ const dynamic_bitset& b);
+
+inline bool operator<=(const dynamic_bitset& a,
+ const dynamic_bitset& b);
+
+inline bool operator>(const dynamic_bitset& a,
+ const dynamic_bitset& b);
+
+inline bool operator>=(const dynamic_bitset& a,
+ const dynamic_bitset& b);
+
+// bitset operations
+inline dynamic_bitset
+operator&(const dynamic_bitset& b1,
+ const dynamic_bitset& b2);
+
+inline dynamic_bitset
+operator|(const dynamic_bitset& b1,
+ const dynamic_bitset& b2);
+
+inline dynamic_bitset
+operator^(const dynamic_bitset& b1,
+ const dynamic_bitset& b2);
+
+inline dynamic_bitset
+operator-(const dynamic_bitset& b1,
+ const dynamic_bitset& b2);
+
+
+template <typename String>
+void
+to_string(const dynamic_bitset& b,
+ String& s);
+
+template <typename BlockOutputIterator>
+void
+to_block_range(const dynamic_bitset& b,
+ BlockOutputIterator result);
+
+template <typename BlockIterator>
+inline void
+from_block_range(BlockIterator first, BlockIterator last,
+ dynamic_bitset& result);
+
+
+//=============================================================================
+// dynamic_bitset implementation
+
+
+//-----------------------------------------------------------------------------
+// constructors, etc.
+
+inline dynamic_bitset::dynamic_bitset()
+ : dynamic_bitset_base(0) { }
+
+inline dynamic_bitset::
+dynamic_bitset(size_type num_bits, unsigned long value)
+ : dynamic_bitset_base(num_bits)
+{
+ const size_type M = std::min(sizeof(unsigned long) * 8, num_bits);
+ for(size_type i = 0; i < M; ++i, value >>= 1) // [G.P.S.] to be optimized
+ if ( value & 0x1 )
+ set_(i);
+}
+
+// copy constructor
+inline dynamic_bitset::
+dynamic_bitset(const dynamic_bitset& b)
+ : dynamic_bitset_base(b.size())
+{
+ memcpy(this->m_bits, b.m_bits, this->m_num_blocks * sizeof(Block));
+}
+
+inline void dynamic_bitset::
+swap(dynamic_bitset& b)
+{
+ std::swap(this->m_bits, b.m_bits);
+ std::swap(this->m_num_bits, b.m_num_bits);
+ std::swap(this->m_num_blocks, b.m_num_blocks);
+}
+
+inline dynamic_bitset& dynamic_bitset::
+operator=(const dynamic_bitset& b)
+{
+ dynamic_bitset tmp(b);
+ this->swap(tmp);
+ return *this;
+}
+
+//-----------------------------------------------------------------------------
+// size changing operations
+
+inline void dynamic_bitset::
+resize(size_type num_bits, bool value)
+{
+ if (num_bits == size())
+ return;
+ if (num_bits == 0)
+ {
+ this->m_num_bits = 0;
+ this->m_num_blocks = 0;
+ delete this->m_bits;
+ this->m_bits = 0;
+ return;
+ }
+ size_type new_nblocks = this->calc_num_blocks(num_bits);
+ Block* d = new Block[new_nblocks];
+ if (num_bits < size()) { // shrink
+ std::copy(this->m_bits, this->m_bits + new_nblocks, d);
+ std::swap(d, this->m_bits);
+ delete []d;
+ } else { // grow
+ std::copy(this->m_bits, this->m_bits + this->m_num_blocks, d);
+ Block val = value? ~static_cast<Block>(0) : static_cast<Block>(0);
+ std::fill(d + this->m_num_blocks, d + new_nblocks, val);
+ std::swap(d, this->m_bits);
+ for (std::size_t i = this->m_num_bits;
+ i < this->m_num_blocks * bits_per_block; ++i)
+ set_(i, value);
+ if (d != 0)
+ delete []d;
+ }
+ this->m_num_bits = num_bits;
+ this->m_num_blocks = this->calc_num_blocks(num_bits);
+ m_zero_unused_bits();
+}
+
+inline void dynamic_bitset::
+clear()
+{
+ if (this->m_bits != 0) {
+ delete this->m_bits;
+ this->m_bits = 0;
+ this->m_num_bits = 0;
+ this->m_num_blocks = 0;
+ }
+}
+
+
+inline void dynamic_bitset::
+push_back(bool bit)
+{
+ this->resize(this->size() + 1);
+ set_(this->size() - 1, bit);
+}
+
+inline void dynamic_bitset::
+append(Block value)
+{
+ std::size_t old_size = size();
+ resize(old_size + bits_per_block);
+ if (size() % bits_per_block == 0)
+ set_block_(this->m_num_blocks - 1, value);
+ else {
+ // G.P.S. to be optimized
+ for (std::size_t i = old_size; i < size(); ++i, value >>= 1)
+ set_(i, value & 1);
+ }
+}
+
+
+//-----------------------------------------------------------------------------
+// bitset operations
+inline dynamic_bitset&
+dynamic_bitset::operator&=(const dynamic_bitset& rhs)
+{
+ AssertIf(size() != rhs.size());
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ this->m_bits[i] &= rhs.m_bits[i];
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::operator|=(const dynamic_bitset& rhs)
+{
+ AssertIf(size() != rhs.size());
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ this->m_bits[i] |= rhs.m_bits[i];
+ m_zero_unused_bits();
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::operator^=(const dynamic_bitset& rhs)
+{
+ AssertIf(size() != rhs.size());
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ this->m_bits[i] ^= rhs.m_bits[i];
+ m_zero_unused_bits();
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::operator-=(const dynamic_bitset& rhs)
+{
+ AssertIf(size() != rhs.size());
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ this->m_bits[i] = this->m_bits[i] & ~rhs.m_bits[i];
+ m_zero_unused_bits();
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::operator<<=(size_type n)
+{
+ if (n >= this->m_num_bits)
+ return reset();
+ //else
+ if (n > 0)
+ {
+ size_type const last = this->m_num_blocks - 1; // m_num_blocks is >= 1
+ size_type const div = n / bits_per_block; // div is <= last
+ size_type const r = n % bits_per_block;
+
+ // PRE: div != 0 or r != 0
+
+ if (r != 0) {
+
+ block_type const rs = bits_per_block - r;
+
+ for (size_type i = last-div; i>0; --i) {
+ this->m_bits[i+div] = (this->m_bits[i] << r) | (this->m_bits[i-1] >> rs);
+ }
+ this->m_bits[div] = this->m_bits[0] << r;
+
+ }
+ else {
+ for (size_type i = last-div; i>0; --i) {
+ this->m_bits[i+div] = this->m_bits[i];
+ }
+ this->m_bits[div] = this->m_bits[0];
+ }
+
+
+ // div blocks are zero filled at the less significant end
+ std::fill(this->m_bits, this->m_bits+div, static_cast<block_type>(0));
+
+
+ }
+
+ return *this;
+
+
+}
+
+
+
+
+
+
+
+// NOTE: this assumes that within a single block bits are
+// numbered from right to left. G.P.S.
+//
+// static Block offset(size_type bit)
+// { return bit % bits_per_block; }
+//
+//
+// In the implementation below the 'if (r != 0)' is logically
+// unnecessary. It's there as an optimization only: in fact
+// for r==0 the first branch becomes the second one with the
+// b[last-div] = b[last] >> r; statement that does the work of
+// the last iteration.
+//
+inline
+dynamic_bitset & dynamic_bitset::operator>>=(size_type n) {
+ if (n >= this->m_num_bits) {
+ return reset();
+ }
+ //else
+ if (n>0){
+
+ size_type const last = this->m_num_blocks - 1; // m_num_blocks is >= 1
+ size_type const div = n / bits_per_block; // div is <= last
+ size_type const r = n % bits_per_block;
+
+ // PRE: div != 0 or r != 0
+
+ if (r != 0) {
+
+ block_type const ls = bits_per_block - r;
+
+ for (size_type i = div; i < last; ++i) {
+ this->m_bits[i-div] = (this->m_bits[i] >> r) | (this->m_bits[i+1] << ls);
+ }
+ // r bits go to zero
+ this->m_bits[last-div] = this->m_bits[last] >> r;
+ }
+
+ else {
+ for (size_type i = div; i <= last; ++i) {
+ this->m_bits[i-div] = this->m_bits[i];
+ }
+ // note the '<=': the last iteration 'absorbs'
+ // this->m_bits[last-div] = this->m_bits[last] >> 0;
+ }
+
+
+
+ // div blocks are zero filled at the most significant end
+ std::fill(this->m_bits+(this->m_num_blocks-div), this->m_bits+this->m_num_blocks, static_cast<block_type>(0));
+ }
+
+ return *this;
+}
+
+
+
+
+
+
+
+inline dynamic_bitset
+dynamic_bitset::operator<<(size_type n) const
+{
+ dynamic_bitset r(*this);
+ return r <<= n;
+}
+
+inline dynamic_bitset
+dynamic_bitset::operator>>(size_type n) const
+{
+ dynamic_bitset r(*this);
+ return r >>= n;
+}
+
+
+//-----------------------------------------------------------------------------
+// basic bit operations
+
+inline dynamic_bitset&
+dynamic_bitset::set(size_type pos, bool val)
+{
+ AssertIf(pos >= this->m_num_bits);
+ set_(pos, val);
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::set()
+{
+ if (this->m_num_bits > 0) {
+ using namespace std;
+ memset(this->m_bits, ~0u, this->m_num_blocks * sizeof(this->m_bits[0]));
+ m_zero_unused_bits();
+ }
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::reset(size_type pos)
+{
+ AssertIf(pos >= this->m_num_bits);
+ reset_(pos);
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::reset()
+{
+ if (this->m_num_bits > 0) {
+ using namespace std;
+ memset(this->m_bits, 0, this->m_num_blocks * sizeof(this->m_bits[0]));
+ }
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::flip(size_type pos)
+{
+ AssertIf(pos >= this->m_num_bits);
+ this->m_bits[this->word(pos)] ^= this->mask1(pos);
+ return *this;
+}
+
+inline dynamic_bitset&
+dynamic_bitset::flip()
+{
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ this->m_bits[i] = ~this->m_bits[i];
+ m_zero_unused_bits();
+ return *this;
+}
+
+inline bool dynamic_bitset::test(size_type pos) const
+{
+ #if UNITY_EDITOR
+ if (pos < this->m_num_bits)
+ return test_(pos);
+ else
+ {
+ ErrorString("dynamic_bitset.test bit out of bounds");
+ return false;
+ }
+ #else
+ AssertIf(pos >= this->m_num_bits);
+ return test_(pos);
+ #endif
+}
+
+inline bool dynamic_bitset::any() const
+{
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ if (this->m_bits[i])
+ return 1;
+ return 0;
+}
+
+inline bool dynamic_bitset::none() const
+{
+ return !any();
+}
+
+inline dynamic_bitset
+dynamic_bitset::operator~() const
+{
+ dynamic_bitset b(*this);
+ b.flip();
+ return b;
+}
+
+
+/* snipped: [gps]
+
+The following is the straightforward implementation of count(), which
+we leave here in a comment for documentation purposes.
+
+template <typename Block, typename Allocator>
+typename dynamic_bitset::size_type
+dynamic_bitset::count() const
+{
+ size_type sum = 0;
+ for (size_type i = 0; i != this->m_num_bits; ++i)
+ if (test_(i))
+ ++sum;
+ return sum;
+}
+
+The actual algorithm used is based on using a lookup
+table.
+
+
+ The basic idea of the method is to pick up X bits at a time
+ from the internal array of blocks and consider those bits as
+ the binary representation of a number N. Then, to use a table
+ of 1<<X elements where table[N] is the number of '1' digits
+ in the binary representation of N (i.e. in our X bits).
+
+ Note that the table can be oversized (i.e. can even have more
+ than 1<<X elements; in that case only the first 1<<X will be
+ actually used) but it cannot be undersized.
+ In this implementation X is 8 (but can be easily changed: you
+ just have to change the definition of count<>::max_bits) and
+ the internal array of blocks is seen as an array of bytes: if
+ a byte has exactly 8 bits then it's enough to sum the value
+ of table[B] for each byte B. Otherwise 8 bits at a time are
+ 'extracted' from each byte by using another loop. As a further
+ efficiency consideration note that even if you have, let's say,
+ 32-bit chars the inner loop will not do 4 (i.e. 32/8) iterations,
+ unless you have at least one bit set in the highest 8 bits of the
+ byte.
+
+ Note also that the outmost if/else is not necessary but is there
+ to help the optimizer (and one of the two branches is always dead
+ code).
+
+ Aras: hardcoded table to be always max_bits=8. To help not so good compilers.
+
+*/
+
+
+inline dynamic_bitset::size_type
+dynamic_bitset::count() const
+{
+ const byte_t * p = reinterpret_cast<const byte_t*>(this->m_bits);
+ const byte_t * past_end = p + this->m_num_blocks * sizeof(Block);
+
+ size_type num = 0;
+
+ while (p < past_end) {
+ num += bitcount<>::table[*p];
+ ++p;
+ }
+
+ return num;
+}
+
+
+//-----------------------------------------------------------------------------
+// conversions
+
+// take as ref param instead?
+template <typename CharT, typename Alloc>
+void
+to_string(const dynamic_bitset& b,
+ std::basic_string<CharT, Alloc>& s)
+{
+ s.assign(b.size(), '0');
+ for (std::size_t i = 0; i < b.size(); ++i)
+ if (b.test(i)) // [G.P.S.]
+ s[b.size() - 1 - i] = '1';
+}
+
+
+// Differently from to_string this function dumps out
+// every bit of the internal representation (useful
+// for debugging purposes)
+//
+template <typename CharT, typename Alloc>
+void
+dump_to_string(const dynamic_bitset& b,
+ std::basic_string<CharT, Alloc>& s)
+{
+ std::size_t const len = b.m_num_blocks * (dynamic_bitset::bits_per_block);
+ s.assign(len, '0');
+ for (std::size_t i = 0; i != len; ++i)
+ if (b[i])// could use test_ here, but we have friend issues.-JGS
+ s[len - 1 - i] = '1';
+}
+
+
+
+template <typename BlockOutputIterator>
+void
+to_block_range(const dynamic_bitset& b,
+ BlockOutputIterator result)
+{
+ AssertIf(!(b.size() != 0 || b.num_blocks() == 0));
+ std::copy (b.m_bits, b.m_bits + b.m_num_blocks, result);
+}
+
+template <typename BlockIterator>
+inline void
+from_block_range(BlockIterator first, BlockIterator last,
+ dynamic_bitset& result)
+{
+ AssertIf(std::distance(first, last) != result.num_blocks());
+ std::copy (first, last, result.m_bits);
+ result.m_zero_unused_bits ();
+}
+
+inline dynamic_bitset::size_type
+dynamic_bitset::size() const
+{
+ return this->m_num_bits;
+}
+
+inline dynamic_bitset::size_type
+dynamic_bitset::num_blocks() const
+{
+ return this->m_num_blocks;
+}
+
+inline bool dynamic_bitset::
+is_subset_of(const dynamic_bitset& a) const
+{
+ AssertIf(this->size() != a.size());
+ for (size_type i = 0; i < this->m_num_blocks; ++i)
+ if (this->m_bits[i] & ~a.m_bits[i])
+ return false;
+ return true;
+}
+
+inline bool dynamic_bitset::
+is_proper_subset_of(const dynamic_bitset& a) const
+{
+ AssertIf(this->size() != a.size());
+ bool proper = false;
+ for (size_type i = 0; i < this->m_num_blocks; ++i) {
+ Block bt = this->m_bits[i], ba = a.m_bits[i];
+ if (ba & ~bt)
+ proper = true;
+ if (bt & ~ba)
+ return false;
+ }
+ return proper;
+}
+
+//-----------------------------------------------------------------------------
+// comparison
+
+inline bool operator==(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ using namespace std;
+ return (a.m_num_bits == b.m_num_bits) &&
+ ((a.m_num_bits == 0) ||
+ !memcmp(a.m_bits, b.m_bits, a.m_num_blocks * sizeof(a.m_bits[0])));
+}
+
+inline bool operator!=(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ return !(a == b);
+}
+
+inline bool operator<(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ AssertIf(a.size() != b.size());
+ typedef dynamic_bitset::size_type size_type;
+
+ if (a.size() == 0)
+ return false;
+
+ // Since we are storing the most significant bit
+ // at pos == size() - 1, we need to do the memcmp in reverse.
+
+ // Compare a block at a time
+ for (size_type i = a.m_num_blocks - 1; i > 0; --i)
+ if (a.m_bits[i] < b.m_bits[i])
+ return true;
+ else if (a.m_bits[i] > b.m_bits[i])
+ return false;
+
+ if (a.m_bits[0] < b.m_bits[0])
+ return true;
+ else
+ return false;
+}
+
+inline bool operator<=(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ return !(a > b);
+}
+
+inline bool operator>(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ AssertIf(a.size() != b.size());
+ typedef dynamic_bitset::size_type size_type;
+
+ if (a.size() == 0)
+ return false;
+
+ // Since we are storing the most significant bit
+ // at pos == size() - 1, we need to do the memcmp in reverse.
+
+ // Compare a block at a time
+ for (size_type i = a.m_num_blocks - 1; i > 0; --i)
+ if (a.m_bits[i] < b.m_bits[i])
+ return false;
+ else if (a.m_bits[i] > b.m_bits[i])
+ return true;
+
+ if (a.m_bits[0] > b.m_bits[0])
+ return true;
+ else
+ return false;
+}
+
+inline bool operator>=(const dynamic_bitset& a,
+ const dynamic_bitset& b)
+{
+ return !(a < b);
+}
+
+//-----------------------------------------------------------------------------
+// bitset operations
+
+inline dynamic_bitset
+operator&(const dynamic_bitset& x,
+ const dynamic_bitset& y)
+{
+ dynamic_bitset b(x);
+ return b &= y;
+}
+
+inline dynamic_bitset
+operator|(const dynamic_bitset& x,
+ const dynamic_bitset& y)
+{
+ dynamic_bitset b(x);
+ return b |= y;
+}
+
+inline dynamic_bitset
+operator^(const dynamic_bitset& x,
+ const dynamic_bitset& y)
+{
+ dynamic_bitset b(x);
+ return b ^= y;
+}
+
+inline dynamic_bitset
+operator-(const dynamic_bitset& x,
+ const dynamic_bitset& y)
+{
+ dynamic_bitset b(x);
+ return b -= y;
+}
+
+
+//-----------------------------------------------------------------------------
+// private member functions
+
+inline void dynamic_bitset::
+set_(size_type bit)
+{
+ this->m_bits[this->word(bit)] |= this->mask1(bit);
+}
+
+inline void dynamic_bitset::
+set_block_(size_type blocknum, Block value)
+{
+ this->m_bits[blocknum] = value;
+}
+
+inline void dynamic_bitset::
+reset_(size_type b)
+{
+ this->m_bits[this->word(b)] &= this->mask0(b);
+}
+
+inline bool dynamic_bitset::test_(size_type b) const
+{
+ return (this->m_bits[this->word(b)] & this->mask1(b)) != static_cast<Block>(0);
+}
+
+inline bool dynamic_bitset::set_(size_type n, bool value)
+{
+ if (value)
+ set_(n);
+ else
+ reset_(n);
+ return value != static_cast<Block>(0);
+}
+
+
+// If size() is not a multiple of bits_per_block
+// then not all the bits in the last block are used.
+// This function resets the unused bits (convenient
+// for the implementation of many member functions)
+//
+inline void dynamic_bitset::m_zero_unused_bits()
+{
+ AssertIf (this->m_num_blocks != this->calc_num_blocks(this->m_num_bits));
+
+ // if != 0 this is the number of bits used in the last block
+ const size_type used_bits = this->m_num_bits % bits_per_block;
+
+ if (used_bits != 0)
+ this->m_bits[this->m_num_blocks - 1] &= ~(~static_cast<Block>(0) << used_bits);
+
+}
+
+#endif
generated by cgit v1.1-26-g67d0 at 2025-05-18 20:10:32 +0000