import java.util.ArrayList;
import java.util.Collections;

public class BSTDictionary<E, K> implements Dictionary<Object, SortableString>{
private BSTNode root;
private BSTNode curr;

	/*
	 * Basic constructor, sets root to null
	 */
	public BSTDictionary() {
		root = null;
	}

	/*
	 * Searches the tree for the given key
	 * @param key the key that dictates the node that is to be found
	 * @return returns the element of the node with the given key or null if not found
	 */
	public  Object search(SortableString key) {
		boolean found = false;
		curr = root;
		while(!found && curr != null) { //while loop to search until found or end of tree
			if(key.compareTo(curr.getKey()) < 0) {//less than | key < curr
				curr = curr.getLeft();

			}
			else if(key.compareTo(curr.getKey()) > 0) {//greater than | key > curr
				curr = curr.getRight();

			}
			else if (key.compareTo(curr.getKey()) == 0) {//if node is found
				found = true;
				}
			}
		if(!found)
		{
		return null;
		}
		else {
			return curr.getElement();
		}
	}

	/*
	 * creates a node with the provided key and element and adds it to the tree
	 *
	 * @param key the key that dictates the node that is to be found
	 * @param element the element of the node
	 */
	public void insert(SortableString key, java.lang.Object element){
		boolean inserted = false;
		curr = root;
		//System.out.println("the key is: " + key + " The element is: " + element); //prints the key and element created
		if(key == null) {
			return;
		}
		else if(root == null) {//case if node inserted is the first one
			root = new BSTNode(key, element, null, null);
		}
		else {
			while(!inserted) { //while loop to navigate until the right spot is found
				if(key.compareTo(curr.getKey()) < 0) {//less than | key < curr

					if(curr.getLeft() == null) {// checks if there is a node left of the parent
						curr.setLeft(new BSTNode(key, element, null, null));//sets a new node to the left of the parent with given params
						inserted = true;
						//System.out.println("added left");
					}
					else {
						curr = curr.getLeft();//moves to the left and repeats loop
					}
				}
				else if(key.compareTo(curr.getKey()) > 0) {//greater than | key > curr
					if(curr.getRight() == null) {//checks of right slot is empty
						curr.setRight(new BSTNode(key, element, null, null));//sets a new node to the right of the parent
						inserted = true;
					//	System.out.println("added right");
					}
					else {
						curr = curr.getRight();//moves to the right and repeats loop
					}
				}
				else {//element is already in the tree if it reaches here
					inserted = true;
				}
			}

		}
	}

	/*
	 * Deletes the specified key from the tree
	 *
	 * @param key the key to be deleted
	 */
	public void delete(SortableString key) {
	//	System.out.println("============");
	//  System.out.println("Deleting: " + key);
		BSTNode parent = root;//lags 1 node behind the curr node
		curr = root;

		if(root == null) {//checks if tree is empty
		//	System.out.println("tree is empty");
			return;
		}
		boolean found = false;
		while(!found && curr != null) {//loops until end of tree or until the key is found
			if(key.compareTo(curr.getKey()) < 0) {//less than | key < curr
				parent = curr;
				curr = curr.getLeft();//moves the curr node along the tree

			}
			else if(key.compareTo(curr.getKey()) > 0) {//greater than | key > curr
				parent = curr;
				curr = curr.getRight();//moves the curr node along the tree

			}
			else if (key.compareTo(curr.getKey()) == 0) {//checks if key is found
		//		System.out.println("found: " + curr.getKey());
				found = true;
				}
			}


		if(curr == null) {//checks if
		//	System.out.println("key is not in the tree: " + key);
		}
		//case 1 -  no children
		else if(curr.getLeft() == null && curr.getRight() == null){
		//	System.out.println("case 1");
			curr = parent;

			if(curr.getLeft() != null) {
				if(curr.getLeft().getKey().compareTo(key) == 0) {
		//			System.out.println("Deleted: " + curr.getLeft().getKey());
					curr.setLeft(null);
				}
			}
			if(curr.getRight() != null) {
				if(curr.getRight().getKey().compareTo(key) == 0) {
		//			System.out.println("Deleted: " + curr.getRight().getKey());
					curr.setRight(null);
				}
			}
		}


		//case 2 - one child

		else if(curr.getLeft() != null && curr.getRight() == null){ //has a left leaf
		//	System.out.println("case 2L");

			BSTNode temp;
			temp = curr.getLeft();
			if(curr == root){
				root = curr.getLeft();
			}
			else {
		//		System.out.println("Deleted: " + curr.getKey());
				curr = parent;
				if(curr.getLeft() != null) {
					if(curr.getLeft().getKey() == key) {
						curr.setLeft(temp);
					}
				}
				else if(curr.getRight() != null) {
					if(curr.getRight().getKey() == key) {
						curr.setRight(temp);
					}
				}
			}
		}

		else if(curr.getLeft() == null && curr.getRight() != null){//has a right leaf
		//	System.out.println("case 2R");
			BSTNode temp;
			temp = curr.getRight();
		//	System.out.println("Deleted: " + curr.getKey());
			if(curr == root){
				root = curr.getRight();
			}
			else {
				curr = parent;
				if(curr.getLeft() != null) {
					if(curr.getLeft().getKey() == key) {
						curr.setLeft(temp);
					}
				}
				else if(curr.getRight() != null) {
					if(curr.getRight().getKey() == key) {
						curr.setRight(temp);
					}
				}
			}
		}

		//case 3 - 2 children
		else if(curr.getLeft() != null && curr.getRight() != null){//has 2 children
		//	System.out.println("case 3");
			BSTNode tempR, tempL;
			tempR =  curr.getRight();
			tempL = curr.getLeft();
		//	System.out.println("Deleted: " + curr.getKey());
			curr = curr.getRight();


			while(curr.getLeft() != null) {
				curr = curr.getLeft();
			}

			if(parent.getLeft() != null && parent.getLeft().getKey() == key) {
				parent.setLeft(curr);
				curr.setLeft(tempL);
				curr.setRight(tempR);
			}
			else if( parent.getRight() != null && parent.getRight().getKey() == key) {
				parent.setRight(curr);
				curr.setLeft(tempL);
				curr.setRight(tempR);
			}
		}
	}


	public void printTree() {
		ArrayList<String> elements = new ArrayList<String>();
		elements = traverse(root, elements);
		Collections.sort(elements);
		for(String s: elements) {
			System.out.println(s + "");
		}

	}

	private ArrayList traverse(BSTNode root,ArrayList list){
	    if (root.getLeft() != null){
	        traverse(root.getLeft(), list);
	    }
	    list.add(root.getElement());
	    if (root.getRight() != null){
	        traverse(root.getRight(), list);
	    }
		return list;
	}



	public int depth() {
		return maxDepth(root);
	}


	private int maxDepth(BSTNode node) {
		if (node == null) {
			return 0;
		} else {
			// compute the depth of each subtree
			int leftDepth = maxDepth(node.getLeft());
			int rightDepth = maxDepth(node.getRight());
			// find the larger one
			if (leftDepth > rightDepth )
				return (leftDepth + 1);
			else
				return (rightDepth + 1);
		}
	}


	public  BSTNode find(Sortable key) {
		curr = root;
		boolean found = false;
		while(!found) {
			if(key.compareTo(curr.getKey()) < 0) {//less than | key < curr
				curr = curr.getLeft();
			}
			else if(key.compareTo(curr.getKey()) < 0) {//greater than | key > curr
				curr = curr.getRight();
			}
			else {

			return curr;
			}
		}
		return null;
	}


}