//CS112 Spring 2008
//Homework 4 Code


import java.awt.*;



public class BinarySearchTree<AnyType extends Comparable<AnyType>>
//you can skip on the generics and make it a BST of ints
{
	private static class BinaryNode<AnyType>
        {
            
            AnyType element;
            BinaryNode<AnyType> left;
            BinaryNode<AnyType> right;
            //you will need to add parameters to know where to display this node: either an x and y coordinate
            //or inorder traversal number and depth (from which you get the x and y coordinate)
            
            BinaryNode(AnyType e)
            {
                this(e,null,null);
            }
            
            BinaryNode(AnyType e, BinaryNode<AnyType> l, BinaryNode<AnyType> r)
            {
                element = e;
                left = l;
                right = r;
            }
        }
        
        private BinaryNode<AnyType> root;
        
        public BinarySearchTree()
        {
            root = null;
        }
        
        public void makeEmpty()
        {
            root = null;
        }
        
        public boolean isEmpty()
        {
            return (root == null);
        }
        
        private boolean contains(AnyType x, BinaryNode<AnyType> t)
        {
            if(t == null)
            {
                return false;
            }
            
            int compareResult = x.compareTo(t.element);
            if(compareResult < 0)
            //look in the left subtree
            {
                return (contains(x,t.left));
            }
            else if(compareResult > 0)
            //look in the right subtree
            {
                return (contains(x,t.right));
            }
            else
            //we have found the element
            {
                return true;
            }
        }
        
        private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t)
        //returns node with smallest element
        //implemented recursively
        {
            if(t == null)
            {
                return null;
            }
            else if(t.left == null)
            {
                return t;
            }
            else
            {
                return(findMin(t.left));
                //tail recursion can be replaced by while loop, see findMax
            }
        }
        
        private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t)
        //returns node with largest element
        //implemented iteratively
        {
            if(t == null)
            {
                return null;
            }
            while(t.right != null)
            //iterate until reaching rightmost node in tree
            {
                t = t.right;
            }
            return t;
        }
        
        private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t)
        {
            if(t == null)
            {
                return (new BinaryNode<AnyType>(x));
            }
            int compareResult = x.compareTo(t.element);
            if(compareResult < 0)
            {
                t.left = insert(x,t.left);
            }
            else if(compareResult > 0)
            {
                t.right = insert(x, t.right);
            }
            else
            //the item is already in the tree
            {
                //this implementation does not support duplicates so do nothing
            }
            return t;
        }
        
        private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t)
        {
            if(t == null)
            {
                return t;
                //the item was not found, so we do nothing
            }
            int compareResult = x.compareTo(t.element);
            if(compareResult < 0)
            //perform the removal on the left subtree
            {
                t.left = remove(x,t.left);
            }
            else if(compareResult > 0)
            //perform the removal on the right subtree
            {
                t.right = remove(x,t.right);
            }
            //if this code is reached then we have found the element to remove
            else if(t.left != null && t.right != null)
            //modify this node, which has two children
            {
                t.element = findMin(t.right).element;
                //set this node to contain the smallest element in the right subtree, preserving the order property
                t.right = remove(t.element,t.right);
                //now remove the node containing this element from the right subtree
                //this will be the below case because the smallest node in right subtree must have no left child
            }
            else
            //remove this node, which has one or no children
            {
                if(t.left != null)
                //if it has a child on the left
                {
                    t = t.left;
                }
                else
                //if it has a child on the right, or it has no childre (both t.left and t.right are null)
                {
                    t = t.right;
                }
            }
            return t;
        }
        
        private void printTree(BinaryNode<AnyType> t)
        {
            if(t != null)
            {
                printTree(t.left);
                System.out.println(t.element);
                printTree(t.right);
            }
        }
        
        //the public functions below use the private functions above, calling them with the root of the tree
        
        public boolean contains(AnyType x)
        {
            return contains(x,root);
        }
        
        public AnyType findMin()
        {
            if(isEmpty())
            {
                throw new java.util.NoSuchElementException();
            }
            return (findMin(root).element);
        }
        
        public AnyType findMax()
        {
            if(isEmpty())
            {
                throw new java.util.NoSuchElementException();
            }
            return (findMax(root).element);
        }
        
        public void insert(AnyType x)
        {
            root = insert(x, root);
        }
        
        public void remove(AnyType x)
        {
            root = remove(x, root);
        }
        
        public void printTree()
        {
            if(isEmpty())
            {
                System.out.println("Empty tree");
            }
            else
            {
                printTree(root);
            }
        }
        
        public void displayTree()
        {
		//call function to compute x coordinate for each node (proportional to inorder traversal number)
                //call function to compute y coordinate of each node (proportional to depth)
        	displayWindow w = new displayWindow(this);
        	w.setVisible(true);
                //above code will create and make visible the display window
        }
        
        public void addGraphics(Graphics g)
        {
        	drawNumberCircle(g,100,100,30,5);
        	drawNumberCircle(g,200,200,30,10);
        	drawLine(g,100,100,200,200,15);
		//the above is just example use of drawLine and drawNumberCircle
                //you want to traverse this tree and call drawLine and drawNumberCircle accordingly
        }
        
        private void drawNumberCircle(Graphics g, int x, int y, int dia, int val)
	{
		g.setColor(Color.ORANGE);
		g.fillOval( x, y, dia, dia );

		g.setColor(Color.RED);
		g.setFont(new Font("Verdana",Font.BOLD,15));
		g.drawString( ""+val, x + dia/2 - 12, y + dia/2 +5 );
	}
	
	private void drawLine( Graphics g, int x1, int y1, int x2, int y2, int radius )
	{
		x1 = x1 + radius;
		y1 = y1 + radius;
		x2 = x2 + radius;
		y2 = y2 + radius;
		double dist = Math.sqrt(Math.pow((x1 - x2), 2)+Math.pow((y1 - y2), 2));
		double alpha1 = radius / dist;
		double alpha2 = (dist - radius) / dist;
		int xn1 = (int)(alpha1 * x1 + (1 - alpha1) * x2);
		int yn1 = (int)(alpha1 * y1 + (1 - alpha1) * y2);
		int xn2 = (int)(alpha2 * x1 + (1 - alpha2) * x2);
		int yn2 = (int)(alpha2 * y1 + (1 - alpha2) * y2);
		
		g.drawLine(xn1, yn1, xn2, yn2);
	}
}