package edu.princeton.cs.algs4.growingtree.framework; /* * @(#)DeleteBSTAnimation.java * * Last Modified: 9/15/01 */ import java.util.*; import java.awt.*; import java.awt.geom.*; /** * * The Animation object that defines the Deletion of a node in a BSTTree. Two constructors exist, * one setting the animator and line paints(preferred), the other using defaults. The animation builds RotationBSTAnimations * as it goes, keeping only one currently animating rotation and allowing rewinding only to the previous * rotation.
* * @author Corey Sanders * @version 1.3 9/15/01 */ public class DeleteBSTAnimation
extends AbstractAnimation implements AnimationListener { /** * Constant that defines the starting location. */ protected final int START = 0; /** * Constant that defines the fading of the erasing node. */ protected final int FADE_NODE = 1; /** * Defines the partitioning through the tree. */ protected int PARTITION_TREE = 2; /** * Defines the final move through the tree. */ protected int FINAL_MOVE = 3; /** * Defines the final move through the tree. */ protected int END = 4; /** * Refers to the current PartitionBSTAnimation being drawn. */ protected PartitionBSTAnimation
currentPartition; /** * Refers to the final moving nodes. */ protected MovingBSTTreeAnimation
finalMovingNodes; /** * Private doubles used to hold the current and previous location steps. */ protected double currentLocation = 0.0; protected double previousLocation = 0.0; /** * PaintSettings for the left line drawn during partitioning. */ PaintSettings leftLinePaintSettings = null; /** * PaintSettings for the right line drawn during partitioning. */ PaintSettings rightLinePaintSettings = null; /** * Holds the node that is erasing. */ private GrowingTreeNode
erasingNode; /** * Holds the node that is replacing. */ private GrowingTreeNode
replacingNode; /** * The constructor which initiates the status and prepares the line paints. The node * which is being deleted must be passed. * * @param erasingNode the BSTTree which is being deleted. * @param RightLinePaintSettings the paint for the right line when drawing the deletion. * @param LeftLinePaintSettings the paint for the left line when drawing the deletion * @param startingCmd the Animation command that this should start. * @param stepTime the time for each step of the Animation. Sets the initial value. */ public DeleteBSTAnimation(GrowingTreeNode
erasingNode, PaintSettings RightLinePaintSettings, PaintSettings LeftLinePaintSettings, String startingCmd, int stepTime) { // Call to AbstractAnimation super(); // If null colors, set defaults if (RightLinePaintSettings == null) { RightLinePaintSettings = PaintSettings.getScheme(PaintSettings.RED); } if (LeftLinePaintSettings == null) { LeftLinePaintSettings = PaintSettings.getScheme(PaintSettings.BLUE); } // Set line colors setLeftLinePaintSettings(LeftLinePaintSettings); setRightLinePaintSettings(RightLinePaintSettings); // Set erasing node setErasingNode(erasingNode); setStartingCommand(startingCmd); setStepTime(stepTime); } /** * The constructor which initiates the status and sets the line paints to null. * * @param erasingNode the BSTTree which is deleted during the deletion. */ public DeleteBSTAnimation(GrowingTreeNode
erasingNode) { this(erasingNode, null, null, Animation.PLAY, DEFAULT_STEP); } /************************/ /* Accessor methods */ /************************/ /** * Gets the node being deleted during the deletion. * * @return BSTTree of the node being deleted. */ public GrowingTreeNode
getErasingNode() { return erasingNode; } /** * Gets the node being replaced during the deletion. * * @return BSTTree of the node being replaced. */ public GrowingTreeNode
getReplacingNode() { return replacingNode; } /** * Gets the PaintSettings for the right line of the partition for deletion. * * @return PaintSettings for the right line of the deletion. */ public PaintSettings getRightLinePaintSettings() { return rightLinePaintSettings; } /** * Gets the paint for the left line of the partition for deletion. * * @return Paint for the left line of the deletion. */ public PaintSettings getLeftLinePaintSettings() { return leftLinePaintSettings; } /************************/ /* Mutator methods */ /************************/ /** * Sets the node being deleted during the Deletion. * * @param GrowingTreeNode of the node being deleted. */ public void setErasingNode(GrowingTreeNode
node) { erasingNode = node; } /** * Sets the node being replaced during the Deletion. * * @param GrowingTreeNode of the node being replaced. */ public void setReplacingNode(GrowingTreeNode
node) { replacingNode = node; } /** * Sets the PaintSettings for the right line of the partition for deletion. * * @param rightPaintSettings for the right line of the deletion. */ public void setRightLinePaintSettings(PaintSettings rightPaintSettings) { rightLinePaintSettings=rightPaintSettings; } /** * Sets the paint for the left line of the partition for deletion. * * @return leftPaint for the left line of the deletion. */ public void setLeftLinePaintSettings(PaintSettings leftPaintSettings) { leftLinePaintSettings=leftPaintSettings; } /***********************/ /* Creation Methods */ /***********************/ /** * Creates the moving nodes corresponding to the descendant of the rotation. */ protected void createFinalMovingNodes() { // Intialize finalMovingNodes = new MovingBSTTreeAnimation
(); // Head node GrowingTreeNode
headNode = (GrowingTreeNode
)getErasingNode().getHead().getChild(); // Head moving node. MovingBSTTree
headMovingNode = new MovingBSTTree
(headNode); if (headNode != getErasingNode() && headNode.isAnimateDrawing() ) { // If there is a grandchild. headMovingNode = new MovingBSTTree
(headNode); // Add grandchild to descendant animation finalMovingNodes.add(headMovingNode, headNode); headMovingNode.setMovePosition(MovingBSTTree.FOLLOW_NODE); // Set listeners finalMovingNodes.addAnimationListener(headNode); (headNode).addAnimator(finalMovingNodes); } // Add all children addNode((GrowingTreeNode
)headNode.getLeftNodeInternal(), finalMovingNodes, MovingBSTTree.FOLLOW_NODE, headMovingNode); addNode((GrowingTreeNode
)headNode.getRightNodeInternal(), finalMovingNodes, MovingBSTTree.FOLLOW_NODE, headMovingNode);
}
/**
* Adds all children nodes to the animator list, setting the Moving node as its parent. The move position
* defines the moving of the new node.
*
* @param node the node which the MovingBSTTree made imitates.
* @param animator the MovingBSTTreeAnimation to which the new MovingBSTTree node is added.
* @param movePostion the moving position of the new MovingBSTTree.
* @param parent MovingBSTTree
parent for the node, specifically for following the node.
*/
protected void addNode(GrowingTreeNode
node, MovingBSTTreeAnimation
animator, int movePosition, MovingBSTTree
parent) { if (node.isEmpty()) return; // Create new MovingBSTTree MovingBSTTree
movingNode = new MovingBSTTree
(node, parent); if (node != getErasingNode() && node.isAnimateDrawing()) { // Sets the move position movingNode.setMovePosition(movePosition); // Adds the animator to the MovingBSTTreeAnimation animator.add(movingNode, node); // Adds the listener to the animation and the animation to the node. animator.addAnimationListener(node); node.addAnimator(animator); } // Recursively goes through children addNode((GrowingTreeNode
)node.getLeftNodeInternal(), animator, MovingBSTTree.FOLLOW_NODE, movingNode); addNode((GrowingTreeNode
)node.getRightNodeInternal(), animator, MovingBSTTree.FOLLOW_NODE, movingNode); } /*********************/ /* 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: *
removeTreeType
- to do the final deletion in the actual code (after partitioning has occured))getErasingNode().getLeftNodeInternal()); // Do actual deletion in tree (Setting the correct final location). getErasingNode().getHead().removeTreeType(getErasingNode()); currentLocation = FINAL_MOVE; messageAction("No right Tree : Replace with Left tree"); // REDRAW Message messageAction(Animation.REDRAW); // Set begin of finalMovingNodes finalMovingNodes.drawAnimation(g2, Animation.PLAY); } } // Non-Empty Right Tree else { // Partition element currentLocation = PARTITION_TREE; //messageAction("Partition the smallest node of right subtree"); int k = ((GrowingTreeNode
)getErasingNode().getRightNodeInternal()).getLeftNodeInternal().size(); currentPartition = (PartitionBSTAnimation
)((GrowingTreeHead
)getErasingNode().getHead()).makePartitionAnimation((GrowingTreeNode
)getErasingNode().getRightNodeInternal(), k); currentPartition.addAnimationListener(this); currentPartition.drawAnimation(g2, Animation.PLAY); // Do not allow the erased node draw during the Partition getErasingNode().setAnimateDrawing(false); } } // The partition of the tree else if (currentLocation == PARTITION_TREE) { // Set values for animation currentPartition.setStepTime(getStepTime()); currentPartition.setStep(getStep()); // Set play status currentPartition.setStatus(Animation.PLAY); // Draw rotation animation currentPartition.drawAnimation(g2, Animation.PLAY); if (currentPartition.getStatus().equals(Animation.FINISH)) { setReplacingNode((GrowingTreeNode
)getErasingNode().getRightNodeInternal());
// Step
setStatus(Animation.STEP);
// Create final moving nodes starting at previous location.
createFinalMovingNodes();
// Do actual deletion in tree (Setting the correct final location).
getErasingNode().getHead().removeTreeType(getErasingNode());
// REDRAW Message
messageAction(Animation.REDRAW);
// Beginning final moving Nodes
finalMovingNodes.drawAnimation(g2, Animation.PLAY);
messageAction("Replace erased node with node " + getReplacingNode().getKey().toString());
currentLocation = FINAL_MOVE;
}
}
// The final move of the node
else if (currentLocation < END) {
// Set play status
finalMovingNodes.setStatus(Animation.PLAY);
// Set values for animation
finalMovingNodes.setStepTime(getStepTime());
finalMovingNodes.setStep(getStep());
// Draw animation
finalMovingNodes.drawAnimation(g2, Animation.PLAY);
}
// Completely finished
if (currentLocation >= END) {
this.erasingNode.getHead().popTreeProperties();
// Set values for animation
finalMovingNodes.setStepTime(getStepTime());
finalMovingNodes.setStep(getStep());
// Set play status
finalMovingNodes.setStatus(Animation.PLAY);
// Draw animation
finalMovingNodes.drawAnimation(g2, Animation.PLAY);
// Set status of moving animation
finalMovingNodes.setStatus(Animation.FINISH);
// Draw animation
finalMovingNodes.drawAnimation(g2, Animation.FINISH);
// Set own status
this.erasingNode.getHead().popTreeProperties();
setStatus(Animation.FINISH);
}
}
// REWIND status
if (getStatus().equals(Animation.REWIND)) {
messageAction(Animation.REWIND);
if (currentLocation <= FADE_NODE || currentLocation >= FINAL_MOVE) {
previousLocation = currentLocation;
if(getStep()) { // Skip middle Animation Steps
currentLocation = Math.floor(currentLocation) - getStepSize();
}
else { // Normal Step
currentLocation -= getStepSize();
}
}
// Rewind to beginning
if (currentLocation <= START ) {
// Set status to stop
setStatus(Animation.PAUSE);
// Erasing node
getErasingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1));
getErasingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1));
getErasingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1));
((DrawableKey)getErasingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1));
// Draw to animating graphic
getErasingNode().drawNodeAndLink(g2);
// Reset location
currentLocation = 0.0;
}
// The fading out of the node.
else if (currentLocation <= FADE_NODE) {
float currentAlpha = (float)((double)FADE_NODE - currentLocation);
// Erasing node
getErasingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
getErasingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
getErasingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
((DrawableKey)getErasingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
// Draw to animating graphic
getErasingNode().drawNodeAndLink(g2);
}
// The searching through the tree
else if (currentLocation == PARTITION_TREE) {
// Set values for animation
currentPartition.setStepTime(getStepTime());
currentPartition.setStep(getStep());
// Set play status
currentPartition.setStatus(Animation.REWIND);
// Draw rotation animation
currentPartition.drawAnimation(g2, Animation.REWIND);
if (currentPartition.getStatus().equals(Animation.PAUSE)) {
messageAction("Cannot Rewind : Beginning of Partition");
// Pause
setStatus(Animation.PAUSE);
}
}
// Precautionary (Cannot go beyond FINAL_MOVE)
else if (currentLocation < FINAL_MOVE) {
currentLocation = FINAL_MOVE;
finalMovingNodes.setStatus(Animation.PAUSE);
messageAction("Cannot Rewind : Beginning of Final Move");
// Pause
setStatus(Animation.PAUSE);
}
// The final move the nodes
else if (currentLocation <= END) {
// Set play status
finalMovingNodes.setStatus(Animation.REWIND);
// Set values for animation
finalMovingNodes.setStepTime(getStepTime());
finalMovingNodes.setStep(getStep());
// Draw animation
finalMovingNodes.drawAnimation(g2, Animation.REWIND);
if (finalMovingNodes.getStatus().equals(Animation.PAUSE)) {
messageAction("Cannot Rewind : Beginning of Final Move");
// Pause
setStatus(Animation.PAUSE);
}
}
}
// PAUSE status
if (getStatus().equals(Animation.PAUSE)) {
messageAction(Animation.PAUSE);
// The fading out of the node.
if (currentLocation < FADE_NODE ) {
float currentAlpha = (float)((double)FADE_NODE - currentLocation);
// Erasing node
getErasingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
getErasingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
getErasingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
((DrawableKey)getErasingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
// Draw to animating graphic
getErasingNode().drawNodeAndLink(g2);
}
// The searching through the tree
else if (currentLocation == PARTITION_TREE) {
// Set play status
currentPartition.setStatus(Animation.PAUSE);
// Draw rotation animation
currentPartition.drawAnimation(g2, Animation.PAUSE);
}
// The rotating up of the node
else if (currentLocation < END ) {
finalMovingNodes.setStatus(Animation.PAUSE);
// Draw animation
finalMovingNodes.drawAnimation(g2);
}
}
// STOP status
if (getStatus().equals(Animation.STOP)) {
messageAction(Animation.STOP);
// The fading out of the node.
if (currentLocation < FADE_NODE ) {
// Do nothing
}
// The searching through the tree
else if (currentLocation == PARTITION_TREE) {
// Set play status
currentPartition.setStatus(Animation.STOP);
// Draw rotation animation
currentPartition.drawAnimation(g2, Animation.STOP);
}
// The rotating up of the node
else if (currentLocation < END ) {
finalMovingNodes.setStatus(Animation.STOP);
// Draw animation
finalMovingNodes.drawAnimation(g2);
}
return;
}
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
messageAction(Animation.FINISH);
if (getReplacingNode() == null) {
messageAction("*--------Deletion of "+getErasingNode().getKey().toString()+"--------*\n"+
"No Replacement for Node");
}
else {
messageAction("*--------Deletion of "+getErasingNode().getKey().toString()+"--------*\n"+
"Node replaced by: "+getReplacingNode().getKey().toString());
}
}
// Call listeners
animationAction();
}
/**
* Draws a dotted line according to the current location within the graphics.
*
* @param g2 Graphics2D to which the line is drawn.
* @param location the double location of progress in the animation.
*/
protected void drawDottedLine( Graphics2D g2, double location) {
// Makes the left dotted line
Line2D.Double dottedLeft = new Line2D.Double( (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 - 1) , (getErasingNode().getCurrentTransform().getTranslateY() + getErasingNode().getCurrentTransform().getScaleY()/2.0) , (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 - 1) , (g2.getClipBounds().getY() + g2.getClipBounds().getHeight()));
// Makes the right dotted line
Line2D.Double dottedRight = new Line2D.Double( (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0+ 1) , (getErasingNode().getCurrentTransform().getTranslateY() + getErasingNode().getCurrentTransform().getScaleY()/2.0) , (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 + 1) , (g2.getClipBounds().getY() + g2.getClipBounds().getHeight()));
// Sets break distance
float dash[] = {10.0f};
BasicStroke dashed = new BasicStroke(2.0f,
BasicStroke.CAP_BUTT,
BasicStroke.JOIN_MITER,
10.0f, dash, 0.0f);
// Draw dotted line.
if (location <= FADE_NODE) { // Fading in
g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, (float)location));
}
else if (location >= FINAL_MOVE) {
g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, (float)(1.0 - (location - (Math.floor(location)))) ));
}
else {// Full Composite
g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1.0F));
}
// Set graphics information
g2.setStroke(dashed);
g2.setPaint(getLeftLinePaintSettings().getPaint());
g2.draw(dottedLeft);
g2.setPaint(getRightLinePaintSettings().getPaint());
g2.draw(dottedRight);
}
/**
* 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.DELETE_BST_ANIMATION, cmd, description, currentLocation / END);
}
/**
* 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);
}
}
}