public class Trie<Value> {

	private class Node {
		private Value val;
		private TreeMap<Character, Node> children;

		public Node() {
			val = null;
			children = new TreeMap<Character, Node>();
		}
	}

	private Node root;

	public Trie() {
		root = null;
	}

	public boolean containsKey(String key) {
		Node node = getNode(key);
		if (node == null)
			return false;
		return node.val != null;
	}

	public void put(String key, Value val) {
		root = put(root, key, val, 0);
	}

	private Node put(Node node, String key, Value val, int index) {
		if (node == null)
			node = new Node();
		if (index == key.length()) {
			node.val = val;
			return node;
		}
		Node next = put(node.children.get(key.charAt(index)), key, val, index + 1);
		node.children.put(key.charAt(index), next);
		return node;
	}

	public Value get(String key) {
		Node node = getNode(key);
		return node == null? null: node.val;
	}

	private Node getNode(String key) {
		int len = key.length();
		Node node = root;
		for (int i = 0; i < len; i++) {
			if (node == null)
				return null;
			node = node.children.get(key.charAt(i));
		}
		return node;
	}

	public void delete(String key) {
		root = delete(root, key, 0);
	}

	private Node delete(Node node, String key, int len) {
		if (node == null)
			return null;
		if(key.length() == len) {
			//it key is not a word in trie
			if (node.val == null)
				return node;
			else {
				//if the node has children
				if (node.children.size() > 0) {
					node.val = null;
					return node;
				} else
					return null;
			}
		}
		Node next = delete(node.children.get(key.charAt(len)), key, len + 1);
		if (next == null) {
			//if word is not in the trie
			if (!node.children.containsKey(key.charAt(len)))
				return node;
			else {
				//if has more the one children or this node has value(it is a word in trie)
				if (node.children.size() > 1 || node.val != null) {
					node.children.remove(key.charAt(len));
					return node;
				} else
					return null;
			}
		} else
			return node;
	}

	public Iterable<String> keys() {
		LinkedList<String> list = new LinkedList<String>();
		collect(root, list, "");
		return list;
	}

	private void collect(Node node, LinkedList<String> list, String str) {
		if (node == null)
			return;
		if (node.val != null)
			list.add(new String(str));
		Iterator<Entry<Character, Node>> iter = node.children.entrySet().iterator();
		while (iter.hasNext()) {
			Entry<Character, Node> entry = iter.next();
			collect(entry.getValue(), list, str + entry.getKey());
		}
	}

	public Iterable<String> keysWithPrefix(String prefix) {
		LinkedList<String> list = new LinkedList<String>();
		Node node = getNode(prefix);
		collect(node, list, prefix);
		return list;
	}

	public String longestPrefixOf(String key) {
		int length = search(root, key, 0);
		return key.substring(0, length);
	}

	private int search(Node node, String key, int len) {
		if (node == null)
			return len;
		if (key.length() == len)
			return len;
		Node next = node.children.get(key.charAt(len));
		if (next == null)
			return len;
		return search(next, key, len + 1);

	}

	public String longestKeyAsPrefixOf(String key) {
		int length = search(root, key, 0, 0);
		return key.substring(0, length);
	}

	private int search(Node node, String key, int longestLen, int currLen) {
		if (node == null)
			return longestLen;
		if (node.val != null)
			longestLen = currLen;
		if (key.length() == currLen)
			return longestLen;
		Node next = node.children.get(key.charAt(currLen));
		return search(next, key, longestLen, currLen + 1);
	}
}