package assignment8;

import java.util.ArrayList;
import java.util.Collection;
import java.util.NoSuchElementException;

public class BinarySearchTree<Type extends Comparable<? super Type>> implements SortedSet<Type> {

    node root;
    int size;

    private class node {
        Type data;
        node left;
        node right;

        public node(Type data, node left, node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public BinarySearchTree() {
        this.root = null;
    }

    @Override
    public boolean add(Type item) {
        return addHelper(item, root);
    }

    /**
     * helper method for the add method
     *
     * @param item
     * @param n
     * @return boolean
     */
    public boolean addHelper(Type item, node n) {
        if(n.data == item) {
            return true;
        }
        else {
            // item goes down the right branch
            if(item.compareTo(n.data) >= 0) {
                if(n.right.equals(null)) {
                    addNode(item, n, true);
                    return true;
                }
                addHelper(item, n.right);
                return true;
            }

            // item goes down the left branch
            if(item.compareTo(n.data) < 0) {
                if(n.left.equals(null)) {
                    addNode(item, n, false);
                    return true;
                }
                addHelper(item, n.left);
                return true;
            }
        }
        return false;
    }

    /**
     * helper method for adding a node to the left or right of the node n, if i is 0 adds to the left and i is 1 adds to the right
     *
     * @param item
     * @param n
     * @param i
     */
    public void addNode(Type item, node n, boolean right) {
        // adds to the right
        if(right == true) {
            node rightNode = new node(item, null, null);
            n.right = rightNode;
        }
        // adds to the left
        else {
            node leftNode = new node(item, null, null);
            n.left = leftNode;
        }
    }

    @Override
    public boolean addAll(Collection<? extends Type> items) {
        boolean bool = false;
        for(Type item: items) {
            if(add(item)) {
                bool = true;
            }
        }
        return bool;
    }

    @Override
    public void clear() {
        // TODO Auto-generated method stub

    }

    @Override
    public boolean contains(Type item) {
        return recursiveContains(item, root);
    }

    /**
     * helper method for the contains that recursively goes through every node to see if it contains an item
     *
     * @param item
     * @param n
     * @return boolean
     */
    public boolean recursiveContains(Type item, node n) {
        if(n.data == item) {
            return true;
        }
        else {
            recursiveContains(item, n.left);
            recursiveContains(item, n.right);
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<? extends Type> items) {
        for(Type item : items) {
            if(contains(item) == false) {
                return false;
            }
            return true;
        }
        return true;
    }

    @Override
    public Type first() throws NoSuchElementException {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean isEmpty() {
        if (size == 0) {
            return true;
        }
        else {
            return false;
        }
    }

    @Override
    public Type last() throws NoSuchElementException {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean remove(Type item) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean removeAll(Collection<? extends Type> items) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int size() {
        return sizeHelper(root);
    }

    /**
     * helper method for size which returns the size of the subtree including the node
     *
     * @param n
     * @return int
     */
    public int sizeHelper(node n) {
        return 1 + sizeHelper(n.left) + sizeHelper(n.right);
    }

    @Override
    public ArrayList<Type> toArrayList() {
        // TODO Auto-generated method stub
        return null;
    }

}