package assignment3;

public class BSTMap <K extends Comparable <K>, V> implements SimpleMap<K,V>{

    int compCount = 0;                      // Creating a int variable set to 0 to count the number of times compareTo is run in search.
    int searchCount = 0;                    // Creating a int variable set to 0 to count the number of times search is run.
    int size = 0;                           // Creating a int variable set to 0 to count the size of the tree.
    private bstNode root;                   // Setting a private variable of type bstNode.
    bstNode <K, V> currentNode = root;      // Creating an object of type bstNode set as the root.
    bstNode <K, V> modNode = root;          // Creating an object of type bstNode set as the root.
    bstNode <K, V> delNode = root;          // Creating an object of type bstNode set as the root.


    // bstNode class.
    private class bstNode <K extends Comparable <K>, V>{
        K key;                                  // Creating key of generic type K
        V value;                                // Creating value of generic type V
        bstNode left, right;                    // Creating left and right of type bstNode


        //Constructor
        public bstNode(K key, V value) {
            // Setting Key and value

            this.key = key;
            this.value = value;
        }
    }
    /*
     *@returns boolean value
     */
    public boolean isEmpty() {
        if (root == null) {                     // Checks to see if root is null.
            return true;                        // Returns true if root is null.
        }
        return false;                           // Else returns false
    }


    /*
     *@returns int value
     */
    public int size() { return size; }          // Returns the size.

    /*
     *@param key, value
     */
    public void insert(K key, V value) throws KeyFoundException {   // Recursive insert function
        if (root == null){
            root.key = key;                     // Sets the roots key.
            root.value = value;                 // Sets the roots value.
            currentNode = root;                 // Setting currentNode to the root
            size++;                             // Increments size of tree.
            return;                             // Returns nothing.
        }

        if (currentNode == null) {
            currentNode.key = key;          // Sets currentNode's key to the parameters key.
            currentNode.value = value;      // Sets currentNode's value to the parameters value.
            size++;                         // Increments size.
            currentNode = root;             // Reseting currentNode to root
            return;                         // Returns nothing.
        }
        else if (key.compareTo(currentNode.key) == 0) {
            currentNode.value = value;                  // Sets currentNode's value to the parameters value.
            currentNode = root;             // Reseting currentNode to root
            return;                                     // Returns Nothing.
        }
        else if (key.compareTo(currentNode.key) < 0) {  // Comparing key to the currentNode's key to see if currentNode should go left.
            currentNode = currentNode.left;             // sets currentNode to the left of currentNode.
            insert(key, value);                         // Calls insert again same parameters.

        }
        else if (key.compareTo(currentNode.key) > 0) {  // Comparing key to the currentNode's key to see if currentNode should go right.
            currentNode = currentNode.right;            // Sets currentNode to the right of currentNode.
            insert(key, value);                         // Calls insert again with the same parameters.
        }

    }


