package edu.princeton.cs.algs4.growingtree.framework; /* * @(#)PartitionBSTAnimation.java * * Last Modified: 9/15/01 */ import java.util.*; import java.awt.*; /** * * The Animation object that defines the Paritioning of a node in a BSTTree. The animation builds RotationBSTAnimations * as it goes, keeping only one currently animating and allowing rewinding only to the beginning of * the currrent rotation.
* * 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.5 9/15/01 */ public class PartitionBSTAnimation
extends AbstractAnimation implements AnimationListener { /** * Constant that defines the starting location. */ private final int START = 0; /** * Constant that defines the selection of the kth element node. */ private int SELECTION_ANIMATION = 1; /** * Defines the rotating upwards through the tree. */ private int ROTATE_UP_TREE = 2; /** * Private doubles used to hold the current and previous location steps. */ private double currentLocation = 0.0; private double previousLocation = 0.0; /** * Refers to the current RotationBSTAnimation being drawn. */ RotationBSTAnimation
currentRotation; /** * Refers to the current RotationBSTAnimation being drawn. */ SelectionBSTAnimation
currentSelection; /** * Holds the node that is replacing. */ private GrowingTreeNode
node; /** * Holds the node that is replacing. */ private GrowingTreeNode
replacingNode; /** * Level count, how far down the replacing node is from the erased node. */ private int levelCount; /** * keySelect count, the kth element to partition to the top. */ private int keySelect; /** * Counts the amount of comparisons made. */ private int rotationCount = 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 keySelect integer finding the kth node * @param startingCmd the Animation command that this should start. * @param stepTime the time for each step of the Animation. Sets the initial value. */ public PartitionBSTAnimation(GrowingTreeNode
node, int keySelect, String startingCmd, int stepTime) { super(); setNode(node); setKeySelect(keySelect); setStartingCommand(startingCmd); setStepTime(stepTime); } /** * The constructor which initiates the status and sets the color schemes to null. No colors * will be changed using this animation. The node * which is animating must be passed. * * @param node the BSTTree which is deleted during the deletion. * @param keySelect integer finding the kth node */ public PartitionBSTAnimation(GrowingTreeNode
node, int keySelect) { this(node, keySelect, 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; } /** * Gets the keySelect of the partition, the kth element. * * @return int keySelect of the partition. */ public int getKeySelect() { return keySelect; } /** * Gets the node currently being rotated up to replace (not set until after selection occurs). * * @return BSTTree of the ndoe currently being replaced and animated. */ public GrowingTreeNode
getReplacingNode() { return replacingNode; } /** * Gets the count of levels for rotated the replacing node to its proper place. * * @return int level count of rotations for the replacing node to its new location. */ public int getLevelCount() { return levelCount; } /************************/ /* 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; } /** * Sets the keySelect of the partition, the kth element. * * @param keySelect kth element of the partition. */ public void setKeySelect(int keySelect) { this.keySelect = keySelect; } /** * Sets the node currently being drawn during the Partition. * * @param GrowingTreeNode of the node currently being replaced and animated. */ public void setReplacingNode(GrowingTreeNode
node) { replacingNode = node; } /** * Sets the count of levels for rotated the replacing node to its proper place. The * count must be the amount of RotateUp calls the node needs to become the highest node in * its tree. The final move does not count as a rotate. * * @param level intt level count of rotations for the replacing node to its new location. */ public void setLevelCount(int level) { levelCount = level; } /*********************/ /* 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. * * BSTTreeHead calls: *
partitionTreeType
- only called if the animation does not complete (otherwise, the animation rotates it to the top)selectTreeType
- called to find the replacing node )getNode().getHead()).makeSelectionAnimation(getNode(), getKeySelect()); messageAction(Animation.REDRAW); currentSelection.addAnimationListener(this); currentSelection.drawAnimation(g2, Animation.PLAY); currentLocation = SELECTION_ANIMATION; } else if (currentLocation == SELECTION_ANIMATION) { // Set values for animation currentSelection.setStepTime(getStepTime()); currentSelection.setStep(getStep()); // Set play status currentSelection.setStatus(Animation.PLAY); // Draw rotation animation currentSelection.drawAnimation(g2, Animation.PLAY); if (currentSelection.getStatus().equals(Animation.FINISH)) { // Do actual selection in tree, setting the replacing node. setReplacingNode((GrowingTreeNode
) ((GrowingTreeHead
)getNode().getHead()).selectTreeType(getNode(), getKeySelect()));
// Set level count as the difference in levels of the nodes.
setLevelCount(getReplacingNode().getLevel() - getNode().getLevel());
// More rotations needed
if (getLevelCount() > 0) {
// Make rotation animation.
currentRotation = (RotationBSTAnimation)getReplacingNode().getHead().makeRotationAnimation(getReplacingNode());
// Pass listeners
currentRotation.addAnimationListener(this);
// Decrease level count
setLevelCount(getLevelCount() - 1);
// Draw rotation animation (Beginning)
currentRotation.drawAnimation(g2, Animation.PLAY);
currentLocation = ROTATE_UP_TREE;
rotationCount++;
setStatus(Animation.STEP);
}
// No more rotations
else {
setStatus(Animation.FINISH);
}
}
}
else if (currentLocation == ROTATE_UP_TREE) {
// Set values for animation
currentRotation.setStepTime(getStepTime());
currentRotation.setStep(getStep());
// Set play status
currentRotation.setStatus(Animation.PLAY);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.PLAY);
if (currentRotation.getStatus().equals(Animation.FINISH)) {
// Rotate up count (more rotations)
if (getLevelCount() > 0) {
// Make next rotation
currentRotation = (RotationBSTAnimation)getReplacingNode().getHead().makeRotationAnimation(getReplacingNode());
// Pass listeners
currentRotation.addAnimationListener(this);
// Decrease level count
setLevelCount(getLevelCount()-1);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.PLAY);
// Keep track of rotation Count
rotationCount++;
setStatus(Animation.STEP);
}
// Final move, no more rotations
else {
setStatus(Animation.FINISH);
}
}
}
}
// REWIND status
if (getStatus().equals(Animation.REWIND)) {
messageAction(Animation.REWIND);
if (currentLocation == SELECTION_ANIMATION) {
// Set values for animation
currentSelection.setStepTime(getStepTime());
currentSelection.setStep(getStep());
// Set play status
currentSelection.setStatus(Animation.REWIND);
// Draw rotation animation
currentSelection.drawAnimation(g2, Animation.REWIND);
if (currentSelection.getStatus().equals(Animation.PAUSE)) {
messageAction("Cannot Rewind : Beginning of Selection");
// Pause status
setStatus(Animation.PAUSE);
}
}
if (currentLocation == ROTATE_UP_TREE) {
// Set values for animation
currentRotation.setStepTime(getStepTime());
currentRotation.setStep(getStep());
// Set play status
currentRotation.setStatus(Animation.REWIND);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.REWIND);
if (currentRotation.getStatus().equals(Animation.PAUSE)) {
messageAction("Cannot Rewind : Beginning of Rotation");
// Pause status
setStatus(Animation.PAUSE);
}
}
}
// PAUSE status
if (getStatus().equals(Animation.PAUSE)) {
if (currentLocation == SELECTION_ANIMATION) {
// Set play status
currentSelection.setStatus(Animation.PAUSE);
// Draw rotation animation
currentSelection.drawAnimation(g2, Animation.PAUSE);
}
if (currentLocation == ROTATE_UP_TREE) {
currentRotation.setStatus(Animation.PAUSE);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.PAUSE);
}
messageAction(Animation.PAUSE);
}
// STOP status
if (getStatus().equals(Animation.STOP)) {
messageAction(Animation.STOP);
return;
}
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
// Finish message
messageAction(Animation.FINISH);
//messageAction("*--------Partition of "+getNode().getKey().toString()+"--------*\nReplaced with "+getKeySelect()+"th element\nReplaced by: "+
//getReplacingNode().getKey().toString()+"\nRotations: "+rotationCount);
}
// 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.PARTITION_BST_ANIMATION, cmd, description, currentLocation / (double)ROTATE_UP_TREE);
}
/**
* 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) {
if (e.getStatus().equals(Animation.ANIMATION_MESSAGE)) {
messageAction(e.getAnimationDescription());
}
if (e.getStatus().equals(Animation.STEP)) {
animationAction(Animation.STEP, null);
}
}
}