import java.util.*;
import java.io.*;

/**
 * A program that creates a binary search tree object
 * Daniel Scarbrough
 * Version 1.0
 */
public class BinarySearchTree <E extends Comparable<E>> {
    private Node root;
    private static String filename = "English.lex";     //holds file name in field
    private int counter;        //counts how many nodes are present

    public BinarySearchTree() {
        root = null;
        counter = 0;
    }


    public  void insert(E object) {
        counter++;
        Node newNode = new Node(object);
        if (root == null) {
            root = newNode;
            return;
        }
        Node current = root;
        Node parent = null;
        while (true) {  //goes until return statement
            parent = current;
            if (object.compareTo(current.data) < 0) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    /**
     * checks the tree to see if it contains the value
     * @param value value to be checked
     * @return true if value is in tree, false if not
     */
    public boolean has (E value){
        Node current = root;
        while (current!=null){
            if(current.data.compareTo(value)>0){
                current=current.left;
            }else if (current.data.compareTo(value)<0){
                current=current.right;
            }
            else if (current.data.equals(value)) return true;
}
        return false;
    }

    /**
     *finds the minimum value in the tree
     * @return the minimum value
     */
    public E findMin(){
        Node current = root;
        if (root == null)
            return null;
        while (current.left != null) {
            current = current.left;
        }
        return current.data;
    }

    /**
     *finds the maximum value in the tree
     * @return the data of the max value
     */
    public E findMax(){
        Node current = root;
        if (root == null)
            return null;
        while (current.right != null) {
            current = current.right;
        }
        return current.data;
    }

    /**
     * get the size of the list
     * @return the size of the list
     */
    public int getSize(){
        return counter;
    }

    /**
     * private method to help test tree
     * @return a string with root, rootleft and rootright
     */
    private String printTest(){
        String str = " ";
        str+= "Root: "  +root.data;
        str += ":rootL: " +root.left.data;
        str += ":rootR: " +root.right.data;
        return str;
    }

    /**
     *finds the next value after the given value
     * @param value to find the succesor of
     * @return data of successor
     */
    public E findSuccessor(E value) {       //mostly identical to findpredecessor, but uses right child
        Node current = root;
        if (root == null)
            return null;
        else if (current.data.equals(value) || has(value) == false)
            return null;
        else {
            if (current.right != null) {
                current = current.right;
            } else
                return null;
            if (current != null) {
                while (current.left != null) {
                    current = current.left;
                }
            }
        }
        return current.data;
    }

    /**
     *finds the value immediately before given value
     * @param value value to find predecessor of
     * @return value of predecessor
     */
    public E findPredecessor(E value) {
        Node current = root;
        if (root == null)
            return null;
        else if (current.data.equals(value) || has(value) == false)
            return null;
        else {
            if (current.left != null) {
                current = current.left;
            } else
                return null;
            if (current != null) {
                while (current.right != null) {
                    current = current.right;
                }
            }
        }
        return current.data;
    }




    /**
     *Main method
     */
    public static void main(String[] args) {
        BinarySearchTree<String> testTree = new BinarySearchTree<>();
        ArrayList<String> arrayList = new ArrayList<>();        //creates an arrayList that will first hold all elements
        int numWords = 0;       //holds the number of words transferred from the file
        try {      //try catch block to catch filenotfound exception
            Scanner scanner = new Scanner(new File(filename));
            //loops through and adds all elements of file to arrayList
            while (scanner.hasNextLine()) {
                arrayList.add(scanner.nextLine());      //adds line of the file to a new spot in the arrayList
                numWords++;     //iterates the number of words so we know how many elements there are
            }
            Collections.shuffle(arrayList);     //shuffles the arrayList

             for(int i = 0; i < arrayList.size(); i++){ //copies all elements from arrayList to the binaryTree.
                 testTree.insert(arrayList.get(i));
             }

            Scanner keyboard = new Scanner(System.in); //holds user input for loop
            boolean stopOrNot = false;      //holds condition for while loop

            System.out.println("Testing binary search tree");
            System.out.println("loaded " +filename + "( " +numWords + " words from " +testTree.findMin() + " to " + testTree.findMax()+")");
            System.out.println("Please enter a word, or hit enter to quit");

            System.out.println(testTree.printTest());


            do {

                String str = keyboard.nextLine();
                if (str.equals("")) {                   //if user input is just "enter" then will close program
                    System.out.println("Goodbye!");
                    stopOrNot = true;
                } else {
                    if (testTree.has(str)) {
                        System.out.println(str + " is a valid word!");
                    } else {
                        System.out.println(str + " is NOT a valid word!");
                    }
                }


            }
            while (!stopOrNot);


        }
        catch(FileNotFoundException ex){
            System.out.println("File not found: Please try again");
        }
    }

    /**
     * private Node class used to make each node object
     */
    private class Node{
        private E data;         //holds the nodes Data
        private Node left;      //holds Nodes pointer to left node (less)
        private Node right;     //holds Nodes pointer to right node (bigger)

        /**
         * @param data  data that the node will hold

         */
        private Node(E data) {     //constructor to set node data
            this.data = data;
            this.left = null;
            this.right = null;
        }



        /**
         * @param node node whos data want printed
         * @return returns data in ()
         */
        private String toString(Node node) {
            return ("(" + node.data + ")");
        }
    }

}