blob: dd19256f0a71568721d7708846ea416e2d5defc9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#pragma once
#include "base/macros.hpp"
#include "std/map.hpp"
#include "std/vector.hpp"
namespace my
{
/// This class is a simple in-memory trie which allows to add
/// key-value pairs and then traverse them in a sorted order.
template <typename StringT, typename ValueT>
class MemTrie
{
public:
MemTrie() = default;
/// Adds a key-value pair to the trie.
void Add(StringT const & key, ValueT const & value)
{
Node * cur = &m_root;
for (auto const & c : key)
cur = cur->GetMove(c);
cur->AddValue(value);
}
/// Traverses all key-value pairs in the trie in a sorted order.
///
/// \param toDo A callable object that will be called on an each
/// key-value pair.
template <typename ToDo>
void ForEach(ToDo const & toDo)
{
StringT prefix;
ForEach(&m_root, prefix, toDo);
}
private:
struct Node
{
using CharT = typename StringT::value_type;
using MovesMap = map<CharT, Node *>;
Node() = default;
~Node()
{
for (auto const & move : m_moves)
delete move.second;
}
Node * GetMove(CharT const & c)
{
Node *& node = m_moves[c];
if (!node)
node = new Node();
return node;
}
void AddValue(const ValueT & value) { m_values.push_back(value); }
MovesMap m_moves;
vector<ValueT> m_values;
DISALLOW_COPY_AND_MOVE(Node);
};
template <typename ToDo>
void ForEach(Node * root, StringT & prefix, ToDo const & toDo)
{
if (!root->m_values.empty())
{
sort(root->m_values.begin(), root->m_values.end());
for (auto const & value : root->m_values)
toDo(prefix, value);
}
for (auto const & move : root->m_moves)
{
prefix.push_back(move.first);
ForEach(move.second, prefix, toDo);
prefix.pop_back();
}
}
Node m_root;
DISALLOW_COPY_AND_MOVE(MemTrie);
}; // class MemTrie
} // namespace my
|
