package bst;

import java.util.ArrayList;
import java.util.Comparator;

import javax.xml.soap.Node;


public class BinarySearchTree<E> {
  BinaryNode<E> root;  // Används också i BSTVisaulizer
  int size;            // Används också i BSTVisaulizer
  private Comparator<E> comp;

	/**
	 * Constructs an empty binary search tree.
	 */
	public BinarySearchTree() {
		root = null;
	    comp = null;
	}

	/**
	 * Constructs an empty binary search tree, sorted according to the specified comparator.
	 */
	public BinarySearchTree(Comparator<E> comp) {
		this.comp = comp;
	}

	/**
	 * Inserts the specified element in the tree if no duplicate exists.
	 * @param x element to be inserted
	 * @return true if the the element was inserted
	 */
	private int compEl(E e1, E e2){
		if(comp == null){
			return ((Comparable<E>) e1).compareTo(e2);
		}else{
			return comp.compare(e1, e2);
		}
	}

	public boolean add(E x) {
		if(size == 0){
			root = new BinaryNode<E>(x);
			 size= 1;
			return true;
		}else{
			return add(root, x);
		}
	}

	private boolean add(BinaryNode<E> n, E x){
		if(n == null){
			n = new BinaryNode<E>(x);
			return true;
		}
		int c = compEl(x, n.element);

		if(c == 0){
			return false;
		}
		if(c<0){
			return add(n.left, x);
		}if(c>0){
			return add(n.right, x);
		}
		return false;
	}

	/**
	 * Computes the height of tree.
	 * @return the height of the tree
	 */
	public int height(){
		return height(root);
	}

	private int height(BinaryNode<E> n){
		if(n == null){
			return 0;
		}else{
			int lefth = height(n.left);
			int righth = height(n.right);
			return 1 + Math.max(lefth, righth);
		}

	}

	/**
	 * Returns the number of elements in this tree.
	 * @return the number of elements in this tree
	 */
	public int size() {
		return size;
	}

	/**
	 * Removes all of the elements from this list.
	 */
	public void clear() {
		size =0;
		root = null;
	}

	/**
	 * Print tree contents in inorder.
	 */
	public void printTree() {
		printTree(root);
	}

	private void printTree(BinaryNode<E> n){
		if(n == null){
			System.out.println("Ajajaj, Tree is empty");
		}else{
			printTree(n.left);
			System.out.println(""+n.element);
			printTree(n.right);
		}
	}

	/**
	 * Builds a complete tree from the elements in the tree.
	 */
	public void rebuild() {

	}

	/*
	 * Adds all elements from the tree rooted at n in inorder to the list sorted.
	 */
	private void toArray(BinaryNode<E> n, ArrayList<E> sorted) {

	}

	/*
	 * Builds a complete tree from the elements from position first to
	 * last in the list sorted.
	 * Elements in the list a are assumed to be in ascending order.
	 * Returns the root of tree.
	 */
	private BinaryNode<E> buildTree(ArrayList<E> sorted, int first, int last) {
		return null;
	}



	static class BinaryNode<E> {
		E element;
		BinaryNode<E> left;
		BinaryNode<E> right;

		private BinaryNode(E element) {
			this.element = element;
		}
	}

}