package edu.princeton.cs.algs4.growingtree.framework;
/*
 * @(#)MovingBSTTree.java
 *
 * Last Modified: 9/15/01
 */

 import java.util.*;
 import java.awt.*;
import java.awt.geom.*;


/** *
 	* The class provides the base structure for a <code>BSTTree</code> that can move to a new position
 	* in the Binary Search Tree. For that reason, it extends the BSTTree class.
    *
	* <p><hr>The MovingBSTTree defines methods necessary to move a BSTTree from one location
	* in a Binary Search Tree to another. Because the methods are moving, they require animation.
	* Consequently, the extension <b>must</b> be from an AnimatingBSTTree. The constructor ensures
	* this construction, however, changes cannot be made. To protect the changes from occuring,
	* the methods have been overiden to have no affect.
	*
	* @author  Corey Sanders
	* @version 2.2 9/15/01
 	*/

public class MovingBSTTree<P extends NodeProperties> extends GrowingTreeNode<P>  {
	/**
	 * Starting Transform for the movement of the node.
	 */
	private AffineTransform startTransform;

	/**
	 * Ending Transform for the movement of the node.
	 */
	private AffineTransform endTransform;

	/**
	 * Starting level for the movement.
	 */
	private int startLevel;

	/**
	 * Ending level for the movement.
	 */
	private int endLevel;

	/**
	 * Section height for movement of the node.
	 */
	private double movingSectionHeight;

	/**
	 * Defines a null movement.
	 */
	public final static int NULL_MOVEMENT = 0;

	/**
	 * Defines moving down and to the right.
	 */
	public final static int DOWN_RIGHT = 11;

	/**
	 * Defines moving down and to the left.
	 */
	public final static int DOWN_LEFT = 12;

	/**
	 * Defines moving up and to the right.
	 */
	public final static int UP_RIGHT = 13;

	/**
	 * Defines moving up and to the left.
	 */
	public final static int UP_LEFT = 14;

	/**
	 * Defines following the parent, as its right child.
	 */
	public final static int FOLLOW_PARENT_RIGHT = 21;

	/**
	 * Defines following the parent as its left child.
	 */
	public final static int FOLLOW_PARENT_LEFT = 22;

	/**
	 * Defines following the node passed as a follower.
	 */
	public final static int FOLLOW_NODE = 23;

	/**
	 * Node that the moving node can follow or imitates.
	 */
	protected GrowingTreeNode<P> node = null;

	/**
	 * Move position for the current node.
	 */
	protected int movePosition= NULL_MOVEMENT;

	/**
	 * Boolean flag whether the current <code>MovingBSTTree</code> has been initiliazed.
	 */
	private boolean initialize;

	/**
	 * Parent of the current node.
	 */
	protected MovingBSTTree<P> movingParent = null;

	/**
	 * Constructor without a parent passed, indicating that <code>FOLLOW_PARENT_LEFT</code> and <code>FOLLOW_PARENT_RIGHT</code>
	 * are not accesible unless a parent is set. The MovingBSTTree constructs as an empty <code>ANIMATING_BST_TREE_TYPEM</code>
	 *, setting the value and key as the value and key of the given node. The MovingBSTTree imitates
	 * the <code>BSTTree</code> node given but does not affect the node.
	 *
	 * @param node BSTTree node that the MovingBSTTree imitates.
	 */
	public MovingBSTTree(GrowingTreeNode<P> node) {
		this(node, null);
	}

