package edu.princeton.cs.algs4.growingtree.framework; /* * @(#)RotationDoubleBSTAnimation.java * * Last Modified: 9/15/01 */ import java.util.*; import java.awt.*; import java.awt.geom.*; /** * * The Animation object that defines a double rotation of a node in a BSTTree. The animation builds two RotationBSTAnimations * as it goes, keeping only one currently animating and allowing rewinding only to the previous * rotation.
* * The Object implements the Animation interface, and should consequently be used only in that * context. The object restores all values changed in the given nodes, however, if the object * is never allowed to finish, the restoring of values becomes impossible. On any exception occuring * elsewhere, the object may not restore the conditions correctly.
* * @author Corey Sanders * @version 1.2 9/15/01 */ public class RotationDoubleBSTAnimation
extends AbstractAnimation implements AnimationListener { /** * Constant that defines the starting location. */ private final int FIRST_ROTATE = 0; /** * Constant that defines the fading of the erasing node. */ private final int SECOND_ROTATE = 1; /** * Private int used to hold the current and previous location steps. */ private int currentLocation = FIRST_ROTATE; /** * Refers to the first Rotation being drawn. */ RotationBSTAnimation
firstRotation; /** * Refers to the second Rotation being drawn. */ RotationBSTAnimation
secondRotation; /** * Holds the node that is replacing. */ private GrowingTreeNode
node; /** * Private doubles used to hold the rotation location. */ private double rotationLocation = 0.0; /** * The constructor which initiates the status and prepares the color schemes. The node * which is being deleted must be passed. * * @param node the BSTTree from which the partition takes place. * @param startingCmd the Animation command that this should start. * @param stepTime the time for each step of the Animation. Sets the initial value. */ public RotationDoubleBSTAnimation(GrowingTreeNode
node, String startingCmd, int stepTime) { super(); // Sets node setNode(node); // Sets starting command and time setStartingCommand(startingCmd); setStepTime(stepTime); } /** * The constructor which initiates the status and sets the color schemes to null. No colors * will be change using this animation. The node * which is animating must be passed. * * @param node the BSTTree which is deleted during the deletion. */ public RotationDoubleBSTAnimation(GrowingTreeNode
node) { this(node, Animation.PLAY, DEFAULT_STEP); } /************************/ /* Accessor methods */ /************************/ /** * Gets the node from which the partitioning takes place. * * @return BSTTree of the node currently being partitioned at the KeySelect. */ public GrowingTreeNode
getNode() { return node; } /************************/ /* Mutator methods */ /************************/ /** * Sets the node from which the partitioning takes place. * * @param node BSTTree of the node currently being partitioned at the KeySelect. */ public void setNode(GrowingTreeNode
node) { this.node = node; } /*********************/ /* Animation methods */ /*********************/ /** * Draws the animation of the next step, using the status of the animation (Animation.PLAY, Animation.PAUSE and so forth). * After completing the drawing, the Animation sends an AnimationEvent to all its listeners, indicating * any information that the listerners may wish to use. * * Other Animation Objects used: *
parentTree = (GrowingTreeNode
)getNode().getParentTree(); // GrandParent GrowingTreeNode
grandParentTree = (GrowingTreeNode
)parentTree.getParentTree(); // Top of tree, only single rotation possible if (grandParentTree == getNode().getHead()) { messageAction("Top of Tree : No Double Rotation"); secondRotation = (RotationBSTAnimation
)((GrowingTreeHead
)getNode().getHead()).makeRotationAnimation(getNode()); secondRotation.addAnimationListener(this); currentLocation = SECOND_ROTATE; secondRotation.drawAnimation(g2, getStatus()); } else { // Opposite direction, resulting in normal rotations (left-right and right-left) if ( ((grandParentTree.getLeftNodeInternal() == parentTree) && (parentTree.getRightNodeInternal() == node)) || ((grandParentTree.getRightNodeInternal() == parentTree) && (parentTree.getLeftNodeInternal() == node)) ) { messageAction("Opposite Direction - Rotate Node Up Twice"); messageAction("*-----Start Rotation at"+node.getKey().toString()+"-----*"); // Rotate node up twice firstRotation = (RotationBSTAnimation
)((GrowingTreeHead
)getNode().getHead()).makeRotationAnimation(getNode()); } else { // Same direction, Splay rotation messageAction("Same Direction - Splay Rotate Parent First"); messageAction("*-----Start Rotation at"+parentTree.getKey().toString()+"-----*"); firstRotation = (RotationBSTAnimation
)((GrowingTreeHead
)parentTree.getHead()).makeRotationAnimation(parentTree); } currentLocation = FIRST_ROTATE; firstRotation.addAnimationListener(this); firstRotation.drawAnimation(g2, getStatus()); } // REDRAW messageAction(Animation.REDRAW); return; } // Currently on a step and no changes have occured. Return to startingStatus if (getStatus().equals(Animation.STEP)) { setStatus(getStartingCommand()); } // PLAY status if (getStatus().equals(Animation.PLAY)) { messageAction(Animation.PLAY); if (currentLocation == FIRST_ROTATE) { // Set values for animation firstRotation.setStepTime(getStepTime()); firstRotation.setStep(getStep()); // Set play status firstRotation.setStatus(Animation.PLAY); // Draw rotation animation firstRotation.drawAnimation(g2, Animation.PLAY); // Set up second rotation if (firstRotation.getStatus().equals(Animation.FINISH)) { messageAction("Second Rotation with "+getNode().getKey().toString()); secondRotation = (RotationBSTAnimation
)((GrowingTreeHead
)getNode().getHead()).makeRotationAnimation(getNode());
messageAction(Animation.REDRAW);
secondRotation.addAnimationListener(this);
currentLocation = SECOND_ROTATE;
secondRotation.drawAnimation(g2, getStatus());
setStatus(Animation.STEP);
}
}
else if (currentLocation == SECOND_ROTATE) {
// Set values for animation
secondRotation.setStepTime(getStepTime());
secondRotation.setStep(getStep());
// Set play status
secondRotation.setStatus(Animation.PLAY);
// Draw rotation animation
secondRotation.drawAnimation(g2, Animation.PLAY);
if (secondRotation.getStatus().equals(Animation.FINISH)) {
setStatus(Animation.FINISH);
}
}
}
// REWIND status
if (getStatus().equals(Animation.REWIND)) {
messageAction(Animation.REWIND);
if (currentLocation == FIRST_ROTATE) {
// Set values for animation
firstRotation.setStepTime(getStepTime());
firstRotation.setStep(getStep());
// Set rewind status
firstRotation.setStatus(Animation.REWIND);
// Draw rotation animation
firstRotation.drawAnimation(g2, Animation.REWIND);
if (firstRotation.getStatus().equals(Animation.PAUSE)) {
setStatus(Animation.PAUSE);
}
}
if (currentLocation == SECOND_ROTATE) {
// Set values for animation
secondRotation.setStepTime(getStepTime());
secondRotation.setStep(getStep());
// Set rewind status
secondRotation.setStatus(Animation.REWIND);
// Draw rotation animation
secondRotation.drawAnimation(g2, Animation.REWIND);
if (secondRotation.getStatus().equals(Animation.PAUSE)) {
setStatus(Animation.PAUSE);
}
}
}
// PAUSE status
if (getStatus().equals(Animation.PAUSE)) {
messageAction(Animation.PAUSE);
if (currentLocation == FIRST_ROTATE) {
// Set pause status
firstRotation.setStatus(Animation.PAUSE);
// Draw rotation animation
firstRotation.drawAnimation(g2, Animation.PAUSE);
}
if (currentLocation == SECOND_ROTATE) {
// Set pause status
secondRotation.setStatus(Animation.PAUSE);
// Draw rotation animation
secondRotation.drawAnimation(g2, Animation.PAUSE);
}
}
// STOP status
if (getStatus().equals(Animation.STOP)) {
messageAction(Animation.STOP);
return;
}
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
messageAction(Animation.FINISH);
messageAction("*--------Double Rotation of "+getNode().getKey().toString()+"--------*");
}
// Call listeners
animationAction();
}
/**
* Calls all of the listeners of the current Animation and passed information regarding the
* progress and status of the current Animation. Additionally, the id of the type of animation is
* passed. Within, the animationEventPerformed
method is called.
*
* @param cmd String Animation command passed instead of the current Status.
* @param description String description for messages.
*/
protected void animationAction(String cmd, String description) {
super.animationAction(AnimationEvent.ROTATION_DOUBLE_BST_ANIMATION, cmd, description, rotationLocation / 2.0);
}
/**
* Implements AnimationListener
which requires the following method.
* The only status of animation it listens for is Animation.ANIMATION_MESSAGE
, to pass
* the message on.
*
* @param e AnimationEvent that represents the information of the Animation.
*/
public void animationEventPerformed(AnimationEvent e) {
// set location each progress call.
rotationLocation = e.getProgress();
if (e.getStatus().equals(Animation.ANIMATION_MESSAGE)) {
messageAction(e.getAnimationDescription());
}
if (e.getStatus().equals(Animation.STEP)) {
animationAction(Animation.STEP, null);
}
}
}