From 8d1661ea333f15ddc2dde3b2a25288d1ccf485d9 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Tue, 4 Feb 2014 19:10:11 +0100 Subject: Moved Trie template into src directory * renamed trie.cc to test.cc in preparation for implementing GoogleTest based test cases --- src/trie.h | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++ test.cc | 24 +++++++++++++ trie.cc | 113 ------------------------------------------------------------- 3 files changed, 118 insertions(+), 113 deletions(-) create mode 100644 src/trie.h create mode 100644 test.cc delete mode 100644 trie.cc diff --git a/src/trie.h b/src/trie.h new file mode 100644 index 0000000..9134c45 --- /dev/null +++ b/src/trie.h @@ -0,0 +1,94 @@ +#ifndef TRIE_SRC_TRIE_H_ +#define TRIE_SRC_TRIE_H_ + +#include +#include + +template < + typename Key +> +class Trie { + public: + typedef std::vector 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::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 resolve(key_list path) const { + 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( + 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 children_; + +}; + +#endif // TRIE_SRC_TRIE_H_ diff --git a/test.cc b/test.cc new file mode 100644 index 0000000..5105f09 --- /dev/null +++ b/test.cc @@ -0,0 +1,24 @@ +#include "trie.h" + +#include +#include + +int main() { + Trie test; + + test.add({1, 2, 3}); + test.add({1, 2, 4}); + test.add({2, 1}); + test.add({2, 1, 1}); + + assert(test.resolve({1, 2}).second != nullptr); + assert(test.resolve({1, 2, 3}).second != nullptr); + assert(test.resolve({1, 2, 4}).second != nullptr); + assert(test.resolve({3}).second == nullptr); + + test.remove({1, 2}); + + assert(test.resolve({1, 2, 4}).second == nullptr); + assert(test.resolve({1, 2, 3}).second == nullptr); + assert(test.resolve({1, 2}).second == nullptr); +} diff --git a/trie.cc b/trie.cc deleted file mode 100644 index f002399..0000000 --- a/trie.cc +++ /dev/null @@ -1,113 +0,0 @@ -#include -#include -#include - -#include -#include - -template < - typename Key -> -class Trie { - public: - typedef std::vector 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::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 resolve(key_list path) const { - 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( - 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 children_; - -}; - -int main() { - Trie test; - - test.add({1, 2, 3}); - test.add({1, 2, 4}); - test.add({2, 1}); - test.add({2, 1, 1}); - - assert(test.resolve({1, 2}).second != nullptr); - assert(test.resolve({1, 2, 3}).second != nullptr); - assert(test.resolve({1, 2, 4}).second != nullptr); - assert(test.resolve({3}).second == nullptr); - - test.remove({1, 2}); - - assert(test.resolve({1, 2, 4}).second == nullptr); - assert(test.resolve({1, 2, 3}).second == nullptr); - assert(test.resolve({1, 2}).second == nullptr); -} -- cgit v1.2.3