/*
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 splayTree;

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 SplayTree<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 SplayTree(TreePanel p) {
		this();
		treePanel = p;

	}
	public SplayTree() {
		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);
		if(found){
                        while(root.key!=k){
                            stateList.add(new ChangeState(getCurrentState(),vt,Operation.INSERT,"Splaying Node"+lastNode.key+"\n"));
                            lastNode.value.sonselect();
                            son=parent=grandParent=supergrandParent=null;
                            parent=this.getParent(k, root);
                            if(parent!=null){
                                grandParent=getParent(parent.key,root);
                                if(grandParent!=null){
                                    supergrandParent=getParent(grandParent.key,root);
                                }
                            }
                            if(parent!=null){
                                stateList.add(new ChangeState(getCurrentState(),vt,Operation.SPLAY,"Parent Node is "+parent.key+"\n"));
                                parent.value.parentselect();
                                if(grandParent!=null){
                                    stateList.add(new ChangeState(getCurrentState(),vt,Operation.SPLAY,"GrandParent Node is "+grandParent.key+"\n"));
                                    grandParent.value.grandparentselect();
                                }
                            }
                            splay(k,vt);
                            lastNode.value.unSelect();
                            if(son!=null)
                                son.value.unSelect();
                            if(parent!=null)
                                parent.value.unSelect();
                            if(grandParent!=null)
                                grandParent.value.unSelect();
                        }
		}
                else{     
                    while(lastNode!=null&&root.key.compareTo(lastNode.key)!=0){
                        stateList.add(new ChangeState(getCurrentState(),vt,Operation.INSERT,"Splaying Node"+lastNode.key+"\n"));
                        lastNode.value.sonselect();
                        son=parent=grandParent=supergrandParent=null;
                        parent=this.getParent(k, root);
                        if(parent!=null){
                            grandParent=getParent(parent.key,root);
                            if(grandParent!=null){
                                supergrandParent=getParent(grandParent.key,root);
                            }
                        }
                        if(parent!=null){
                            stateList.add(new ChangeState(getCurrentState(),vt,Operation.SPLAY,"Parent Node is "+parent.key+"\n"));
                            parent.value.parentselect();
                            if(grandParent!=null){
                                stateList.add(new ChangeState(getCurrentState(),vt,Operation.SPLAY,"GrandParent Node is "+grandParent.key+"\n"));
                                grandParent.value.grandparentselect();
                            }
                        }
                        splay(lastNode.key,vt);
                        lastNode.value.unSelect();
                        if(son!=null)
                            son.value.unSelect();
                        if(parent!=null)
                            parent.value.unSelect();
                        if(grandParent!=null)
                            grandParent.value.unSelect();
                    }
                }
		
		traversePostOrder(root, 0, 0, treePanel.getGraphics(), true, false);

		
		VirtualState fin = getCurrentState();
		fin.setNodesMoving(true);
                ChangeState changeState = new ChangeState(fin, vt, Operation.FIND, "Done.\n");
		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 branch\n");
                        node.value.unSelect();
			stateList.add(s);
			lastNode=node;
			return findHelper(node.right, k, vt);
		}
	}
	
	private Node<K,V> findHelperforSplay(Node<K, V> node, K k) {
		if (node == null) return null;
		if (k.compareTo(node.key) < 0) {
			lastNode=node;
			return findHelperforSplay(node.left, k);
		}
		else if (node.key.equals(k)){
			found=true;
			return null;
		} 
		else 
		{
			lastNode=node;
			return findHelperforSplay(node.right, k);
		}
	}

	
	/**
	 * 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);
                
		while(root.key!=k){
                    traversePostOrder(root, 0, 0, null, true, false);
                    stateList.add(new ChangeState(getCurrentState(),sc,Operation.INSERT,"Splaying Node"+lastNode.key+"\n"));                
                    lastNode.value.sonselect();                    
                    son=parent=grandParent=supergrandParent=null;
                    parent=this.getParent(k, root);
                    if(parent!=null){
                        grandParent=getParent(parent.key,root);
                        if(grandParent!=null){
                            supergrandParent=getParent(grandParent.key,root);
                        }
                    }
                    if(parent!=null){
                        stateList.add(new ChangeState(getCurrentState(),sc,Operation.SPLAY,"Parent Node is "+parent.key+"\n"));
                        parent.value.parentselect();                        
                        if(grandParent!=null){
                            stateList.add(new ChangeState(getCurrentState(),sc,Operation.SPLAY,"GrandParent Node is "+grandParent.key+"\n"));
                            grandParent.value.grandparentselect();
                        }
                    }
                    splay(k,sc);
                    lastNode.value.unSelect();
                    if(son!=null)
                        son.value.unSelect();
                    if(parent!=null)
                        parent.value.unSelect();
                    if(grandParent!=null)
                        grandParent.value.unSelect();
		}
		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.");
		lastNode=null;
	}


	/**
	 * 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);
			temp.check=true;
                        lastNode=temp;
			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++;
                        lastNode=node;
			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++;
                        lastNode=node;
			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.\n");
                    if(root!=null)
                        return root.value;
                    else
                        return null;
                }
		
		root = removeHelper(root, k, sc);

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

		while(root!=null&&lastNode!=null&&root.key.compareTo(lastNode.key)!=0){
                    stateList.add(new ChangeState(getCurrentState(),sc,Operation.INSERT,"Splaying Node"+lastNode.key+"\n"));
                    lastNode.value.sonselect();
                    son=parent=grandParent=supergrandParent=null;
                    if(lastNode!=null){
                        son=lastNode;
                        parent=getParent(lastNode.key,root);
                    }
                    else
                        break;
                    if(parent!=null){
                        grandParent=getParent(parent.key,root);
                        if(grandParent!=null){
                            supergrandParent=getParent(grandParent.key,root);
                        }
                    }
                    if(parent!=null){
                        stateList.add(new ChangeState(getCurrentState(),sc,Operation.SPLAY,"Parent Node is "+parent.key+"\n"));
                        parent.value.parentselect();
                        if(grandParent!=null){
                            stateList.add(new ChangeState(getCurrentState(),sc,Operation.SPLAY,"GrandParent Node is "+grandParent.key+"\n"));
                            grandParent.value.grandparentselect();
                        }
                    }
                    splay(lastNode.key,sc);
                    lastNode.value.unSelect();
                    if(son!=null)
                        son.value.unSelect();
                    if(parent!=null)
                        parent.value.unSelect();
                    if(grandParent!=null)
                        grandParent.value.unSelect();
		}
                
		
		traversePostOrder(root, 0, 0, null, true, false);
		
		VirtualState fin = getCurrentState();
		fin.setNodesMoving(true);
                ChangeState changeState = new ChangeState(fin, sc, Operation.REMOVE, "Done.\n");
		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
		// found it
		{
                    if(node.left==null || node.right==null){
                        node.value.select();
			ChangeState s = new ChangeState(getCurrentState(), sc, Operation.REMOVE, "Deleting node" + node.key + "\n");
			node.value.unSelect();
                        stateList.add(s);
                    }

//			System.out.println("deleting node "+node.key+" left child is "+node.left+" and right child is "+node.right);
			if (node.left == null) {
                            node=replaceRight(node.right,node,sc);
			} else if (node.right == null) {
                            node=replaceLeft(node.left,node,sc);
			} 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 to splay the node to root
	 public void splay(K key, VirtualStateCollection sc){
            System.out.println("SPlaying"+key);

            if(parent==null)
                return;
            traversePostOrder(root, 0, 0, treePanel.getGraphics(), true, false);
                        
            VirtualState oldState = getCurrentState();
            
            /*Single Rotation*/
	    	if(grandParent==null){
                    if(parent.left!=null && parent.left.key==key){
                        //System.out.println("case left single");
                        son=parent.left;                        
                        root=son;
                        if(son.right!=null){
                            stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : single rotation \n Changing sub-trees\n"));
                        }
                        else{
                            stateList.add(new ChangeState(oldState, sc, Operation.SPLAY,"Case : single rotation\n Parent node "+parent.key+" becomes Son node "+son.key+"'s right child\n"));
                        }
                        VirtualState next = oldState.copy();
                        
                        if(son.right!=null){
                            next.removeLine(-parent.hashCode());
                            next.addLine(-parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.right.hashCode())).hideGoingForward = true;
                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent node "+parent.key+" becomes Son node "+son.key+"'s right child\n"));
                        }
                        parent.left=son.right;		//changing sub-trees);

                        
                        //action 2
			next = next.copy();
                        Line rtPointer=next.addLine(son.hashCode(),next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                        //moving son to become parent
                        if(son.right==null){
                            next.addLine(-parent.hashCode(),next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                            rtPointer.hideGoingForward=true;
                        }
                        else{
                            next.removeLine(son.hashCode());
                            next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                        }
                        son.right=parent;
                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
	    		}
                    else if(parent.right!=null && parent.right.key==key){
                            //System.out.println("case right single");
                        son=parent.right;
                        root=son;
                        if(son.right!=null){
                            stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : single rotation \n Changing sub-trees\n"));
                        }
                        else{
                            stateList.add(new ChangeState(oldState, sc, Operation.SPLAY,"Case : single rotation\n Parent node "+parent.key+" becomes Son node "+son.key+"'s left child\n"));
                        }                        
                        VirtualState next = oldState.copy();
                        
                        if(son.left!=null){
                            next.removeLine(parent.hashCode());
                            next.addLine(parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.left.hashCode())).hideGoingForward = true;
                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "re-positioning Parent node "+parent.key+" and Son node "+son.key+"\n"));
                        }
                        parent.right=son.left;		//changing sub-trees

                        next=next.copy();
                        Line rtPointer=next.addLine(-son.hashCode(),next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                        if(son.left==null){
                            next.addLine(parent.hashCode(),next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                            rtPointer.hideGoingForward=true;
                        }
                        else{
                            next.removeLine(-son.hashCode());
                            next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                        }
                        son.left=parent;
                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
                        
                                                    //moving son to become parent

                    }
	    	}
	    	else{
	    		/* Double rotations case*/
	    		/*zig zag case 
	    		 * a "right zig zag" case is the one in which parent is right son of grandparent
	    		 * and son is left son of parent...something like >
	    		 * a "left zig zag" case has parent as left son of grandparent and 
	    		 * son is right son of Parent like <
	    		 * a left zig zig has all GrandparentG, Parent P, Son S on left side
	    		 * a right zig zig has all G, P , S on right side
	    		 * */
	    		if(grandParent.left!=null && grandParent.left.key==parent.key){
                            if(parent.left!=null && parent.left.key==key){
                                /*left zig zig case*/
                                //System.out.println("case left zig zig");

                                son=parent.left;
                                VirtualState next = oldState.copy();
                                if(parent.right!=null||son.right!=null){
                                    stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zig rotation\n changing sub-trees\n"));
                                }
                                else{
                                    stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zig rotation\n Parent becomes Son's right child.\n"));
                                }

                                if(parent.right!=null){
                                    next.removeLine(-grandParent.hashCode());
                                    next.addLine(-grandParent.hashCode(), next.getNode(grandParent.hashCode()), next.getNode(parent.right.hashCode()));
                                    if(son.right!=null){
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "changing sub-trees\n"));
                                    }
                                    else{
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's right child.\n"));
                                    }
                                }
                                grandParent.left=parent.right;	//changing sub-trees

                                next=next.copy();
                                if(son.right!=null){
                                    next.removeLine(-parent.hashCode());
                                    next.addLine(-parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.right.hashCode()));
                                    stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's right child.\n"));
                                }
                                parent.left=son.right;			//changing sub-trees

                                //repositioning GPS
                                next=next.copy();
                                
                                Line rtPointer=next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                if(son.right==null){
                                    next.addLine(-parent.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                                    rtPointer.hideGoingForward=true;
                                }
                                else{
                                    next.removeLine(son.hashCode());
                                    next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                }
                                son.right=parent;
                                stateList.add(new ChangeState(next, sc, Operation.SPLAY, "GrandParent becomes Parent's right child.\n"));
                                

                                next=next.copy();
                                
                                Line rtPointer1=next.addLine(parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode()));
                                if(parent.right==null){
                                    next.addLine(-grandParent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode())).hideGoingForward=true;
                                    rtPointer1.hideGoingForward=true;
                                }
                                 else{
                                    next.removeLine(parent.hashCode());
                                    next.addLine(parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode()));
                                 }
                                parent.right=grandParent;
                                stateList.add(new ChangeState(next,sc,Operation.SPLAY," rotating.\n"));
                                
                                next=next.copy();
                                
                                if(root.key==grandParent.key)
                                        root=son;
                                else{                                    
                                        if(supergrandParent.right!=null&&supergrandParent.right.key==grandParent.key){
                                                supergrandParent.right=son;                                                
                                        }
                                        else{
                                                supergrandParent.left=son;
                                        }                                        
                                }
                                stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
                            }
                            else if(parent.right!=null && parent.right.key==key){
                                    /*left zig zag case*/
//                                    System.out.println("case left zig zag");
                                    VirtualState next = oldState.copy();
                                    son=parent.right;
                                    if(son.left!=null||son.right!=null){
                                        stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zag rotation\n changing sub-trees\n"));
                                    }
                                    else{
                                        stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zag rotation\n Parent becomes Son's left child.\n"));
                                    }

                                    
                                    if(son.left!=null){
                                        next.removeLine(parent.hashCode());
                                        next.addLine(parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.left.hashCode()));
                                        if(son.right!=null){
                                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "changing sub-trees\n"));
                                        }
                                        else{
                                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's left child.\n"));
                                        }
                                    }

                                    parent.right=son.left;		//changing sub-trees

                                    next=next.copy();
                                    if(son.right!=null){
                                        next.removeLine(-grandParent.hashCode());
                                        next.addLine(-grandParent.hashCode(), next.getNode(grandParent.hashCode()), next.getNode(son.right.hashCode()));
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's left child.\n"));
                                     }
                                    grandParent.left=son.right;

                                    //repositioning GPS

                                    next=next.copy();
                                    stateList.add(new ChangeState(next, sc, Operation.SPLAY, "GrandParent becomes Son's right child.\n"));
                                    Line rtPointer=next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                    if(son.left==null){
                                        next.addLine(parent.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                                        rtPointer.hideGoingForward=true;
                                    }
                                    else{
                                        next.removeLine(-son.hashCode());
                                        next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                    }
                                    son.left=parent;
                                    
                                    

                                    next=next.copy();
                                    Line rtPointer1=next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode()));

                                    if(son.right==null){
                                        next.addLine(-grandParent.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode())).hideGoingForward=true;
                                        rtPointer1.hideGoingForward=true;

                                    }
                                    else{
                                        next.removeLine(son.hashCode());
                                        next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode()));
                                    }
                                    son.right=grandParent;

                                    stateList.add(new ChangeState(next,sc,Operation.SPLAY," rotating.\n"));
                                    next=next.copy();

                                    if(root.key==grandParent.key)
                                            root=son;
                                    else{
                                            if(supergrandParent.right!=null&&supergrandParent.right.key==grandParent.key){
                                                    supergrandParent.right=son;
                                            }
                                            else{
                                                    supergrandParent.left=son;
                                            }
                                    }
                                    stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
                            }
	    		}
	    		else if(grandParent.right!=null && grandParent.right.key==parent.key){
	    			if(parent.left!=null && parent.left.key==key){                                    
	    				/*right zig zag case*/
	    				//System.out.println("case right zig zag");
	    				son=parent.left;
                                        VirtualState next = oldState.copy();

                                        if(son.left!=null||son.right!=null){
                                        stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zag rotation\n changing sub-trees.\n"));
                                        }
                                        else{
                                            stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zag rotation\n GrandParent becomes Son's right child.\n"));
                                        }
                                        
                                        if(son.left!=null){
                                            next.removeLine(grandParent.hashCode());
                                            next.addLine(grandParent.hashCode(), next.getNode(grandParent.hashCode()), next.getNode(son.left.hashCode()));
                                            if(son.right!=null){
                                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "changing sub-trees.\n"));
                                            }
                                            else{
                                                stateList.add(new ChangeState(next, sc, Operation.SPLAY, "GrandParent becomes Son's left child.\n"));
                                            }
                                        }

	    				grandParent.right=son.left;	//changing sub-trees
                                        next=next.copy();
                                        
                                        if(son.right!=null){
                                            next.removeLine(-parent.hashCode());
                                            next.addLine(-parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.right.hashCode()));
                                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "GrandParent becomes Son's left child.\n"));
                                        }

	    				parent.left=son.right;		//changing sub-trees
	    				//repositioning GPS
	    				
                                        next=next.copy();
                                        Line rtPointer=next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode()));

                                        if(son.left==null){
                                            next.addLine(grandParent.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode())).hideGoingForward=true;
                                            rtPointer.hideGoingForward=true;
                                        }
                                        else{
                                            next.removeLine(-son.hashCode());
                                            next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(grandParent.hashCode()));
                                        }
                                        son.left=grandParent;
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's right child.\n"));

                                        
                                        next=next.copy();
                                        Line rtPointer1=next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                        if(son.right==null){
                                            next.addLine(-parent.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                                            rtPointer1.hideGoingForward=true;
                                        }
                                        else{
                                            next.removeLine(son.hashCode());
                                            next.addLine(son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                        }
                                        son.right=parent;
                                        stateList.add(new ChangeState(next,sc,Operation.SPLAY," rotating.\n"));

                                        next=next.copy();
	    				if(root.key==grandParent.key)
	    					root=son;
	    				else{
	    					if(supergrandParent.right!=null&&supergrandParent.right.key==grandParent.key){
	    						supergrandParent.right=son;
                                                        
	    					}
	    					else{
	    						supergrandParent.left=son;
	    					}
	    				}
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
	    			}
	    			else if(parent.right!=null && parent.right.key==key){
	    				/*right zig zig case*/
	    				//System.out.println("case right zig zig");
                                        VirtualState next = oldState.copy();
	    				son=parent.right;//changing sub-trees

                                        if(parent.left!=null||son.left!=null){
                                            stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zig rotation\n changing sub-trees\n"));
                                        }
                                        else{
                                            stateList.add(new ChangeState(oldState,sc,Operation.SPLAY,"Case : Zig Zig rotation\n Parent becomes Son's left child.\n"));
                                        }

                                        if(parent.left!=null){
                                            next.removeLine(grandParent.hashCode());
                                            next.addLine(grandParent.hashCode(), next.getNode(grandParent.hashCode()), next.getNode(parent.left.hashCode())).hideGoingForward = true;
                                            if(son.left!=null){
                                                stateList.add(new ChangeState(next, sc, Operation.SPLAY, "changing sub-trees\n"));
                                            }
                                            else{
                                                stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's left child.\n"));
                                            }
                                        }
	    				grandParent.right=parent.left;

                                        next=next.copy();
                                        if(son.left!=null){
                                            next.removeLine(parent.hashCode());
                                            next.addLine(parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(son.left.hashCode())).hideGoingForward = true;
                                            stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Parent becomes Son's left child.\n"));
                                        }
	    				parent.right=son.left;
	    				//repositioning GPS
                                        
                                        next=next.copy();
                                        Line rtPointer=next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                        if(son.left==null){
                                            next.addLine(parent.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode())).hideGoingForward=true;
                                           rtPointer.hideGoingForward=true;
                                        }
                                        else{
                                            next.removeLine(-son.hashCode());
                                            next.addLine(-son.hashCode(), next.getNode(son.hashCode()), next.getNode(parent.hashCode()));
                                        }
                                        son.left=parent;

	    				stateList.add(new ChangeState(next, sc, Operation.SPLAY, "GrandParent becomes Parent's left child.\n"));
                                        next=next.copy();
                                        Line rtPointer1=next.addLine(-parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode()));
                                        if(parent.left==null){
                                            next.addLine(grandParent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode())).hideGoingForward=true;
                                            rtPointer1.hideGoingForward=true;
                                        }
                                        else{
                                            next.removeLine(-parent.hashCode());
                                            next.addLine(-parent.hashCode(), next.getNode(parent.hashCode()), next.getNode(grandParent.hashCode()));
                                        }
                                        parent.left=grandParent;
                                        stateList.add(new ChangeState(next,sc,Operation.SPLAY," rotating.\n"));

                                        next=next.copy();
	    				if(root.key==grandParent.key)
	    					root=son;	
	    				else{
	    					if(supergrandParent.right!=null&&supergrandParent.right.key==grandParent.key){
	    						supergrandParent.right=son;
	    					}
	    					else{
	    						supergrandParent.left=son;
	    					}
	    				}
                                        stateList.add(new ChangeState(next, sc, Operation.SPLAY, "Splaying over\n"));
	    			}
	    		}
	    	}//end of grandparent
            traversePostOrder(root,0,0,treePanel.getGraphics(),true,false);
            
	    }
	 
	 
	 //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));
			}
		}
}