[search] Fuzzy search by category.

1 files changed, 49 insertions, 17 deletions

diff --git a/base/mem_trie.hpp b/base/mem_trie.hpp
index fdd35af365..d5394f5bf3 100644
--- a/base/mem_trie.hpp
+++ b/base/mem_trie.hpp
@@ -15,7 +15,12 @@ namespace my
 template <typename String, typename Value>
 class MemTrie
 {
+private:
+  struct Node;
+
 public:
+  using Char = typename String::value_type;
+
   MemTrie() = default;
   MemTrie(MemTrie && rhs) { *this = std::move(rhs); }
 
@@ -27,6 +32,31 @@ public:
     return *this;
   }
 
+  // A read-only iterator. Any modification to the
+  // underlying trie is assumed to invalidate the iterator.
+  class Iterator
+  {
+  public:
+    Iterator(MemTrie::Node const & node) : m_node(node) {}
+
+    template <typename ToDo>
+    void ForEachMove(ToDo && todo) const
+    {
+      for (auto const & move : m_node.m_moves)
+        todo(move.first, Iterator(*move.second));
+    }
+
+    template <typename ToDo>
+    void ForEachInNode(ToDo && todo) const
+    {
+      for (auto const & value : m_node.m_values)
+        todo(value);
+    }
+
+  private:
+    MemTrie::Node const & m_node;
+  };
+
   // Adds a key-value pair to the trie.
   void Add(String const & key, Value const & value)
   {
@@ -41,40 +71,42 @@ public:
     cur->AddValue(value);
   }
 
-  // Traverses all key-value pairs in the trie and calls |toDo| on each of them.
+  // Traverses all key-value pairs in the trie and calls |todo| on each of them.
   template <typename ToDo>
-  void ForEachInTrie(ToDo && toDo) const
+  void ForEachInTrie(ToDo && todo) const
   {
     String prefix;
-    ForEachInSubtree(m_root, prefix, std::forward<ToDo>(toDo));
+    ForEachInSubtree(m_root, prefix, std::forward<ToDo>(todo));
   }
 
-  // Calls |toDo| for each key-value pair in the node that is reachable
+  // Calls |todo| for each key-value pair in the node that is reachable
   // by |prefix| from the trie root. Does nothing if such node does
   // not exist.
   template <typename ToDo>
-  void ForEachInNode(String const & prefix, ToDo && toDo) const
+  void ForEachInNode(String const & prefix, ToDo && todo) const
   {
     if (auto const * root = MoveTo(prefix))
-      ForEachInNode(*root, prefix, std::forward<ToDo>(toDo));
+      ForEachInNode(*root, prefix, std::forward<ToDo>(todo));
   }
 
-  // Calls |toDo| for each key-value pair in a subtree that is
+  // Calls |todo| for each key-value pair in a subtree that is
   // reachable by |prefix| from the trie root. Does nothing if such
   // subtree does not exist.
   template <typename ToDo>
-  void ForEachInSubtree(String prefix, ToDo && toDo) const
+  void ForEachInSubtree(String prefix, ToDo && todo) const
   {
     if (auto const * root = MoveTo(prefix))
-      ForEachInSubtree(*root, prefix, std::forward<ToDo>(toDo));
+      ForEachInSubtree(*root, prefix, std::forward<ToDo>(todo));
   }
 
   size_t GetNumNodes() const { return m_numNodes; }
+  Iterator GetRootIterator() const { return Iterator(m_root); }
+  Node const & GetRoot() const { return m_root; }
 
 private:
   struct Node
   {
-    using Char = typename String::value_type;
+    friend class MemTrie<String, Value>::Iterator;
 
     Node() = default;
     Node(Node && /* rhs */) = default;
@@ -117,27 +149,27 @@ private:
     return cur;
   }
 
-  // Calls |toDo| for each key-value pair in a |node| that is
+  // Calls |todo| for each key-value pair in a |node| that is
   // reachable by |prefix| from the trie root.
   template <typename ToDo>
-  void ForEachInNode(Node const & node, String const & prefix, ToDo && toDo) const
+  void ForEachInNode(Node const & node, String const & prefix, ToDo && todo) const
   {
     for (auto const & value : node.m_values)
-      toDo(prefix, value);
+      todo(prefix, value);
   }
 
-  // Calls |toDo| for each key-value pair in subtree where |node| is a
+  // Calls |todo| for each key-value pair in subtree where |node| is a
   // root of the subtree. |prefix| is a path from the trie root to the
   // |node|.
   template <typename ToDo>
-  void ForEachInSubtree(Node const & node, String & prefix, ToDo && toDo) const
+  void ForEachInSubtree(Node const & node, String & prefix, ToDo && todo) const
   {
-    ForEachInNode(node, prefix, toDo);
+    ForEachInNode(node, prefix, todo);
 
     for (auto const & move : node.m_moves)
     {
       prefix.push_back(move.first);
-      ForEachInSubtree(*move.second, prefix, toDo);
+      ForEachInSubtree(*move.second, prefix, todo);
       prefix.pop_back();
     }
   }