blob: fe69ef7a9b2c0b8cedb75357dd2fbed428a81418 (
plain) (
blame)
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
|
#ifndef PREFIX_SEARCH_H_A6672A1D
#define PREFIX_SEARCH_H_A6672A1D
#include <unordered_map>
#include <vector>
#include <stdexcept>
template <typename T>
class prefix_search {
public:
prefix_search(size_t depth = 0) : depth_(depth), count_(0)
{
}
size_t getDepth() const
{
return depth_;
}
size_t getCount() const
{
return count_;
}
void add(std::string& key, T val, size_t i = 0)
{
count_++;
if (i == key.length())
{
elements_.push_back(val);
} else {
char next = key.at(i);
if (!children_.count(next))
{
children_.emplace(next, prefix_search<T> { depth_ + 1 } );
}
children_.at(next).add(key, val, i + 1);
}
}
T at(size_t i) const
{
if (i < elements_.size())
{
return elements_.at(i);
} else {
i -= elements_.size();
for (const auto& mapping : children_)
{
if (mapping.second.count_ > i)
{
return mapping.second.at(i);
} else {
i -= mapping.second.count_;
}
}
}
throw std::out_of_range("Index out of range");
}
const prefix_search<T>& find(const std::string& val, size_t i) const
{
if (i == val.length() || !children_.count(val.at(i)))
{
return *this;
}
return children_.at(val.at(i)).find(val, i+1);
}
private:
size_t depth_;
size_t count_;
std::unordered_map<char, prefix_search<T>> children_;
std::vector<T> elements_;
};
#endif /* end of include guard: PREFIX_SEARCH_H_A6672A1D */
|
