From fa3d8f677b6a30c2115e7d167d4938e293dfad81 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 19 Aug 2018 16:27:07 +0200 Subject: Add StaticBitVec type --- chilbert/Hilbert.ipp | 8 ++++ chilbert/StaticBitVec.hpp | 112 +++++++++++++++++++++++++++++++++++++++++++ test/test_bitvec.cpp | 11 +++++ test/test_gray_code_rank.cpp | 10 ++++ test/test_hilbert.cpp | 23 +++++++++ 5 files changed, 164 insertions(+) create mode 100644 chilbert/StaticBitVec.hpp diff --git a/chilbert/Hilbert.ipp b/chilbert/Hilbert.ipp index 9d23271..726b204 100644 --- a/chilbert/Hilbert.ipp +++ b/chilbert/Hilbert.ipp @@ -27,6 +27,7 @@ #include "chilbert/Hilbert.hpp" #include "chilbert/SetBits.hpp" #include "chilbert/SetLocation.hpp" +#include "chilbert/StaticBitVec.hpp" #include @@ -72,6 +73,13 @@ num_bits(const T& vec, return vec.size(); } +template +size_t +num_bits(const StaticBitVec&, void* = nullptr) +{ + return N; +} + // 'Transforms' a point. template inline void diff --git a/chilbert/StaticBitVec.hpp b/chilbert/StaticBitVec.hpp new file mode 100644 index 0000000..1501746 --- /dev/null +++ b/chilbert/StaticBitVec.hpp @@ -0,0 +1,112 @@ +/* + Copyright (C) 2018 David Robillard + Copyright (C) 2006-2007 Chris Hamilton + + This program is free software: you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free Software + Foundation, either version 2 of the License, or (at your option) any later + version. + + This program is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + details. + + You should have received a copy of the GNU General Public License along with + this program. If not, see . +*/ + +#ifndef CHILBERT_STATICBITVEC_HPP +#define CHILBERT_STATICBITVEC_HPP + +#include "chilbert/BitVecIndex.hpp" +#include "chilbert/BitVecIterator.hpp" +#include "chilbert/BitVecMask.hpp" +#include "chilbert/MultiBitVec.hpp" +#include "chilbert/Operations.hpp" + +#include +#include +#include +#include +#include +#include +#include + +namespace chilbert { + +template +class StaticBitVec : public MultiBitVec> +{ +public: + using Rack = typename MultiBitVec>::Rack; + + using MultiBitVec>::bits_per_rack; + + StaticBitVec() = default; + + /// Constructor for compatibility with CBigBitVec + explicit StaticBitVec(const size_t bits) + { + assert(bits == size()); + } + + /// Constructor for compatibility with CBigBitVec + StaticBitVec(const size_t bits, const Rack value) + : StaticBitVec{bits} + { + m_racks[0] = value; + } + + /// Return the size in bits + size_t size() const { return N; } + + /// Return a reference to the `index`th rack +#ifndef NDEBUG + const auto& rack(const size_t index) const { return m_racks.at(index); } + auto& rack(const size_t index) { return m_racks.at(index); } +#else + const auto& rack(const size_t index) const { return m_racks[index]; } + auto& rack(const size_t index) { return m_racks[index]; } +#endif + + /// Return a raw pointer to the racks + Rack* data() { return m_racks.data(); } + const Rack* data() const { return m_racks.data(); } + + /// Return the total size of all racks in bytes + static constexpr size_t data_size() { return num_racks() * sizeof(Rack); } + + /// Return the number of racks + static constexpr size_t num_racks() + { + return (std::max(N, size_t(1)) + bits_per_rack - 1) / bits_per_rack; + } + +private: + std::array m_racks{}; +}; + +template +struct is_bitvec> +{ + constexpr static bool value = true; +}; + +template +void +grayCode(StaticBitVec& value) +{ + grayCode(static_cast>&>(value)); +} + +template +void +grayCodeInv(StaticBitVec& value) +{ + grayCodeInv(static_cast>&>(value)); +} + +} // namespace chilbert + +#endif diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp index 0b6e534..b891aca 100644 --- a/test/test_bitvec.cpp +++ b/test/test_bitvec.cpp @@ -21,6 +21,7 @@ #include "chilbert/BigBitVec.hpp" #include "chilbert/FixBitVec.hpp" +#include "chilbert/StaticBitVec.hpp" #include #include @@ -348,5 +349,15 @@ main() test(ctx); test(ctx); + test, 0>(ctx); + test, 1>(ctx); + test, 31>(ctx); + test, 32>(ctx); + test, 33>(ctx); + test, 63>(ctx); + test, 64>(ctx); + test, 65>(ctx); + test, 997>(ctx); + return 0; } diff --git a/test/test_gray_code_rank.cpp b/test/test_gray_code_rank.cpp index a421159..8be40f1 100644 --- a/test/test_gray_code_rank.cpp +++ b/test/test_gray_code_rank.cpp @@ -22,6 +22,7 @@ #include "chilbert/BigBitVec.hpp" #include "chilbert/FixBitVec.hpp" #include "chilbert/GrayCodeRank.hpp" +#include "chilbert/StaticBitVec.hpp" #include #include @@ -138,5 +139,14 @@ main() test(ctx); test(ctx); + test, 64, 1>(ctx); + test, 64, 31>(ctx); + test, 64, 32>(ctx); + test, 64, 33>(ctx); + test, 64, 60>(ctx); + test, 64, 64>(ctx); + test, 96, 65>(ctx); + test, 1024, 997>(ctx); + return 0; } diff --git a/test/test_hilbert.cpp b/test/test_hilbert.cpp index 6a3d1b8..36a2992 100644 --- a/test/test_hilbert.cpp +++ b/test/test_hilbert.cpp @@ -22,6 +22,7 @@ #include "chilbert/BigBitVec.hpp" #include "chilbert/FixBitVec.hpp" #include "chilbert/Hilbert.hpp" +#include "chilbert/StaticBitVec.hpp" #include @@ -182,6 +183,17 @@ main() test_standard(ctx); test_standard(ctx); + test_standard, 4, 2>(ctx); + test_standard, 32, 2>(ctx); + test_standard, 16, 4>(ctx); + test_standard, 8, 8>(ctx); + test_standard, 4, 16>(ctx); + test_standard, 2, 32>(ctx); + test_standard, 1, 64>(ctx); + test_standard, 4, 65>(ctx); + test_standard, 32, 64>(ctx); + test_standard, 63, 128>(ctx); + test_compact(ctx); test_compact(ctx); test_compact(ctx); @@ -194,5 +206,16 @@ main() test_compact(ctx); test_compact(ctx); + test_compact, 4, 2>(ctx); + test_compact, 32, 2>(ctx); + test_compact, 16, 4>(ctx); + test_compact, 8, 8>(ctx); + test_compact, 4, 16>(ctx); + test_compact, 2, 32>(ctx); + test_compact, 1, 64>(ctx); + test_compact, 4, 65>(ctx); + test_compact, 32, 64>(ctx); + test_compact, 63, 128>(ctx); + return 0; } -- cgit v1.2.1