Add interval tree

2 files changed, 341 insertions, 0 deletions

diff --git a/deps/interval_tree/test/CMakeLists.txt b/deps/interval_tree/test/CMakeLists.txt
new file mode 100644
index 0000000..c56eea6
--- /dev/null
+++ b/deps/interval_tree/test/CMakeLists.txt
@@ -0,0 +1,5 @@
+add_executable(gtest_interval_tree gtest_interval_tree.cpp)
+target_link_libraries(gtest_interval_tree interval_tree gtest)
+
+include(GoogleTest)
+gtest_discover_tests(gtest_interval_tree)
\ No newline at end of file
diff --git a/deps/interval_tree/test/gtest_interval_tree.cpp b/deps/interval_tree/test/gtest_interval_tree.cpp
new file mode 100644
index 0000000..417c275
--- /dev/null
+++ b/deps/interval_tree/test/gtest_interval_tree.cpp
@@ -0,0 +1,336 @@
+#include <gtest/gtest.h>
+
+#include "itree.h"
+
+void *my_dup(void *p)
+{
+    return p ? strdup((const char *)p) : NULL;
+}
+
+void my_rel(void *p)
+{
+    if (p)
+    {
+        free(p);
+    }
+}
+
+// find overlap
+#if 1
+TEST(INTERVAL_TREE, FIND)
+{
+    itree_t *tree;
+    interval_t *result;
+    interval_t query;
+    interval_t segment;
+
+    // new
+    tree = itree_new(my_dup, my_rel);
+    EXPECT_TRUE(tree != nullptr);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"Hello",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // find
+    query = {
+        .low = 5,
+        .high = 5,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // find
+    query = {
+        .low = 6,
+        .high = 8,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // find
+    query = {
+        .low = 5,
+        .high = 9,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // find
+    query = {
+        .low = 9,
+        .high = 9,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // find
+    query = {
+        .low = 1,
+        .high = 14,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // not found
+    query = {
+        .low = 1,
+        .high = 4,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result == nullptr);
+
+    // not found
+    query = {
+        .low = 10,
+        .high = 14,
+    };
+    result = itree_find(tree, &query);
+
+    itree_delete(tree);
+}
+#endif
+
+#if 1
+TEST(INTERVAL_TREE, DELETE1)
+{
+    itree_t *tree;
+    interval_t query;
+    interval_t segment;
+
+    // new
+    tree = itree_new(my_dup, my_rel);
+    EXPECT_TRUE(tree != nullptr);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"Hello",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // delete
+    query = {
+        .low = 5,
+        .high = 5,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 0);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // delete
+    query = {
+        .low = 9,
+        .high = 9,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 0);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // delete
+    query = {
+        .low = 5,
+        .high = 9,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 1);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    itree_delete(tree);
+}
+#endif
+
+#if 1
+TEST(INTERVAL_TREE, DELETE2)
+{
+    itree_t *tree;
+    interval_t query;
+    interval_t segment;
+
+    // new
+    tree = itree_new(my_dup, my_rel);
+    EXPECT_TRUE(tree != nullptr);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"Hello",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // insert
+    segment = {
+        .low = 15,
+        .high = 19,
+        .data = (void *)"World",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 2);
+
+    // delete
+    query = {
+        .low = 1,
+        .high = 20,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // delete
+    query = {
+        .low = 1,
+        .high = 20,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 1);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    itree_delete(tree);
+}
+#endif
+
+#if 1
+TEST(INTERVAL_TREE, REPEAT1)
+{
+    itree_t *tree;
+    interval_t segment;
+    interval_t query;
+
+    // new
+    tree = itree_new(my_dup, my_rel);
+    EXPECT_TRUE(tree != nullptr);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"Hello",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"World",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 2);
+
+    // remove
+    query = {
+        .low = 5,
+        .high = 9,
+    };
+    EXPECT_TRUE(itree_remove(tree, &query) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+    EXPECT_TRUE(itree_remove(tree, &query) == 1);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    itree_delete(tree);
+}
+#endif
+
+#if 1 // repeat, return the fist one
+TEST(INTERVAL_TREE, REPEAT2)
+{
+    itree_t *tree;
+    ilist_t *list;
+    ilisttrav_t *trav;
+    interval_t *result;
+    interval_t query;
+    interval_t segment;
+
+    // new
+    tree = itree_new(my_dup, my_rel);
+    EXPECT_TRUE(tree != nullptr);
+    EXPECT_TRUE(itree_size(tree) == 0);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"Hello",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 1);
+
+    // insert
+    segment = {
+        .low = 5,
+        .high = 9,
+        .data = (void *)"World",
+    };
+    EXPECT_TRUE(itree_insert(tree, &segment) == 1);
+    EXPECT_TRUE(itree_size(tree) == 2);
+
+    // find
+    query = {
+        .low = 5,
+        .high = 9,
+    };
+    result = itree_find(tree, &query);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    // find all, free the repeat
+    query = {
+        .low = 5,
+        .high = 9,
+    };
+    list = itree_findall(tree, &query);
+    EXPECT_TRUE(list != nullptr);
+    EXPECT_TRUE(ilist_size(list) == 2);
+    trav = ilisttrav_new(list);
+    EXPECT_TRUE(trav != nullptr);
+
+    result = (interval_t *)ilisttrav_first(trav);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "Hello");
+
+    result = (interval_t *)ilisttrav_next(trav);
+    EXPECT_TRUE(result != nullptr);
+    EXPECT_TRUE(result->low == 5);
+    EXPECT_TRUE(result->high == 9);
+    EXPECT_STREQ((const char *)result->data, "World");
+
+    ilisttrav_delete(trav);
+    ilist_delete(list);
+
+    itree_delete(tree);
+}
+#endif
+
+int main(int argc, char **argv)
+{
+    ::testing::InitGoogleTest(&argc, argv);
+    return RUN_ALL_TESTS();
+}