package AutoComplete;

import java.util.StringTokenizer;
import java.util.Hashtable;
import java.io.Serializable;

/**
 * a trie
 */
public class trie implements Serializable
{
	private Object element = null;
	private Hashtable next = null;
	
	/**
	 * constructor
	 * @param p_currString string for the current node
	 */
	public trie(StringTokenizer p_currString, Object p_element) {
		if(p_currString.hasMoreTokens()) {
			String currString = p_currString.nextToken();
			trie temp = new trie(p_currString, p_element);
			next = new Hashtable(10);
			next.put(currString, temp);
		} else {
			element = p_element;
		}
	}
	
	public trie(String p_currString, Object p_element) {
		if(!p_currString.equals("")) {
			String currString = p_currString.substring(0,1);
			trie temp = new trie(p_currString.substring(1), p_element);
			next = new Hashtable(10);
			next.put(currString, temp);
		} else {
			element = p_element;
		}
	}
	
	public trie() {
		next = new Hashtable();
	}
	
	/**
	 * insert into a trie
	 */
	public void put(StringTokenizer p_insertion, Object p_element) {
		trie temp;
		if(p_insertion.hasMoreTokens()) {
			if(next == null) next = new Hashtable();
			String currString = p_insertion.nextToken();
			if((temp = (trie)next.get(currString))==null) {
				temp = new trie(p_insertion, p_element);
				next.put(currString, temp);
			} else {
				temp.put(p_insertion, p_element);
			}
		} else {
			element = p_element;
		}
	}
	
	public void put(String p_insertion, Object p_element) {
		trie temp;
		if(!p_insertion.equals("")) {
			if(next == null) next = new Hashtable();
			String currString = p_insertion.substring(0,1);
			if((temp = (trie)next.get(currString))==null) {
				temp = new trie(p_insertion.substring(1), p_element);
				next.put(currString, temp);
			} else {
				temp.put(p_insertion.substring(1), p_element);
			}
		} else {
			element = p_element;
		}
	}
	
	public Object get(StringTokenizer p_start) {
		trie temp;
		if(p_start.hasMoreTokens()) {
			if(next == null)
				return null;
			String currString = p_start.nextToken();
			if((temp = (trie)next.get(currString)) == null) {
				return null;
			} else {
				return temp.get(p_start);
			}
		} else {
			return element;
		}
	}
	
	public Object get(String p_start) {
		trie temp;
		if(!p_start.equals("")) {
			if(next == null)
				return null;
			String currString = p_start.substring(0,1);
			if((temp = (trie)next.get(currString)) == null) {
				return null;
			} else {
				return temp.get(p_start.substring(1));
			}
		} else {
			return element;
		}
	}
	
	public boolean remove(StringTokenizer p_start) {
		trie temp;
		if(p_start.hasMoreTokens()) {
			String currString = p_start.nextToken();
			if((temp = (trie)next.get(currString)) == null) {
				return false;
			} else {
				if(temp.remove(p_start)) {
					next.remove(currString);
					if(next.isEmpty())
						return true;
					else
						return false;
				}
			}
		} else {
			element = null;
			if(next == null)
				return true;
			if(next.isEmpty())
				return true;
			else
				return false;
		}
		return false;
	}
	
	public boolean remove(String p_start) {
		trie temp;
		if(!p_start.equals("")) {
			String currString = p_start.substring(0,1);
			if((temp = (trie)next.get(currString)) == null) {
				return false;
			} else {
				if(temp.remove(p_start.substring(1))) {
					next.remove(currString);
					if(next.isEmpty())
						return true;
					else
						return false;
				}
			}
		} else {
			element = null;
			if(next == null)
				return true;
			if(next.isEmpty())
				return true;
			else
				return false;
		}
		return false;
	}
	
	public String getEnd(StringTokenizer p_start) {
		trie temp;
		if(p_start.hasMoreTokens()) {
			if(next == null) return null;
			String currString = p_start.nextToken();
			if((temp = (trie)next.get(currString)) == null) {
				return null;
			} else {
				String result = temp.getEnd(p_start);
				if (result == null) {
					return null;
				} else {
					return currString + result;
				}
			}
		} else {
			if (element != null) {
				return "";
			} else {
				if(next.isEmpty()) return "";
				String currString = (String)(next.keys()).nextElement();
				temp = (trie)next.get(currString);
				String result = temp.getEnd(p_start);
				return currString + result;
			}
		}
	}
	
	public String getEnd(String p_start) {
		trie temp;
		if(!p_start.equals("")) {
			if(next == null) return null;
			String currString = p_start.substring(0,1);
			if((temp = (trie)next.get(currString)) == null) {
				return null;
			} else {
				String result = temp.getEnd(p_start.substring(1));
				if (result == null) {
					return null;
				} else {
					return result;
				}
			}
		} else {
			if (element != null) {
				return "";
			} else {
				if(next.isEmpty()) return "";
				String currString = (String)(next.keys()).nextElement();
				temp = (trie)next.get(currString);
				String result = temp.getEnd(p_start);
				return currString + result;
			}
		}
	}
}
