Trie

trie.cpp

//============================================================================
// Name        : trie.cpp
// Author      : dagang.wei
// Version     :
// Copyright   : 
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <algorithm>
#include <string>
#include <map>
#include <iostream>

class Trie {
private:
	typedef std::map<char, Trie*> T_Map;

	static char TAIL;

	char m_value;
	std::map<char, Trie*> m_children;

public:
	Trie(char value) :
			m_value(value) {
		//std::cout << "Trie(" << value << ")" << std::endl;
	}

	~Trie() {
		//std::cout << "~Trie()" << std::endl;

		for (T_Map::iterator it = m_children.begin(); it != m_children.end();
				++it) {
			if (NULL != it->second) {
				delete it->second;
			}
		}
	}

	void add(const std::string& word) {
		std::cout << "+add(" + word << ")" << std::endl;
		if (0 == word.size()) {
			m_children[TAIL] = new Trie(TAIL);
		} else {
			char c = word[0];

			T_Map::iterator it_child = m_children.find(c);

			if (m_children.end() == it_child) {
				m_children[c] = new Trie(c);
			}
			m_children[c]->add(word.substr(1));
		}
	}

	bool exist(const std::string& word) {
		std::cout << "+exist(" << word << ")" << ", value: " << m_value
				<< std::endl;

		if (0 == word.size()) {
			std::cout << "-exist(" << word << ")" << ", value: " << m_value
					<< std::endl;

			return m_children.end() != m_children.find(TAIL);
		}

		if (m_children.end() != m_children.find(word[0])) {
			return m_children[word[0]]->exist(word.substr(1));
		}

		return false;
	}

	void print(int indent) {
		std::cout << m_value << std::endl;

		for (T_Map::iterator it = m_children.begin(); it != m_children.end();
				++it) {
			for (int i = 0; i < indent; ++i) {
				std::cout << " ";
			}
			std::cout << "|-";
			it->second->print(indent + 2);
		}
	}
};

char Trie::TAIL = -1;

int main() {
	Trie trie(0);
	trie.add("pole");
	trie.add("peek");
	trie.add("poke");

	trie.print(0);

	bool found = false;

	found = trie.exist("peek");
	std::cout << "found peek: " << found << std::endl;
	found = trie.exist("pole");
	std::cout << "found pole: " << found << std::endl;
	found = trie.exist("peek");
	std::cout << "found peek: " << found << std::endl;
	found = trie.exist("pee");
	std::cout << "found pee: " << found << std::endl;

	return 0;
}