Factor out common operations for multi-rack bit vectors

4 files changed, 420 insertions, 366 deletions

diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index 977fabb..91a516d 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -22,32 +22,35 @@
 #include "chilbert/BitVecIndex.hpp"
 #include "chilbert/BitVecIterator.hpp"
 #include "chilbert/BitVecMask.hpp"
+#include "chilbert/MultiBitVec.hpp"
 #include "chilbert/Operations.hpp"
 
 #include <algorithm>
-#include <cassert>
-#include <climits>
 #include <cstddef>
 #include <cstdlib>
 #include <cstring>
-#include <iostream>
 #include <memory>
 
 namespace chilbert {
 
-class CBigBitVec
+class CBigBitVec : public MultiBitVec<CBigBitVec>
 {
 public:
-	using Rack = uintptr_t;
-	using Mask = BitVecMask<Rack>;
+	struct RacksDeleter
+	{
+		void operator()(Rack* const racks) { free(racks); }
+	};
 
-	using iterator       = BitVecIterator<CBigBitVec>;
-	using const_iterator = ConstBitVecIterator<CBigBitVec>;
+	struct NullDeleter
+	{
+		void operator()(const Rack* const) {}
+	};
 
-	static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT;
+	using RacksPtr      = std::unique_ptr<Rack[], RacksDeleter>;
+	using ConstRacksPtr = std::unique_ptr<const Rack[], NullDeleter>;
 
 	explicit CBigBitVec(const size_t bits)
-	  : m_pcRacks{make_racks(calculate_num_racks(bits))}
+	  : m_racks{make_racks(calculate_num_racks(bits))}
 	  , m_size{bits}
 	{
 	}
@@ -55,97 +58,32 @@ public:
 	CBigBitVec(const size_t bits, const Rack value)
 	  : CBigBitVec{bits}
 	{
-		m_pcRacks[0] = value;
+		m_racks[0] = value;
 	}
 
 	CBigBitVec(const CBigBitVec& vec)
-	  : m_pcRacks{make_racks(vec.num_racks())}
+	  : m_racks{make_racks(vec.num_racks())}
 	  , m_size{vec.m_size}
 	{
-		if (vec.m_pcRacks) {
-			memcpy(
-			  m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * num_racks());
+		if (vec.data()) {
+			memcpy(data(), vec.data(), data_size());
 		}
 	}
 
 	CBigBitVec(CBigBitVec&& vec) = default;
 
-	/// Return the size in bits
-	size_t size() const { return m_size; }
-
-	/// Set all bits to zero
-	CBigBitVec& reset()
-	{
-		memset(m_pcRacks.get(), 0, sizeof(Rack) * num_racks());
-		return *this;
-	}
-
-	/// Set all bits to one
-	CBigBitVec& set()
-	{
-		if (m_size) {
-			memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * num_racks());
-			const auto pad = m_size % bits_per_rack;
-			if (pad) {
-				m_pcRacks[num_racks() - 1] |= ~Rack{0} >> pad;
-			}
-		}
-
-		return *this;
-	}
-
-	/// Truncate to a given precision in bits (zero MSBs)
-	CBigBitVec& truncate(const size_t bits)
-	{
-		const Mask m = mask(bits);
-
-		m_pcRacks[m.rack] &= (m.mask - 1);
-
-		for (size_t i = m.rack + 1; i < num_racks(); ++i) {
-			m_pcRacks[i] = 0;
-		}
-
-		return *this;
-	}
-
-	bool operator==(const CBigBitVec& vec) const
-	{
-		return (num_racks() == vec.num_racks() &&
-		        (num_racks() == 0 ||
-		         !memcmp(racks(), vec.racks(), num_racks() * sizeof(Rack))));
-	}
-
-	bool operator!=(const CBigBitVec& vec) const { return !(*this == vec); }
-
-	bool operator<(const CBigBitVec& vec) const
-	{
-		assert(size() == vec.size());
-
-		for (size_t ri = 0; ri < num_racks(); ++ri) {
-			size_t i = num_racks() - ri - 1;
-			if (m_pcRacks[i] < vec.m_pcRacks[i]) {
-				return true;
-			} else if (m_pcRacks[i] > vec.m_pcRacks[i]) {
-				return false;
-			}
-		}
-		return false;
-	}
-
 	CBigBitVec& operator=(const CBigBitVec& vec)
 	{
 		if (num_racks() < vec.num_racks()) {
-			m_pcRacks = make_racks(vec.num_racks());
-			m_size    = vec.m_size;
-			memcpy(
-			  m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * num_racks());
+			m_racks = make_racks(vec.num_racks());
+			m_size  = vec.m_size;
+			memcpy(data(), vec.data(), data_size());
 		} else if (vec.num_racks() > 0) {
 			m_size = vec.m_size;
-			memcpy(
-			  m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * num_racks());
+			memcpy(data(), vec.data(), data_size());
 		} else {
 			m_size = 0;
-			m_pcRacks.reset();
+			m_racks.reset();
 		}
 
 		return *this;
@@ -153,269 +91,24 @@ public:
 
 	CBigBitVec& operator=(CBigBitVec&& vec) = default;
 
-	/// Return the value of the bit covered by `mask`
-	bool test(const Mask mask) const
-	{
-		return m_pcRacks[mask.rack] & mask.mask;
-	}
-
-	/// Return the value of the `index`th bit
-	bool test(const size_t index) const { return test(mask(index)); }
-
-	/// Set the bit covered by `mask` to 1
-	CBigBitVec& set(const Mask mask)
-	{
-		m_pcRacks[mask.rack] |= mask.mask;
-		return *this;
-	}
-
-	/// Set the `index`th bit to 1
-	CBigBitVec& set(const size_t index) { return set(mask(index)); }
-
-	/// Reset the bit covered by `mask` to 0
-	CBigBitVec& reset(const Mask mask)
-	{
-		m_pcRacks[mask.rack] &= ~mask.mask;
-		return *this;
-	}
-
-	/// Reset the `index`th bit to 0
-	CBigBitVec& reset(const size_t index) { return reset(mask(index)); }
-
-	/// Set the bit covered by `mask` to `value`
-	CBigBitVec& set(const Mask mask, const bool value)
-	{
-		auto& rack = m_pcRacks[mask.rack];
-		rack ^= (-Rack{value} ^ rack) & mask.mask;
-		return *this;
-	}
-
-	/// Set the `index`th bit to `value`
-	CBigBitVec& set(const size_t index, const bool value)
-	{
-		return set(mask(index), value);
-	}
-
-	/// Flip the value of the bit covered by `mask`
-	CBigBitVec& flip(const Mask mask)
-	{
-		m_pcRacks[mask.rack] ^= mask.mask;
-		return *this;
-	}
-
-	/// Flip the value of the `index`th bit
-	CBigBitVec& flip(const size_t index) { return flip(mask(index)); }
-
-	CBigBitVec& operator&=(const CBigBitVec& vec)
-	{
-		for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) {
-			m_pcRacks[i] &= vec.m_pcRacks[i];
-		}
-
-		return *this;
-	}
-
-	CBigBitVec& operator|=(const CBigBitVec& vec)
-	{
-		for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) {
-			m_pcRacks[i] |= vec.m_pcRacks[i];
-		}
-
-		return *this;
-	}
-
-	CBigBitVec& operator^=(const CBigBitVec& vec)
-	{
-		for (size_t i = 0; i < std::min(num_racks(), vec.num_racks()); ++i) {
-			m_pcRacks[i] ^= vec.m_pcRacks[i];
-		}
-
-		return *this;
-	}
-
-	CBigBitVec& operator<<=(const size_t bits)
-	{
-		if (bits == 0) {
-			return *this;
-		} else if (bits >= size()) {
-			reset();
-			return *this;
-		}
-
-		const Index index{bits};
-
-		if (index.rack > 0) {
-			// Shift entire racks
-			for (size_t i = num_racks() - 1; i >= index.rack; --i) {
-				m_pcRacks[i] = m_pcRacks[i - index.rack];
-			}
-			for (size_t i = 0; i < index.rack; ++i) {
-				m_pcRacks[i] = 0;
-			}
-		}
-
-		if (index.bit > 0) {
-			// Shift bits within racks
-			size_t bi = bits_per_rack - index.bit;
-			size_t i;
-			for (i = num_racks() - 1; i >= index.rack + 1; --i) {
-				m_pcRacks[i] <<= index.bit;
-				m_pcRacks[i] |= m_pcRacks[i - 1] >> bi;
-			}
-			m_pcRacks[i] <<= index.bit;
-		}
-
-		return *this;
-	}
-
-	CBigBitVec& operator>>=(const size_t bits)
-	{
-		if (bits == 0) {
-			return *this;
-		} else if (bits >= size()) {
-			reset();
-			return *this;
-		}
-
-		const Index index{bits};
-
-		if (index.rack > 0) {
-			// Shift entire racks
-			size_t i;
-			for (i = 0; i < num_racks() - index.rack; ++i) {
-				m_pcRacks[i] = m_pcRacks[i + index.rack];
-			}
-			for (; i < num_racks(); ++i) {
-				m_pcRacks[i] = 0;
-			}
-		}
-
-		if (index.bit > 0) {
-			// Shift bits within racks
-			size_t bi = bits_per_rack - index.bit;
-			size_t i;
-			for (i = 0; i < num_racks() - index.rack - 1; ++i) {
-				m_pcRacks[i] >>= index.bit;
-				m_pcRacks[i] |= m_pcRacks[i + 1] << bi;
-			}
-			m_pcRacks[i] >>= index.bit;
-		}
-
-		return *this;
-	}
-
-	/// Right-rotate by `bits` positions
-	CBigBitVec& rotr(const size_t bits)
-	{
-		assert(bits <= size());
-		if (bits == 0 || bits == size()) {
-			return *this;
-		}
-
-		CBigBitVec t1(*this);
-		(*this) >>= bits;
-		t1 <<= (size() - bits);
-		(*this) |= t1;
-
-		truncate(size());
-
-		return *this;
-	}
-
-	/// Left-rotate by `bits` positions
-	CBigBitVec& rotl(const size_t bits)
-	{
-		assert(bits <= size());
-		if (bits == 0 || bits == size()) {
-			return *this;
-		}
-
-		CBigBitVec t1(*this);
-		(*this) <<= bits;
-		t1 >>= (size() - bits);
-		(*this) |= t1;
-
-		truncate(size());
-
-		return *this;
-	}
+	/// Return the size in bits
+	size_t size() const { return m_size; }
 
-	/// Return true iff all bits are zero
-	bool none() const
-	{
-		for (size_t i = 0; i < num_racks(); ++i) {
-			if (m_pcRacks[i]) {
-				return false;
-			}
-		}
-		return true;
-	}
+	/// Return a reference to the `index`th rack
+	const Rack& rack(const size_t index) const { return m_racks[index]; }
+	Rack&       rack(const size_t index) { return m_racks[index]; }
 
-	/// 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 = ffs(m_pcRacks[i]);
-			if (j) {
-				return (i * bits_per_rack) + static_cast<size_t>(j);
-			}
-		}
-		return 0;
-	}
+	/// Return a raw pointer to the racks
+	Rack*       data() { return m_racks.get(); }
+	const Rack* data() const { return m_racks.get(); }
 