    /*
     *@param key
     */
    public void delete(K key) throws KeyNotFoundException {

        if(delNode == null) throw new KeyNotFoundException();           // Throws exception if the tree is null.

        else if (key.compareTo(delNode.key) == 0) {                     // Checks if the key is the same as the node's key


            if(delNode.left == null && delNode.right == null){          // Checks if the node has no children.
                delNode = null;                                         // sets node to null
                size--;                                                 // decrements size
                bstNode <K, V> delNode = root;                          // resets node's location to the root.
                return;
            }
            else if(delNode.left != null && delNode.right == null) {    // Checks if node has only left child
                bstNode <K, V> replaceNode = delNode.left;              // Creates a instance of a node.
                while(replaceNode.right != null) {                      // Search's for the replacing node
                    replaceNode = replaceNode.right;                    // Sets the replacing node.
                }
                delNode = replaceNode;                                  // Replaces the parent node
                replaceNode = null;                                     // Sets the leaf to null
                size--;                                                 // Decrements size
                bstNode <K, V> delNode = root;                          // Resets the position of the node to root
                return;
            }
            else if(delNode.left == null && delNode.right != null) {    // Checks if node has only right child
                bstNode <K, V> replaceNode = delNode.right;             // Creates instance of a node
                while(replaceNode.left != null) {                       // Search's for a replacing node
                    replaceNode = replaceNode.left;                     // Sets the replacing node.
                }
                delNode = replaceNode;                                  // Replaces the parent node
                replaceNode = null;                                     // Sets leaf to null
                size--;                                                 // Decrements the size
                bstNode <K, V> delNode = root;                          // Resets the position of the node to root
                return;
            }
            else if (delNode.left != null && delNode.right != null) {   // Checks if node has two children
                bstNode <K, V> replaceNode = delNode.right;             // Creates an instance of a node
                while (replaceNode.left != null) {                      // Search's for a replacing node
                    replaceNode = replaceNode.left;                     // Sets the replacing node.
                }
                if(replaceNode.right != null){                          // Checks the right subtree of the parent.
                    bstNode <K, V> temp = replaceNode.right;            // Creates new instance of a node.
                    delNode = replaceNode;                              // Overwrites the deleteNode
                    replaceNode = temp;                                 // Overwrites the node that replaced deleteNode
                    temp = null;                                        // Deletes a leaf
                    size--;                                             // Decrements size
                    bstNode <K, V> delNode = root;                      // Resets the location of delNode to the root.
                    return;
                }
                delNode = null;                                         // deletes the root basically.
                size--;                                                 // Decrements size
                bstNode <K, V> delNode = root;                          // Resets the delNode to the root.
                return;
                }

        }else if (key.compareTo(delNode.key) < 0) {                     // Searching for the correct node that should be deleted.
            delNode = delNode.left;                                     // Traverse left in the tree
            delete(key);                                                // Recursively call delete
        }else if(key.compareTo(delNode.key) > 0) {                      // Searching for the correct node that should be deleted.
            delNode = delNode.right;                                    //Traverse right in the tree
            delete(key);                                                // Recursively call delete
        }

    }


    /*
     * @params key
     * @returns V type
     */
    public V search(K key) throws KeyNotFoundException {
        compCount = 0;                          // Resets compareTo counter to 0.
        searchCount++;                          // Increments the search counter
        bstNode <K, V> currentNode = root;      // Sets a currentNode to root
        while (key.compareTo(currentNode.key) != 0) {                                       // Loops until exception is thrown or key is found
           compCount++;                                                                     // Incrementing compareTo count
            if (key.compareTo(currentNode.key) < 0) {                                       // Compares the key to the key of the current node to see which direction the tree should traverse.
                if (currentNode.left == null) throw new KeyNotFoundException();     // Throws KeyNotFoundException if the next location is null.
                currentNode = currentNode.left;                                             // traverses to the left
                compCount++;                                                                // Increments the compareTo counter
                continue;                                                                   // Continues to the next iteration of the loop
            }
            if (key.compareTo(currentNode.key) > 0) {                                       // Compares the key to the key of the current node to see which direction the tree should traverse.
                if (currentNode.right == null) throw new KeyNotFoundException();        // Throws KeyNotFoundException if the next location is null.
                currentNode = currentNode.right;                                            // Traverses to the right
                compCount++;                                                                // Increments the compare to counter
                continue;                                                                   // continues to the next iteration of the loop
            }
        }
        return currentNode.value;               // Returns the value of the node that was being looked for.
    }


    /*
     * @param key, value
     */
    public void modify(K key, V value) throws KeyNotFoundException {

        if(modNode == null) throw new KeyNotFoundException();       // Throws exception if tree is null.

        else if (key.compareTo(modNode.key) == 0) {     // Checking if the node we are modifying is found
            modNode.value = value;                      // Modifying the value of the node
            bstNode <K, V> modNode = root;              // Reseting the location of modNode
            return;
        }else if (key.compareTo(modNode.key) < 0) {     // Seeing if we should traverse left through the tree
            modNode = modNode.left;                     // Traverse left
            modify(key, value);                         // Recursively calling modify
        }else if(key.compareTo(modNode.key) > 0) {      // Seeing if we should traverse right through the tree
            modNode = modNode.right;                    // Traverse right
            modify(key, value);                         // Recursively calling modify
        }

    }

    /*
     *@returns int value
     */
    public int getNumCompares() {
        return compCount;               // Returns the compareTo count
    }

    /*
     *@returns int value
     */
    public int getNumSearch() {
        return searchCount;
    }
}