Add Compact Hilbert Index tests

3 files changed, 87 insertions, 27 deletions

diff --git a/test/test_gray_code_rank.cpp b/test/test_gray_code_rank.cpp
index c52bab6..7980bf3 100644
--- a/test/test_gray_code_rank.cpp
+++ b/test/test_gray_code_rank.cpp
@@ -31,21 +31,6 @@
 #include <iostream>
 #include <iterator>
 
-/// Return an array of D precisions with sum at most N
-template <size_t N, size_t D>
-std::array<size_t, D>
-make_random_precisions(Context& ctx)
-{
-	std::array<size_t, D> ms;
-	size_t                bits_left = N;
-	for (size_t i = 0; i < D; ++i) {
-		ms[i] = rand_between(ctx, 1, bits_left / (D - i) + 1);
-		bits_left -= ms[i];
-	}
-
-	return ms;
-}
-
 template <class T, size_t N, size_t D>
 T
 get_mask(const std::array<size_t, D>& ms, const size_t d, const size_t step)
diff --git a/test/test_hilbert.cpp b/test/test_hilbert.cpp
index 2a5fe87..005c110 100644
--- a/test/test_hilbert.cpp
+++ b/test/test_hilbert.cpp
@@ -37,6 +37,18 @@ make_random_point(Context& ctx)
 	return p;
 }
 
+/// Return a `D`-dimensional point within `ms` per-dimension precision
+template <size_t D>
+std::array<uint64_t, D>
+make_random_point(Context& ctx, const std::array<size_t, D>& ms)
+{
+	std::array<uint64_t, D> p;
+	for (size_t i = 0; i < D; ++i) {
+		p[i] = rand_between(ctx, 0, (1UL << ms[i]) - 1);
+	}
+	return p;
+}
+
 /// Return the squared distance from point `a` to point `b`
 template <class T, size_t D>
 T
@@ -84,7 +96,7 @@ from_big_int(const mpz_class& num)
 
 template <class T, size_t M, size_t D>
 void
-test(Context& ctx)
+test_standard(Context& ctx)
 {
 	static_assert(M < sizeof(chilbert::FBV_UINT) * CHAR_BIT, "");
 
@@ -117,22 +129,70 @@ test(Context& ctx)
 	assert(squared_distance(pa, pb) == 1);
 }
 
+template <class T, size_t M, size_t D>
+void
+test_compact(Context& ctx)
+{
+	static_assert(M < sizeof(chilbert::FBV_UINT) * CHAR_BIT, "");
+
+	// Generate random point and its hilbert index
+	const auto ms = make_random_precisions<D * M, D>(ctx);
+	const auto pa = make_random_point<D>(ctx, ms);
+
+	T ha = make_zero_bitvec<T, D * M>();
+	assert(ha.size() >= D * M);
+	chilbert::coordsToCompactIndex(pa.data(), ms.data(), D, ha);
+
+	{
+		// Ensure unmapping results in the original point
+		auto pa_out = make_random_point<M, D>(ctx);
+		chilbert::compactIndexToCoords(pa_out.data(), ms.data(), D, ha);
+		assert(pa_out == pa);
+	}
+
+	// Convert hilbert indices to a big integer for manipulation/comparison
+	const auto ia = to_big_int(ha);
+
+	// Generate the next hilbert index
+	const auto ib = ia + 1;
+	const auto hb = from_big_int<T, D * M>(ib);
+
+	// Unmap next hilbert index to a point
+	auto pb = make_random_point<M, D>(ctx);
+	chilbert::compactIndexToCoords(pb.data(), ms.data(), D, hb);
+
+	// Ensure next point is 1 unit of distance away from first
+	assert(squared_distance(pa, pb) == 1);
+}
+
 int
 main()
 {
 	Context ctx;
 
-	test<chilbert::CFixBitVec, 4, 2>(ctx);
-	test<chilbert::CFixBitVec, 32, 2>(ctx);
-	test<chilbert::CFixBitVec, 16, 4>(ctx);
-	test<chilbert::CFixBitVec, 8, 8>(ctx);
-	test<chilbert::CFixBitVec, 4, 16>(ctx);
-	test<chilbert::CFixBitVec, 2, 32>(ctx);
-	test<chilbert::CFixBitVec, 1, 64>(ctx);
-
-	test<chilbert::CBigBitVec, 4, 65>(ctx);
-	test<chilbert::CBigBitVec, 32, 64>(ctx);
-	test<chilbert::CBigBitVec, 63, 128>(ctx);
+	test_standard<chilbert::CFixBitVec, 4, 2>(ctx);
+	test_standard<chilbert::CFixBitVec, 32, 2>(ctx);
+	test_standard<chilbert::CFixBitVec, 16, 4>(ctx);
+	test_standard<chilbert::CFixBitVec, 8, 8>(ctx);
+	test_standard<chilbert::CFixBitVec, 4, 16>(ctx);
+	test_standard<chilbert::CFixBitVec, 2, 32>(ctx);
+	test_standard<chilbert::CFixBitVec, 1, 64>(ctx);
+
+	test_standard<chilbert::CBigBitVec, 4, 65>(ctx);
+	test_standard<chilbert::CBigBitVec, 32, 64>(ctx);
+	test_standard<chilbert::CBigBitVec, 63, 128>(ctx);
+
+	test_compact<chilbert::CFixBitVec, 4, 2>(ctx);
+	test_compact<chilbert::CFixBitVec, 32, 2>(ctx);
+	test_compact<chilbert::CFixBitVec, 16, 4>(ctx);
+	test_compact<chilbert::CFixBitVec, 8, 8>(ctx);
+	test_compact<chilbert::CFixBitVec, 4, 16>(ctx);
+	test_compact<chilbert::CFixBitVec, 2, 32>(ctx);
+	test_compact<chilbert::CFixBitVec, 1, 64>(ctx);
+
+	test_compact<chilbert::CBigBitVec, 4, 65>(ctx);
+	test_compact<chilbert::CBigBitVec, 32, 64>(ctx);
+	test_compact<chilbert::CBigBitVec, 63, 128>(ctx);
 
 	return 0;
 }
diff --git a/test/test_utils.hpp b/test/test_utils.hpp
index acee5d0..a695134 100644
--- a/test/test_utils.hpp
+++ b/test/test_utils.hpp
@@ -66,4 +66,19 @@ rand_between(Context& ctx, const size_t min, const size_t max)
 	return r;
 }
 
+/// Return an array of D precisions with sum at most N and each at most Max
+template <size_t N, size_t D, size_t Max = 64>
+std::array<size_t, D>
+make_random_precisions(Context& ctx)
+{
+	std::array<size_t, D> ms;
+	size_t                bits_left = N;
+	for (size_t i = 0; i < D; ++i) {
+		ms[i] = rand_between(ctx, 1, std::min(Max, bits_left / (D - i) + 1));
+		bits_left -= ms[i];
+	}
+
+	return ms;
+}
+
 #endif