aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAdrian Kummerländer2014-02-06 16:14:16 +0100
committerAdrian Kummerländer2014-02-06 16:14:16 +0100
commitc86f957426a2399217bcca466dec7a83d0981ba3 (patch)
tree4f87e24cc6ef067f610cd64b03de09cc20e6a4e7 /src
parent4784dd77398d362130a794607b478547e5628ab3 (diff)
downloadTrie-c86f957426a2399217bcca466dec7a83d0981ba3.tar
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.gz
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.bz2
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.lz
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.xz
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.zst
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.zip
Implemented trie value support
* template can now be specialized on a value type * simple existance check of trie paths can be achieved using the check member method * new get member method can be used to query values ** values are stored as std::pair<bool, Value> to make them optional * expanded test cases accordingly
Diffstat (limited to 'src')
-rw-r--r--src/trie.h50
1 files changed, 41 insertions, 9 deletions
diff --git a/src/trie.h b/src/trie.h
index 873a375..46fcb4b 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -5,31 +5,57 @@
#include <map>
template <
- typename Key
+ typename Key,
+ typename Value = std::nullptr_t
>
class Trie {
public:
typedef std::vector<Key> key_list;
Trie():
- children_() { }
+ value_(),
+ children_() {
+ this->value_.first = false;
+ }
inline void add(key_list path) {
this->add(path, path.begin());
}
+ inline void add(key_list path, Value value) {
+ Trie* tmp = this->add(path, path.begin());
+
+ tmp->value_.first = true;
+ tmp->value_.second = value;
+ }
+
inline void remove(key_list path) {
this->remove(path, path.begin());
}
- inline std::pair<bool, const Trie*> resolve(key_list path) const {
- return this->resolve(path, path.begin());
+ inline bool check(key_list path) {
+ return this->resolve(path).first;
+ }
+
+ inline std::pair<bool, Value*> get(key_list path) {
+ std::pair<bool, Trie*> tmp(this->resolve(path));
+
+ if ( tmp.first ) {
+ if ( tmp.second->value_.first ) {
+ return std::make_pair(true, &tmp.second->value_.second);
+ } else {
+ return std::make_pair(false, nullptr);
+ }
+ } else {
+ return std::make_pair(false, nullptr);
+ }
}
private:
+ std::pair<bool, Value> value_;
std::map<Key, Trie> children_;
- inline void add(
+ inline Trie* add(
key_list& path,
typename key_list::const_iterator currStep
) {
@@ -38,7 +64,9 @@ class Trie {
this->children_[*currStep]
);
- trie.add(path, ++currStep);
+ return trie.add(path, ++currStep);
+ } else {
+ return this;
}
}
@@ -66,11 +94,15 @@ class Trie {
}
}
- inline std::pair<bool, const Trie*> resolve(
+ inline std::pair<bool, Trie*> resolve(key_list path) {
+ return this->resolve(path, path.begin());
+ }
+
+ inline std::pair<bool, Trie*> resolve(
key_list& path,
typename key_list::const_iterator currStep
- ) const {
- typename std::map<Key, Trie>::const_iterator matchingTrie(
+ ) {
+ typename std::map<Key, Trie>::iterator matchingTrie(
this->children_.find(*currStep)
);