public class Trie {
    private TrieNode root = null;

    public void insert(String word) {
	root = insert(word, root);
    }

    private TrieNode insert(String word, TrieNode t) {
	TrieNode newNode, tmpNode;
	boolean ends = false;
	char first;

	if (word.length() == 0) {
	    return t;
	} else if (word.length() == 1) {
	    ends = true;
	}
	first = word.charAt(0);

	if (t == null) {
	    // If we have an empty tree we can just append the node to 
	    // this branch.
	    newNode = new TrieNode(first, ends);
	    tmpNode = insert(word.substring(1), null);
	    newNode.setChild(tmpNode);
	    return newNode;
	} else if (first < t.getLetter()) {
	    // The node should be before this sibling, so we "squeeze"
	    // it in, and point out the sibling.
	    newNode = new TrieNode(first, ends, t, null);
	    tmpNode = insert(word.substring(1), null);
	    newNode.setChild(tmpNode);
	    return newNode;
	} else if (first > t.getLetter()) {
	    // We have not yet come to the place where this node should
	    // be appended to the tree.
	    tmpNode = insert(word, t.getSibling());
	    t.setSibling(tmpNode);
	    return t;	    
	}
	// A node with the current letter already exists. Continue with
	// appending the rest of the word to this subtree.
	if (ends) {
	    // Do not forget to mark this node as an end node if it is the
	    // final letter of the word.
	    t.setEnd(ends);
	} else {
	    // Otherwise just append the rest of the word to this subtree.
	    tmpNode = insert(word.substring(1), t.getChild());
	    t.setChild(tmpNode);		
	}
	return t;
    }
    
    public boolean exists(String word) {
	return exists(word, root);
    }

    private boolean exists(String word, TrieNode t) {
	char first;
	if (word.length() == 0) {
	    return false;
	}
	first = word.charAt(0);

	if (t == null) {
	    // If we have an empty tree so the word cannot exist in the tree.
	    return false;
	} else if (first < t.getLetter()) {
	    // The node should be before this sibling, so we should already have
	    // found it.
	    return false;
	} else if (first > t.getLetter()) {
	    // We have not yet come to the place where this node should
	    // be appended to the tree.
	    return exists(word, t.getSibling());	    
	} 
	// The initial letters match...
	if (word.length() == 1) {
	     // ...and this is the final letter of so the boolean say if 
	    // we have inserted this word into our tree or not.
	    return t.getEnd();
	}
	// ...and this is NOT the final letter of the word so let us 
	// match the rest.
	return exists(word.substring(1), t.getChild());
    }

    public boolean existsVerbose(String word) {
	// Exactly the same as exists but also writes out the node id of 
	// the matched nodes during the search.
	boolean retval = existsVerbose(word, root);
	System.out.println();
	return retval;
    }

    private boolean existsVerbose(String word, TrieNode t) {
	char first;
	if (word.length() == 0) {
	    return false;
	}
	first = word.charAt(0);

	if (t == null) {
	    return false;
	} else if (first < t.getLetter()) {
	    return false;
	} else if (first > t.getLetter()) {
	    return existsVerbose(word, t.getSibling());	    
	}
	System.out.print(t.getId() + " ");
	if (word.length() == 1) {
	    return t.getEnd();
	}
	return existsVerbose(word.substring(1), t.getChild());
    }

    public void printTrie() {
	printTrie(root, "");
    }

    private void printTrie(TrieNode t, String prefix) {
	String word;
	if (t != null) {
	    word = prefix + t.getLetter();

	    // Is this a word? Print the word
	    if (t.getEnd()) {
		System.out.println(word);
	    }
	    
	    // Children should be printed. They share the same WORD as prefix
	    if (t.getChild() != null) {
		printTrie(t.getChild(), word);
	    }
	    
	    // Siblings should be printed. They share the same PREFIX
	    if (t.getSibling() != null) {
		printTrie(t.getSibling(), prefix);
	    }
	}
    }

    public void printWordsStartingWith(String s) {
	printWordsStartingWith(s, root, s);
    }

    private void printWordsStartingWith(String s, TrieNode t, String prefix) {
	// This is nothing new really. First we do the same as
	// exists(s) to find the prefix string s. Then we start
	// printTrie from that node with s as prefix. We must supply
	// both the string s where one letter is "shaved off" at the
	// time and prefix which will be passed to printTrie.

	char first;
	if (s.length() == 0) {
	    // The searchstring s is empty so the tree from this point
	    // on is the one we want to print.
	    printTrie(t, prefix);
	} else {
	    // We have to continue to search for the subtree. First
	    // pick out the initial letter of the searchstring s
	    first = s.charAt(0);

	    if (t == null) {
		// If we have an empty tree so s cannot exist in the tree.
		return;
	    } else if (first < t.getLetter()) {
		// The node should be before this sibling, so we should already have
		// found it.
		return;
	    } else if (first > t.getLetter()) {
		// We have not yet come to the place where this node should
		// be appended to the tree.
		printWordsStartingWith(s, t.getSibling(), prefix);	    
	    }  else {
		// The initial letters match and this is NOT the final
		// letter of the word so let us match the rest.
		printWordsStartingWith(s.substring(1), t.getChild(), prefix);
	    }
	}
    }
}