/* 
 * Trie.java 
 * Implementation of tries in Java
 *
 * Author:    David Aspinall
 * Copyright: University of Edinburgh, 2001 / David Aspinall.
 *
 * Trie.java,v 1.1 2002/11/29 13:59:44 da Exp
 *
 */

class Trie {
    private static final int STOP=0;

    // Single field of trie
    private Trie[] subtries;

    public Trie() {
	subtries = new Trie[27];
    }

    // Add a word to the trie, only allow l.c. a-z
    public void addWord(String w) {
	if (w.length() == 0) {
	    // Add stop indicator to Trie
	    subtries[STOP] = new Trie();
	} else {
	    int firstletter =  w.charAt(0);
	    if (firstletter < 'a' || firstletter > 'z') 
		throw new IllegalArgumentException("Illegal character in addWord");

	    int letterindex = firstletter-'a'+1;

	    if (subtries[letterindex] == null) 
		subtries[letterindex] = new Trie();

	    subtries[letterindex].addWord(w.substring(1));
	}
    }

    private String toString(String prefix) {
	// Return a string of all words stored in the trie.
	String words = "";
	if (subtries[0] != null) 
	    // STOP found, add word here.
	    words = prefix + "\n";
	for (int i = 1; i < subtries.length; i++) {
	    if (subtries[i] != null) {
		words = words + 
		    subtries[i].toString(prefix + (char)(i + 'a' -1));
	    }
	}
	return words;
    }
    public String toString() {
	return toString("");
    }
    
    public static void main(String [] args) {
	Trie test = new Trie();
	for (int i = 0; i < args.length; i++) {
	    test.addWord(args[i]);
	}
	System.out.print(test);
    }
}