aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-08-18 17:37:59 +0200
committerDavid Robillard <d@drobilla.net>2018-09-29 14:46:57 +0200
commitad4f4edefc5da702e9efa4ec7b40830e91abb6cf (patch)
tree8741fc79ad732b8d3f19e81a530107ec4bd7a3c3
parent13bcfa8bc31510b926a1f638d071dc83253179e2 (diff)
downloadchilbert-ad4f4edefc5da702e9efa4ec7b40830e91abb6cf.tar.gz
chilbert-ad4f4edefc5da702e9efa4ec7b40830e91abb6cf.tar.bz2
chilbert-ad4f4edefc5da702e9efa4ec7b40830e91abb6cf.zip
Add Compact Hilbert Index tests
-rw-r--r--test/test_gray_code_rank.cpp15
-rw-r--r--test/test_hilbert.cpp84
-rw-r--r--test/test_utils.hpp15
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