From 12915304570507e00848aba700f0ed3a26dbb9b6 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Thu, 13 Jul 2023 15:34:49 -0400 Subject: Initial commit of VPTree-related code Point lookups are currently broken; I suspect that there is something wrong with tree construction, although the quickselect implementation seems to be fine. --- tests/testing.h | 31 ++++++++-- tests/vptree_tests.cpp | 162 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 188 insertions(+), 5 deletions(-) create mode 100644 tests/vptree_tests.cpp (limited to 'tests') diff --git a/tests/testing.h b/tests/testing.h index fe6623e..1d5db59 100644 --- a/tests/testing.h +++ b/tests/testing.h @@ -23,6 +23,7 @@ typedef de::WeightedRecord WRec; typedef de::Record Rec; +typedef de::Point PRec; template std::vector strip_wrapping(std::vector> vec) { @@ -75,7 +76,26 @@ static bool roughly_equal(int n1, int n2, size_t mag, double epsilon) { return ((double) std::abs(n1 - n2) / (double) mag) < epsilon; } -template +static de::MutableBuffer *create_2d_mbuffer(size_t cnt) { + auto buffer = new de::MutableBuffer(cnt, cnt); + + for (int64_t i=0; iappend({rand(), rand()}); + } + + return buffer; +} + +static de::MutableBuffer *create_2d_sequential_mbuffer(size_t cnt) { + auto buffer = new de::MutableBuffer(cnt, cnt); + for (int64_t i=0; iappend({i, i}); + } + + return buffer; +} + +template static de::MutableBuffer *create_test_mbuffer(size_t cnt) { auto buffer = new de::MutableBuffer(cnt, cnt); @@ -95,7 +115,7 @@ static de::MutableBuffer *create_test_mbuffer(size_t cnt) return buffer; } -template +template static de::MutableBuffer *create_sequential_mbuffer(decltype(R::key) start, decltype(R::key) stop) { size_t cnt = stop - start; @@ -116,7 +136,7 @@ static de::MutableBuffer *create_sequential_mbuffer(decltype(R::key) start, d return buffer; } -template +template static de::MutableBuffer *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt) { auto buffer = new de::MutableBuffer(cnt, ts_cnt); @@ -147,7 +167,8 @@ static de::MutableBuffer *create_test_mbuffer_tombstones(size_t cnt, size_t t return buffer; } -template +template +requires de::WeightedRecordInterface && de::KVPInterface static de::MutableBuffer *create_weighted_mbuffer(size_t cnt) { auto buffer = new de::MutableBuffer(cnt, cnt); @@ -170,7 +191,7 @@ static de::MutableBuffer *create_weighted_mbuffer(size_t cnt) return buffer; } -template +template static de::MutableBuffer *create_double_seq_mbuffer(size_t cnt, bool ts=false) { auto buffer = new de::MutableBuffer(cnt, cnt); diff --git a/tests/vptree_tests.cpp b/tests/vptree_tests.cpp new file mode 100644 index 0000000..1b5c18c --- /dev/null +++ b/tests/vptree_tests.cpp @@ -0,0 +1,162 @@ +/* + * tests/vptree_tests.cpp + * + * Unit tests for VPTree (knn queries) + * + * Copyright (C) 2023 Douglas Rumbaugh + * + * All rights reserved. Published under the Modified BSD License. + * + */ + +#include "shard/VPTree.h" +#include "testing.h" + +#include + +using namespace de; + + +typedef VPTree Shard; + +START_TEST(t_mbuffer_init) +{ + size_t n= 24; + auto buffer = new MutableBuffer(n, n); + + for (int64_t i=0; iappend({i, i}); + } + + Shard* shard = new Shard(buffer); + ck_assert_uint_eq(shard->get_record_count(), n); + + delete buffer; + delete shard; +} + + +START_TEST(t_wss_init) +{ + size_t n = 512; + auto mbuffer1 = create_2d_mbuffer(n); + auto mbuffer2 = create_2d_mbuffer(n); + auto mbuffer3 = create_2d_mbuffer(n); + + auto shard1 = new Shard(mbuffer1); + auto shard2 = new Shard(mbuffer2); + auto shard3 = new Shard(mbuffer3); + + Shard* shards[3] = {shard1, shard2, shard3}; + auto shard4 = new Shard(shards, 3); + + ck_assert_int_eq(shard4->get_record_count(), n * 3); + ck_assert_int_eq(shard4->get_tombstone_count(), 0); + + delete mbuffer1; + delete mbuffer2; + delete mbuffer3; + + delete shard1; + delete shard2; + delete shard3; + delete shard4; +} + + +START_TEST(t_point_lookup) +{ + size_t n = 30; + + auto buffer = create_2d_sequential_mbuffer(n); + auto wss = Shard(buffer); + + for (size_t i=0; iget_data() + i); + r.x = rec->rec.x; + r.y = rec->rec.y; + + fprintf(stderr, "%ld\n", i); + + auto result = wss.point_lookup(r); + ck_assert_ptr_nonnull(result); + ck_assert_int_eq(result->rec.x, r.x); + ck_assert_int_eq(result->rec.y, r.y); + } + + delete buffer; +} +END_TEST + + +START_TEST(t_point_lookup_miss) +{ + size_t n = 10000; + + auto buffer = create_2d_sequential_mbuffer(n); + auto wss = Shard(buffer); + + for (size_t i=n + 100; i<2*n; i++) { + PRec r; + r.x = i; + r.y = i; + + auto result = wss.point_lookup(r); + ck_assert_ptr_null(result); + } + + delete buffer; +} + + +Suite *unit_testing() +{ + Suite *unit = suite_create("VPTree Shard Unit Testing"); + + TCase *create = tcase_create("de::VPTree constructor Testing"); + tcase_add_test(create, t_mbuffer_init); + tcase_add_test(create, t_wss_init); + tcase_set_timeout(create, 100); + suite_add_tcase(unit, create); + + + TCase *lookup = tcase_create("de:VPTree:point_lookup Testing"); + tcase_add_test(lookup, t_point_lookup); + tcase_add_test(lookup, t_point_lookup_miss); + suite_add_tcase(unit, lookup); + + + /* + TCase *sampling = tcase_create("de:VPTree::VPTreeQuery Testing"); + tcase_add_test(sampling, t_wss_query); + tcase_add_test(sampling, t_wss_query_merge); + tcase_add_test(sampling, t_wss_buffer_query_rejection); + tcase_add_test(sampling, t_wss_buffer_query_scan); + suite_add_tcase(unit, sampling); + */ + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} -- cgit v1.2.3