aboutsummaryrefslogtreecommitdiff
path: root/src/trie.h
blob: 9134c454073adfe2ac1052f01cb1917cf39b0782 (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
91
92
93
94
#ifndef TRIE_SRC_TRIE_H_
#define TRIE_SRC_TRIE_H_

#include <vector>
#include <map>

template <
	typename Key
>
class Trie {
	public:
		typedef std::vector<Key> key_list;

		Trie():
			children_() { }

		inline void add(key_list path) {
			this->add(path, path.begin());
		}

		inline void add(
			key_list& path,
			typename key_list::const_iterator currStep
		) {
			if ( currStep != path.end() ) {
				Trie& trie(
					this->children_[*currStep]
				);

				trie.add(path, ++currStep);
			}
		}

		inline void remove(key_list path) {
			this->remove(path, path.begin());
		}

		inline void remove(
			key_list& path,
			typename key_list::const_iterator currStep
		) {
			if ( currStep != path.end() ) {
				typename std::map<Key, Trie>::iterator matchingTrie(
					this->children_.find(*currStep)
				);

				if ( matchingTrie != this->children_.end() ) {
					typename key_list::const_iterator nextStep(
						++currStep
					);

					if ( (*matchingTrie).second.children_.empty() ||
					     nextStep == path.end() ) {
						this->children_.erase(matchingTrie);
					} else {
						(*matchingTrie).second.remove(path, nextStep);
					}
				}
			}
		}

		inline std::pair<bool, const Trie*> resolve(key_list path) const {
			return this->resolve(path, path.begin());
		}

		inline std::pair<bool, const Trie*> resolve(
			key_list& path,
			typename key_list::const_iterator currStep
		) const {
			typename std::map<Key, Trie>::const_iterator matchingTrie(
				this->children_.find(*currStep)
			);

			if ( matchingTrie != this->children_.end() ) {
				typename key_list::const_iterator nextStep(
					++currStep
				);

				if ( nextStep == path.end() ) {
					return std::make_pair(true, &(*matchingTrie).second);
				} else {
					return (*matchingTrie).second.resolve(path, nextStep);
				}
			} else {
				return std::make_pair(false, nullptr);
			}
		}

	private:
		std::map<Key, Trie> children_;

};

#endif  // TRIE_SRC_TRIE_H_