From 2f13baa843bd1fb5db6630a2823681ffaff9fb11 Mon Sep 17 00:00:00 2001
From: Joel Klinghed <the_jk@spawned.biz>
Date: Sat, 27 Sep 2025 18:25:10 +0200
Subject: Add simple prefix_tree

Will be used by tokenizer for short lists of strings
---
 src/prefix_tree.hh | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 src/prefix_tree.hh

(limited to 'src/prefix_tree.hh')

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
-- 
cgit v1.3