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 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
 create mode 100644 src/trie.h

(limited to 'src')

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 <vector>
+#include <map>
+
+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_;
+
+};
+
+#endif  // TRIE_SRC_TRIE_H_
-- 
cgit v1.2.3