package project5;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;
import org.w3c.dom.Node;

/**
 * This is an implementation of a binary search tree
 * All elements in the bst are organized in ascending/increasing order
 * based on the order of the String elements associated with the
 * Nodes' Word elements
 *
 * @author William Margulies
 *
 */
public class BSTIndex implements Index {
    // initializes class variables
    private int size;
    Node root;

    /*
     * Default constructor. Constructs a BSTIndex with
     * a size of 0
     */
    public BSTIndex() {
        size = 0;
    }

    /*
     * Getter method that returns the BSTIndex's size
     * 
     * @return int size of the BSTIndex
     */
    public int size() {
        return size;
    }

    /*
     * Calls the constructor for the private class ListIterator()
     * 
     * @return iterator, an Iterator<Word> type instance of an iterator through the
     * BST
     */
    public Iterator<Word> iterator() {
        return new ListIterator();
    }

    /*
     * Adds a new Node containing a new Word
     * with the text content from the String
     * parameter item to the binary search tree
     * using the addHelper method
     * 
     * @param item the word relating to the Word to add
     * 
     * @throw IllegalArgumentException if the parameter is
     * invalid
     */
    public void add(String item)
            throws IllegalArgumentException {
        // if the parameter is null, throw an exception
        if (item == null) {
            throw new IllegalArgumentException("Item cannot be null");
        }
        // If the tree is empty, assign the new Node to the root value
        // and increment the size
        if (root == null) {
            root = new Node(new Word(item));
            size++;
            return;
        }
        // otherwise, call the addHelper method to add the Word
        addHelper(root, item);
    }

    /*
     * Used in conjunction with the add method to recursively
     * add a new Word to the BSTIndex.
     * 
     * @param current the current Node to be analyzing
     * 
     * @param item the String of the Word to add to the tree
     */
    private void addHelper(Node current, String item) {
        // calculate the comparison value of the current node
        int compareResult = current.val.getWord().compareTo(item);

        if (compareResult == 0) {
            // Word already exists, increment its count
            current.val.incrementCount();
        } else if (compareResult > 0) {
            // if the result shows the added value is less than the
            // current value, move leftwards
            if (current.left == null) {
                // Create a new Node with appropriate Node if the
                // current's left child is null and increase size
                current.left = new Node(new Word(item));
                size++;
            } else {
                // If the child is not null, recursively traverse the
                // left node
                addHelper(current.left, item);
            }
        } else {
            // if the result shows the added value is greater than the
            // current value, move rightwards
            if (current.right == null) {
                // Create a new Node with appropriate Node if the
                // current's right child is null and increase size
                current.right = new Node(new Word(item));
                size++;
            } else {
                // If the child is not null, recursively traverse the
                // left node
                addHelper(current.right, item);
            }
        }
    }

    /**
     * Compares the parameter Object o with this list to see if they are equal.
     *
     * @param o the object to compare with
     * @return true if the object is equal to this list, false otherwise
     */
    public boolean equals(Object o) {
        // if o is null or does not implement Index, return false
        if (o == null || !(o instanceof Index)) {
            return false;
        }

        Index other = (Index) o;
        // if the lists' sizes are unequal, return false
        if (other.size() != size()) {
            return false;
        }
        // initialize iterators and variables to capture their values
        Iterator<Word> otherIterator = other.iterator();
        Iterator<Word> thisIterator = this.iterator();
        Word otherTemp;
        Word thisTemp;
        // Loop through each value in each list to find discrepancies
        // Return false if a discrepancy is found
        for (int i = 0; i < size(); i++) {
            otherTemp = otherIterator.next();
            thisTemp = (Word) thisIterator.next();
            if (!otherTemp.equals(thisTemp)) {
                return false;
            }
        }
        // if no discrepancies are found, return true.
        return true;
    }

    /*
     * Remove a Word with the getWord value str from the
     * BSTIndex recursively using deleteHelper
     */
    public void remove(String str) {
        deleteHelper(str, root);
    }

    /*
     * Recursively deletes a Word Node with the getWord value
     * str from the BSTIndex
     * 
     * @param str the word of the Word object to remove
     * 
     * @param current the current Node to analyze
     * 
     * @return the corrected Node to place in its correct place
     */
    public Node deleteHelper(String str, Node current) {
        // if the current Node is null, return null
        if (current == null) {
            return null;
        }
        // create a comparison variable between the word value and
        // the current Node's value
        int compareResult = current.val.getWord().compareTo(str);
        // if the word value is greater than the current Node's value,
        // analyze the left child node
        if (compareResult > 0) {
            current.left = deleteHelper(str, current.left);
        } else if (compareResult < 0) {
            // if the word value is greater than the current Node's value,
            // analyze the leftmost node
            current.right = deleteHelper(str, current.right);
        } else {
            // if the word value is equal to the current Node's value, check
            // if the Node's children are null for simple removal
            if (current.left == null) {
                return current.right;
            } else if (current.right == null) {
                return current.left;
            }
            // if the children are not null, assign the current Node
            // its successor's value and remove that value from the tree
            current.val = minValue(current.right);
            current.right = deleteHelper(current.val.getWord(), current.right);
        }
        // return the current Node
        return current;
    }

    /*
     * Helper method to return the minimum Word value
     * in the given Node's subtree.
     * 
     * @param node is the Node whose subtree will be explored
     * 
     * @return the minimum Word value of this subtree
     */
    private Word minValue(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.val;
    }

    /*
     * Finds and returns the getCount value of a word
     * with a given word value str
     * 
     * @param str is the Word's word value to find the count of
     * 
     * @return an int value of the found Word or -1 if not found
     */
    public int get(String str) {
        // start parasing the root node
        Node curr = root;
        // whle curr in not null, and the end of the tree is not
        // parsed
        while (curr != null) {
            // if the value to be searched for is less than the
            // current value, parse leftwards
            if (curr.val.getWord().compareTo(str) == -1) {
                curr = curr.left;
                // if the value to be searched for is greater than the
                // current value, parse rightwrads
            } else if (curr.val.getWord().compareTo(str) == 1) {
                curr = curr.right;
                // if the values are equal, return the count of this node
            } else if (curr.val.getWord().equals(str)) {
                return curr.val.getCount();
            }
        }
        // if the Node cannot be found, return -1
        return -1;
    }
    /*
     * This is the implementation of an iterator through
     * this binary search tree
     */
    private class ListIterator implements Iterator<Word> {
        // instantiate class variables
        Stack<Word> stack;
        Word curr;
        /*  
        * Construct a default ListIterator
        */
        public ListIterator() {
           stack = new Stack<>();
            //calls the orderHelper method to organize a stack
           if (root != null) {
                orderHelper(root);
            }
        }
        /*
         * Helper method to put 
         */
        public void orderHelper(Node n) {
            if (n.left == null && n.right == null) {
                stack.push(n.val);
                return;
            } else if (n.right == null) {
                stack.push(n.val);
                orderHelper(n.left);
                return;
            } else if (n.left == null) {
                orderHelper(n.right);
                stack.push(n.val);
                return;
            }

            orderHelper(n.right);
            stack.push(n.val);
            orderHelper(n.left);
        }

        public Word next() {
            curr = stack.pop();
            return curr;
        }

        public void remove() {
            root = deleteHelper(curr.getWord(), root);
            if (root != null) {
                size--;
            }
        }

        public boolean hasNext() {
            if (stack.isEmpty()) {
                return false;
            }
            return true;
        }
    }

    private class Node {
        Word val;
        Node left, right;

        public Node(Word wor) {
            this.val = wor;
        }
    }
}