/*
This file is part of the algoviz@vt collection of algorithm
visualizations.

This program is free software: you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this distribution. If not, see
<http://www.gnu.org/licenses/>.
*/

package bst;

import java.awt.Color;
import java.awt.Graphics;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;

/**
 * A Binary Search Tree class. Although this class is heavily modified, the core
 * BST functionality remains intact. Basically, the modifications make tracing
 * each BST operations easy.
 * 
 * @author Andrew Whitaker (aawhitak@vt.edu)
 * @author Andy Street <andy@vt.edu> [Major updates for AVL]
 * @author Akash Jana (akjana35@gmail.com)
 * 
 * @param <K> The data type of the keys for the Binary Search Tree.
 * @param <V> The data type of the values in this BST.
 */
public class BST<K extends Comparable<K>, V extends GraphicalNode> implements DictionaryADT<K, V>
{
	public static enum Orientation {
		LEFT, RIGHT;
	}
	private static int count=0;
	/* The root of this tree */
	private Node<K, V> root;
	private Node<K,V> lastNode;
	/* The number of nodes in the tree */
	private int nodeCount;
	/*
	 * A list containing the States that the most recent operation has gone
	 * through.
	 */
	private ArrayList<State> stateList;
	/* The TreePanel that this BST belongs to. */
	private TreePanel treePanel;
	/* The number of levels in this tree. */
	private int levels;
	private boolean found=false;
        VirtualState initialState;
        private Node<K,V> son,parent,grandParent,supergrandParent;

	/**
	 * Creates a new BST.
	 * 
	 * @param p
	 */
	public BST(TreePanel p) {
		this();
		treePanel = p;

	}
	public BST() {
		root = null;
		nodeCount = 0;
		stateList = new ArrayList<State>();
		levels = 0;
		lastNode=null;
	}

	/**
	 * Clears the BST (not implemented)
	 */
	public void clear() {
            root=null;
		// TODO Auto-generated method stub

	}

	public Node<K,V> find(K k) {
		found=false;
		stateList.clear();
                lastNode=null;
                stateList.clear();
		
		VirtualStateCollection vt = new VirtualStateCollection();
//                vt.setDelay(treePanel.ANIMATION_TIME);
		ChangeState initial = new ChangeState(getCurrentState(), vt, Operation.FIND, "Starting find operation.\n");
		
		stateList.add(initial);
		
		Node<K,V> tmp= findHelper(root, k, vt);
				
		traversePostOrder(root, 0, 0, treePanel.getGraphics(), true, false);

		
		VirtualState fin = getCurrentState();
		fin.setNodesMoving(true);
                ChangeState changeState = new ChangeState(fin, vt, Operation.FIND, "Done.");
		lastNode=null;

		return tmp;
	}
	
	