	/**
	 * Constructor with a parent passed. The MovingBSTTree constructs as an empty <code>ANIMATING_BST_TREE_TYPEM</code>
	 *, setting the value and key as the value and key of the given node. The MovingBSTTree imitates
	 * the <code>BSTTree</code> node given but does not affect the node.
	 *
	 * @param node BSTTree node that the MovingBSTTree imitates.
	 * @param movingParent MovingBSTTree that is the parent of the current node, allowing the follow parent move positions.
	 */
	public MovingBSTTree(GrowingTreeNode<P> node, MovingBSTTree<P> movingParent) {
		super(ANIMATING_BST_TREE_TYPE, (P) node.getNodeProperties().clone(), node.getHead().getLogger());
			
 		// Sets the node
		setNode(node);
		setHead((GrowingTreeHead<P>)node.getHead());

		setStartTransform(node.getCurrentTransform());
		setStartLevel(node.getLevel());
		setMovingSectionHeight(((GrowingTreeHead<P>)node.getHead()).getSectionHeight());
		setEndTransform(getStartTransform());
		setEndLevel(getStartLevel());
		setMovingParent(movingParent);
		
		// Settings cloned so changes do no affect the node
		setNodeSettings((NodeSettings)node.getSettings().clone());
		getSettings().setNodeFillPaint(node.getNodeProperties().getNodeColor());
		((DrawableKey)getValue()).setKeySettings((KeySettings)((DrawableKey)node.getValue()).getSettings().clone());

	}

	/**********************/
	/* Accessor Methods   */
	/**********************/

	/**
	 * Gets the node that the <code>MovingBSTTree</code> is imitating.
	 *
	 * @return BSTTree node that the <code>MovingBSTTree</code> is imitating.
	 */
	public GrowingTreeNode<P> getNode() {
		return node;
	}


	/**
	 * Gets the moving parent of the <code>MovingBSTTree</code>.
	 *
	 * @return <code>MovingBSTTree</code> parent .
	 */
	public MovingBSTTree<P> getMovingParent() {
		return movingParent;
	}

	/**
	 * Gets the section height for the drawing of the node.
	 *
	 * @return double section height used for the moving node.
	 */
	public double getMovingSectionHeight() {
		return movingSectionHeight;
	}


	/**
	 * Gets the starting transform for the moving of the node.
	 *
	 * @return transform start for the <code>MovingBSTTree</code>.
	 */
	public AffineTransform getStartTransform() {
		return startTransform;
	}

	/**
	 * Gets the ending transform for the moving of the node.
	 *
	 * @return ending transform for the <code>MovingBSTTree</code>.
	 */
	public AffineTransform getEndTransform() {
		return endTransform;
	}

	/**
	 * Gets the starting level for the moving of the node.
	 *
	 * @return starting level for the <code>MovingBSTTree</code>.
	 */
	public int getStartLevel() {
		return startLevel;
	}

	/**
	 * Gets the ending level for the moving of the node.
	 *
	 * @return ending transform for the <code>MovingBSTTree</code>.
	 */
	public int getEndLevel() {
		return endLevel;
	}

	/**
	 * Gets the move position for the moving node.
	 *
	 * @return integer representing a predefined move position.
	 */
	public int getMovePosition() {
		return movePosition;
	}

	/**********************/
	/* Mutator Methods    */
	/**********************/

	/**
	 * Sets the node that the <code>MovingBSTTree</code> imitates. The key and value are set according
	 * to the given node.
	 *
	 * @param node BSTTree node that the MovingBSTTree imitates.
	 */
	public void setNode(GrowingTreeNode<P> node) {
		assert (node != null);
		this.node = node;
        this.setNode(node.getKey(), (DrawableKey)((DrawableKey)node.getValue()).clone());
	}

	/**
	 * Sets the moving parent of the <code>MovingBSTTree</code>. After the parent is set,
	 * the movements <code>FOLLOW_PARENT_RIGHT</code> and <code>FOLLOW_PARENT_LEFT</code>
	 * are allowed.
	 *
	 * @param movingParent <code>MovingBSTTree</code> parent for the node.
	 */
	public void setMovingParent(MovingBSTTree<P> movingParent) {
		this.movingParent = movingParent;
	}

