Added TrieSpline and PGM Range queries + tests and bugfixes

3 files changed, 144 insertions, 3 deletions

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
@@ -96,6 +96,27 @@ static de::MutableBuffer<R> *create_test_mbuffer(size_t cnt)
 }
 
 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) 
 {
     auto buffer = new de::MutableBuffer<R>(cnt, true, 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;
 }