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




class BinarySearchTree <E extends Comparable<E>> {

	private Node root;
	public int size = 0;

	/**
	 * Node class - identifies a particular element with the value it holds and
	 * the address of the subsequent element.
	 * @author Andy Van Heuit
	 */
	private class Node{

		public final E value;
		public Node leftChild, rightChild;

		private Node(E value){
			this.value = value;
			leftChild = null;
			rightChild = null;
		}

		public String toString(){
			return "(" + value + ")";
		}
	}

	public BinarySearchTree(){
		root = null;
	}

	public void insert(E value){
		if(root == null){
			root = new Node(value);
			size++;
			return;
		}

		else{

			Node newNode = root;

			while(newNode != null){

				if(value.compareTo(newNode.value) < 0){
					newNode = newNode.leftChild;
				}

				else{
					newNode = newNode.rightChild;
				}

			}

		newNode = new Node(value);
		size++;

		}

	}


	public boolean has(E value){

		if(root == null) return false;

		else{

			Node nextNode = null;

			for(Node compare = root; compare != null; compare = nextNode){

				if(value.compareTo(compare.value) == 0){
					return true;
				}

				else{

					if(value.compareTo(compare.value) <= 0){
						nextNode = compare.leftChild;
					}

					else{
						nextNode = compare.rightChild;
					}

				}

			}
		}

		return false;

	}

	public E findMin(){
		Node min = root;

		while(min.leftChild != null && min != null){
			min = min.leftChild;
		}

		return min.value;

	}

	public E findMax(){
		Node max = root;

		while(max.rightChild != null){
			max = max.rightChild;
		}

		return max.value;

	}

	public int getSize(){
		return size;
	}

	public void print(){
		print(root);
		System.out.println();
	}

	private void print(Node node){
		if(node == null) return;

		print(node.leftChild);
		print(node.rightChild);

		System.out.println(node.value + " ");
	}

	private static String[] loadWordFile(String filename){

		ArrayList<String> getWords = new ArrayList<String>();
		Scanner fileReader;

		try{
			fileReader = new Scanner(new File(filename));
		}

		catch(FileNotFoundException e){
			System.err.println("File " + filename + " not found.");
			System.exit(1);
			return null;
		}

		while(fileReader.hasNextLine()){
			getWords.add(fileReader.nextLine());
		}

		fileReader.close();
		return getWords.toArray(new String[getWords.size()]);

	}

	public static String[] shuffle(String[] set) {
		for (int i = 1; i < set.length; i++) {
			int j = (int) (Math.random() * (i + 1));
			String swap = set[i];
			set[i] = set[j];
			set[j] = swap;
		}
		return set;
	}

	public static void main(String[] args){

		BinarySearchTree<String> tree = new BinarySearchTree<String>();

		String[] test = loadWordFile("english.lex");

		shuffle(test);

		for(int i = 0; i < test.length; i++){
			tree.insert(test[i]);
		}

		System.out.println(tree.getSize());
		System.out.println(tree.root);
		System.out.println("First element: " + tree.findMin());
		System.out.println("Last element: " + tree.findMax());
		System.out.println();

		Scanner inputScanner;
		System.out.println(">");
		for(int i = 1; i > 0; i++){
			inputScanner = new Scanner(System.in);
			String input = inputScanner.nextLine();

			if(input.equals("")){
				System.out.println("Goodbye!");
				System.exit(1);
			}

			else{

				if(tree.has(input)){

					System.out.println("\""+ input + "\" is a valid word!");

				}

				else{

					System.out.println("\"" + input + "\" is not a valid word.");

				}
			}
		}

	}

}