/*
 * Author: Ruo Ding
 * Date: June 26, 2012
 */
import java.io.File;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;
 
 
public class SimpleTrie {
 
	/**
	 * @param args
	 */
	private SimpleTrieNode root;
	private SimpleTrieNode head;
	public SimpleTrie()
	{
		root = new SimpleTrieNode();
		head = null;
	}
 
	public void initTrie(String aWord)
	{
		if (head!=null)
			return;
 
		SimpleTrieNode scanningNode = root;
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			String subWord = aWord.substring(0, i+1);
			scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
			scanningNode = scanningNode.subNodes[iChar];
		}
		scanningNode.isWord = true;
		head = scanningNode;
	}
 
	public void insert(String word)
	{
		SimpleTrieNode scanningNode = root;
		String aWord = word.toLowerCase();
 
		if (head == null)
		{
			initTrie(aWord);
			return;
		}
 
		SimpleTrieNode nextWord = null;
		SimpleTrieNode prevWord = null;
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (scanningNode.subNodes[iChar] != null)
			{
				scanningNode = scanningNode.subNodes[iChar];
 
				if (scanningNode.values.length == aWord.length() &&
					scanningNode.toString().equals(aWord) &&
					!scanningNode.isWord)
				{
					// if the word occur as a prefix in our list, 
					// than find the fist word with this prefix, insert this in the front
					nextWord = findNextWord(scanningNode, 0);
					scanningNode.isWord = true;
					if (nextWord.prev != null)
					{
						prevWord = nextWord.prev;
						prevWord.next = scanningNode;
						scanningNode.prev = prevWord;
					}
 
					scanningNode.next = nextWord;
					nextWord.prev = scanningNode;
					return;
				}
			}else
			{
				if (prevWord == null && nextWord == null)
				{
					nextWord = findNextWord(scanningNode, iChar+1);
					prevWord = findPrevWord(scanningNode, iChar-1);					
				}
				String subWord = aWord.substring(0, i+1);
				scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
				scanningNode = scanningNode.subNodes[iChar];
			}
		}
		scanningNode.isWord = true;
 
		if (prevWord != null)
		{
			prevWord.next = scanningNode;
			scanningNode.prev = prevWord;
		}
		if (nextWord != null)
		{
			nextWord.prev = scanningNode;
			scanningNode.next = nextWord;
		}
	}
 
	public SimpleTrieNode find(String word)
	{
		if (head == null)
		{
			return null;
		}
 
 
		SimpleTrieNode scanningNode = root;
		String aWord = word.toLowerCase();
		for (int i = 0; i < aWord.length(); i++)
		{
			char letter = aWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (scanningNode.subNodes[iChar] != null)
			{
				scanningNode = scanningNode.subNodes[iChar];
				if (scanningNode.values.length == aWord.length())
				{
					if (scanningNode.isWord)
					{
						return scanningNode;
					}else
					{
						return null;
					}
				}
			}else
			{
				return null;
			}	
		}
 
		return null;
	}
 
	public SimpleTrieNode remove(String word)
	{
		SimpleTrieNode toRemove = find(word);
		if(toRemove.prev!=null)
		{
			toRemove.prev.next = toRemove.next;
		}
		if(toRemove.next!=null)
		{
			toRemove.next.prev = toRemove.prev;
		}
		return toRemove;
	}
 
 
	public SimpleTrieNode getHead() {
		return head;
	}
 
	// give the parent node and the index starts to scan in parent node
	public SimpleTrieNode findNextWord(SimpleTrieNode node, int cIndex)
	{
		if (node == null)
			return null;
 
		String subWord = node.toString();
 
		for (int i = cIndex; i<node.subNodes.length; i++)
		{
			if (node.subNodes[i] != null)
			{
				if (node.subNodes[i].isWord)
				{
					return node.subNodes[i];
				}else
				{
					return findNextWord(node.subNodes[i], 0);
				}
			}
		}
 
		// none found in the same or below level, proceed to the next in its parent level
		SimpleTrieNode theParent = null;
		for (int i = 0; i < subWord.length()-1; i++)
		{
			if (theParent == null)
			{
				theParent = root;
			}
			char letter = subWord.charAt(i);
			int iChar = Character.getNumericValue(letter) - 10;
			if (theParent.subNodes[iChar]!=null)
			{
				theParent = theParent.subNodes[iChar];
			}else
			{
				return null;
			}
		}
 
		int nextIndex = -1;
		if (subWord.length()>=1)
		{
			char nextChar = subWord.charAt(subWord.length()-1);
			nextIndex = Character.getNumericValue(nextChar) - 10;
		}
		return findNextWord(theParent, nextIndex+1);
 
	}
 
	// give the parent node and the index starts to scan in parent node
	public SimpleTrieNode findPrevWord(SimpleTrieNode node, int cIndex)
	{
		if (node == null)
			return null;
 
		String subWord = node.toString();
 
		for (int i = cIndex; i >= 0; i--)
		{
			if (node.subNodes[i] != null)
			{
				SimpleTrieNode rSubNode = findPrevWord(node.subNodes[i], 25);
				if (rSubNode != null)
				{
					return rSubNode;
				}else if (node.subNodes[i].isWord)
				{
					return node.subNodes[i];
				}
			}
		}
 
		//if none exist before the index in the node child, check if node is a word 
		if (node.isWord)
		{
			return node;
		}
 
		// none found in the same or below level, proceed to the prev in its parent level
		SimpleTrieNode theParent = null;
		int iChar = -1;
		int i;
		for ( i = 0; i < subWord.length()-1; i++)
		{
			if (theParent == null)
			{
				theParent = root;
			}
			char letter = subWord.charAt(i);
			iChar = Character.getNumericValue(letter) - 10;
			if (theParent.subNodes[iChar]!=null)
			{
				theParent = theParent.subNodes[iChar];
			}else
			{
				return null;
			}
		}
		int nextIndex = -1;
		if (subWord.length()>=1)
		{
			char nextChar = subWord.charAt(subWord.length()-1);
			nextIndex = Character.getNumericValue(nextChar) - 10;
		}
		return findPrevWord(theParent, nextIndex-1);
 
	}
 
 
	// main just test some basic functions for this SimpleTrie
	public static void main(String[] args) {
 
		SimpleTrie ourTrie = new SimpleTrie();
		File dbFile = new File("dictionary.txt");
		int wordsCount = 0;
		int nodesCount = 0;
		ArrayList<String> allWords = new ArrayList<String>();
		Hashtable<String, Integer> table = new Hashtable<String, Integer>();
		int duplicateCounts = 0;
		try{
 
			if (dbFile.exists())
			{
				Scanner preProcessor = new Scanner(dbFile);
				while (preProcessor.hasNextLine())
				{
 
					String theWord = preProcessor.nextLine();
					if (theWord.equals("abalone"))
					{
						System.out.println("Hit abalone");
					}
					ourTrie.insert(theWord);
					allWords.add(theWord);
					wordsCount++;
					if (table.get(theWord)!=null)
					{
						duplicateCounts++;
					}
					table.put(theWord, new Integer(1));
				}
				preProcessor.close();
			}
			SimpleTrieNode aR = ourTrie.remove("zimbalon");
			System.out.println(aR.toString());
			SimpleTrieNode printNode = ourTrie.getHead();
			while(printNode!=null)
			{
				//System.out.println(printNode.toString());
				printNode = printNode.next;
				nodesCount++;
			}
 
			for (int i = 0; i< allWords.size(); i++)
			{
				String aWord = allWords.get(i);
				if (ourTrie.find(aWord) == null)
				{
					System.out.println("Word: \'" + aWord + "\' not found!");
				}
			}
 
 
		}catch(Exception e)
		{
			System.out.println("Faild with Error: " + e.getMessage() + ", at line: " + wordsCount + ", at node " + nodesCount);
		}
 
 
 
		System.out.println("TotalWord from dic is: " + wordsCount + ", and total nodes is: " + nodesCount + ", dupcount: " + duplicateCounts);
 
	}
 
}
 
 
 
 
public class SimpleTrieNode {
 
	/**
	 * @param args
	 */
	public SimpleTrieNode prev;
	public SimpleTrieNode next;
	public SimpleTrieNode[] subNodes;
	public char[] values;
	public char sValue;
	public boolean isWord; // true indicate the node contains a word in our dictionary
 
	public SimpleTrieNode()
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
	}
 
	public SimpleTrieNode(String word)
	{
		prev = null;
		next = null;
		subNodes = new SimpleTrieNode[26];
		values = word.toCharArray();
		if (values.length >= 1)
		{
			sValue = values[values.length-1];
		}
	}
 
 
	public String toString()
	{
		if (values == null)
			return "";
 
		return new String(values);
	}
}