aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-08-19 17:47:51 +0200
committerDavid Robillard <d@drobilla.net>2018-09-29 14:49:34 +0200
commit864a0cab22998cfd465f3dd2f0514f96c907ed95 (patch)
tree7e826e910dfa2b574654a5deba8fc1ece4b400e8
parent601c2080e9667ba686e39823c1ebd58844550002 (diff)
downloadchilbert-864a0cab22998cfd465f3dd2f0514f96c907ed95.tar.gz
chilbert-864a0cab22998cfd465f3dd2f0514f96c907ed95.tar.bz2
chilbert-864a0cab22998cfd465f3dd2f0514f96c907ed95.zip
Add BoundedBitVec
-rw-r--r--chilbert/BoundedBitVec.hpp113
-rw-r--r--chilbert/Hilbert.ipp8
-rw-r--r--test/test_bitvec.cpp12
-rw-r--r--test/test_gray_code_rank.cpp11
-rw-r--r--test/test_hilbert.cpp14
5 files changed, 157 insertions, 1 deletions
diff --git a/chilbert/BoundedBitVec.hpp b/chilbert/BoundedBitVec.hpp
new file mode 100644
index 0000000..30ab21e
--- /dev/null
+++ b/chilbert/BoundedBitVec.hpp
@@ -0,0 +1,113 @@
+/*
+ Copyright (C) 2018 David Robillard <d@drobilla.net>
+ Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>
+
+ 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 <https://www.gnu.org/licenses/>.
+*/
+
+#ifndef CHILBERT_BOUNDEDBITVEC_HPP
+#define CHILBERT_BOUNDEDBITVEC_HPP
+
+#include "chilbert/BitVecIndex.hpp"
+#include "chilbert/BitVecIterator.hpp"
+#include "chilbert/BitVecMask.hpp"
+#include "chilbert/MultiBitVec.hpp"
+#include "chilbert/Operations.hpp"
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <cstdlib>
+#include <cstring>
+
+namespace chilbert {
+
+template <size_t MaxN>
+class BoundedBitVec : public MultiBitVec<BoundedBitVec<MaxN>>
+{
+public:
+ using Rack = typename MultiBitVec<BoundedBitVec<MaxN>>::Rack;
+
+ using MultiBitVec<BoundedBitVec<MaxN>>::bits_per_rack;
+
+ BoundedBitVec() = default;
+
+ explicit BoundedBitVec(const size_t bits)
+ : m_size{bits}
+ {
+ assert(bits <= MaxN);
+ }
+
+ BoundedBitVec(const size_t bits, const Rack value)
+ : BoundedBitVec{bits}
+ {
+ m_racks[0] = value;
+ }
+
+ /// Return the size in bits
+ size_t size() const { return m_size; }
+
+ /// 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
+ size_t data_size() const { return num_racks() * sizeof(Rack); }
+
+ /// Return the number of racks
+ size_t num_racks() const { return calculate_num_racks(m_size); }
+
+private:
+ static constexpr size_t calculate_num_racks(const size_t bits)
+ {
+ return (std::max(bits, size_t(1)) + bits_per_rack - 1) / bits_per_rack;
+ }
+
+ std::array<Rack, calculate_num_racks(MaxN)> m_racks{};
+ size_t m_size;
+};
+
+template <size_t MaxN>
+struct is_bitvec<BoundedBitVec<MaxN>>
+{
+ constexpr static bool value = true;
+};
+
+template <size_t MaxN>
+void
+gray_code(BoundedBitVec<MaxN>& value)
+{
+ gray_code(static_cast<MultiBitVec<BoundedBitVec<MaxN>>&>(value));
+}
+
+template <size_t MaxN>
+void
+gray_code_inv(BoundedBitVec<MaxN>& value)
+{
+ gray_code_inv(static_cast<MultiBitVec<BoundedBitVec<MaxN>>&>(value));
+}
+
+} // namespace chilbert
+
+#endif
diff --git a/chilbert/Hilbert.ipp b/chilbert/Hilbert.ipp
index 0b02fba..571166d 100644
--- a/chilbert/Hilbert.ipp
+++ b/chilbert/Hilbert.ipp
@@ -19,6 +19,7 @@
#ifndef CHILBERT_ALGORITHM_HPP
#define CHILBERT_ALGORITHM_HPP
+#include "chilbert/BoundedBitVec.hpp"
#include "chilbert/DynamicBitVec.hpp"
#include "chilbert/GrayCodeRank.hpp"
#include "chilbert/Hilbert.hpp"
@@ -63,6 +64,13 @@ num_bits(const StaticBitVec<N>&, void* = nullptr)
return N;
}
+template <size_t MaxN>
+size_t
+num_bits(const BoundedBitVec<MaxN>& vec, void* = nullptr)
+{
+ return vec.size();
+}
+
/** Copy a range of bits from one field to the start of another.
*
* @param h Source bit field
diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp
index ffdf823..1596042 100644
--- a/test/test_bitvec.cpp
+++ b/test/test_bitvec.cpp
@@ -19,6 +19,7 @@
#include "test_utils.hpp"
+#include "chilbert/BoundedBitVec.hpp"
#include "chilbert/DynamicBitVec.hpp"
#include "chilbert/SmallBitVec.hpp"
#include "chilbert/StaticBitVec.hpp"
@@ -359,5 +360,16 @@ main()
test<chilbert::StaticBitVec<65>, 65>(ctx);
test<chilbert::StaticBitVec<997>, 997>(ctx);
+ test<chilbert::BoundedBitVec<0>, 0>(ctx);
+ test<chilbert::BoundedBitVec<1>, 1>(ctx);
+ test<chilbert::BoundedBitVec<31>, 31>(ctx);
+ test<chilbert::BoundedBitVec<32>, 32>(ctx);
+ test<chilbert::BoundedBitVec<64>, 33>(ctx);
+ test<chilbert::BoundedBitVec<64>, 63>(ctx);
+ test<chilbert::BoundedBitVec<64>, 64>(ctx);
+ test<chilbert::BoundedBitVec<128>, 65>(ctx);
+ test<chilbert::BoundedBitVec<997>, 997>(ctx);
+ test<chilbert::BoundedBitVec<2048>, 997>(ctx);
+
return 0;
}
diff --git a/test/test_gray_code_rank.cpp b/test/test_gray_code_rank.cpp
index ed31d44..0c06a33 100644
--- a/test/test_gray_code_rank.cpp
+++ b/test/test_gray_code_rank.cpp
@@ -19,6 +19,7 @@
#include "test_utils.hpp"
+#include "chilbert/BoundedBitVec.hpp"
#include "chilbert/DynamicBitVec.hpp"
#include "chilbert/GrayCodeRank.hpp"
#include "chilbert/SmallBitVec.hpp"
@@ -148,5 +149,15 @@ main()
test<chilbert::StaticBitVec<65>, 96, 65>(ctx);
test<chilbert::StaticBitVec<997>, 1024, 997>(ctx);
+ test<chilbert::BoundedBitVec<1>, 64, 1>(ctx);
+ test<chilbert::BoundedBitVec<31>, 64, 31>(ctx);
+ test<chilbert::BoundedBitVec<32>, 64, 32>(ctx);
+ test<chilbert::BoundedBitVec<64>, 64, 33>(ctx);
+ test<chilbert::BoundedBitVec<64>, 64, 60>(ctx);
+ test<chilbert::BoundedBitVec<64>, 64, 64>(ctx);
+ test<chilbert::BoundedBitVec<128>, 96, 65>(ctx);
+ test<chilbert::BoundedBitVec<997>, 1024, 997>(ctx);
+ test<chilbert::BoundedBitVec<2048>, 1024, 997>(ctx);
+
return 0;
}
diff --git a/test/test_hilbert.cpp b/test/test_hilbert.cpp
index 3abcdd5..ad99454 100644
--- a/test/test_hilbert.cpp
+++ b/test/test_hilbert.cpp
@@ -19,9 +19,10 @@
#include "test_utils.hpp"
+#include "chilbert/BoundedBitVec.hpp"
#include "chilbert/DynamicBitVec.hpp"
-#include "chilbert/SmallBitVec.hpp"
#include "chilbert/Hilbert.hpp"
+#include "chilbert/SmallBitVec.hpp"
#include "chilbert/StaticBitVec.hpp"
#include <gmpxx.h>
@@ -194,6 +195,17 @@ main()
test_standard<chilbert::StaticBitVec<32 * 64>, 32, 64>(ctx);
test_standard<chilbert::StaticBitVec<63 * 128>, 63, 128>(ctx);
+ test_standard<chilbert::BoundedBitVec<4 * 2>, 4, 2>(ctx);
+ test_standard<chilbert::BoundedBitVec<32 * 2>, 32, 2>(ctx);
+ test_standard<chilbert::BoundedBitVec<16 * 4>, 16, 4>(ctx);
+ test_standard<chilbert::BoundedBitVec<8 * 8>, 8, 8>(ctx);
+ test_standard<chilbert::BoundedBitVec<4 * 16>, 4, 16>(ctx);
+ test_standard<chilbert::BoundedBitVec<2 * 32>, 2, 32>(ctx);
+ test_standard<chilbert::BoundedBitVec<1 * 64>, 1, 64>(ctx);
+ test_standard<chilbert::BoundedBitVec<4 * 128>, 4, 65>(ctx);
+ test_standard<chilbert::BoundedBitVec<32 * 128>, 32, 64>(ctx);
+ test_standard<chilbert::BoundedBitVec<63 * 128>, 63, 128>(ctx);
+
test_compact<chilbert::SmallBitVec, 4, 2>(ctx);
test_compact<chilbert::SmallBitVec, 32, 2>(ctx);
test_compact<chilbert::SmallBitVec, 16, 4>(ctx);