From c86f957426a2399217bcca466dec7a83d0981ba3 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Thu, 6 Feb 2014 16:14:16 +0100 Subject: 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 to make them optional * expanded test cases accordingly --- src/trie.h | 50 +++++++++++++++++++++++++++++++++++++++++--------- test.cc | 55 ++++++++++++++++++++++++++++++------------------------- 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 template < - typename Key + typename Key, + typename Value = std::nullptr_t > class Trie { public: typedef std::vector 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 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 get(key_list path) { + std::pair 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 value_; std::map 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 resolve( + inline std::pair resolve(key_list path) { + return this->resolve(path, path.begin()); + } + + inline std::pair resolve( key_list& path, typename key_list::const_iterator currStep - ) const { - typename std::map::const_iterator matchingTrie( + ) { + typename std::map::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 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) { -- cgit v1.2.3