diff options
| -rw-r--r-- | trie.cc | 76 |
1 files changed, 76 insertions, 0 deletions
@@ -0,0 +1,76 @@ +#include <cstdint> +#include <forward_list> +#include <map> +#include <memory> + +#include <cassert> +#include <iostream> + +template < + typename Key +> +class Trie { + public: + typedef std::unique_ptr<Trie> ptr; + + Trie(): + children_() { } + + inline void add(std::forward_list<Key> path) { + this->add(path, path.begin()); + } + + inline void add(std::forward_list<Key>& path, + typename std::forward_list<Key>::const_iterator curr) { + if ( curr != path.end() ) { + Trie::ptr& trie = this->children_[*curr]; + + if ( trie ) { + trie->add(path, ++curr); + } else { + trie.reset(new Trie<Key>()); + trie->add(path, ++curr); + } + } + } + + inline Trie* resolve(std::forward_list<Key> path) const { + return this->resolve(path, path.begin()); + } + + inline Trie* resolve( + std::forward_list<Key>& path, + typename std::forward_list<Key>::const_iterator curr + ) const { + auto trie = this->children_.find(*curr); + + if ( trie != this->children_.end() ) { + auto next = ++curr; + + if ( next == path.end() ) { + return (*trie).second.get(); + } else { + return (*trie).second->resolve(path, next); + } + } else { + return nullptr; + } + } + + protected: + std::map<Key, Trie::ptr> children_; + +}; + +int main() { + Trie<uint8_t> test; + + test.add(std::forward_list<uint8_t>{1, 2, 3}); + test.add(std::forward_list<uint8_t>{1, 2, 4}); + test.add(std::forward_list<uint8_t>{2, 1}); + test.add(std::forward_list<uint8_t>{2, 1, 1}); + + assert(test.resolve(std::forward_list<uint8_t>{1, 2}) != nullptr); + assert(test.resolve(std::forward_list<uint8_t>{1, 2, 4}) != nullptr); + assert(test.resolve(std::forward_list<uint8_t>{3}) == nullptr); +} |