import java.io.*;
/**
   An implementation of tries with linked lists. Each node of the trie is a 
   fixed-size array of pointers on its sons. All algorithms (addToTrie,
   isInTrie, removeFromTrie) are linear. The space used is bounded
   by <code>Card(alphabet)*sum of lengths of words</code>.
*/
public class FixedArrayTrie implements Trie{
    /**
       The alphabet used to form the strings composing the trie.
    */
    public static Alphabet alphabet; 
    /**
       True if the node is terminal.
    */
    public boolean terminal;
    /**
       The array of sons of the node.
    */
    public FixedArrayTrie[] next;
 

    public FixedArrayTrie() {
	next = new FixedArrayTrie[alphabet.size];
    }
    /**
       Computes the pair composed of 
       the length of the longest prefix of s[j..n-1] in the trie
       and the vertex reached by this prefix. Implements the function
       <code>LongestPrefixInTrie()</code> of Section 1.3.1.
       Complexity: linear in the length of <code>s</code>.
       @param s the input string
       @param j the starting index
       @return the computed pair
    */
    public  Pair longestPrefixInTrie(String s,int j) {
	int n = s.length(); 
	FixedArrayTrie p = this;
	for(int i = j; i < n; i++) {
	    FixedArrayTrie q = p.next[alphabet.toShort(s.charAt(i))];
	    if(q == null) 
		return new Pair(i-j, p);
	    else
		p = q;
	}
	return new Pair(n-j, p);
    }
    /**
       Returns true if the trie contains <code>s</code>.
       Implements the function <code>IsInTrie()</code> of Section 1.3.1.
       Complexity: linear in the length of <code>s</code>.
    */
    public boolean isInTrie(String s){
	return longestPrefixInTrie(s,0).length == s.length();
    }
    /**
       Adds the word s to the trie. Implements 
       the function <code>AddToTrie()</code> of Section 1.3.1.
       Complexity: linear in the length
       of <code>s</code>.
       @param s the string to be added
    */  
    public void addToTrie(String s){
	int n = s.length();
	Pair v = longestPrefixInTrie(s, 0);
	FixedArrayTrie p = (FixedArrayTrie) v.vertex;
	int j = v.length;
	for(; j < n; j++){
	    FixedArrayTrie q = new FixedArrayTrie();
	    p.next[alphabet.toShort(s.charAt(j))] = q;
	    p = q;
	}
	p.terminal = true;
    }

    /**
       Returns true if the node <code>p</code> is a leaf of the trie.
       Implements the function <code>IsLeaf()</code> of Section 1.3.1.
    */
    public boolean isLeaf(){
	for(int i = 0; i < alphabet.size; i++)
	    if(next[i]!= null)
		return false;
	return true;
    }

    /**
       Removes the string s from the trie. 
       Implements the function <code>RemoveFromTrie()</code> of Section 1.3.1.
       Complexity: linear in the length of <code>s</code>.
       @param s the string to be removed
    */
    public void removeFromTrie(String s){
	int i, n = s.length();
	FixedArrayTrie p = this, q;
	FixedArrayTrie[] father = new FixedArrayTrie[n];
	for(i = 0; i < n; i++) {
	    q = p;
	    p = p.next[alphabet.toShort(s.charAt(i))];
	    father[i] = q;
	}
	p.terminal = false;
	while(p.isLeaf()&&!p.terminal){
	    i--;
	    p = father[i];
	    p.next[alphabet.toShort(s.charAt(i))] = null;
	}
    }
  
    String toWords(String w, FixedArrayTrie p) {
	//list of words in the trie
	String s = new String();
	if (p.terminal) s = w + '\n';
	for (int i = 0; i < alphabet.size; i++) {
	    FixedArrayTrie q = p.next[i];
	    if (q != null) 
		s = s + toWords(w + alphabet.toChar(i), q);
	}
	return s;
    }
    public String toString(){
	return toWords("", this);	   
    }
    /**
       Builds a trie representing the list of strings read
       from a file line by line.
       @param name the name of the file
    */
    public void fromFile(String name) throws IOException {
	FileReader fileIn = new FileReader(name);
	BufferedReader r = new BufferedReader(fileIn);
	String line;
	while ((line = r.readLine()) != null) {
	    addToTrie(line);}
	fileIn.close();
    }
    public static void main(String[] args) throws IOException{
	alphabet = Alphabet.english();
	Trie t = new FixedArrayTrie();
	t.addToTrie("let");
	t.addToTrie("letter");
	t.addToTrie("set");
	System.out.println(t);
	t.removeFromTrie("letter");
	System.out.println(t);

	//  FixedArrayTrie t = new FixedArrayTrie(new Alphabet((char)0,256));
	//  t.fromFile(args[0]);

}

}