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

---
 trie.cc | 113 ----------------------------------------------------------------
 1 file changed, 113 deletions(-)
 delete mode 100644 trie.cc

(limited to 'trie.cc')

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);
-}
-- 
cgit v1.2.3