From d47eeea719448f649e93b6a9ec7593b4cb2fb40e Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Mon, 5 Jun 2023 14:25:19 -0400
Subject: Added TrieSpline and PGM Range queries + tests and bugfixes

---
 tests/pgm_tests.cpp        | 59 ++++++++++++++++++++++++++++++++++++++++
 tests/testing.h            | 21 +++++++++++++++
 tests/triespline_tests.cpp | 67 +++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 144 insertions(+), 3 deletions(-)

(limited to 'tests')

diff --git a/tests/pgm_tests.cpp b/tests/pgm_tests.cpp
index 33979ae..254de03 100644
--- a/tests/pgm_tests.cpp
+++ b/tests/pgm_tests.cpp
@@ -139,6 +139,60 @@ START_TEST(t_point_lookup_miss)
 }
 
 
+START_TEST(t_range_query)
+{
+    auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
+    auto shard = Shard(buffer);
+
+    pgm_range_query_parms<Rec> parms;
+    parms.lower_bound = 300;
+    parms.upper_bound = 500;
+
+    auto state = PGMRangeQuery<Rec>::get_query_state(&shard, &parms);
+    auto result = PGMRangeQuery<Rec>::query(&shard, state, &parms);
+    PGMRangeQuery<Rec>::delete_query_state(state);
+
+    ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1);
+    for (size_t i=0; i<result.size(); i++) {
+        ck_assert_int_le(result[i].rec.key, parms.upper_bound);
+        ck_assert_int_ge(result[i].rec.key, parms.lower_bound);
+    }
+
+    delete buffer;
+}
+END_TEST
+
+
+START_TEST(t_buffer_range_query)
+{
+    auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
+
+    pgm_range_query_parms<Rec> parms;
+    parms.lower_bound = 300;
+    parms.upper_bound = 500;
+
+    auto state = PGMRangeQuery<Rec>::get_buffer_query_state(buffer, &parms);
+    auto result = PGMRangeQuery<Rec>::buffer_query(buffer, state, &parms);
+    PGMRangeQuery<Rec>::delete_buffer_query_state(state);
+
+    ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1);
+    for (size_t i=0; i<result.size(); i++) {
+        ck_assert_int_le(result[i].rec.key, parms.upper_bound);
+        ck_assert_int_ge(result[i].rec.key, parms.lower_bound);
+    }
+
+    delete buffer;
+}
+END_TEST
+
+
+START_TEST(t_range_query_merge)
+{
+
+}
+END_TEST
+
+
 START_TEST(t_full_cancelation)
 {
     size_t n = 100;
@@ -190,6 +244,11 @@ Suite *unit_testing()
     tcase_add_test(lookup, t_point_lookup_miss);
     suite_add_tcase(unit, lookup);
 
+    TCase *range_query = tcase_create("de:PGM::range_query Testing");
+    tcase_add_test(range_query, t_range_query);
+    tcase_add_test(range_query, t_buffer_range_query);
+    tcase_add_test(range_query, t_range_query_merge);
+    suite_add_tcase(unit, range_query);
 
     return unit;
 }
diff --git a/tests/testing.h b/tests/testing.h
index 0be65e3..4277015 100644
--- a/tests/testing.h
+++ b/tests/testing.h
@@ -95,6 +95,27 @@ static de::MutableBuffer<R> *create_test_mbuffer(size_t cnt)
     return buffer;
 }
 
+template <de::RecordInterface R>
+static de::MutableBuffer<R> *create_sequential_mbuffer(decltype(R::key) start, decltype(R::key) stop)
+{
+    size_t cnt = stop - start;
+    auto buffer = new de::MutableBuffer<R>(cnt, true, cnt);
+
+    for (size_t i=start; i<stop; i++) {
+        R rec;
+        rec.key = i;
+        rec.value = i;
+
+        if constexpr (de::WeightedRecordInterface<R>) {
+            rec.weight = 1;
+        }
+
+        buffer->append(rec);
+    }
+
+    return buffer;
+}
+
 template <de::RecordInterface R>
 static de::MutableBuffer<R> *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt) 
 {
diff --git a/tests/triespline_tests.cpp b/tests/triespline_tests.cpp
index 982be79..d88d4b1 100644
--- a/tests/triespline_tests.cpp
+++ b/tests/triespline_tests.cpp
@@ -1,5 +1,5 @@
 /*
- * tests/irs_tests.cpp
+ * tests/triespline_tests.cpp
  *
  * Unit tests for TrieSpline (Augmented B+Tree) shard
  *
@@ -45,7 +45,7 @@ START_TEST(t_mbuffer_init)
 }
 
 
-START_TEST(t_irs_init)
+START_TEST(t_init)
 {
     size_t n = 512;
     auto mbuffer1 = create_test_mbuffer<Rec>(n);
@@ -169,13 +169,67 @@ START_TEST(t_full_cancelation)
 END_TEST
 
 
+START_TEST(t_range_query)
+{
+    auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
+    auto shard = Shard(buffer);
+
+    ts_range_query_parms<Rec> parms;
+    parms.lower_bound = 300;
+    parms.upper_bound = 500;
+
+    auto state = TrieSplineRangeQuery<Rec>::get_query_state(&shard, &parms);
+    auto result = TrieSplineRangeQuery<Rec>::query(&shard, state, &parms);
+    TrieSplineRangeQuery<Rec>::delete_query_state(state);
+
+    ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1);
+    for (size_t i=0; i<result.size(); i++) {
+        ck_assert_int_le(result[i].rec.key, parms.upper_bound);
+        ck_assert_int_ge(result[i].rec.key, parms.lower_bound);
+    }
+
+    delete buffer;
+}
+END_TEST
+
+
+START_TEST(t_buffer_range_query)
+{
+    auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
+
+    ts_range_query_parms<Rec> parms;
+    parms.lower_bound = 300;
+    parms.upper_bound = 500;
+
+    auto state = TrieSplineRangeQuery<Rec>::get_buffer_query_state(buffer, &parms);
+    auto result = TrieSplineRangeQuery<Rec>::buffer_query(buffer, state, &parms);
+    TrieSplineRangeQuery<Rec>::delete_buffer_query_state(state);
+
+    ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1);
+    for (size_t i=0; i<result.size(); i++) {
+        ck_assert_int_le(result[i].rec.key, parms.upper_bound);
+        ck_assert_int_ge(result[i].rec.key, parms.lower_bound);
+    }
+
+    delete buffer;
+}
+END_TEST
+
+
+START_TEST(t_range_query_merge)
+{
+
+}
+END_TEST
+
+
 Suite *unit_testing()
 {
     Suite *unit = suite_create("TrieSpline Shard Unit Testing");
 
     TCase *create = tcase_create("de::TrieSpline constructor Testing");
     tcase_add_test(create, t_mbuffer_init);
-    tcase_add_test(create, t_irs_init);
+    tcase_add_test(create, t_init);
     tcase_set_timeout(create, 100);
     suite_add_tcase(unit, create);
 
@@ -191,6 +245,13 @@ Suite *unit_testing()
     suite_add_tcase(unit, lookup);
 
 
+    TCase *range_query = tcase_create("de:TrieSpline::range_query Testing");
+    tcase_add_test(range_query, t_range_query);
+    tcase_add_test(range_query, t_buffer_range_query);
+    tcase_add_test(range_query, t_range_query_merge);
+    suite_add_tcase(unit, range_query);
+
+
     return unit;
 }
 
-- 
cgit v1.2.3