From 2f13baa843bd1fb5db6630a2823681ffaff9fb11 Mon Sep 17 00:00:00 2001 From: Joel Klinghed Date: Sat, 27 Sep 2025 18:25:10 +0200 Subject: Add simple prefix_tree Will be used by tokenizer for short lists of strings --- test/prefix_tree.cc | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 test/prefix_tree.cc (limited to 'test/prefix_tree.cc') diff --git a/test/prefix_tree.cc b/test/prefix_tree.cc new file mode 100644 index 0000000..6c00adb --- /dev/null +++ b/test/prefix_tree.cc @@ -0,0 +1,47 @@ +#include "prefix_tree.hh" + +#include + +TEST(prefix_tree, empty) { + auto builder = prefix_tree::builder(); + 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(), "foo"); + EXPECT_FALSE(ret.has_value()); +} + +TEST(prefix_tree, sanity) { + auto builder = prefix_tree::builder(); + builder->add("foo"); + builder->add("bar"); + builder->add("foobar"); + 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(), "foo"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); + ret = prefix_tree::lookup(tree.value(), "foobar"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(6, ret.value()); + ret = prefix_tree::lookup(tree.value(), "bar"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); + ret = prefix_tree::lookup(tree.value(), "ba"); + EXPECT_FALSE(ret.has_value()); + ret = prefix_tree::lookup(tree.value(), "barf"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); + ret = prefix_tree::lookup(tree.value(), "foob"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); + ret = prefix_tree::lookup(tree.value(), "foozum"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); + ret = prefix_tree::lookup(tree.value(), "barfoo"); + ASSERT_TRUE(ret.has_value()); + EXPECT_EQ(3, ret.value()); +} -- cgit v1.3