-	/// 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<size_t>(pop_count(m_pcRacks[i]));
-		}
-		return c;
-	}
-
-	/// Flip all bits (one's complement)
-	CBigBitVec& flip()
-	{
-		for (size_t i = 0; i < num_racks(); ++i) {
-			m_pcRacks[i] = ~m_pcRacks[i];
-		}
-		return *this;
-	}
-
-	/// Return a pointer to the racks
-	Rack*       racks() { return m_pcRacks.get(); }
-	const Rack* racks() const { return m_pcRacks.get(); }
+	/// 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); }
 
-	Mask mask(const size_t i = 0) const
-	{
-		assert(i <= size());
-		return Mask{i};
-	}
-
-	iterator begin(const size_t i = 0) { return iterator(*this, i); }
-
-	iterator end() { return iterator(*this, size()); }
-
-	const_iterator begin(const size_t i = 0) const
-	{
-		return const_iterator(*this, i);
-	}
-
-	const_iterator end() const { return const_iterator(*this, size()); }
-
 private:
-	using Index = BitVecIndex<CBigBitVec>;
-
-	struct RacksDeleter
-	{
-		void operator()(Rack* const racks) { free(racks); }
-	};
-
-	using RacksPtr = std::unique_ptr<Rack[], RacksDeleter>;
-
 	static size_t calculate_num_racks(const size_t bits)
 	{
 		return (std::max(bits, size_t(1)) + bits_per_rack - 1) / bits_per_rack;
@@ -426,7 +119,7 @@ private:
 		return RacksPtr{static_cast<Rack*>(calloc(n, sizeof(Rack)))};
 	}
 