	/**
	 * Sets the section height for the drawing of the node. The section is very necessary
	 * in drawing a moving node, because the distance the node travels up or down is determined
	 * by the section height.
	 *
	 * @param height the section height used for the moving node.
	 */
	public void setMovingSectionHeight(double height) {
		movingSectionHeight = height;
	}



	/**
	 * Sets the starting transform for the moving of the node.
	 *
	 * @param startTransform starting transform for the <code>MovingBSTTree</code>.
	 */
	public void setStartTransform(AffineTransform startTransform) {
		this.startTransform = startTransform;
	}

	/**
	 * Sets the ending transform for the moving of the node. This makes the moving node
	 * not initialize to the move position and instead use the end transform set here.
	 * To set the move position for initialization, use <code>setMovePosition</code>.
	 *
	 * @param endTransform ending transform for the <code>MovingBSTTree</code>.
	 */
	public void setEndTransform(AffineTransform endTransform) {
		this.endTransform = endTransform;
	}

	/**
	 * Sets the starting level for the moving of the node.
	 *
	 * @param startLevel starting level for the <code>MovingBSTTree</code>.
	 */
	public void setStartLevel(int startLevel) {
		this.startLevel = startLevel;
	}

	/**
	 * Sets the ending level for the moving of the node. This makes the moving node
	 * not initialize to the move position and instead use the end level set here.
	 * To set the move position for initialization, use <code>setMovePosition</code>.
	 *
	 * @param endLevel ending transform for the <code>MovingBSTTree</code>.
	 */
	public void setEndLevel(int endLevel) {
		this.endLevel = endLevel;
	}

	/**
	 * Sets the move position for the moving node. Setting this forces initialization of
	 * the node when <code>drawNodeAndLink</code> is called.
	 *
	 * @param m integer representing a predefined move position.
	 */
	public void setMovePosition(int m) {
		movePosition = m;
		if (m == NULL_MOVEMENT)
			initialize = false;
		else
			initialize = true;
	}


	/****************************/
	/* Overiding methods        */
	/****************************/

  	/**
  	 * Sets the tree type for the BSTTree. Overiden to disallow changes in AnimatingBSTTre.
  	 *
  	 * @param treeType setting for the tree (no affect).
  	 */
  	 public void setTreeType(int treeType) {
		  super.setTreeType(ANIMATING_BST_TREE_TYPE);
  	 }

