public class PrefixTree implements Tree { 
 	//Data
	protected char content;
	protected Object marker;	//The marker denotes the end of a key		 
	protected PrefixTree[] child;

	//Constructors
 	public PrefixTree() { 
		content = ' ';	//Root contains blank - represents empty string
		marker = null;
		child = new PrefixTree[26];	//alphabet = "abcdefghijklmnopqrstuvwxyz"
	} 	
	
	public PrefixTree(int i) {
		content = (char)('a' + i);
		marker = null;
		child = new PrefixTree[26];	//alphabet = "abcdefghijklmnopqrstuvwxyz"
	}
	
	//Access methods
	public char character() { return content; }
	public boolean endOfKey() { return marker != null ; }
	public Object data() { return marker; }
	public PrefixTree[] child() { return child; }
	
	//Protected methods
	protected PrefixTree insert(String s) {
		PrefixTree current = this;
		PrefixTree result = null;
		
		if(s.length() == 0)		//For empty String
			current.marker = new Boolean(true);
		
		System.out.println("     Inserted characters:");
		for(int i = 0; i < s.length(); i++) {
			if(current.child[s.charAt(i)-'a'] != null) {
				current = current.child[s.charAt(i)-'a'];
				System.out.print(current.content + "   ");
			}
			
			else {
				result = new PrefixTree((int)(s.charAt(i)-'a'));
				current.child[s.charAt(i)-'a'] = result;
				current = current.child[s.charAt(i)-'a'];
				System.out.print(current.content + "   ");
			}
	
			if(i == s.length()-1) {
				current.marker = new Boolean(true);
				result = current;
			}
		}
		
		System.out.println("\nFinished inserting the word: " + s + "\n");
		return result;
	}
	
	protected PrefixTree search(String s) {
		PrefixTree current = this;
		System.out.println("\n     Searching for string: " + s);
		
		while(current != null) {
			for(int i = 0; i < s.length(); i++) {				
				if(current.child[s.charAt(i)-'a'] == null) {
					System.out.println("Cannot find string: " + s);
					return null;
				}
				else {
					current = current.child[s.charAt(i)-'a'];
					System.out.println("Found character: " + current.content);
				}
			}
			
			if (current.marker != null) {
				System.out.println("Found string: " + s);
				return current;
			}
			else {
				System.out.println("Cannot find string: " + s +"(only present as a substring)");
				return null;
			}
		}
		
		return null; 
	}
	
	//Tree methods implementation	
	public void add(Object value) { insert((String)value); }
	public boolean contains(Object value) { return search((String)value) != null; }	
	public boolean isEmpty() { return size() == 0; }
	
	public int height() {
		PrefixTree[] child = child();
		int max = -1;
		for(int i = 0; i < child.length; i++) {
			PrefixTree t = child[i];
			if(t != null) {
				int h = t.height();
				if(max < h) max = h;
			}
		}
		return max + 1;
	}
	
	public int numberOfLiefs() { throw new UnsupportedOperationException(); }
    public Object clone() { throw new UnsupportedOperationException(); }
	public Object remove(Object value) { throw new UnsupportedOperationException(); }
	
	public int size() { 
		int result = 0;
 		java.util.Iterator<String> it = iterator();
		while(it.hasNext()) {
			it.next();
			result++;
		}
 		return result;
	}
	
	public void clear() { throw new UnsupportedOperationException(); }
	
	public java.util.Iterator iterator() { return treePreorderIterator(); }
	
    public java.util.Iterator treeInorderIterator() {
    	throw new UnsupportedOperationException();
    }
    
    public java.util.Iterator treePreorderIterator() {
    	return new PrefixTreePreorderIterator(this);
    }

	public java.util.Iterator treeBreadthFirstIterator() {
		return new PrefixTreeBreadthFirstIterator(this);
	}
	
	public java.util.Iterator treePostorderIterator() {
		throw new UnsupportedOperationException();
	}
  	
	public String toString() {
		String result = "";
 		java.util.Iterator<String> it = iterator();
		while(it.hasNext())
			result = result + it.next() + "\n";
 		return result;
	}
	
  	//Other methods
  	public String characters() {
  		String result = "";
		java.util.Iterator<Character> it = treeBreadthFirstIterator();
		PrefixTreeBreadthFirstIterator itw = (PrefixTreeBreadthFirstIterator)it;
		for(int i = 0; i < itw.numberOfLevels(); i++) {
			java.util.Iterator<Character> currentLevelIt = itw.getData(i).iterator();
			result = result + "\nLevel #: " + i + "\n";
			while(currentLevelIt.hasNext())
				result = result + currentLevelIt.next() + "   ";
		}
		return result;
 	}
}