aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAdrian Kummerländer2014-02-04 17:40:40 +0100
committerAdrian Kummerländer2014-02-04 17:40:40 +0100
commit24dee38d72ffa8b0a2515dc40c00a43b46526438 (patch)
tree5607cdbbaa2371b51ca5efda2c6ef8364a0a9759
parent7125d86a61030d5bec037d287840e0565d62a594 (diff)
downloadTrie-24dee38d72ffa8b0a2515dc40c00a43b46526438.tar
Trie-24dee38d72ffa8b0a2515dc40c00a43b46526438.tar.gz
Trie-24dee38d72ffa8b0a2515dc40c00a43b46526438.tar.bz2
Trie-24dee38d72ffa8b0a2515dc40c00a43b46526438.tar.xz
Trie-24dee38d72ffa8b0a2515dc40c00a43b46526438.zip
Added key_list typedef and tried to improve expressiveness
-rw-r--r--trie.cc34
1 files changed, 21 insertions, 13 deletions
diff --git a/trie.cc b/trie.cc
index 55dee38..1da306c 100644
--- a/trie.cc
+++ b/trie.cc
@@ -10,41 +10,49 @@ template <
>
class Trie {
public:
+ typedef std::forward_list<Key> key_list;
+
Trie():
children_() { }
- inline void add(std::forward_list<Key> path) {
+ inline void add(key_list path) {
this->add(path, path.begin());
}
- inline void add(std::forward_list<Key>& path,
- typename std::forward_list<Key>::const_iterator curr) {
+ inline void add(
+ key_list& path,
+ typename key_list::const_iterator curr
+ ) {
if ( curr != path.end() ) {
- Trie& trie = this->children_[*curr];
+ Trie& trie(
+ this->children_[*curr]
+ );
trie.add(path, ++curr);
}
}
- inline std::pair<bool, const Trie*> resolve(
- std::forward_list<Key> path
- ) const {
+ inline std::pair<bool, const Trie*> resolve(key_list path) const {
return this->resolve(path, path.begin());
}
inline std::pair<bool, const Trie*> resolve(
- std::forward_list<Key>& path,
- typename std::forward_list<Key>::const_iterator currStep
+ key_list& path,
+ typename key_list::const_iterator currStep
) const {
- auto matchingTrie = this->children_.find(*curr);
+ typename std::map<Key, Trie>::const_iterator matchingTrie(
+ this->children_.find(*currStep)
+ );
if ( matchingTrie != this->children_.end() ) {
- auto nextStep = ++currStep;
+ typename key_list::const_iterator nextStep(
+ ++currStep
+ );
if ( nextStep == path.end() ) {
- return std::make_pair(true, &(*trie).second);
+ return std::make_pair(true, &(*matchingTrie).second);
} else {
- return (*trie).second.resolve(path, nextStep);
+ return (*matchingTrie).second.resolve(path, nextStep);
}
} else {
return std::make_pair(false, nullptr);