DictionaryTreeImpl.java

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Set;
import java.util.TreeSet;
import java.util.ArrayList;

/*
	If depth is equal to 0, retrieve all strings from the dictionary and add to one of the 8
	nodes surrounding the root node.

		Get the signature of first character in string.
		Add to the Set of the given Dictionary Tree Impl using addToSet() method.
	
	For all nodes at depth greater than 0, then recursively traverse the nodes of the tree,
	looking through the set of each node and deciding whether to add to next node or not, using
	same method as above.
	

*/
/*
	FOR MARKERS:
	Half way through coding this class I attended a lecture where I was informed
	you're not allowed to use if/else if statements for the methods to convert chars 
	to sigs and so on, so at this point I decided to use a different implementation for
	structure and then create a class with these stored in that are constructed with 
	every implementation and are able to be used easily. You can find these in my 'Predictive'
	class. Feel free to see the original implementation below commented out at the end of the page.
*/
public class DictionaryTreeImpl extends Predictive implements Dictionary {
	
	/*
		In this implementation I have decided to use the Linked Hash Map 
		as according to documentation, it has almost the efficiency of a 
		Hash map with similar indexing (which we need to order the keys) 
		as a Tree map.
	*/
	private DictTree root;

	public DictionaryTreeImpl() {
		/*	
			My implementation worked through initially populating the frontier nodes
			with all of the words from the dictionary that are valid. For example, if
			the first char of the signature we are looking at is equal to 2 then we add
			to the second child node. Then, it recursively goes through the nodes and 
			removes words that are not equal to the depth in length and adds them to the
			child nodes of those nodes using the same method as in the constructor (recursively) 
			until it constructs an empty node (as no more strings are being sent down the line).
			This was originally using this class recursively (DictionaryTreeImpl), so I had an 
			array of DictionaryTreeImpl nodes, but after having many problems and colleagues suggesting
			I use a seperate Tree implementation outside of this class, this brings you what you can see
			right now.
		*/

		root = new DictTree();
		//dictionary at "usr/share/dict/words"
		File dict = new File("words3");

		try {
			//System.out.println("Scanning Dictionary and adding to the list...");
	        Scanner scan = new Scanner(dict);

	        while (scan.hasNextLine()) {
					
				String currWord = scan.nextLine();
					
				currWord = currWord.toLowerCase();

				if(isValidWord(currWord)) {
						
					//System.out.println("Adding '" + currWord + "' to the tree...");

					addToTree(root, currWord, currWord);

					//System.out.println(root);
						
					//System.out.println();
				}
			
			}
	        
	   		scan.close();

	    } 
		    
		catch(FileNotFoundException e) {
		        
		    e.printStackTrace();
		
		}
	
	}

	/**
		Adds a string to the tree recursively.
		@param currentNode The current node of the tree you wish to manipulate.
		@param word The word you wish to add to the tree.
		@param wordBuffer A substring of the 'word' parameter that signifies what the next node to explore is based on the first character.
	*/
	public void addToTree(DictTree currentNode, String word, String wordBuffer) {
		
		System.out.println("wordBuffer: " + wordBuffer);

		if(currentNode == null) {
			System.out.println("current node is null for word '" + word + "'");
			currentNode = new DictTree();

		}

		if(wordBuffer.equals("")) {

			/* 
				If our word buffer is empty, then there are no more characters to use to 
				traverse the tree, so the current node must be the destination node for the
				current word. 
			*/

			currentNode.addWord(word);

		}

		else {

			/* 
				Else, we want to remove the first character from the buffer, convert it to
				a key/signature using the letterToKey method in the Predictive superclass,
				and then run this method again using the correct child node to match the key.
			*/
			System.out.println("Not null for " + currentNode);
			int nextNodeSignature = letterToKey(wordBuffer.charAt(0));

			/*
				i - 2 because letterToKey returns between 2 and 9, and the array's index is 
				from 0 to 7.
			*/	
				
			//currentNode.constructChildFromSignature(nextNodeSignature);
			
		
			addToTree(currentNode.getChildFromSignature(nextNodeSignature), word, wordBuffer.substring(1));
			
			//addToTree(currentNode.childNodes[nextNodeSignature - 2], word, wordBuffer.substring(1));

			//check javadoc for further explaination.
			/*
				currentNode: 	first takes the first char from the word buffer and converts
							 	this to a signature. This is then used to choose the correct
							 	child node to explore next based on the node we are currently
							 	on.
				word: 			The current word.
				wordBuffer:		This removes all need for for loops or while loops, treating
								the string like a queue which takes the first character after
								each recurse of the method, until it becomes empty.
			*/


		}
		
	}

	public Set<String> signatureToWords(String sig) {
		
		/*
			
		*/

		//System.out.println("signatureToWords() running...");
		
		DictTree node = root;

		//System.out.println("About to run while loop...");
		
		boolean abort = false;

		while((!sig.equals("")) && !(abort)) {
			//System.out.println("in while loop because !sig.equals() is " + (!sig.equals("")) + " and !abort is " + (!abort));
			//System.out.println("while condition is currently " + ((!sig.equals("")) || (abort)));	

			int sigforindex = Integer.parseInt("" + sig.charAt(0));

			node = node.getChildFromSignature(sigforindex);
			
			if(node == null) {
				//System.out.println("Aborting search, child node is null.");
				abort = true;

			}
			else {
				//System.out.println("Getting substring for sig.");
				sig = sig.substring(1);

			}

		}

		System.out.println("Outside of loop...");

		if(abort) {

			//if sig not found in tree earlier and search was aborted, return empty set.
			Set<String> set = new TreeSet<String>();
			return set;

		}
		else {
			//else search was performed successfully and return the set at current node.
			return node.getWords();

		}

		
	}

	public void signatureToWordsToPrint(Set<String> set) {

		Object[] arr = set.toArray();

		for(int i = 0; i < arr.length; i++) {

			System.out.print((String)(arr[i]) + " ");

		}

	}
	
	private boolean isValidWord(String word) {
		
		char[] chars = word.toCharArray();

		for (char c : chars) {
			
			if(!Character.isLetter(c))
			{
				return false;
			}

		}

		return true;
	}

	public DictTree getRoot() {

		return root;

	}

}

DictTree.java

import java.util.Collections;
import java.util.Map;
import java.util.Hashtable;
import java.util.Set;
import java.util.TreeSet;
import java.util.ArrayList;

public class DictTree extends Predictive {
	
	private Set<String> wordsList;
	public DictTree[] childNodes;

	public DictTree() {

		super();

		wordsList = new TreeSet<String>();
		childNodes = new DictTree[8];

	}



	public Set<String> getWords() {

		return this.wordsList; //Just return the list this node contains.

	}

	public void addWord(String word) {

		if(!wordsList.contains(word)) { // if set doesn't already contain the word...

			wordsList.add(word); // ...add the word to the set.

		}
	}

	public void constructChildFromSignature(int i) {
			//System.out.println("Constructing child at child node " + i + "...");
			this.childNodes[i - 2] = new DictTree();
		
	}

	public DictTree getChildFromSignature(int i) {
		//System.out.println("Getting child node number " + (i));
		return childNodes[i - 2];

	}

	public void toString(int depth, int index) {

		System.out.println("NODE - Depth: " + depth + ". Index: " + index);

		for(int i = 0; i < 8; i++) {

			if(getChildFromSignature(index + 2) == null) {
				System.out.println("leaf");
			}
			else {
				toString(depth + 1, i);
			}

		}


	}
}