From 2e4d666eec1a372d4b64c527d6c4945ad98d2b58 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 16 Sep 2022 21:19:57 -0400 Subject: Update clang-format configuration --- include/chilbert/detail/BitVecIndex.hpp | 31 +- include/chilbert/detail/BitVecIterator.hpp | 79 ++-- include/chilbert/detail/BitVecMask.hpp | 58 ++- include/chilbert/detail/MultiBitVec.hpp | 672 ++++++++++++++--------------- include/chilbert/detail/gray_code_rank.hpp | 220 +++++----- include/chilbert/detail/operations.hpp | 92 ++-- include/chilbert/detail/traits.hpp | 9 +- 7 files changed, 579 insertions(+), 582 deletions(-) (limited to 'include/chilbert/detail') diff --git a/include/chilbert/detail/BitVecIndex.hpp b/include/chilbert/detail/BitVecIndex.hpp index c8d0469..c337c70 100644 --- a/include/chilbert/detail/BitVecIndex.hpp +++ b/include/chilbert/detail/BitVecIndex.hpp @@ -27,22 +27,21 @@ namespace chilbert { namespace detail { /// Index into a multi-rack bit vector -template -struct BitVecIndex -{ - using Rack = typename BitVec::Rack; - - static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; - - explicit BitVecIndex(const size_t bits) - : rack{bits / bits_per_rack} - , bit{bits - rack * bits_per_rack} - { - assert(bit < bits_per_rack); - } - - size_t rack; - size_t bit; +template +struct BitVecIndex { + using Rack = typename BitVec::Rack; + + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + + explicit BitVecIndex(const size_t bits) + : rack{bits / bits_per_rack} + , bit{bits - rack * bits_per_rack} + { + assert(bit < bits_per_rack); + } + + size_t rack; + size_t bit; }; } // namespace detail diff --git a/include/chilbert/detail/BitVecIterator.hpp b/include/chilbert/detail/BitVecIterator.hpp index 2458da9..43af2ee 100644 --- a/include/chilbert/detail/BitVecIterator.hpp +++ b/include/chilbert/detail/BitVecIterator.hpp @@ -26,72 +26,69 @@ namespace chilbert { namespace detail { -template +template class BitVecIteratorBase : public BitVecMask { public: - using Mask = typename BitVec::Mask; + using Mask = typename BitVec::Mask; - BitVecIteratorBase& operator++() - { - Mask::operator++(); - return *this; - } + BitVecIteratorBase& operator++() + { + Mask::operator++(); + return *this; + } - BitVecIteratorBase& operator--() - { - Mask::operator--(); - return *this; - } + BitVecIteratorBase& operator--() + { + Mask::operator--(); + return *this; + } - bool operator==(const BitVecIteratorBase& rhs) const - { - return m_vec == rhs.m_vec && Mask::operator==(rhs); - } + bool operator==(const BitVecIteratorBase& rhs) const + { + return m_vec == rhs.m_vec && Mask::operator==(rhs); + } - bool operator!=(const BitVecIteratorBase& rhs) const - { - return !operator==(rhs); - } + bool operator!=(const BitVecIteratorBase& rhs) const + { + return !operator==(rhs); + } - bool operator*() const { return m_vec->test(*this); } + bool operator*() const { return m_vec->test(*this); } protected: - BitVecIteratorBase(BitVec& vec, const size_t index) - : Mask{index} - , m_vec{&vec} - { - } + BitVecIteratorBase(BitVec& vec, const size_t index) + : Mask{index} + , m_vec{&vec} + {} - BitVec* m_vec; + BitVec* m_vec; }; -template +template class BitVecIterator : public BitVecIteratorBase { public: - void set() { this->m_vec->set(*this); } - void reset() { this->m_vec->reset(*this); } + void set() { this->m_vec->set(*this); } + void reset() { this->m_vec->reset(*this); } private: - friend BitVec; + friend BitVec; - BitVecIterator(BitVec& vec, const size_t index) - : BitVecIteratorBase{vec, index} - { - } + BitVecIterator(BitVec& vec, const size_t index) + : BitVecIteratorBase{vec, index} + {} }; -template +template class ConstBitVecIterator : public BitVecIteratorBase { private: - friend BitVec; + friend BitVec; - ConstBitVecIterator(const BitVec& vec, const size_t index) - : BitVecIteratorBase{vec, index} - { - } + ConstBitVecIterator(const BitVec& vec, const size_t index) + : BitVecIteratorBase{vec, index} + {} }; } // namespace detail diff --git a/include/chilbert/detail/BitVecMask.hpp b/include/chilbert/detail/BitVecMask.hpp index 5674114..855e4f3 100644 --- a/include/chilbert/detail/BitVecMask.hpp +++ b/include/chilbert/detail/BitVecMask.hpp @@ -30,42 +30,40 @@ namespace detail { * This enables fast iteration while setting or resetting bits since it is * internally stored as a mask which avoids repeated index math. */ -template -struct BitVecMask -{ - static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; +template +struct BitVecMask { + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; - explicit BitVecMask(const size_t index) - : rack{index / bits_per_rack} - , mask{Rack{1} << (index - rack * bits_per_rack)} - { - } + explicit BitVecMask(const size_t index) + : rack{index / bits_per_rack} + , mask{Rack{1} << (index - rack * bits_per_rack)} + {} - void operator++() - { - if ((mask <<= 1U) == 0U) { - mask = 1U; - ++rack; - } - } + void operator++() + { + if ((mask <<= 1U) == 0U) { + mask = 1U; + ++rack; + } + } - void operator--() - { - if ((mask >>= 1U) == 0U) { - mask = Rack{1} << (bits_per_rack - 1U); - --rack; - } - } + void operator--() + { + if ((mask >>= 1U) == 0U) { + mask = Rack{1} << (bits_per_rack - 1U); + --rack; + } + } - bool operator==(const BitVecMask& rhs) const - { - return rack == rhs.rack && mask == rhs.mask; - } + bool operator==(const BitVecMask& rhs) const + { + return rack == rhs.rack && mask == rhs.mask; + } - bool operator!=(const BitVecMask& rhs) const { return !operator==(rhs); } + bool operator!=(const BitVecMask& rhs) const { return !operator==(rhs); } - size_t rack; - Rack mask; + size_t rack; + Rack mask; }; } // namespace detail diff --git a/include/chilbert/detail/MultiBitVec.hpp b/include/chilbert/detail/MultiBitVec.hpp index 6db1065..e8ae08a 100644 --- a/include/chilbert/detail/MultiBitVec.hpp +++ b/include/chilbert/detail/MultiBitVec.hpp @@ -33,358 +33,358 @@ namespace chilbert { namespace detail { -template +template class MultiBitVec { public: - using Rack = uintptr_t; - using Mask = BitVecMask; - - using iterator = BitVecIterator>; - using const_iterator = ConstBitVecIterator>; - - static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; - - /// Return the value of the bit covered by `mask` - bool test(const Mask mask) const { return rack(mask.rack) & mask.mask; } - - /// Return the value of the `index`th bit - bool test(const size_t index) const { return test(mask(index)); } - - /// Set all bits to one - Derived& set() - { - if (size()) { - memset(data(), 0xFF, data_size()); - self()->truncate(); - } - - return *self(); - } - - /// Set the bit covered by `mask` to 1 - Derived& set(const Mask mask) - { - rack(mask.rack) |= mask.mask; - return *self(); - } - - /// Set the `index`th bit to 1 - Derived& set(const size_t index) { return set(mask(index)); } - - /// Set the bit covered by `mask` to `value` - Derived& set(const Mask mask, const bool value) - { - auto& r = rack(mask.rack); - r ^= (-Rack{value} ^ r) & mask.mask; - return *self(); - } - - /// Set the `index`th bit to `value` - Derived& set(const size_t index, const bool value) - { - return set(mask(index), value); - } - - /// Set all bits to zero - Derived& reset() - { - memset(data(), 0, data_size()); - return *self(); - } - - /// Reset the bit covered by `mask` to 0 - Derived& reset(const Mask mask) - { - rack(mask.rack) &= ~mask.mask; - return *self(); - } - - /// Reset the `index`th bit to 0 - Derived& reset(const size_t index) { return reset(mask(index)); } - - /// Flip all bits (one's complement) - Derived& flip() - { - for (size_t i = 0; i < num_racks(); ++i) { - rack(i) = ~rack(i); - } - return *self(); - } - - /// Flip the value of the bit covered by `mask` - Derived& flip(const Mask mask) - { - rack(mask.rack) ^= mask.mask; - return *self(); - } - - /// Flip the value of the `index`th bit - Derived& flip(const size_t index) { return flip(mask(index)); } - - /// Clear any bits in storage outside the valid range if necessary - void truncate() - { - if (const auto pad = num_racks() * bits_per_rack - size()) { - rack(num_racks() - 1) &= ~Rack{0} >> pad; - } - } - - /// Right-rotate by `bits` positions - Derived& rotr(const size_t bits) - { - assert(bits <= size()); - if (bits == 0 || bits == size()) { - return *self(); - } - - Derived t1(*self()); - *self() >>= bits; - t1 <<= (size() - bits); - *self() |= t1; - - truncate(); - return *self(); - } - - /// Left-rotate by `bits` positions - Derived& rotl(const size_t bits) - { - assert(bits <= size()); - if (bits == 0 || bits == size()) { - return *self(); - } - - Derived t1(*self()); - *self() <<= bits; - t1 >>= (size() - bits); - *self() |= t1; - - truncate(); - return *self(); - } - - /// Return true iff all bits are zero - bool none() const - { - for (size_t i = 0; i < num_racks(); ++i) { - if (rack(i)) { - return false; - } - } - return true; - } - - /// Return 1 + the index of the first set bit, or 0 if there are none - size_t find_first() const - { - for (size_t i = 0; i < num_racks(); ++i) { - const int j = chilbert::detail::find_first(rack(i)); - if (j) { - return (i * bits_per_rack) + static_cast(j); - } - } - return 0; - } - - /// Return the number of set bits - size_t count() const - { - size_t c = 0; - for (size_t i = 0; i < num_racks(); ++i) { - c += static_cast(pop_count(rack(i))); - } - return c; - } - - /// Return a mask that covers the bit with index `i` - Mask mask(const size_t i = 0) const - { - assert(i <= size()); - return Mask{i}; - } - - bool operator==(const Derived& vec) const - { - return (num_racks() == vec.num_racks() && - (num_racks() == 0 || - !memcmp(data(), vec.data(), num_racks() * sizeof(Rack)))); - } - - bool operator!=(const Derived& vec) const { return !(*this == vec); } - - bool operator<(const Derived& vec) const - { - assert(size() == vec.size()); - - for (size_t ri = 0; ri < num_racks(); ++ri) { - const size_t i = num_racks() - ri - 1; - if (rack(i) < vec.rack(i)) { - return true; - } - - if (rack(i) > vec.rack(i)) { - return false; - } - } - return false; - } - - Derived& operator&=(const Derived& vec) - { - for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { - rack(i) &= vec.rack(i); - } - - return *self(); - } - - Derived& operator|=(const Derived& vec) - { - for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { - rack(i) |= vec.rack(i); - } - - return *self(); - } - - Derived& operator^=(const Derived& vec) - { - for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { - rack(i) ^= vec.rack(i); - } - - return *self(); - } - - Derived& operator<<=(const size_t bits) - { - if (bits == 0) { - return *self(); - } - - if (bits >= size()) { - reset(); - return *self(); - } - - const Index index{bits}; - - if (index.bit == 0) { - // Simple rack-aligned shift - for (size_t i = num_racks() - 1; i >= index.rack; --i) { - rack(i) = rack(i - index.rack); - } - } else { - // Rack + bit offset shift - const size_t right_shift = bits_per_rack - index.bit; - for (size_t i = num_racks() - index.rack - 1; i > 0; --i) { - rack(i + index.rack) = - (rack(i) << index.bit) | (rack(i - 1) >> right_shift); - } - - rack(index.rack) = rack(0) << index.bit; - } - - // Zero least significant racks - for (size_t i = 0; i < index.rack; ++i) { - rack(i) = 0; - } - - return *self(); - } - - Derived& operator>>=(const size_t bits) - { - if (bits == 0) { - return *self(); - } - - if (bits >= size()) { - reset(); - return *self(); - } - - const Index index{bits}; - - if (index.bit == 0) { - // Simple rack-aligned shift - for (size_t i = 0; i < num_racks() - index.rack; ++i) { - rack(i) = rack(i + index.rack); - } - } else { - // Rack + bit offset shift - const size_t last = num_racks() - 1; - const size_t left_shift = bits_per_rack - index.bit; - for (size_t i = index.rack; i < last; ++i) { - rack(i - index.rack) = - (rack(i) >> index.bit) | (rack(i + 1) << left_shift); - } - - rack(last - index.rack) = rack(last) >> index.bit; - } - - // Zero most significant racks - for (size_t i = num_racks() - index.rack; i < num_racks(); ++i) { - rack(i) = 0; - } - - return *self(); - } - - auto begin(const size_t i = 0) { return iterator(*self(), i); } - auto end() { return iterator(*self(), size()); } - auto begin(const size_t i = 0) const { return const_iterator(*self(), i); } - auto end() const { return const_iterator(self(), size()); } - - const Rack& rack(const size_t index) const { return self()->rack(index); } - Rack& rack(const size_t index) { return self()->rack(index); } - Rack* data() { return self()->data(); } - const Rack* data() const { return self()->data(); } - size_t num_racks() const { return self()->num_racks(); } - size_t size() const { return self()->size(); } - size_t data_size() const { return self()->data_size(); } + using Rack = uintptr_t; + using Mask = BitVecMask; + + using iterator = BitVecIterator>; + using const_iterator = ConstBitVecIterator>; + + static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + + /// Return the value of the bit covered by `mask` + bool test(const Mask mask) const { return rack(mask.rack) & mask.mask; } + + /// Return the value of the `index`th bit + bool test(const size_t index) const { return test(mask(index)); } + + /// Set all bits to one + Derived& set() + { + if (size()) { + memset(data(), 0xFF, data_size()); + self()->truncate(); + } + + return *self(); + } + + /// Set the bit covered by `mask` to 1 + Derived& set(const Mask mask) + { + rack(mask.rack) |= mask.mask; + return *self(); + } + + /// Set the `index`th bit to 1 + Derived& set(const size_t index) { return set(mask(index)); } + + /// Set the bit covered by `mask` to `value` + Derived& set(const Mask mask, const bool value) + { + auto& r = rack(mask.rack); + r ^= (-Rack{value} ^ r) & mask.mask; + return *self(); + } + + /// Set the `index`th bit to `value` + Derived& set(const size_t index, const bool value) + { + return set(mask(index), value); + } + + /// Set all bits to zero + Derived& reset() + { + memset(data(), 0, data_size()); + return *self(); + } + + /// Reset the bit covered by `mask` to 0 + Derived& reset(const Mask mask) + { + rack(mask.rack) &= ~mask.mask; + return *self(); + } + + /// Reset the `index`th bit to 0 + Derived& reset(const size_t index) { return reset(mask(index)); } + + /// Flip all bits (one's complement) + Derived& flip() + { + for (size_t i = 0; i < num_racks(); ++i) { + rack(i) = ~rack(i); + } + return *self(); + } + + /// Flip the value of the bit covered by `mask` + Derived& flip(const Mask mask) + { + rack(mask.rack) ^= mask.mask; + return *self(); + } + + /// Flip the value of the `index`th bit + Derived& flip(const size_t index) { return flip(mask(index)); } + + /// Clear any bits in storage outside the valid range if necessary + void truncate() + { + if (const auto pad = num_racks() * bits_per_rack - size()) { + rack(num_racks() - 1) &= ~Rack{0} >> pad; + } + } + + /// Right-rotate by `bits` positions + Derived& rotr(const size_t bits) + { + assert(bits <= size()); + if (bits == 0 || bits == size()) { + return *self(); + } + + Derived t1(*self()); + *self() >>= bits; + t1 <<= (size() - bits); + *self() |= t1; + + truncate(); + return *self(); + } + + /// Left-rotate by `bits` positions + Derived& rotl(const size_t bits) + { + assert(bits <= size()); + if (bits == 0 || bits == size()) { + return *self(); + } + + Derived t1(*self()); + *self() <<= bits; + t1 >>= (size() - bits); + *self() |= t1; + + truncate(); + return *self(); + } + + /// Return true iff all bits are zero + bool none() const + { + for (size_t i = 0; i < num_racks(); ++i) { + if (rack(i)) { + return false; + } + } + return true; + } + + /// Return 1 + the index of the first set bit, or 0 if there are none + size_t find_first() const + { + for (size_t i = 0; i < num_racks(); ++i) { + const int j = chilbert::detail::find_first(rack(i)); + if (j) { + return (i * bits_per_rack) + static_cast(j); + } + } + return 0; + } + + /// Return the number of set bits + size_t count() const + { + size_t c = 0; + for (size_t i = 0; i < num_racks(); ++i) { + c += static_cast(pop_count(rack(i))); + } + return c; + } + + /// Return a mask that covers the bit with index `i` + Mask mask(const size_t i = 0) const + { + assert(i <= size()); + return Mask{i}; + } + + bool operator==(const Derived& vec) const + { + return (num_racks() == vec.num_racks() && + (num_racks() == 0 || + !memcmp(data(), vec.data(), num_racks() * sizeof(Rack)))); + } + + bool operator!=(const Derived& vec) const { return !(*this == vec); } + + bool operator<(const Derived& vec) const + { + assert(size() == vec.size()); + + for (size_t ri = 0; ri < num_racks(); ++ri) { + const size_t i = num_racks() - ri - 1; + if (rack(i) < vec.rack(i)) { + return true; + } + + if (rack(i) > vec.rack(i)) { + return false; + } + } + return false; + } + + Derived& operator&=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) &= vec.rack(i); + } + + return *self(); + } + + Derived& operator|=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) |= vec.rack(i); + } + + return *self(); + } + + Derived& operator^=(const Derived& vec) + { + for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) { + rack(i) ^= vec.rack(i); + } + + return *self(); + } + + Derived& operator<<=(const size_t bits) + { + if (bits == 0) { + return *self(); + } + + if (bits >= size()) { + reset(); + return *self(); + } + + const Index index{bits}; + + if (index.bit == 0) { + // Simple rack-aligned shift + for (size_t i = num_racks() - 1; i >= index.rack; --i) { + rack(i) = rack(i - index.rack); + } + } else { + // Rack + bit offset shift + const size_t right_shift = bits_per_rack - index.bit; + for (size_t i = num_racks() - index.rack - 1; i > 0; --i) { + rack(i + index.rack) = + (rack(i) << index.bit) | (rack(i - 1) >> right_shift); + } + + rack(index.rack) = rack(0) << index.bit; + } + + // Zero least significant racks + for (size_t i = 0; i < index.rack; ++i) { + rack(i) = 0; + } + + return *self(); + } + + Derived& operator>>=(const size_t bits) + { + if (bits == 0) { + return *self(); + } + + if (bits >= size()) { + reset(); + return *self(); + } + + const Index index{bits}; + + if (index.bit == 0) { + // Simple rack-aligned shift + for (size_t i = 0; i < num_racks() - index.rack; ++i) { + rack(i) = rack(i + index.rack); + } + } else { + // Rack + bit offset shift + const size_t last = num_racks() - 1; + const size_t left_shift = bits_per_rack - index.bit; + for (size_t i = index.rack; i < last; ++i) { + rack(i - index.rack) = + (rack(i) >> index.bit) | (rack(i + 1) << left_shift); + } + + rack(last - index.rack) = rack(last) >> index.bit; + } + + // Zero most significant racks + for (size_t i = num_racks() - index.rack; i < num_racks(); ++i) { + rack(i) = 0; + } + + return *self(); + } + + auto begin(const size_t i = 0) { return iterator(*self(), i); } + auto end() { return iterator(*self(), size()); } + auto begin(const size_t i = 0) const { return const_iterator(*self(), i); } + auto end() const { return const_iterator(self(), size()); } + + const Rack& rack(const size_t index) const { return self()->rack(index); } + Rack& rack(const size_t index) { return self()->rack(index); } + Rack* data() { return self()->data(); } + const Rack* data() const { return self()->data(); } + size_t num_racks() const { return self()->num_racks(); } + size_t size() const { return self()->size(); } + size_t data_size() const { return self()->data_size(); } private: - using Index = detail::BitVecIndex; + using Index = detail::BitVecIndex; - Derived* self() { return static_cast(this); } - const Derived* self() const { return static_cast(this); } + Derived* self() { return static_cast(this); } + const Derived* self() const { return static_cast(this); } }; -template +template void gray_code(MultiBitVec& value) { - typename MultiBitVec::Rack s = 0; - - constexpr size_t left_shift = MultiBitVec::bits_per_rack - 1; - for (size_t ri = 0; ri < value.num_racks(); ++ri) { - const size_t i = value.num_racks() - ri - 1U; - auto& rack = value.rack(i); - const auto t = rack & 1U; - gray_code(rack); - rack ^= (s << left_shift); - s = t; - } + typename MultiBitVec::Rack s = 0; + + constexpr size_t left_shift = MultiBitVec::bits_per_rack - 1; + for (size_t ri = 0; ri < value.num_racks(); ++ri) { + const size_t i = value.num_racks() - ri - 1U; + auto& rack = value.rack(i); + const auto t = rack & 1U; + gray_code(rack); + rack ^= (s << left_shift); + s = t; + } } -template +template void gray_code_inv(MultiBitVec& value) { - using Rack = typename MultiBitVec::Rack; - - constexpr std::array masks{Rack{0}, ~Rack{0}}; - bool s = false; - - for (size_t ri = 0; ri < value.num_racks(); ++ri) { - const size_t i = value.num_racks() - ri - 1; - auto& rack = value.rack(i); - gray_code_inv(rack); - rack ^= masks[s]; - s = rack & 1U; - } + using Rack = typename MultiBitVec::Rack; + + constexpr std::array masks{Rack{0}, ~Rack{0}}; + bool s = false; + + for (size_t ri = 0; ri < value.num_racks(); ++ri) { + const size_t i = value.num_racks() - ri - 1; + auto& rack = value.rack(i); + gray_code_inv(rack); + rack ^= masks[s]; + s = rack & 1U; + } } } // namespace detail diff --git a/include/chilbert/detail/gray_code_rank.hpp b/include/chilbert/detail/gray_code_rank.hpp index b6811ff..a326617 100644 --- a/include/chilbert/detail/gray_code_rank.hpp +++ b/include/chilbert/detail/gray_code_rank.hpp @@ -30,7 +30,7 @@ namespace detail { // a Compact Hilbert Index. It compresses a previously // calculated index when provided the rotation // at each level of precision. -template +template inline void compact_index(const size_t* const ms, const size_t* const ds, @@ -39,60 +39,60 @@ compact_index(const size_t* const ms, H& h, HC& hc) { - assert(h.size() >= n * m); - assert(hc.size() >= std::accumulate(ms, ms + n, size_t(0))); - - reset_bits(hc); - - auto hm = h.mask(0); - auto hcm = hc.mask(0); - - // Run through the levels of precision - for (size_t i = 0; i < m; ++i) { - // Run through the dimensions - size_t j = ds[i]; - do { - // This dimension contributes a bit? - if (ms[j] > i) { - if (h.test(hm)) { - hc.set(hcm); - } - ++hcm; - } - - if (++j == n) { - j = 0; - } - ++hm; - } while (j != ds[i]); - } + assert(h.size() >= n * m); + assert(hc.size() >= std::accumulate(ms, ms + n, size_t(0))); + + reset_bits(hc); + + auto hm = h.mask(0); + auto hcm = hc.mask(0); + + // Run through the levels of precision + for (size_t i = 0; i < m; ++i) { + // Run through the dimensions + size_t j = ds[i]; + do { + // This dimension contributes a bit? + if (ms[j] > i) { + if (h.test(hm)) { + hc.set(hcm); + } + ++hcm; + } + + if (++j == n) { + j = 0; + } + ++hm; + } while (j != ds[i]); + } } -template +template inline void gray_code_rank(const I& mask, const I& gi, const size_t n, I& r) { - assert(mask.size() == n); - assert(gi.size() == n); - assert(r.size() == n); - - r.reset(); - - auto mi = mask.begin(); - auto gii = gi.begin(); - auto ri = r.begin(); - - for (size_t i = 0; i < n; ++i, ++mi, ++gii) { - if (*mi) { - if (*gii) { - ri.set(); - } - ++ri; - } - } + assert(mask.size() == n); + assert(gi.size() == n); + assert(r.size() == n); + + r.reset(); + + auto mi = mask.begin(); + auto gii = gi.begin(); + auto ri = r.begin(); + + for (size_t i = 0; i < n; ++i, ++mi, ++gii) { + if (*mi) { + if (*gii) { + ri.set(); + } + ++ri; + } + } } -template +template inline void gray_code_rank_inv(const I& mask, const I& ptrn, @@ -102,51 +102,51 @@ gray_code_rank_inv(const I& mask, I& g, I& gi) { - assert(mask.size() == n); - assert(ptrn.size() == n); - assert(r.size() == n); - assert(g.size() == n); - assert(gi.size() == n); - - g.reset(); - gi.reset(); - - auto m = mask.mask(n - 1); - auto ri = r.begin(b - 1); - - typename I::Rack gi0 = 0; - typename I::Rack gi1 = 0; - typename I::Rack g0 = 0; - - for (size_t i = 0; i < n; ++i) { - if (mask.test(m)) { // Unconstrained bit - gi1 = gi0; - gi0 = *ri; - g0 = gi0 ^ gi1; - if (gi0) { - gi.set(m); - } - if (g0) { - g.set(m); - } - --ri; - } else { // Constrained bit - g0 = (ptrn.test(m) > 0); - gi1 = gi0; - gi0 = g0 ^ gi1; - if (gi0) { - gi.set(m); - } - if (g0) { - g.set(m); - } - } - - --m; - } + assert(mask.size() == n); + assert(ptrn.size() == n); + assert(r.size() == n); + assert(g.size() == n); + assert(gi.size() == n); + + g.reset(); + gi.reset(); + + auto m = mask.mask(n - 1); + auto ri = r.begin(b - 1); + + typename I::Rack gi0 = 0; + typename I::Rack gi1 = 0; + typename I::Rack g0 = 0; + + for (size_t i = 0; i < n; ++i) { + if (mask.test(m)) { // Unconstrained bit + gi1 = gi0; + gi0 = *ri; + g0 = gi0 ^ gi1; + if (gi0) { + gi.set(m); + } + if (g0) { + g.set(m); + } + --ri; + } else { // Constrained bit + g0 = (ptrn.test(m) > 0); + gi1 = gi0; + gi0 = g0 ^ gi1; + if (gi0) { + gi.set(m); + } + if (g0) { + g.set(m); + } + } + + --m; + } } -template +template inline void extract_mask(const size_t* const ms, const size_t n, @@ -155,25 +155,25 @@ extract_mask(const size_t* const ms, I& mask, size_t& b) { - assert(d < n); - assert(mask.size() == n); - - mask.reset(); - b = 0; - - auto mi = mask.begin(); - size_t j = d; // #D j = (d==n-1) ? 0 : d+1; - do { - if (ms[j] > i) { - mi.set(); - ++b; - } - - ++mi; - if (++j == n) { - j = 0; - } - } while (j != d); + assert(d < n); + assert(mask.size() == n); + + mask.reset(); + b = 0; + + auto mi = mask.begin(); + size_t j = d; // #D j = (d==n-1) ? 0 : d+1; + do { + if (ms[j] > i) { + mi.set(); + ++b; + } + + ++mi; + if (++j == n) { + j = 0; + } + } while (j != d); } } // namespace detail diff --git a/include/chilbert/detail/operations.hpp b/include/chilbert/detail/operations.hpp index a196ba4..ed9dfac 100644 --- a/include/chilbert/detail/operations.hpp +++ b/include/chilbert/detail/operations.hpp @@ -32,135 +32,139 @@ namespace chilbert { namespace detail { /// Reset all bits in `field` -template +template std::enable_if_t::value> reset_bits(T& field) { - field = static_cast(0); + field = static_cast(0); } /// Reset all bits in `field` -template +template std::enable_if_t> reset_bits(T& field) { - field.reset(); + field.reset(); } /// Return the `index`th bit in `field` -template +template std::enable_if_t::value, bool> test_bit(const T& field, const size_t index) { - assert(size_t(index) < sizeof(field) * CHAR_BIT); - return field & (T{1} << index); + assert(size_t(index) < sizeof(field) * CHAR_BIT); + return field & (T{1} << index); } /// Return the `index`th bit in `field` -template +template std::enable_if_t, bool> test_bit(const T& field, const size_t index) { - return field.test(index); + return field.test(index); } /// Set the `index`th bit in `field` -template +template std::enable_if_t::value> set_bit(T& field, const size_t index) { - assert(size_t(index) < sizeof(field) * CHAR_BIT); - field |= (T{1} << index); - assert(test_bit(field, index)); + assert(size_t(index) < sizeof(field) * CHAR_BIT); + field |= (T{1} << index); + assert(test_bit(field, index)); } /// Set the `index`th bit in `field` to `value` -template +template std::enable_if_t::value> set_bit(T& field, const size_t index, const bool value) { - assert(size_t(index) < sizeof(field) * CHAR_BIT); - field ^= (-T{value} ^ field) & (T{1U} << index); - assert(test_bit(field, index) == value); + assert(size_t(index) < sizeof(field) * CHAR_BIT); + field ^= (-T{value} ^ field) & (T{1U} << index); + assert(test_bit(field, index) == value); } /// Set the `index`th bit in `field` -template +template std::enable_if_t> set_bit(T& field, const size_t index) { - field.set(index); + field.set(index); } /// Set the `index`th bit in `field` to `value` -template +template std::enable_if_t> set_bit(T& field, const size_t index, const bool value) { - field.set(index, value); + field.set(index, value); } /// Return 1 + the index of the least significant 1-bit of `field`, or zero -template -inline int pop_count(const T& field); +template +inline int +pop_count(const T& field); -template <> +template<> inline int pop_count(const unsigned long& field) { - return __builtin_popcountl(field); + return __builtin_popcountl(field); } -template <> +template<> inline int pop_count(const unsigned long long& field) { - return __builtin_popcountll(field); + return __builtin_popcountll(field); } /// Return 1 + the index of the least significant 1-bit of `field`, or zero -template -inline int find_first(const T field); +template +inline int +find_first(const T field); -template <> +template<> inline int find_first(const unsigned long field) { - return __builtin_ffsl(static_cast(field)); + return __builtin_ffsl(static_cast(field)); } -template <> +template<> inline int find_first(const unsigned long long field) { - return __builtin_ffsll(static_cast(field)); + return __builtin_ffsll(static_cast(field)); } /// Calculates the Gray Code of `value` in place -template -std::enable_if_t> gray_code(T& value); +template +std::enable_if_t> +gray_code(T& value); /// Implementation of grayCode for any integral type -template +template std::enable_if_t::value> gray_code(T& value) { - value ^= (value >> 1U); + value ^= (value >> 1U); } /// Calculates the inverse Gray Code of `value` in place -template -std::enable_if_t> gray_code_inv(T& value); +template +std::enable_if_t> +gray_code_inv(T& value); /// Implementation of gray_code_inv for any integral type -template +template std::enable_if_t::value> gray_code_inv(T& value) { - constexpr T shift_end = sizeof(T) * CHAR_BIT; - for (T shift = 1U; shift < shift_end; shift <<= 1U) { - value ^= (value >> shift); - } + constexpr T shift_end = sizeof(T) * CHAR_BIT; + for (T shift = 1U; shift < shift_end; shift <<= 1U) { + value ^= (value >> shift); + } } } // namespace detail diff --git a/include/chilbert/detail/traits.hpp b/include/chilbert/detail/traits.hpp index 3e3f4d2..e6a2023 100644 --- a/include/chilbert/detail/traits.hpp +++ b/include/chilbert/detail/traits.hpp @@ -23,14 +23,13 @@ namespace chilbert { namespace detail { /// Member `value` is true iff T is a chilbert bitset -template -struct is_bitvec -{ - static constexpr bool value = false; +template +struct is_bitvec { + static constexpr bool value = false; }; /// True iff T is a chilbert bitset -template +template static constexpr bool is_bitvec_v = is_bitvec::value; } // namespace detail -- cgit v1.2.1