diff options
Diffstat (limited to 'source/modules/asura-utils/dynamic_bitset.h')
| -rw-r--r-- | source/modules/asura-utils/dynamic_bitset.h | 1150 |
1 files changed, 0 insertions, 1150 deletions
diff --git a/source/modules/asura-utils/dynamic_bitset.h b/source/modules/asura-utils/dynamic_bitset.h deleted file mode 100644 index 2b04d07..0000000 --- a/source/modules/asura-utils/dynamic_bitset.h +++ /dev/null @@ -1,1150 +0,0 @@ -#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 "Type.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 - Assert(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 ASURA_EDITOR - if (pos < this->m_num_bits) - return test_(pos); - else - { - //ErrorString("dynamic_bitset.test bit out of bounds"); - return false; - } -#else -#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 { - Assert(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) -{ - Assert(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) -{ - Assert(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) -{ - Assert(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) -{ - Assert(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) -{ - Assert(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) -{ - Assert(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) -{ - Assert(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 ASURA_EDITOR - if (pos < this->m_num_bits) - return test_(pos); - else - { - //ErrorString("dynamic_bitset.test bit out of bounds"); - return false; - } -#else - Assert(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) -{ - Assert(!(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) -{ - Assert(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 -{ - Assert(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 -{ - Assert(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) -{ - Assert(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) -{ - Assert(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() -{ - Assert(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 |