aboutsummaryrefslogtreecommitdiff
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
parent4784dd77398d362130a794607b478547e5628ab3 (diff)
downloadTrie-c86f957426a2399217bcca466dec7a83d0981ba3.tar
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.gz
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.bz2
Trie-c86f957426a2399217bcca466dec7a83d0981ba3.tar.xz
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
-rw-r--r--src/trie.h50
-rw-r--r--test.cc55
2 files changed, 71 insertions, 34 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)
);
diff --git a/test.cc b/test.cc
index 2c38a3f..ff0b04f 100644
--- a/test.cc
+++ b/test.cc
@@ -14,20 +14,12 @@ TEST_F(TrieTest, Basic) {
trie.add({2, 3, 4, 5});
trie.add({2, 3, 1, 2});
- EXPECT_EQ(trie.resolve({1, 1, 1, 1}).first, true);
- EXPECT_NE(trie.resolve({1, 1, 1, 1}).second, nullptr);
+ EXPECT_EQ(trie.check({1, 1, 1, 1}), true);
+ EXPECT_EQ(trie.check({1, 2, 1, 2}), true);
+ EXPECT_EQ(trie.check({1, 2}), true);
- EXPECT_EQ(trie.resolve({1, 2, 1, 2}).first, true);
- EXPECT_NE(trie.resolve({1, 2, 1, 2}).second, nullptr);
-
- EXPECT_EQ(trie.resolve({1, 2}).first, true);
- EXPECT_NE(trie.resolve({1, 2}).second, nullptr);
-
- EXPECT_EQ(trie.resolve({1, 1, 2, 3}).first, false);
- EXPECT_EQ(trie.resolve({1, 1, 2, 3}).second, nullptr);
-
- EXPECT_EQ(trie.resolve({2, 1, 4}).first, false);
- EXPECT_EQ(trie.resolve({2, 1, 4}).second, nullptr);
+ EXPECT_EQ(trie.check({1, 1, 2, 3}), false);
+ EXPECT_EQ(trie.check({2, 1, 4}), false);
}
TEST_F(TrieTest, Remove) {
@@ -40,22 +32,35 @@ TEST_F(TrieTest, Remove) {
trie.remove({1, 1, 1, 1});
- EXPECT_EQ(trie.resolve({1, 1, 1, 1}).first, false);
- EXPECT_EQ(trie.resolve({1, 1, 1, 1}).second, nullptr);
-
- EXPECT_EQ(trie.resolve({1, 2, 1, 2}).first, true);
- EXPECT_NE(trie.resolve({1, 2, 1, 2}).second, nullptr);
+ EXPECT_EQ(trie.check({1, 1, 1, 1}), false);
+ EXPECT_EQ(trie.check({1, 2, 1, 2}), true);
trie.remove({2, 3});
- EXPECT_EQ(trie.resolve({2, 3, 4, 5}).first, false);
- EXPECT_EQ(trie.resolve({2, 3, 4, 5}).second, nullptr);
-
- EXPECT_EQ(trie.resolve({2, 3}).first, false);
- EXPECT_EQ(trie.resolve({2, 3}).second, nullptr);
+ EXPECT_EQ(trie.check({2, 3, 4, 5}), false);
+ EXPECT_EQ(trie.check({2, 3}), false);
+ EXPECT_EQ(trie.check({2}), true);
+}
- EXPECT_EQ(trie.resolve({2}).first, true);
- EXPECT_NE(trie.resolve({2}).second, nullptr);
+TEST_F(TrieTest, Value) {
+ Trie<uint8_t, uint8_t> trie;
+
+ trie.add({1, 1, 1, 1}, 42);
+ trie.add({1, 2, 1, 2}, 43);
+ trie.add({2, 3, 4, 5}, 44);
+ trie.add({2, 3, 1, 2}, 45);
+
+ EXPECT_EQ(trie.get({1, 1, 1, 1}).first, true);
+ EXPECT_EQ(*trie.get({1, 1, 1, 1}).second, 42);
+ EXPECT_EQ(trie.get({1, 2, 1, 2}).first, true);
+ EXPECT_EQ(*trie.get({1, 2, 1, 2}).second, 43);
+ EXPECT_EQ(trie.get({2, 3, 4, 5}).first, true);
+ EXPECT_EQ(*trie.get({2, 3, 4, 5}).second, 44);
+ EXPECT_EQ(trie.get({2, 3, 4, 5}).first, true);
+ EXPECT_EQ(*trie.get({2, 3, 1, 2}).second, 45);
+
+ EXPECT_EQ(trie.get({1, 2}).first, false);
+ EXPECT_EQ(trie.get({1, 2}).second, nullptr);
}
int main(int argc, char **argv) {