	/**
	 * Sets the node of the tree in the given Graphics2D, by setting the AffineTransform.
	 * If the move position needs to be initialized, it is built within this method.
	 * <p> <code>FOLLOW_PARENT_RIGHT</code>, <code>FOLLOW_PARENT_LEFT</code>, and <code>FOLLOW_NODE</code>
	 * do not initialize but must be reconfigured every call to the method. The other movements
	 * are not changed after the first initlization.
	 *
	 * @param g2 graphics to which the node is drawn.
	 * @param step double value [0,1] which indicates the progress of the drawing.
	 */
	public void makeNode(Graphics2D g2, double step) {

		// 0 <= step <= 1
		if (step > 1)
			step = 1;
		if (step < 0)
			step = 0;


		// Set screen bounds
		setScreenBounds(g2.getClipBounds());

		// Initialize if necessary
		if(initialize) {
			initMovingBSTTree();
		}

		// Three movements reconfiguring every call.

		if (movePosition == FOLLOW_PARENT_RIGHT) {
			setFollowRightMovingTransform(g2);
			return;
		}

		if (movePosition == FOLLOW_PARENT_LEFT) {
			setFollowLeftMovingTransform(g2);
			return;
		}

		if (movePosition == FOLLOW_NODE) {
			setFollowNodeMovingTransform(g2, step);
			return;
		}

		// Set the drawingLevel, currentPower2, and currentTransform.
		setDrawingLevel((getStartLevel() * (1.0- step)) + (getEndLevel() * (step)));

		setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));

		setCurrentTransform(AffineTransformList.getTransformStep(getStartTransform(), getEndTransform(), step));

	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D.
	 * If the move position needs to be initialized, it is built within this method.
	 * <p> <code>FOLLOW_PARENT_RIGHT</code>, <code>FOLLOW_PARENT_LEFT</code>, and <code>FOLLOW_NODE</code>
	 * do not initialize but must be reconfigured every call to the method. The other movements
	 * are not changed after the first initlization.
	 *
	 * @param g2 graphics to which the node is drawn.
	 * @param step double value [0,1] which indicates the progress of the drawing.
	 */
	public void drawNodeAndLink(Graphics2D g2, double step) {
		
        // 0 <= step <= 1
		if (step > 1)
			step = 1;
		if (step < 0)
			step = 0;


		// Set screen bounds
		setScreenBounds(g2.getClipBounds());

		// Initialize if necessary
		if(initialize) {
			initMovingBSTTree();
		}

		// Three movements reconfiguring every call.

		if (movePosition == FOLLOW_PARENT_RIGHT) {
			drawFollowRight(g2);
			return;
		}

		if (movePosition == FOLLOW_PARENT_LEFT) {
			drawFollowLeft(g2);
			return;
		}

		if (movePosition == FOLLOW_NODE) {
			drawFollowNode(g2, step);
			return;
		}

		// Set the drawingLevel, currentPower2, and currentTransform.
		setDrawingLevel((getStartLevel() * (1.0- step)) + (getEndLevel() * (step)));

		setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));

		setCurrentTransform(AffineTransformList.getTransformStep(getStartTransform(), getEndTransform(), step));

		// Super call with the defined values.
		drawNodeAndLink(g2, getMovingSectionHeight(), getCurrentTransform(), (getDrawingLevel()), getCurrentPower2());
	}

	/**
	 * Initiliazes the node with the move position passed.
	 *
	 * @param movePostition the move position set for the node and initialized to.
	 */
	public void initMovingBSTTree(int movePosition) {
		setMovePosition(movePosition);
		initMovingBSTTree();
	}

	/**
	 * Initiliazes the node with the move position defined within the node. The only move positions
	 * that need initialization are
	 * <ul>
	 * <li><code>DOWN_RIGHT</code></li>
	 * <li><code>DOWN_LEFT</code></li>
	 * <li><code>UP_RIGHT</code></li>
	 * <li><code>UP_LEFT</code></li>
	 * </ul>
	 */
	public void initMovingBSTTree() {

		if (getScreenBounds() == null || getStartTransform() == null)
				return;

		if (movePosition == DOWN_RIGHT) {

			setEndLevel(getStartLevel() + 1);

			AffineTransform transform = (AffineTransform)getStartTransform().clone();

			transform.translate(  ( ( (getScreenBounds().getWidth())/Math.pow(2.0, (getStartLevel() + 1)) )/getStartTransform().getScaleX()), (getMovingSectionHeight()/getStartTransform().getScaleY()) );

			setEndTransform(transform);
		}
		if (movePosition == DOWN_LEFT) {
			setEndLevel(getStartLevel() + 1);

			AffineTransform transform = (AffineTransform)getStartTransform().clone();

			transform.translate(  -( ((getScreenBounds().getWidth())/Math.pow(2.0, (getStartLevel() + 1)) )/getStartTransform().getScaleX()), (getMovingSectionHeight()/getStartTransform().getScaleY()) );

			setEndTransform(transform);

		}
		if (movePosition == UP_RIGHT) {
			setEndLevel(getStartLevel() - 1);

			AffineTransform transform = (AffineTransform)getStartTransform().clone();

			transform.translate(  ( ( (getScreenBounds().getWidth())/Math.pow(2.0, (getStartLevel())) )/getStartTransform().getScaleX()), -(getMovingSectionHeight()/getStartTransform().getScaleY()) );

			setEndTransform(transform);

		}
		if (movePosition == UP_LEFT) {
			setEndLevel(getStartLevel() - 1);

			AffineTransform transform = (AffineTransform)getStartTransform().clone();

			transform.translate(  -( ( (getScreenBounds().getWidth())/Math.pow(2.0, (getStartLevel())) )/getStartTransform().getScaleX()), -(getMovingSectionHeight()/getStartTransform().getScaleY()) );

			setEndTransform(transform);

		}


		// Turn of initialization
		initialize = false;

	}



	/**
	 * Draws the moving node in the given Graphics2D to follow its parent as if it were the right child.
	 * If the parent is not defined, the node is draw at its starting transform and level.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 */
	public void drawFollowRight(Graphics2D g2) {

		// NULL parent
		if (movingParent == null) {
			setDrawingLevel(getStartLevel());
			setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));
			setCurrentTransform(getStartTransform());

			// Super call with the defined values.
			drawNodeAndLink(g2, getMovingSectionHeight(), getCurrentTransform(), getDrawingLevel(), getCurrentPower2());
			return;
		}
		else {

			// Set values according to parent
			AffineTransform transform = (AffineTransform)movingParent.getCurrentTransform().clone();

			setDrawingLevel(movingParent.getDrawingLevel() + 1);

			setCurrentPower2(movingParent.getCurrentPower2() * 2.0);

			setMovingSectionHeight(movingParent.getMovingSectionHeight());

			transform.translate(  ( ((getScreenBounds().getWidth())/movingParent.getCurrentPower2())/movingParent.getCurrentTransform().getScaleX()), (getMovingSectionHeight()/movingParent.getCurrentTransform().getScaleY()) );

			setCurrentTransform(transform);
		}

		// Super call
		drawNodeAndLink(g2, getMovingSectionHeight(), getCurrentTransform(), getDrawingLevel(), getCurrentPower2()  );

		setEndLevel((int)Math.ceil(getDrawingLevel()));
		setEndTransform(getCurrentTransform());
	}

	/**
	 * Draws the moving node in the given Graphics2D to follow its parent as if it were the left child.
	 * If the parent is not defined, the node is draw at its starting transform and level.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 */
	public void drawFollowLeft(Graphics2D g2) {

		if (movingParent == null) {
			setDrawingLevel(getStartLevel());
			setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));
			setCurrentTransform(getStartTransform());

		}

		else {
			AffineTransform transform = (AffineTransform)movingParent.getCurrentTransform().clone();

			setDrawingLevel(movingParent.getDrawingLevel() + 1);

			setCurrentPower2(movingParent.getCurrentPower2() * 2.0);

			setMovingSectionHeight(movingParent.getMovingSectionHeight());

			transform.translate(  ( -((getScreenBounds().getWidth())/movingParent.getCurrentPower2())/movingParent.getCurrentTransform().getScaleX()), (getMovingSectionHeight()/movingParent.getCurrentTransform().getScaleY()) );

			setCurrentTransform(transform);
		}

		// Super call
		drawNodeAndLink(g2, getMovingSectionHeight(), getCurrentTransform(), getDrawingLevel(), getCurrentPower2()  );

		setEndLevel((int)Math.ceil(getDrawingLevel()));
		setEndTransform(getCurrentTransform());


	}

	/**
	 * Draws the moving node in the given Graphics2D to follow the location of the imitating node.
	 * The step is necessary to determine the progress of the animation. The <code>FOLLOW_NODE</code>
	 * movement simply starts at the start transform and ends at the current transform of the imitating node.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 * @param step double value [0,1] which indicates the progress of the drawing.
	 */
	public void drawFollowNode(Graphics2D g2, double step) {

		double sectionHeight = (1.0-step) * getMovingSectionHeight() + (step) * node.getSectionHeight();

		setEndLevel(node.getLevel());

		setEndTransform(node.getCurrentTransform());

		setDrawingLevel((getStartLevel() * (1.0- step)) + (getEndLevel() * (step)));

		setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));


		setCurrentTransform(AffineTransformList.getTransformStep(getStartTransform(), getEndTransform(), step));

		drawNodeAndLink(g2, sectionHeight, getCurrentTransform(), (getDrawingLevel()), getCurrentPower2());


	}

	/**
	 * Draws the moving node in the given Graphics2D to follow the location of the imitating node.
	 * The step is necessary to determine the progress of the animation. The <code>FOLLOW_NODE</code>
	 * movement simply starts at the start transform and ends at the current transform of the imitating node.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 * @param step double value [0,1] which indicates the progress of the drawing.
	 * @param bottomLinks boolean whether the bottom links should be drawn.
	 */
	public void drawFollowNode(Graphics2D g2, double step, boolean bottomLinks) {

		double sectionHeight = (1.0-step) * getMovingSectionHeight() + (step) * node.getSectionHeight();

		setEndLevel(node.getLevel());

		setEndTransform(node.getCurrentTransform());

		setDrawingLevel((getStartLevel() * (1.0- step)) + (getEndLevel() * (step)));

		setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));


		setCurrentTransform(AffineTransformList.getTransformStep(getStartTransform(), getEndTransform(), step));

		drawNodeAndLink(g2, sectionHeight, getCurrentTransform(), (getDrawingLevel()), getCurrentPower2(), bottomLinks);


	}


	/**
	 * Sets the current transform for a given following node.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 * @param step double value [0,1] which indicates the progress of the drawing.
	 */
	public void setFollowNodeMovingTransform(Graphics2D g2, double step) {

		double sectionHeight = (1.0-step) * getMovingSectionHeight() + (step) * node.getSectionHeight();

		setEndLevel(node.getLevel());

		setEndTransform(node.getCurrentTransform());

		setDrawingLevel((getStartLevel() * (1.0- step)) + (getEndLevel() * (step)));

		setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));

		setCurrentTransform(AffineTransformList.getTransformStep(getStartTransform(), getEndTransform(), step));

	}


	/**
	 * Sets the current transform for a given following node.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 */
	public void setFollowRightMovingTransform(Graphics2D g2) {

		// NULL parent
		if (movingParent == null) {
			setDrawingLevel(getStartLevel());
			setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));
			setCurrentTransform(getStartTransform());

			// Super call with the defined values.
			return;
		}
		else {

			// Set values according to parent
			AffineTransform transform = (AffineTransform)movingParent.getCurrentTransform().clone();

			setDrawingLevel(movingParent.getDrawingLevel() + 1);

			setCurrentPower2(movingParent.getCurrentPower2() * 2.0);

			setMovingSectionHeight(movingParent.getMovingSectionHeight());

			transform.translate(  ( ((getScreenBounds().getWidth())/movingParent.getCurrentPower2())/movingParent.getCurrentTransform().getScaleX()), (getMovingSectionHeight()/movingParent.getCurrentTransform().getScaleY()) );

			setCurrentTransform(transform);
		}

	}

	/**
	 * Sets the current transform for a given following node.
	 *
	 * @param g2 Graphics2D to which to node is drawn.
	 */
	public void setFollowLeftMovingTransform(Graphics2D g2) {

		if (movingParent == null) {
			setDrawingLevel(getStartLevel());
			setCurrentPower2(Math.pow(2.0, (getDrawingLevel() + 1) ));
			setCurrentTransform(getStartTransform());
		}

		else {
			AffineTransform transform = (AffineTransform)movingParent.getCurrentTransform().clone();

			setDrawingLevel(movingParent.getDrawingLevel() + 1);

			setCurrentPower2(movingParent.getCurrentPower2() * 2.0);

			setMovingSectionHeight(movingParent.getMovingSectionHeight());

			transform.translate(  ( -((getScreenBounds().getWidth())/movingParent.getCurrentPower2())/movingParent.getCurrentTransform().getScaleX()), (getMovingSectionHeight()/movingParent.getCurrentTransform().getScaleY()) );

			setCurrentTransform(transform);
		}

	}

}