Anonymous

/* example Trie structure
  
  -
 [0]
  |
 a|     d     b
 [1]---[2]---[4]
  |           |
 c|          a|     e     d
 [3]         [5]---[6]---[9]
              |
             d|     e
             [7]---[8]

*/


class TrieNode 
{
    char letter;
	int  index;
	
	TrieNode next; // next node on same level  // sibling
	TrieNode link; // link to next level       // child
	
    public TrieNode(int i, char l)
	{	letter = l;
		index = i;
    }

	public void printNode(String message)
	{	System.out.println(index + " " + letter +  " link=" + link + " next=" + next + " " + message);
	}
	public String returnNode(String message)
	{	return(index + " " + letter + " " + " link=" + link + " next=" + next + " " + message);
	}
 
} // end class TrieNode

public class Trie 
{	TrieNode root;
	TrieNode current;
	int nextIndexNumber = 0;

    public Trie()
	{	root = new TrieNode(nextIndexNumber, '-' ); // 0, <>
		root.next = null;
		nextIndexNumber++;
	}
	
	public void printTrie()
	{	System.out.println("TRIE");
		inorder(root);
	}
	
	private void inorder(TrieNode currentNode)
	{
	 if(currentNode.link != null) inorder(currentNode.link);  
	 System.out.println( currentNode + " " + currentNode.returnNode(""));  
	 if(currentNode.next != null) inorder(currentNode.next); 
	}
	
	
	public TrieNode head()
	{	return root;
	}
	
	public TrieNode isChild(TrieNode currentNode, char letter)
	{	if(currentNode.link == null)	return null;
		currentNode = currentNode.link;
		while(true)
		{	if(currentNode.letter == letter)	return currentNode;
			else if(currentNode.next == null)	return null;
			else currentNode = currentNode.next;
		}
	}
	
	public TrieNode findNodeIndex(TrieNode currentNode, int i) 
	{	if(currentNode.link != null)	findNodeIndex(currentNode.link, i); 
		//System.out.println( currentNode + " " + currentNode.returnNode(""));
		if(currentNode.index == i)	return currentNode;
		if(currentNode.next != null)	findNodeIndex(currentNode.next, i);
	
		return null;
	}

	public TrieNode addNode(TrieNode currentNode, char l)
	{	TrieNode newNode = new TrieNode(nextIndexNumber, l);
		
		if(currentNode.link == null)
		{	currentNode.link = newNode;
		}
		else
		{	currentNode = currentNode.link;
			while(true)
			{	if(currentNode.next == null)	break;
				else currentNode = currentNode.next;
			}
			currentNode.next = newNode;
		}
		
		//newNode.printNode("Added");
		nextIndexNumber++;
		
		return newNode;
	}
	
}	// end class Trie