diff options
Diffstat (limited to 'test')
-rw-r--r-- | test/test_bitvec.cpp | 498 | ||||
-rw-r--r-- | test/test_gray_code_rank.cpp | 206 | ||||
-rw-r--r-- | test/test_hilbert.cpp | 272 | ||||
-rw-r--r-- | test/test_utils.hpp | 63 |
4 files changed, 519 insertions, 520 deletions
diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp index c123212..892744a 100644 --- a/test/test_bitvec.cpp +++ b/test/test_bitvec.cpp @@ -30,357 +30,357 @@ #include <cstddef> #include <cstdlib> -template <class T, size_t N> +template<class T, size_t N> void test_and(Context& ctx) { - const T a = make_random_bitvec<T, N>(ctx); - const T b = make_random_bitvec<T, N>(ctx); - T r = a; - assert((a & b) == (r &= b)); - - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == (a.test(i) && b.test(i))); - } + const T a = make_random_bitvec<T, N>(ctx); + const T b = make_random_bitvec<T, N>(ctx); + T r = a; + assert((a & b) == (r &= b)); + + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == (a.test(i) && b.test(i))); + } } -template <class T, size_t N> +template<class T, size_t N> void test_or(Context& ctx) { - const T a = make_random_bitvec<T, N>(ctx); - const T b = make_random_bitvec<T, N>(ctx); - T r = a; - assert((a | b) == (r |= b)); - - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == (a.test(i) || b.test(i))); - } + const T a = make_random_bitvec<T, N>(ctx); + const T b = make_random_bitvec<T, N>(ctx); + T r = a; + assert((a | b) == (r |= b)); + + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == (a.test(i) || b.test(i))); + } } -template <class T, size_t N> +template<class T, size_t N> void test_xor(Context& ctx) { - const T a = make_random_bitvec<T, N>(ctx); - const T b = make_random_bitvec<T, N>(ctx); - T r = a; - assert((a ^ b) == (r ^= b)); - - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == (a.test(i) != b.test(i))); - } + const T a = make_random_bitvec<T, N>(ctx); + const T b = make_random_bitvec<T, N>(ctx); + T r = a; + assert((a ^ b) == (r ^= b)); + + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == (a.test(i) != b.test(i))); + } } -template <class T, size_t N> +template<class T, size_t N> void test_not(Context& ctx) { - const T v = make_random_bitvec<T, N>(ctx); - const T r = ~v; + const T v = make_random_bitvec<T, N>(ctx); + const T r = ~v; - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == !v.test(i)); - } + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == !v.test(i)); + } } -template <class T, size_t N> +template<class T, size_t N> void test_flip_one(Context&) { - T v = make_zero_bitvec<T, N>(); - for (size_t i = 0; i < N; ++i) { - assert(v.none()); - v.flip(i); - for (size_t j = 0; j < N; ++j) { - assert(v.test(j) == (j == i)); - } - - v.flip(i); - assert(v.none()); - } + T v = make_zero_bitvec<T, N>(); + for (size_t i = 0; i < N; ++i) { + assert(v.none()); + v.flip(i); + for (size_t j = 0; j < N; ++j) { + assert(v.test(j) == (j == i)); + } + + v.flip(i); + assert(v.none()); + } } -template <class T, size_t N> +template<class T, size_t N> void test_flip_all(Context& ctx) { - const T a = make_random_bitvec<T, N>(ctx); - T r = a; - r.flip(); - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == !a.test(i)); - } + const T a = make_random_bitvec<T, N>(ctx); + T r = a; + r.flip(); + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == !a.test(i)); + } } -template <class T, size_t N> +template<class T, size_t N> void test_none(Context&) { - T v = make_zero_bitvec<T, N>(); - assert(v.none()); - v.set(); - assert(v.none() == (N == 0)); - if (N > 1) { - v.reset(N / 2); - assert(!v.none()); - v.reset(); - v.set(N / 2); - assert(!v.none()); - } + T v = make_zero_bitvec<T, N>(); + assert(v.none()); + v.set(); + assert(v.none() == (N == 0)); + if (N > 1) { + v.reset(N / 2); + assert(!v.none()); + v.reset(); + v.set(N / 2); + assert(!v.none()); + } } -template <class T, size_t N> +template<class T, size_t N> void test_set_reset_one(Context&) { - T v = make_zero_bitvec<T, N>(); - for (size_t i = 0; i < N; ++i) { - assert(v.none()); - v.set(i); - for (size_t j = 0; j < N; ++j) { - assert(v.test(j) == (j == i)); - } - - v.reset(i); - assert(v.none()); - } + T v = make_zero_bitvec<T, N>(); + for (size_t i = 0; i < N; ++i) { + assert(v.none()); + v.set(i); + for (size_t j = 0; j < N; ++j) { + assert(v.test(j) == (j == i)); + } + + v.reset(i); + assert(v.none()); + } } -template <class T, size_t N> +template<class T, size_t N> void test_set_all(Context&) { - T v = make_zero_bitvec<T, N>(); - v.set(); - for (size_t i = 0; i < N; ++i) { - assert(v.test(i)); - } + T v = make_zero_bitvec<T, N>(); + v.set(); + for (size_t i = 0; i < N; ++i) { + assert(v.test(i)); + } } -template <class T, size_t N> +template<class T, size_t N> void test_reset_all(Context&) { - T v = make_zero_bitvec<T, N>(); - v.set(); - v.reset(); - for (size_t i = 0; i < N; ++i) { - assert(!v.test(i)); - } + T v = make_zero_bitvec<T, N>(); + v.set(); + v.reset(); + for (size_t i = 0; i < N; ++i) { + assert(!v.test(i)); + } } -template <class T, size_t N> +template<class T, size_t N> void test_left_shift(Context& ctx) { - for (size_t s = 0; s < N; ++s) { - const T v = make_random_bitvec<T, N>(ctx); - T r = v; - assert((v << s) == (r <<= s)); - - for (size_t i = 0; i < s; ++i) { - assert(!r.test(i)); - } - - for (size_t i = s; i < N; ++i) { - assert(r.test(i) == v.test(i - s)); - } - } + for (size_t s = 0; s < N; ++s) { + const T v = make_random_bitvec<T, N>(ctx); + T r = v; + assert((v << s) == (r <<= s)); + + for (size_t i = 0; i < s; ++i) { + assert(!r.test(i)); + } + + for (size_t i = s; i < N; ++i) { + assert(r.test(i) == v.test(i - s)); + } + } } -template <class T, size_t N> +template<class T, size_t N> void test_right_shift(Context& ctx) { - for (size_t s = 0; s < N; ++s) { - const T v = make_random_bitvec<T, N>(ctx); - T r = v; - assert((v >> s) == (r >>= s)); - - for (size_t i = N - 1; i > N - s - 1; --i) { - assert(!r.test(i)); - } - - for (size_t i = 0; i <= N - s - 1; ++i) { - assert(r.test(i) == v.test(i + s)); - } - } + for (size_t s = 0; s < N; ++s) { + const T v = make_random_bitvec<T, N>(ctx); + T r = v; + assert((v >> s) == (r >>= s)); + + for (size_t i = N - 1; i > N - s - 1; --i) { + assert(!r.test(i)); + } + + for (size_t i = 0; i <= N - s - 1; ++i) { + assert(r.test(i) == v.test(i + s)); + } + } } -template <class T, size_t N> +template<class T, size_t N> void test_left_rotate(Context& ctx) { - const T v = make_random_bitvec<T, N>(ctx); - for (size_t bits = 0; bits <= N; ++bits) { - T r = v; - r.rotl(bits); - - if (N > 0) { - for (size_t i = 0; i < N; ++i) { - assert(r.test((i + bits) % N) == v.test(i)); - } - } - } + const T v = make_random_bitvec<T, N>(ctx); + for (size_t bits = 0; bits <= N; ++bits) { + T r = v; + r.rotl(bits); + + if (N > 0) { + for (size_t i = 0; i < N; ++i) { + assert(r.test((i + bits) % N) == v.test(i)); + } + } + } } -template <class T, size_t N> +template<class T, size_t N> void test_right_rotate(Context& ctx) { - const T v = make_random_bitvec<T, N>(ctx); - for (size_t bits = 0; bits <= N; ++bits) { - T r = v; - r.rotr(bits); - - if (N > 0) { - for (size_t i = 0; i < N; ++i) { - assert(r.test(i) == v.test((i + bits) % N)); - } - } - } + const T v = make_random_bitvec<T, N>(ctx); + for (size_t bits = 0; bits <= N; ++bits) { + T r = v; + r.rotr(bits); + + if (N > 0) { + for (size_t i = 0; i < N; ++i) { + assert(r.test(i) == v.test((i + bits) % N)); + } + } + } } -template <class T, size_t N> +template<class T, size_t N> void test_find_first(Context&) { - T v = make_zero_bitvec<T, N>(); - for (size_t i = 0; i < N; ++i) { - v.reset(); - v.set(i); - for (size_t j = i + 1; j < N; ++j) { - v.set(j, rand() % 2); - } - assert(size_t(v.find_first()) == i + 1); - } + T v = make_zero_bitvec<T, N>(); + for (size_t i = 0; i < N; ++i) { + v.reset(); + v.set(i); + for (size_t j = i + 1; j < N; ++j) { + v.set(j, rand() % 2); + } + assert(size_t(v.find_first()) == i + 1); + } } -template <class T, size_t N> +template<class T, size_t N> void test_gray_code(Context& ctx) { - const T v = make_random_bitvec<T, N>(ctx); - T r = v; - chilbert::detail::gray_code(r); + const T v = make_random_bitvec<T, N>(ctx); + T r = v; + chilbert::detail::gray_code(r); - if (N > 0) { - assert(N == 1 || r == (v ^ (v >> 1))); + if (N > 0) { + assert(N == 1 || r == (v ^ (v >> 1))); - T s = r; - chilbert::detail::gray_code_inv(s); - assert(s == v); - } + T s = r; + chilbert::detail::gray_code_inv(s); + assert(s == v); + } } -template <class T, size_t N> +template<class T, size_t N> void test_comparison(Context&) { - T a = make_zero_bitvec<T, N>(); - T b = make_zero_bitvec<T, N>(); + T a = make_zero_bitvec<T, N>(); + T b = make_zero_bitvec<T, N>(); - for (size_t bit = 1; bit < N; ++bit) { - chilbert::detail::set_bit(a, bit, 1); + for (size_t bit = 1; bit < N; ++bit) { + chilbert::detail::set_bit(a, bit, 1); - for (size_t i = 0; i < bit; ++i) { - chilbert::detail::set_bit(a, i, rand() % 2 == 0); - chilbert::detail::set_bit(b, i, rand() % 2 == 0); - } + for (size_t i = 0; i < bit; ++i) { + chilbert::detail::set_bit(a, i, rand() % 2 == 0); + chilbert::detail::set_bit(b, i, rand() % 2 == 0); + } - assert(b < a); - } + assert(b < a); + } } -template <class T, size_t N> +template<class T, size_t N> void test_iteration(Context&) { - T v = make_zero_bitvec<T, N>(); - size_t count = 0; - for (const auto bit : v) { - assert(!bit); - ++count; - } - assert(count == N); - - v.flip(); - count = 0; - for (const auto bit : v) { - assert(bit); - ++count; - } - assert(count == N); + T v = make_zero_bitvec<T, N>(); + size_t count = 0; + for (const auto bit : v) { + assert(!bit); + ++count; + } + assert(count == N); + + v.flip(); + count = 0; + for (const auto bit : v) { + assert(bit); + ++count; + } + assert(count == N); } -template <class T, size_t N> +template<class T, size_t N> void test(Context& ctx) { - test_and<T, N>(ctx); - test_or<T, N>(ctx); - test_xor<T, N>(ctx); - test_not<T, N>(ctx); - test_flip_one<T, N>(ctx); - test_flip_all<T, N>(ctx); - test_none<T, N>(ctx); - test_set_reset_one<T, N>(ctx); - test_set_all<T, N>(ctx); - test_reset_all<T, N>(ctx); - test_left_shift<T, N>(ctx); - test_right_shift<T, N>(ctx); - test_left_rotate<T, N>(ctx); - test_right_rotate<T, N>(ctx); - test_find_first<T, N>(ctx); - test_gray_code<T, N>(ctx); - test_comparison<T, N>(ctx); - test_iteration<T, N>(ctx); + test_and<T, N>(ctx); + test_or<T, N>(ctx); + test_xor<T, N>(ctx); + test_not<T, N>(ctx); + test_flip_one<T, N>(ctx); + test_flip_all<T, N>(ctx); + test_none<T, N>(ctx); + test_set_reset_one<T, N>(ctx); + test_set_all<T, N>(ctx); + test_reset_all<T, N>(ctx); + test_left_shift<T, N>(ctx); + test_right_shift<T, N>(ctx); + test_left_rotate<T, N>(ctx); + test_right_rotate<T, N>(ctx); + test_find_first<T, N>(ctx); + test_gray_code<T, N>(ctx); + test_comparison<T, N>(ctx); + test_iteration<T, N>(ctx); } int main() { - Context ctx; - - // test<chilbert::SmallBitVec, 0>(ctx); - test<chilbert::SmallBitVec, 1>(ctx); - test<chilbert::SmallBitVec, 31>(ctx); - test<chilbert::SmallBitVec, 32>(ctx); - test<chilbert::SmallBitVec, 33>(ctx); - test<chilbert::SmallBitVec, 63>(ctx); - test<chilbert::SmallBitVec, 64>(ctx); - - test<chilbert::DynamicBitVec, 0>(ctx); - test<chilbert::DynamicBitVec, 1>(ctx); - test<chilbert::DynamicBitVec, 31>(ctx); - test<chilbert::DynamicBitVec, 32>(ctx); - test<chilbert::DynamicBitVec, 33>(ctx); - test<chilbert::DynamicBitVec, 63>(ctx); - test<chilbert::DynamicBitVec, 64>(ctx); - test<chilbert::DynamicBitVec, 65>(ctx); - test<chilbert::DynamicBitVec, 997>(ctx); - - test<chilbert::StaticBitVec<0>, 0>(ctx); - test<chilbert::StaticBitVec<1>, 1>(ctx); - test<chilbert::StaticBitVec<31>, 31>(ctx); - test<chilbert::StaticBitVec<32>, 32>(ctx); - test<chilbert::StaticBitVec<33>, 33>(ctx); - test<chilbert::StaticBitVec<63>, 63>(ctx); - test<chilbert::StaticBitVec<64>, 64>(ctx); - 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; + Context ctx; + + // test<chilbert::SmallBitVec, 0>(ctx); + test<chilbert::SmallBitVec, 1>(ctx); + test<chilbert::SmallBitVec, 31>(ctx); + test<chilbert::SmallBitVec, 32>(ctx); + test<chilbert::SmallBitVec, 33>(ctx); + test<chilbert::SmallBitVec, 63>(ctx); + test<chilbert::SmallBitVec, 64>(ctx); + + test<chilbert::DynamicBitVec, 0>(ctx); + test<chilbert::DynamicBitVec, 1>(ctx); + test<chilbert::DynamicBitVec, 31>(ctx); + test<chilbert::DynamicBitVec, 32>(ctx); + test<chilbert::DynamicBitVec, 33>(ctx); + test<chilbert::DynamicBitVec, 63>(ctx); + test<chilbert::DynamicBitVec, 64>(ctx); + test<chilbert::DynamicBitVec, 65>(ctx); + test<chilbert::DynamicBitVec, 997>(ctx); + + test<chilbert::StaticBitVec<0>, 0>(ctx); + test<chilbert::StaticBitVec<1>, 1>(ctx); + test<chilbert::StaticBitVec<31>, 31>(ctx); + test<chilbert::StaticBitVec<32>, 32>(ctx); + test<chilbert::StaticBitVec<33>, 33>(ctx); + test<chilbert::StaticBitVec<63>, 63>(ctx); + test<chilbert::StaticBitVec<64>, 64>(ctx); + 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 3b6f9bb..906b26c 100644 --- a/test/test_gray_code_rank.cpp +++ b/test/test_gray_code_rank.cpp @@ -33,132 +33,132 @@ #include <cstddef> #include <iterator> -template <class T, size_t Max, size_t D> +template<class T, size_t Max, size_t D> T get_mask(const std::array<size_t, D>& ms, const size_t d, const size_t step) { - T mask = make_zero_bitvec<T, D>(); - size_t b = 0U; - chilbert::detail::extract_mask(ms.data(), D, d, step, mask, b); + T mask = make_zero_bitvec<T, D>(); + size_t b = 0U; + chilbert::detail::extract_mask(ms.data(), D, d, step, mask, b); - assert(b == mask.count()); + assert(b == mask.count()); - return mask; + return mask; } -template <class T, size_t Max, size_t D> +template<class T, size_t Max, size_t D> void test_extract_mask(Context& ctx) { - for (size_t d = 0; d < D; ++d) { - const auto ms = make_random_precisions<Max, D>(ctx); - const auto max_m = *std::max_element(std::begin(ms), std::end(ms)); - const size_t step = rand_between(ctx, 0, max_m); - const auto mask = get_mask<T, D>(ms, d, step); - - for (size_t i = 0; i < D; ++i) { - assert(mask.test(i) == (ms[(d + i) % D] > step)); - } - } + for (size_t d = 0; d < D; ++d) { + const auto ms = make_random_precisions<Max, D>(ctx); + const auto max_m = *std::max_element(std::begin(ms), std::end(ms)); + const size_t step = rand_between(ctx, 0, max_m); + const auto mask = get_mask<T, D>(ms, d, step); + + for (size_t i = 0; i < D; ++i) { + assert(mask.test(i) == (ms[(d + i) % D] > step)); + } + } } -template <class T, size_t Max, size_t D> +template<class T, size_t Max, size_t D> void test_gray_code_rank(Context& ctx) { - for (size_t d = 0; d < D; ++d) { - // Generate random mask - const auto mask = make_random_bitvec<T, D>(ctx); - - // Generate two random values and their gray codes - const auto a = make_random_bitvec<T, D>(ctx); - const auto b = make_random_bitvec<T, D>(ctx); - - auto ga = a; - chilbert::detail::gray_code(ga); - - auto gb = b; - chilbert::detail::gray_code(gb); - - // Calculate gray code ranks - auto ra = make_zero_bitvec<T, D>(); - chilbert::detail::gray_code_rank(mask, ga, D, ra); - - auto rb = make_zero_bitvec<T, D>(); - chilbert::detail::gray_code_rank(mask, gb, D, rb); - - // Ensure ranks have at most mask.count() bits - auto max = make_zero_bitvec<T, D>(); - chilbert::detail::set_bit(max, mask.count(), 1); - assert(ra < max); - assert(rb < max); - - // Test fundamental property of gray code ranks - const auto mga = ga & mask; - const auto mgb = gb & mask; - assert((mga < mgb) == (ra < rb)); - - // Test inversion - const auto pat = ~mask; - auto ga_out = make_zero_bitvec<T, D>(); - auto gag_out = make_zero_bitvec<T, D>(); - chilbert::detail::gray_code_rank_inv( - mask, pat, ra, D, mask.count(), gag_out, ga_out); - assert((ga_out & mask) == (ga & mask)); - - auto gag_check = ga_out; - chilbert::detail::gray_code(gag_check); - assert(gag_check == gag_out); - } + for (size_t d = 0; d < D; ++d) { + // Generate random mask + const auto mask = make_random_bitvec<T, D>(ctx); + + // Generate two random values and their gray codes + const auto a = make_random_bitvec<T, D>(ctx); + const auto b = make_random_bitvec<T, D>(ctx); + + auto ga = a; + chilbert::detail::gray_code(ga); + + auto gb = b; + chilbert::detail::gray_code(gb); + + // Calculate gray code ranks + auto ra = make_zero_bitvec<T, D>(); + chilbert::detail::gray_code_rank(mask, ga, D, ra); + + auto rb = make_zero_bitvec<T, D>(); + chilbert::detail::gray_code_rank(mask, gb, D, rb); + + // Ensure ranks have at most mask.count() bits + auto max = make_zero_bitvec<T, D>(); + chilbert::detail::set_bit(max, mask.count(), 1); + assert(ra < max); + assert(rb < max); + + // Test fundamental property of gray code ranks + const auto mga = ga & mask; + const auto mgb = gb & mask; + assert((mga < mgb) == (ra < rb)); + + // Test inversion + const auto pat = ~mask; + auto ga_out = make_zero_bitvec<T, D>(); + auto gag_out = make_zero_bitvec<T, D>(); + chilbert::detail::gray_code_rank_inv( + mask, pat, ra, D, mask.count(), gag_out, ga_out); + assert((ga_out & mask) == (ga & mask)); + + auto gag_check = ga_out; + chilbert::detail::gray_code(gag_check); + assert(gag_check == gag_out); + } } -template <class T, size_t Max, size_t D> +template<class T, size_t Max, size_t D> void test(Context& ctx) { - test_extract_mask<T, Max, D>(ctx); - test_gray_code_rank<T, Max, D>(ctx); + test_extract_mask<T, Max, D>(ctx); + test_gray_code_rank<T, Max, D>(ctx); } int main() { - Context ctx; - - test<chilbert::SmallBitVec, 64, 1>(ctx); - test<chilbert::SmallBitVec, 64, 31>(ctx); - test<chilbert::SmallBitVec, 64, 32>(ctx); - test<chilbert::SmallBitVec, 64, 33>(ctx); - test<chilbert::SmallBitVec, 64, 60>(ctx); - test<chilbert::SmallBitVec, 64, 64>(ctx); - - test<chilbert::DynamicBitVec, 64, 1>(ctx); - test<chilbert::DynamicBitVec, 64, 31>(ctx); - test<chilbert::DynamicBitVec, 64, 32>(ctx); - test<chilbert::DynamicBitVec, 64, 33>(ctx); - test<chilbert::DynamicBitVec, 64, 60>(ctx); - test<chilbert::DynamicBitVec, 64, 64>(ctx); - test<chilbert::DynamicBitVec, 96, 65>(ctx); - test<chilbert::DynamicBitVec, 1024, 997>(ctx); - - test<chilbert::StaticBitVec<1>, 64, 1>(ctx); - test<chilbert::StaticBitVec<31>, 64, 31>(ctx); - test<chilbert::StaticBitVec<32>, 64, 32>(ctx); - test<chilbert::StaticBitVec<33>, 64, 33>(ctx); - test<chilbert::StaticBitVec<60>, 64, 60>(ctx); - test<chilbert::StaticBitVec<64>, 64, 64>(ctx); - 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; + Context ctx; + + test<chilbert::SmallBitVec, 64, 1>(ctx); + test<chilbert::SmallBitVec, 64, 31>(ctx); + test<chilbert::SmallBitVec, 64, 32>(ctx); + test<chilbert::SmallBitVec, 64, 33>(ctx); + test<chilbert::SmallBitVec, 64, 60>(ctx); + test<chilbert::SmallBitVec, 64, 64>(ctx); + + test<chilbert::DynamicBitVec, 64, 1>(ctx); + test<chilbert::DynamicBitVec, 64, 31>(ctx); + test<chilbert::DynamicBitVec, 64, 32>(ctx); + test<chilbert::DynamicBitVec, 64, 33>(ctx); + test<chilbert::DynamicBitVec, 64, 60>(ctx); + test<chilbert::DynamicBitVec, 64, 64>(ctx); + test<chilbert::DynamicBitVec, 96, 65>(ctx); + test<chilbert::DynamicBitVec, 1024, 997>(ctx); + + test<chilbert::StaticBitVec<1>, 64, 1>(ctx); + test<chilbert::StaticBitVec<31>, 64, 31>(ctx); + test<chilbert::StaticBitVec<32>, 64, 32>(ctx); + test<chilbert::StaticBitVec<33>, 64, 33>(ctx); + test<chilbert::StaticBitVec<60>, 64, 60>(ctx); + test<chilbert::StaticBitVec<64>, 64, 64>(ctx); + 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 a0a64c0..1ed6f8c 100644 --- a/test/test_hilbert.cpp +++ b/test/test_hilbert.cpp @@ -35,191 +35,191 @@ #include <cstdint> /// Return a `D`-dimensional point within `ms` per-dimension precision -template <size_t D> +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; + 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> +template<class T, size_t D> T squared_distance(const std::array<T, D>& a, const std::array<T, D>& b) { - T sdist = 0; - for (size_t i = 0; i < D; ++i) { - const T diff = a[i] > b[i] ? a[i] - b[i] : b[i] - a[i]; - sdist += diff * diff; - } - return sdist; + T sdist = 0; + for (size_t i = 0; i < D; ++i) { + const T diff = a[i] > b[i] ? a[i] - b[i] : b[i] - a[i]; + sdist += diff * diff; + } + return sdist; } /// Convert bit vector `vec` to a big integer -template <class T> +template<class T> mpz_class to_big_int(const T& vec) { - using Rack = typename T::Rack; - - mpz_t ia; - mpz_init(ia); - mpz_import(ia, vec.num_racks(), -1, sizeof(Rack), 0, 0, vec.data()); - const mpz_class num(ia); - mpz_clear(ia); - return num; + using Rack = typename T::Rack; + + mpz_t ia; + mpz_init(ia); + mpz_import(ia, vec.num_racks(), -1, sizeof(Rack), 0, 0, vec.data()); + const mpz_class num(ia); + mpz_clear(ia); + return num; } /// Convert big integer `num` to a bit vector -template <class T, size_t M> +template<class T, size_t M> T from_big_int(const mpz_class& num) { - using Rack = typename T::Rack; + using Rack = typename T::Rack; - T vec = make_zero_bitvec<T, M>(); - size_t count = 0; - mpz_export(vec.data(), &count, -1, sizeof(Rack), 0, 0, num.get_mpz_t()); - assert(count <= static_cast<size_t>(vec.num_racks())); - return vec; + T vec = make_zero_bitvec<T, M>(); + size_t count = 0; + mpz_export(vec.data(), &count, -1, sizeof(Rack), 0, 0, num.get_mpz_t()); + assert(count <= static_cast<size_t>(vec.num_racks())); + return vec; } -template <class H, size_t M, size_t D> +template<class H, size_t M, size_t D> void test_standard(Context& ctx) { - static_assert(M < sizeof(typename H::Rack) * CHAR_BIT, ""); + static_assert(M < sizeof(typename H::Rack) * CHAR_BIT, ""); - // Generate random point and its hilbert index - const auto pa = make_random_point<M, D>(ctx); + // Generate random point and its hilbert index + const auto pa = make_random_point<M, D>(ctx); - H ha = make_zero_bitvec<H, D * M>(); - assert(ha.size() >= D * M); - chilbert::coords_to_index(pa, M, D, ha); + H ha = make_zero_bitvec<H, D * M>(); + assert(ha.size() >= D * M); + chilbert::coords_to_index(pa, M, D, ha); - { - // Ensure unmapping results in the original point - auto pa_out = make_random_point<M, D>(ctx); - chilbert::index_to_coords(pa_out, M, D, ha); - assert(pa_out == pa); - } + { + // Ensure unmapping results in the original point + auto pa_out = make_random_point<M, D>(ctx); + chilbert::index_to_coords(pa_out, M, D, ha); + assert(pa_out == pa); + } - // Convert hilbert indices to a big integer for manipulation/comparison - const auto ia = to_big_int(ha); + // 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<H, D * M>(ib); + // Generate the next hilbert index + const auto ib = ia + 1; + const auto hb = from_big_int<H, D * M>(ib); - // Unmap next hilbert index to a point - auto pb = make_random_point<M, D>(ctx); - chilbert::index_to_coords(pb, M, D, hb); + // Unmap next hilbert index to a point + auto pb = make_random_point<M, D>(ctx); + chilbert::index_to_coords(pb, M, D, hb); - // Ensure next point is 1 unit of distance away from first - assert(squared_distance(pa, pb) == 1); + // Ensure next point is 1 unit of distance away from first + assert(squared_distance(pa, pb) == 1); } -template <class T, size_t M, size_t D> +template<class T, size_t M, size_t D> void test_compact(Context& ctx) { - static_assert(M < sizeof(typename T::Rack) * CHAR_BIT, ""); + static_assert(M < sizeof(typename T::Rack) * 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); + // 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::coords_to_compact_index(pa, ms.data(), D, ha); + T ha = make_zero_bitvec<T, D * M>(); + assert(ha.size() >= D * M); + chilbert::coords_to_compact_index(pa, ms.data(), D, ha); - { - // Ensure unmapping results in the original point - auto pa_out = make_random_point<M, D>(ctx); - chilbert::compact_index_to_coords(pa_out, ms.data(), D, ha); - assert(pa_out == pa); - } + { + // Ensure unmapping results in the original point + auto pa_out = make_random_point<M, D>(ctx); + chilbert::compact_index_to_coords(pa_out, 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); + // 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); + // 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::compact_index_to_coords(pb, ms.data(), D, hb); + // Unmap next hilbert index to a point + auto pb = make_random_point<M, D>(ctx); + chilbert::compact_index_to_coords(pb, ms.data(), D, hb); - // Ensure next point is 1 unit of distance away from first - assert(squared_distance(pa, pb) == 1); + // Ensure next point is 1 unit of distance away from first + assert(squared_distance(pa, pb) == 1); } int main() { - Context ctx; - - test_standard<chilbert::SmallBitVec, 4, 2>(ctx); - test_standard<chilbert::SmallBitVec, 32, 2>(ctx); - test_standard<chilbert::SmallBitVec, 16, 4>(ctx); - test_standard<chilbert::SmallBitVec, 8, 8>(ctx); - test_standard<chilbert::SmallBitVec, 4, 16>(ctx); - test_standard<chilbert::SmallBitVec, 2, 32>(ctx); - test_standard<chilbert::SmallBitVec, 1, 64>(ctx); - - test_standard<chilbert::DynamicBitVec, 4, 65>(ctx); - test_standard<chilbert::DynamicBitVec, 32, 64>(ctx); - test_standard<chilbert::DynamicBitVec, 63, 128>(ctx); - - test_standard<chilbert::StaticBitVec<4 * 2>, 4, 2>(ctx); - test_standard<chilbert::StaticBitVec<32 * 2>, 32, 2>(ctx); - test_standard<chilbert::StaticBitVec<16 * 4>, 16, 4>(ctx); - test_standard<chilbert::StaticBitVec<8 * 8>, 8, 8>(ctx); - test_standard<chilbert::StaticBitVec<4 * 16>, 4, 16>(ctx); - test_standard<chilbert::StaticBitVec<2 * 32>, 2, 32>(ctx); - test_standard<chilbert::StaticBitVec<1 * 64>, 1, 64>(ctx); - test_standard<chilbert::StaticBitVec<4 * 65>, 4, 65>(ctx); - 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); - test_compact<chilbert::SmallBitVec, 8, 8>(ctx); - test_compact<chilbert::SmallBitVec, 4, 16>(ctx); - test_compact<chilbert::SmallBitVec, 2, 32>(ctx); - test_compact<chilbert::SmallBitVec, 1, 64>(ctx); - - test_compact<chilbert::DynamicBitVec, 4, 65>(ctx); - test_compact<chilbert::DynamicBitVec, 32, 64>(ctx); - test_compact<chilbert::DynamicBitVec, 63, 128>(ctx); - - test_compact<chilbert::StaticBitVec<4 * 2>, 4, 2>(ctx); - test_compact<chilbert::StaticBitVec<32 * 2>, 32, 2>(ctx); - test_compact<chilbert::StaticBitVec<16 * 4>, 16, 4>(ctx); - test_compact<chilbert::StaticBitVec<8 * 8>, 8, 8>(ctx); - test_compact<chilbert::StaticBitVec<4 * 16>, 4, 16>(ctx); - test_compact<chilbert::StaticBitVec<2 * 32>, 2, 32>(ctx); - test_compact<chilbert::StaticBitVec<1 * 64>, 1, 64>(ctx); - test_compact<chilbert::StaticBitVec<4 * 65>, 4, 65>(ctx); - test_compact<chilbert::StaticBitVec<32 * 64>, 32, 64>(ctx); - test_compact<chilbert::StaticBitVec<63 * 128>, 63, 128>(ctx); - - return 0; + Context ctx; + + test_standard<chilbert::SmallBitVec, 4, 2>(ctx); + test_standard<chilbert::SmallBitVec, 32, 2>(ctx); + test_standard<chilbert::SmallBitVec, 16, 4>(ctx); + test_standard<chilbert::SmallBitVec, 8, 8>(ctx); + test_standard<chilbert::SmallBitVec, 4, 16>(ctx); + test_standard<chilbert::SmallBitVec, 2, 32>(ctx); + test_standard<chilbert::SmallBitVec, 1, 64>(ctx); + + test_standard<chilbert::DynamicBitVec, 4, 65>(ctx); + test_standard<chilbert::DynamicBitVec, 32, 64>(ctx); + test_standard<chilbert::DynamicBitVec, 63, 128>(ctx); + + test_standard<chilbert::StaticBitVec<4 * 2>, 4, 2>(ctx); + test_standard<chilbert::StaticBitVec<32 * 2>, 32, 2>(ctx); + test_standard<chilbert::StaticBitVec<16 * 4>, 16, 4>(ctx); + test_standard<chilbert::StaticBitVec<8 * 8>, 8, 8>(ctx); + test_standard<chilbert::StaticBitVec<4 * 16>, 4, 16>(ctx); + test_standard<chilbert::StaticBitVec<2 * 32>, 2, 32>(ctx); + test_standard<chilbert::StaticBitVec<1 * 64>, 1, 64>(ctx); + test_standard<chilbert::StaticBitVec<4 * 65>, 4, 65>(ctx); + 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); + test_compact<chilbert::SmallBitVec, 8, 8>(ctx); + test_compact<chilbert::SmallBitVec, 4, 16>(ctx); + test_compact<chilbert::SmallBitVec, 2, 32>(ctx); + test_compact<chilbert::SmallBitVec, 1, 64>(ctx); + + test_compact<chilbert::DynamicBitVec, 4, 65>(ctx); + test_compact<chilbert::DynamicBitVec, 32, 64>(ctx); + test_compact<chilbert::DynamicBitVec, 63, 128>(ctx); + + test_compact<chilbert::StaticBitVec<4 * 2>, 4, 2>(ctx); + test_compact<chilbert::StaticBitVec<32 * 2>, 32, 2>(ctx); + test_compact<chilbert::StaticBitVec<16 * 4>, 16, 4>(ctx); + test_compact<chilbert::StaticBitVec<8 * 8>, 8, 8>(ctx); + test_compact<chilbert::StaticBitVec<4 * 16>, 4, 16>(ctx); + test_compact<chilbert::StaticBitVec<2 * 32>, 2, 32>(ctx); + test_compact<chilbert::StaticBitVec<1 * 64>, 1, 64>(ctx); + test_compact<chilbert::StaticBitVec<4 * 65>, 4, 65>(ctx); + test_compact<chilbert::StaticBitVec<32 * 64>, 32, 64>(ctx); + test_compact<chilbert::StaticBitVec<63 * 128>, 63, 128>(ctx); + + return 0; } diff --git a/test/test_utils.hpp b/test/test_utils.hpp index 65bd1b1..c3b6edb 100644 --- a/test/test_utils.hpp +++ b/test/test_utils.hpp @@ -26,70 +26,69 @@ #include <random> /// Test context -struct Context -{ - std::random_device rng; - std::uniform_int_distribution<size_t> dist{0, SIZE_MAX}; +struct Context { + std::random_device rng; + std::uniform_int_distribution<size_t> dist{0, SIZE_MAX}; }; /// Return a bit vector of type T with N zero bits -template <class T, size_t N> +template<class T, size_t N> T make_zero_bitvec() { - T v(N); - v.reset(); - return v; + T v(N); + v.reset(); + return v; } /// Return a bit vector of type T with N random bits -template <class T, size_t N> +template<class T, size_t N> T make_random_bitvec(Context& ctx) { - T v(N); - for (size_t i = 0; i < N; ++i) { - v.set(i, ctx.dist(ctx.rng) & 1U); - } - return v; + T v(N); + for (size_t i = 0; i < N; ++i) { + v.set(i, ctx.dist(ctx.rng) & 1U); + } + return v; } /// Return a random number in [min, max) static inline size_t rand_between(Context& ctx, const size_t min, const size_t max) { - assert(max >= min); - const size_t r = (max == min) ? min : ctx.dist(ctx.rng) % (max - min) + min; - assert(r >= min && r < max); - return r; + assert(max >= min); + const size_t r = (max == min) ? min : ctx.dist(ctx.rng) % (max - min) + min; + assert(r >= min && r < max); + return r; } /// Return an array of D precisions each at most Max and with sum at most N -template <size_t N, size_t D, size_t Max = 64> +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{}; + 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]; - } + 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; + return ms; } /// Return a `D`-dimensional point with `M` bits of precision per dimension -template <size_t M, size_t D> +template<size_t M, size_t D> std::array<uint64_t, D> make_random_point(Context& ctx) { - std::array<uint64_t, D> p{}; - for (size_t i = 0; i < D; ++i) { - p[i] = rand_between(ctx, 0, (1UL << M) - 1); - } - return p; + std::array<uint64_t, D> p{}; + for (size_t i = 0; i < D; ++i) { + p[i] = rand_between(ctx, 0, (1UL << M) - 1); + } + return p; } #endif |