prefix_tree: Make a byte optimized version for really small trees

Currently supports 8-bit distances and 16-bit distances.

1 files changed, 26 insertions, 0 deletions

diff --git a/test/prefix_tree.cc b/test/prefix_tree.cc
index 6c00adb..86c8990 100644
--- a/test/prefix_tree.cc
+++ b/test/prefix_tree.cc
@@ -1,5 +1,7 @@
 #include "prefix_tree.hh"
 
+#include "str.hh"
+
 #include <gtest/gtest.h>
 
 TEST(prefix_tree, empty) {
@@ -45,3 +47,27 @@ TEST(prefix_tree, sanity) {
   ASSERT_TRUE(ret.has_value());
   EXPECT_EQ(3, ret.value());
 }
+
+TEST(prefix_tree, many_and_long) {
+  auto builder = prefix_tree::builder();
+  for (auto str : str::split(
+           "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do "
+           "eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut "
+           "enim ad minim veniam, quis nostrud exercitation ullamco laboris "
+           "nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in "
+           "reprehenderit in voluptate velit esse cillum dolore eu fugiat "
+           "nulla pariatur. Excepteur sint occaecat cupidatat non proident, "
+           "sunt in culpa qui officia deserunt mollit anim id est laborum.")) {
+    builder->add(str);
+  }
+  auto tree = builder->build();
+  ASSERT_TRUE(tree.has_value());
+  auto ret = prefix_tree::lookup(tree.value(), "");
+  EXPECT_FALSE(ret.has_value());
+  ret = prefix_tree::lookup(tree.value(), "Lorem");
+  ASSERT_TRUE(ret.has_value());
+  EXPECT_EQ(5, ret.value());
+  ret = prefix_tree::lookup(tree.value(), "cillum");
+  ASSERT_TRUE(ret.has_value());
+  EXPECT_EQ(6, ret.value());
+}