	/**
	 * Find helper method. Works just like a normal BST find method, but tracks
	 * each "State" the BST is in using a list.
	 * 
	 * @param node
	 *            The node to recursively find from.
	 * @param k
	 *            The key to look for.
	 * @return The Vent corresponding to the key.
	 */
	private Node<K,V> findHelper(Node<K, V> node, K k, VirtualStateCollection vt) {
		if (node == null){
                    ChangeState s = new ChangeState(getCurrentState(), vt, Operation.FIND, "Node not found\n");
                    stateList.add(s);
                    return null;
                }
		if (k.compareTo(node.key) < 0) {
                    node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), vt, Operation.FIND, "Following " + node.key + "'s left branch\n");
                        node.value.unSelect();
			stateList.add(s);
			lastNode=node;
			return findHelper(node.left, k, vt);
		}
		else if (node.key.equals(k)) 
		{
                    lastNode=node;
			found=true;
                        node.value.select();
                        ChangeState s = new ChangeState(getCurrentState(), vt, Operation.FIND, "Found node successfully\n");
                        node.value.unSelect();
			stateList.add(s);
			return node;
		} 
		else 
		{
                    node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), vt, Operation.FIND, "Following " + node.key + "\'s right branchn");
                        node.value.unSelect();
			stateList.add(s);
			lastNode=node;
			return findHelper(node.right, k, vt);
		}
	}
	
	
	/**
	 * Inserts a new node in the Binary Search Tree with the specified K and
	 * Vent.
	 * 
	 * @param k
	 *            The key to put into the new node.
	 * @param e
	 *            The element to put into the new node.
	 */
	public void insert(K k, V e) {
		stateList.clear();
                lastNode=null;
		
		VirtualStateCollection sc = new VirtualStateCollection();
//                sc.setDelay(treePanel.ANIMATION_TIME);
		ChangeState initial = new ChangeState(getCurrentState(), sc, Operation.INSERT, "Starting insert operation.\n");
		
		stateList.add(initial);
		
		root = insertHelper(root, k, e, sc);
                
		levels=getLevels();
		treePanel.setLevels(levels);
		
		traversePostOrder(root, 0, 0, null, true, false);
		VirtualState fin = getCurrentState();
		fin.setNodesMoving(true);
                ChangeState changeState = new ChangeState(fin, sc, Operation.INSERT, "Done.");
	}


	/**
	 * Helper method for insertion. Works just like a regular BST insertion
	 * except "States" are kept track of.
	 * 
	 * @param node
	 *            The node to recursively insert on.
	 * @param k
	 *            The key to insert
	 * @param it
	 *            The element to insert
	 * @return The newly inserted node.
	 */
	private Node<K, V> insertHelper(Node<K, V> node, K k, V it, VirtualStateCollection sc)
	{
		if (node == null) {
			levels++;
			Node<K,V> temp= new Node<K, V>(k, it, null, null);
                        ChangeState s = new ChangeState(getCurrentState(), sc, Operation.INSERT, "New Node Inserted\n");
                        stateList.add(s);
			return temp;
		}

		if (k.compareTo(node.key) < 0) {
			node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), sc, Operation.INSERT, "Following " + node.key + "'s left branch\n");
			node.value.unSelect();
			stateList.add(s);
			levels++;
			node.left = insertHelper(node.left, k, it, sc);
			node.updateHeight();
		} else {
			node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), sc, Operation.INSERT, "Following " + node.key + "'s right branch\n");
			node.value.unSelect();
			stateList.add(s);
			levels++;
			node.right = insertHelper(node.right, k, it, sc);
			node.updateHeight();
		}
		return node;
	}
	
	/**
	 * Prints the BST to the specified writer.
	 * 
	 * @param w
	 *            The writer to write the BST to.
	 */
	public void print(Writer w) {
		printHelper(root, w);
	}

	/**
	 * @return The list of states that the BST went through to complete the last
	 *         operation.
	 */
	public ArrayList<State> getStateList() {
		return stateList;
	}

	/**
	 * Helper method for printing a BST.
	 * 
	 * @param root
	 *            The node to recursively print.
	 * @param w
	 *            The writer to print to.
	 */
	private void printHelper(Node<K, V> root, Writer w) {
		if (root == null) {
			return;
		}
		printHelper(root.left, w);
		try {
			w.write(root.value + " ");
		} catch (IOException e) {
		}
		printHelper(root.right, w);
	}

	/**
	 * Removes the node with the specified key from the tree.
	 */
	public V remove(K k) {
		lastNode=null;
		stateList.clear();
		VirtualStateCollection sc = new VirtualStateCollection();
//                sc.setDelay(treePanel.ANIMATION_TIME);
		ChangeState initial = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Starting remove operation.\n");
		
		stateList.add(initial);

                if(root.key.compareTo(k)==0){
                    if(root.left==null&&root.right==null){
                        root=null;
                    }
                    else if (root.left == null) {
                        root=root.right;
                    } else if (root.right == null) {
                        root=root.left;
                    } else {
                        Node<K, V> tmp = getMin(root.right,sc);
                        root.key=tmp.key;
                        root.right = deleteMin(root.right);
                    }
                    traversePostOrder(root, 0, 0, null, true, false);

                    VirtualState fin = getCurrentState();
                    fin.setNodesMoving(true);
                    ChangeState changeState = new ChangeState(fin, sc, Operation.REMOVE, "Done.");
                    if(root!=null)
                        return root.value;
                    else
                        return null;
                }
		
		root = removeHelper(root, k, sc);

//                if(lastNode!=null){
//                    System.out.println("lastNode is "+lastNode.value);
//                }

		               
		
		traversePostOrder(root, 0, 0, null, true, false);
		
		VirtualState fin = getCurrentState();
		fin.setNodesMoving(true);
                ChangeState changeState = new ChangeState(fin, sc, Operation.REMOVE, "Done.");
		if(root!=null)
			return root.value;
		else
			return null;

	}

	/**
	 * Helper for the remove method. State-tracking has not been implemented for
	 * remove().
	 * 
	 * @param node
	 *            The node to recursively remove on.
	 * @param k
	 *            The key to remove.
	 * @return The node that was removed.
	 */
	public Node<K, V> removeHelper(Node<K, V> node, K k, VirtualStateCollection sc) {
		if (node == null)
			return null;
		else if (k.compareTo(node.key) < 0) {
			lastNode=node;
			node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Following " + node.key + "'s left branch\n");
			node.value.unSelect();
			stateList.add(s);
			levels++;
			node.left = removeHelper(node.left, k, sc);
			node.updateHeight();
		} else if (k.compareTo(node.key) > 0) {
			lastNode=node;
			node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Following " + node.key + "'s right branch\n");
			node.value.unSelect();
			stateList.add(s);
			levels++;
			node.right = removeHelper(node.right, k, sc);
			node.updateHeight();
		} else {
                            node.value.select();
                            ChangeState s = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Deleting node" + node.key + "\nFollowing "+node.key+"'s right branch\n");
                            node.value.unSelect();
                            stateList.add(s);

                            Node<K, V> tmp = getMin(node.right,sc);
                            Node<K,V> old=node;
                            Node<K,V> oldright=node.right;
                            //node.value=tmp.value;
                            node.key=tmp.key;

                            node.right = deleteMin(node.right);


                            VirtualState next=initialState.copy();

                            if(tmp.key.compareTo(this.getParent(old.key, root).key)<0){
                                next.removeLine(-this.getParent(old.key, root).hashCode());
                                next.addLine(-this.getParent(old.key, root).hashCode(), next.getNode(this.getParent(old.key, root).hashCode()), next.getNode(tmp.hashCode()));
                                stateList.add(new ChangeState(next,sc,Operation.REMOVE,"Changing pointer to replace left child\n"));
                            }
                            else{
                                next.removeLine(this.getParent(old.key, root).hashCode());
                                next.addLine(this.getParent(old.key, root).hashCode(), next.getNode(this.getParent(old.key, root).hashCode()), next.getNode(tmp.hashCode()));
                                stateList.add(new ChangeState(next,sc,Operation.REMOVE,"Changing pointer to replace left child\n"));
                            }


                            next=next.copy();
                            next.addLine(-tmp.hashCode(), next.getNode(tmp.hashCode()), next.getNode(node.left.hashCode()));
                            if(oldright.key.compareTo(tmp.key)!=0)
                                stateList.add(new ChangeState(next,sc,Operation.REMOVE,"Changing pointer to replace right child\n"));

                            next=next.copy();
                            node.value=tmp.value;
                            if(node.right!=null)
                                next.addLine(tmp.hashCode(), next.getNode(tmp.hashCode()), next.getNode(node.right.hashCode()));
                            if(tmp.right!=null)
                                stateList.add(new ChangeState(next,sc,Operation.REMOVE,"Changing pointers to reposition In-order Successor's right child\n"));
                            else{
                                ChangeState f = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Deletion over \n");
                                stateList.add(f);
                                return node;
                            }

                            next=next.copy();
                            if(tmp.right!=null){
                                next.removeLine(tmp.hashCode());
                                next.addLine(this.getParent(tmp.key, root).hashCode(),next.getNode(this.getParent(tmp.key, root).hashCode()),next.getNode(tmp.right.hashCode()));
                            }
                            ChangeState f = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Deletion over \n");
                            stateList.add(f);
			}
		return node;
	}

        private Node<K,V> replaceRight(Node<K,V> node,Node<K,V> parent,VirtualStateCollection sc){
            Node<K,V> temp=getParent(parent.key,root);
                            if(node==null)
                                return null;
                            VirtualState oldState=getCurrentState();
                            ChangeState sa=(new ChangeState(oldState,sc,Operation.REMOVE,"Following "+node.key+"'s right branch\nFound Replacement Node\n Changing pointers\n"));
                            stateList.add(sa);
                            VirtualState next=oldState.copy();
                            if(temp.right==parent){
                                next.removeLine(parent.hashCode());
                                next.removeLine(temp.hashCode());
                                next.addLine(temp.hashCode(),next.getNode(temp.hashCode()),next.getNode(node.hashCode()));
                            }
                            else{
                                next.removeLine(parent.hashCode());
                                next.removeLine(-temp.hashCode());
                                next.addLine(-temp.hashCode(),next.getNode(temp.hashCode()),next.getNode(node.hashCode()));
                            }
                            ChangeState f = new ChangeState(next, sc, Operation.REMOVE, "Deletion over \n");
                            stateList.add(f);

                            return node;
        }

        private Node<K,V> replaceLeft(Node<K,V> node,Node<K,V> parent,VirtualStateCollection sc){
            Node<K,V> temp=getParent(parent.key,root);
                            VirtualState oldState=getCurrentState();
                            ChangeState sa=(new ChangeState(oldState,sc,Operation.REMOVE,"Following "+node.key+"'s left branch\nFound Replacement Node\n Changing pointers\n"));
                            stateList.add(sa);
                            VirtualState next=oldState.copy();
                            if(temp.right==parent){
                                next.removeLine(-parent.hashCode());
                                next.removeLine(temp.hashCode());
                                next.addLine(temp.hashCode(),next.getNode(temp.hashCode()),next.getNode(node.hashCode()));
                            }
                            else{
                                next.removeLine(-parent.hashCode());
                                next.removeLine(-temp.hashCode());
                                next.addLine(-temp.hashCode(),next.getNode(temp.hashCode()),next.getNode(node.hashCode()));
                            }
                            ChangeState f = new ChangeState(next, sc, Operation.REMOVE, "Deletion over \n");
                            stateList.add(f);

                            return node;
        }

	/**
	 * Helper method for remove, gets the minimum node in the subtree at root.
	 * 
	 * @param root
	 *            The subtree to search for the minimum node.
	 * @return The minimum node in the subtree.
	 */
	private Node<K, V> getMin(Node<K, V> node,VirtualStateCollection sc) {
                
		if (node.left == null) {
                    initialState=getCurrentState();
                    node.value.select();
                    stateList.add(new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Found in-order successor node "+node.key+"\n"));
                    node.value.unSelect();
			return node;
		} else {
                    node.value.select();
                ChangeState f = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Following "+node.key+"'s left branch\n");
                node.value.unSelect();
                stateList.add(f);
			return getMin(node.left,sc);
		}
	}

	/**
	 * Helper for the remove method.
	 * 
	 * @param node
	 *            The subtree to remove the minimum from.
	 * @return The node that was removed.
	 */
	
	private Node<K, V> deleteMin(Node<K, V> node) {
		if (node.left == null){
                    return node.right;
                }
		else {
			node.left = deleteMin(node.left);
			return node;
		}
	}

	/**
	 * Returns the size of this tree.
	 */
	public int size() {
		// TODO Auto-generated method stub
		return nodeCount;
	}

	/**
	 * Draws the tree in a post-order traversal. Draws each node at the proper
	 * place, using the BST's TreePanel.
	 * 
	 * @param g	The graphics to draw on.
	 * @param recalc	If the tree should be recalculated.
	 * @param draw		If the tree should be redrawn
	 */
	public void drawPostOrder(Graphics g, boolean recalc, boolean draw) {
		traversePostOrder(root, 0, 0, g, recalc, draw);
	}

	/**
	 * Recursive helper for drawing the tree.
	 * @param node	The node to draw/traverse
	 * @param x		The "abstract x" of the current node.
	 * @param y		The "abstract y" of the current node.
	 * @param g		The graphics to draw on.
	 * @param recalcPos		If the tree should be recalculated
	 * @param draw			If the tree should be drawn.
	 */
	public void traversePostOrder(Node<K, V> node, int x, int y,
			Graphics g, boolean recalcPos, boolean draw) {

		if (node == null) {
			return;
		}
		traversePostOrder(node.left, x * 2, y + 1, g, recalcPos, draw);
		traversePostOrder(node.right, x * 2 + 1, y + 1, g, recalcPos, draw);
		visit(node, x, y, g, recalcPos, draw);

		if (node.left != null && !(node.left.value).isHidden() && draw) {
			g.setColor(Color.BLACK);
			GraphicalNode n = node.left.value;
			GraphicalNode parent = node.value;
                        g.drawLine(parent.getX() + (GraphicalNode.NODE_WIDTH / 2), parent.getY() + GraphicalNode.NODE_HEIGHT, n.getX() + (GraphicalNode.NODE_WIDTH / 2), n.getY());//, g);
		}
		if (node.right != null && !(node.right.value).isHidden() && draw) {
			g.setColor(Color.BLACK);
			GraphicalNode n = node.right.value;
			GraphicalNode parent = node.value;
                        g.drawLine(parent.getX() + (GraphicalNode.NODE_WIDTH / 2), parent.getY() + GraphicalNode.NODE_HEIGHT, n.getX() + (GraphicalNode.NODE_WIDTH / 2), n.getY());//, g);
		}
		

		
	}

	/**
	 * Visit the specified node.
	 * @param node	The node to visit.
	 * @param x		The x position of the node.
	 * @param y		The y position of the node.
	 * @param g		The graphics to draw on
	 * @param recalcPos	Recalculate the tree?
	 * @param draw		Redraw the tree?
	 */
	private void visit(Node<K, V> node, int x, int y, Graphics g,
			boolean recalcPos, boolean draw) {
//		System.out.println("visiting node "+node.key);
		GraphicalNode curr = node.value;
		if (recalcPos) {
			curr.setXPos(treePanel.getPhysicalX(x, y));
			curr.setYPos(y * TreePanel.NODE_VERTICAL_DISTANCE);
//                        System.out.println(curr.getX()+"        "+curr.getY());
			curr.setAbstractX(x);
			curr.setAbstractY(y);
		}

		if (draw) {
			curr.draw(g);
		}
	}

	/**
	 * Gets the VirtualState of the whole tree.
	 */
	private VirtualState getCurrentState()
	{
		return getCurrentState(root);
	}
	
	/**
	 * Returns the VirtualState of the tree with root r
	 * 
	 * @param r the root
	 * @return the current VirtualState of that tree
	 */
	private VirtualState getCurrentState(Node<K, V> r)
	{
		VirtualState ret = new VirtualState();
		
		_saveState(ret, r);
		
		return ret;
	}
	
	private void _saveState(VirtualState s, Node<K, V> n)
	{
		if(n == null) return;
		
		s.addNode(n);

		Node<K, V> left = n.left;
		Node<K, V> right = n.right;

		Location myLoc = n.value.getLocation();
		
		if(left != null)// && !left.value.isHidden())
		{
			Location lLoc = left.value.getLocation();

			Line l = new Line(myLoc, lLoc);
			l.id = -n.value.hashCode();

			s.addLine(l);
		}
		
		if(right != null)// && !right.value.isHidden())
		{
			Location rLoc = right.value.getLocation();

			Line l = new Line(myLoc, rLoc);
			l.id = n.value.hashCode();

			s.addLine(l);
		}
		
		_saveState(s, left);
		_saveState(s, right);
	}
	
	 //Method getParent returns the parent node for input node key
		public Node<K,V> getParent(K key,Node<K,V> root){
			if(root!=null&&key==root.key){
				return null;
			}
			else if(key.compareTo(root.key)<0){
				if(root.left!=null&&root.left.key==key)
					return root;
				else return getParent(key,root.left);
			}			
			else{
				if(root.right!=null&&root.right.key==key)
					return root;
				else
					return getParent(key,root.right);		
			}
		}
		
		public void traversePreOrder(Node<K,V> node){
			if(node==null|| count>100){
				return;
			}
			visit1(node);
			traversePreOrder(node.left);
			traversePreOrder(node.right);
		}
		
		public void visit1(Node<K,V> node){
			count++;
			System.out.println(node.key+" pre"+ node.left +" and "+node.right+" count is "+count);
		}
		
		public int getLevels(){
			int levelCount=0;
			if(root==null)
				return levelCount;
			else{
				levelCount++;
				return getLevels2(levelCount,root);
			}
		}
		
		public int getLevels2(int levelCount, Node<K,V> node){
			if(node==null||node.isLeaf())
				return levelCount;
			else{
				levelCount++;
				return Math.max(getLevels2(levelCount,node.left), getLevels2(levelCount,node.right));
			}
		}
}