diff options
author | Adrian Kummerländer | 2014-02-04 19:10:11 +0100 |
---|---|---|
committer | Adrian Kummerländer | 2014-02-04 19:10:11 +0100 |
commit | 8d1661ea333f15ddc2dde3b2a25288d1ccf485d9 (patch) | |
tree | 77137bc4739d5c18272cc30ee96bf6969626ab70 /trie.cc | |
parent | e0028fb5303218feebe61b2cd93d4601c40fde79 (diff) | |
download | Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar.gz Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar.bz2 Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar.lz Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar.xz Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.tar.zst Trie-8d1661ea333f15ddc2dde3b2a25288d1ccf485d9.zip |
Moved Trie template into src directory
* renamed trie.cc to test.cc in preparation for implementing GoogleTest based test cases
Diffstat (limited to 'trie.cc')
-rw-r--r-- | trie.cc | 113 |
1 files changed, 0 insertions, 113 deletions
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 <cstdint> -#include <vector> -#include <map> - -#include <cassert> -#include <iostream> - -template < - typename Key -> -class Trie { - public: - typedef std::vector<Key> 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<Key, Trie>::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<bool, const Trie*> resolve(key_list path) const { - return this->resolve(path, path.begin()); - } - - inline std::pair<bool, const Trie*> resolve( - key_list& path, - typename key_list::const_iterator currStep - ) const { - typename std::map<Key, Trie>::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<Key, Trie> children_; - -}; - -int main() { - Trie<uint8_t> 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); -} |