-	RacksPtr m_pcRacks;
+	RacksPtr m_racks;
 	size_t   m_size;
 };
 
@@ -440,32 +133,14 @@ template <>
 void
 grayCode(CBigBitVec& value)
 {
-	CBigBitVec::Rack s = 0;
-
-	for (intptr_t i = static_cast<intptr_t>(value.num_racks() - 1); i >= 0;
-	     --i) {
-		const auto t = value.racks()[i] & 1;
-		grayCode(value.racks()[i]);
-		value.racks()[i] ^= (s << (CBigBitVec::bits_per_rack - 1));
-		s = t;
-	}
+	grayCode(static_cast<MultiBitVec<CBigBitVec>&>(value));
 }
 
 template <>
 void
 grayCodeInv(CBigBitVec& value)
 {
-	CBigBitVec::Rack s = 0;
-
-	for (intptr_t i = static_cast<intptr_t>(value.num_racks() - 1); i >= 0;
-	     --i) {
-		auto& rack = value.racks()[i];
-		grayCodeInv(rack);
-		if (s) {
-			rack = ~rack;
-		}
-		s = rack & 1;
-	}
+	grayCodeInv(static_cast<MultiBitVec<CBigBitVec>&>(value));
 }
 
 } // namespace chilbert
diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp
index 99ed1ee..da26d12 100644
--- a/chilbert/FixBitVec.hpp
+++ b/chilbert/FixBitVec.hpp
@@ -262,12 +262,12 @@ public:
 	Rack& rack() { return m_rack; }
 	Rack  rack() const { return m_rack; }
 
