Add simple prefix_tree

Will be used by tokenizer for short lists of strings

1 files changed, 36 insertions, 0 deletions

diff --git a/src/prefix_tree.hh b/src/prefix_tree.hh
new file mode 100644
index 0000000..6e4c792
--- /dev/null
+++ b/src/prefix_tree.hh
@@ -0,0 +1,36 @@
+#ifndef PREFIX_TREE_HH
+#define PREFIX_TREE_HH
+
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+
+namespace prefix_tree {
+
+class Builder {
+ public:
+  virtual ~Builder() = default;
+
+  virtual void add(std::string_view str) = 0;
+  [[nodiscard]]
+  virtual std::optional<std::string> build() const = 0;
+
+ protected:
+  Builder() = default;
+
+  Builder(Builder const&) = delete;
+  Builder& operator=(Builder const&) = delete;
+};
+
+[[nodiscard]]
+std::unique_ptr<Builder> builder();
+
+// Returns the length of the prefix of str that exists in tree.
+// Returns nullopt if prefix of str doesn't match any string in tree.
+[[nodiscard]]
+std::optional<size_t> lookup(std::string_view tree, std::string_view str);
+
+}  // namespace prefix_tree
+
+#endif  // PREFIX_TREE_HH