-	/// Return a pointer to the racks
-	Rack*       racks() { return &m_rack; }
-	const Rack* racks() const { return &m_rack; }
+	/// Return a raw pointer to the racks
+	Rack*       data() { return &m_rack; }
+	const Rack* data() const { return &m_rack; }
 
 	/// Return the number of racks
-	int num_racks() const { return 1; }
+	size_t num_racks() const { return 1; }
 
 	template <class BitVec>
 	class iterator_base : public Mask
diff --git a/chilbert/MultiBitVec.hpp b/chilbert/MultiBitVec.hpp
new file mode 100644
index 0000000..42b12c9
--- /dev/null
+++ b/chilbert/MultiBitVec.hpp
@@ -0,0 +1,379 @@
+/*
+  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_MULTIBITVEC_HPP
+#define CHILBERT_MULTIBITVEC_HPP
+
+#include "chilbert/BitVecIterator.hpp"
+#include "chilbert/Operations.hpp"
+
+#include <cassert>
+#include <climits>
+#include <cstdint>
+#include <cstring>
+
+namespace chilbert {
+
+template <class Derived>
+class MultiBitVec
+{
+public:
+	using Rack = uintptr_t;
+	using Mask = BitVecMask<Rack>;
+
+	using iterator       = BitVecIterator<MultiBitVec<Derived>>;
+	using const_iterator = ConstBitVecIterator<MultiBitVec<Derived>>;
+
+	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 = ffs(rack(i));
+			if (j) {
+				return (i * bits_per_rack) + static_cast<size_t>(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<size_t>(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) {
+			size_t i = num_racks() - ri - 1;
+			if (rack(i) < vec.rack(i)) {
+				return true;
+			} else 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();
+		} else if (bits >= size()) {
+			reset();
+			return *self();
+		}
+
+		const Index index{bits};
+
+		if (index.rack > 0) {
+			// Shift entire racks
+			for (size_t i = num_racks() - 1; i >= index.rack; --i) {
+				rack(i) = rack(i - index.rack);
+			}
+			for (size_t i = 0; i < index.rack; ++i) {
+				rack(i) = 0;
+			}
+		}
+
+		if (index.bit > 0) {
+			// Shift bits within racks
+			size_t bi = bits_per_rack - index.bit;
+			size_t i;
+			for (i = num_racks() - 1; i >= index.rack + 1; --i) {
+				rack(i) <<= index.bit;
+				rack(i) |= rack(i - 1) >> bi;
+			}
+			rack(i) <<= index.bit;
+		}
+
+		return *self();
+	}
+
+	Derived& operator>>=(const size_t bits)
+	{
+		if (bits == 0) {
+			return *self();
+		} else if (bits >= size()) {
+			reset();
+			return *self();
+		}
+
+		const Index index{bits};
+
+		if (index.rack > 0) {
+			// Shift entire racks
+			size_t i;
+			for (i = 0; i < num_racks() - index.rack; ++i) {
+				rack(i) = rack(i + index.rack);
+			}
+			for (; i < num_racks(); ++i) {
+				rack(i) = 0;
+			}
+		}
+
+		if (index.bit > 0) {
+			// Shift bits within racks
+			size_t bi = bits_per_rack - index.bit;
+			size_t i;
+			for (i = 0; i < num_racks() - index.rack - 1; ++i) {
+				rack(i) >>= index.bit;
+				rack(i) |= rack(i + 1) << bi;
+			}
+			rack(i) >>= index.bit;
+		}
+
+		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 = BitVecIndex<Derived>;
+
+	Derived*       self() { return static_cast<Derived*>(this); }
+	const Derived* self() const { return static_cast<const Derived*>(this); }
+};
+
+template <class Derived>
+void
+grayCode(MultiBitVec<Derived>& value)
+{
+	typename MultiBitVec<Derived>::Rack s = 0;
+
+	for (size_t ri = 0; ri < value.num_racks(); ++ri) {
+		const size_t i = value.num_racks() - ri - 1;
+		const auto   t = value.rack(i) & 1;
+		grayCode(value.rack(i));
+		value.rack(i) ^= (s << (MultiBitVec<Derived>::bits_per_rack - 1));
+		s = t;
+	}
+}
+
+template <class Derived>
+void
+grayCodeInv(MultiBitVec<Derived>& value)
+{
+	typename MultiBitVec<Derived>::Rack s = 0;
+
+	for (size_t ri = 0; ri < value.num_racks(); ++ri) {
+		const size_t i    = value.num_racks() - ri - 1;
+		auto&        rack = value.rack(i);
+		grayCodeInv(rack);
+		if (s) {
+			rack = ~rack;
+		}
+		s = rack & 1;
+	}
+}
+
+} // namespace chilbert
+
+#endif
diff --git a/test/test_hilbert.cpp b/test/test_hilbert.cpp
index e3a0daf..20646a2 100644
--- a/test/test_hilbert.cpp
+++ b/test/test_hilbert.cpp
@@ -70,7 +70,7 @@ to_big_int(const T& vec)
 	mpz_t ia;
 	mpz_init(ia);
 	mpz_import(
-	  ia, vec.num_racks(), -1, sizeof(chilbert::FBV_UINT), 0, 0, vec.racks());
+	  ia, vec.num_racks(), -1, sizeof(chilbert::FBV_UINT), 0, 0, vec.data());
 	const mpz_class num(ia);
 	mpz_clear(ia);
 	return num;
@@ -83,7 +83,7 @@ from_big_int(const mpz_class& num)
 {
 	T      vec   = make_zero_bitvec<T, M>();
 	size_t count = 0;
-	mpz_export(vec.racks(),
+	mpz_export(vec.data(),
 	           &count,
 	           -1,
 	           sizeof(chilbert::FBV_UINT),