package edu.princeton.cs.algs4.growingtree.framework; /* * @(#)SelectionBSTAnimation.java * * Last Modified: 9/15/01 */ import java.util.*; import java.lang.*; import java.awt.*; import java.awt.font.*; import java.awt.geom.*; /** * * The Animation object that defines a selection within a BSTTree.
* * 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.4 9/15/01 */ public class SelectionBSTAnimation
extends AbstractAnimation {
public static final float ENLARGE_SIZE = 1.4F;
/**
* Constant that defines the starting location.
*/
private final int START = 1;
/**
* Defines the final node location.
*/
private int FINAL_NODE;
/**
* Defines the end location.
*/
protected int END;
/**
* Color Scheme used for the animation on left, using one of the NodeSettings Schemes.
*/
private NodeSettings animationSchemeLeft;
/**
* Color Scheme used for the animation on right, using one of the NodeSettings Schemes.
*/
private NodeSettings animationSchemeRight;
/**
* Color Scheme used for the animator, using one of the NodeSettings Schemes.
*/
private NodeSettings animatorScheme;
/**
* Color Scheme used for the key of the animator, using one of the KeySettings Schemes.
*/
private KeySettings keyAnimatorScheme;
/**
* Private doubles used to hold the current and previous location steps.
*/
protected double currentLocation = 0.0;
private double previousLocation = 0.0;
/**
* Refers to the list of AffineTransforms used to emphasize each given node.
*/
private AffineTransformList enlargeTransforms;
/**
* Refers to the linked list which will store the node of each step, used to draw the
* pass of each node.
*/
protected LinkedList currentNode;
/**
* The Default step conversion used in animation (300).
*/
//public final static int DEFAULT_CONVERSION = 600;
/**
* The constructor which initiates the status and prepares the colorSchemes. The node
* which is animating must be passed. The first step added is the identity step.
*
* @param elementCount the integer count of the kth element being partitioned.
* @param headNode the head of the tree being searched.
* @param AnimationSchemeLeft the node) {
nodes.add(node);
node.addAnimator(this);
this.addAnimationListener(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.
*
* @param g2 the graphics to which the animation step should be drawn.
* @param startingStatus the status used as the starting command of animation, if needed.
*/
public void drawAnimation(Graphics2D g2, String startingStatus) {
setStartingCommand(startingStatus);
// BEGIN status
if (getStatus().equals(Animation.BEGIN)) {
currentLocation = 0;
previousLocation = 0;
// Empty nodes, set to finish.
if (nodes.isEmpty()) {
setStatus(Animation.FINISH);
}
else {
// Set current node
currentNode = (GrowingTreeNode )nodes.getFirst();
// Set originalElementCount
originalElementCount = getElementCount();
// Set transforms list
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);
// Make initial enlarge Transforms list
enlargeTransforms.add(currentTransform);
enlargeTransforms.add(enlargeTransform);
enlargeTransforms.add(currentTransform);
animationAction();
messageAction(Animation.BEGIN + " Selection for "+getElementCount()+"th smallest from "+currentNode.getKey().toString());
// set starting status
setStatus(getStartingCommand());
// Draw all nodes
int size= nodes.size();
for(int i=0; i nextNode = ((GrowingTreeNode )nodes.get((int)Math.floor(currentLocation)));
messageAction("Size of "+currentNode.getKey().toString()+" left tree : " + currentNode.getLeftNodeInternal().size());
// Left
if(currentNode.getLeftNodeInternal() == nextNode ) {
currentNode.saveLeftSettings();
currentNode.getSettings().setNodeSettings(getAnimationSchemeLeft());
currentNode.getSettings().setLeftSettings(getAnimationSchemeLeft());
//currentNode.drawNodeAndLeftLink();
messageAction(" ("+getElementCount()+" < "+currentNode.getLeftNodeInternal().size()+" ) ");
messageAction("Selection for "+getElementCount()+"th element proceeds left");
}
// Right
if(currentNode.getRightNodeInternal() == nextNode ) {
currentNode.saveRightSettings();
currentNode.getSettings().setNodeSettings(getAnimationSchemeRight());
currentNode.getSettings().setRightSettings(getAnimationSchemeRight());
//currentNode.drawNodeAndRightLink();
messageAction(" ("+getElementCount()+" > "+currentNode.getLeftNodeInternal().size()+" ) ");
messageAction("Selection for "+getElementCount()+"th element proceeds right");
setElementCount(getElementCount() - currentNode.getLeftNodeInternal().size() - 1);
}
// Next node set
currentNode = nextNode;
//messageAction("Selection continues with "+currentNode.getKey().toString()+",\n looking for its "+getElementCount()+"th element ");
}
// The beginning node of the selection, if the selection is not of that node.
if (currentNode == nodes.getFirst() && (nodes.size() > 1)) {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeFirstNode = (AffineTransform)currentTransform.clone();
enlargeFirstNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeFirstNode);
enlargeTransforms.set(2,currentTransform);
currentNode.drawNodeAndLink(g2);
currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
// If the selection is at the final node
else if (currentNode == nodes.getLast()) {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeLastNode);
enlargeTransforms.set(2,enlargeLastNode);
currentNode.drawNodeAndLink(g2);
currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
// In the middle of the selection
else {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeTransform);
enlargeTransforms.set(2,currentTransform);
// Draw just the node and links.
currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
}
// Final animation
else if (currentLocation < END) {
// Draw the node
currentNode.drawNodeAndLink(g2);
// Save
currentNode.saveSettings();
((DrawableKey)currentNode.getValue()).saveSettings();
// Set setttings
currentNode.setNodeSettings(getAnimatorScheme());
((DrawableKey)currentNode.getValue()).setKeySettings(getKeyAnimatorScheme());
// Draw the node large
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);
currentNode.drawNode(g2, enlargeLastNode);
// Restore
currentNode.restoreSettings();
((DrawableKey)currentNode.getValue()).restoreSettings();
}
// Finally, FINISH
else {
setStatus(Animation.FINISH);
}
}
// REWIND status
if (getStatus().equals(Animation.REWIND)) {
messageAction(Animation.REWIND);
previousLocation = currentLocation;
if(getStep()) { // Skip middle Animation Steps
currentLocation = Math.floor(currentLocation) - getStepSize();
}
else { // Normal Step
currentLocation -= getStepSize();
}
if (currentLocation < START) {
// Set status to stop
setStatus(Animation.PAUSE);
currentLocation = 0;
}
if (currentLocation < FINAL_NODE) {
if (previousLocation >= END) {
currentNode.restoreSettings();
((DrawableKey)currentNode.getValue()).restoreSettings();
}
// Finished a step in the Animation.
if (Math.ceil(currentLocation) == Math.floor(previousLocation)) {
// Set Step status
setStatus(Animation.STEP);
GrowingTreeNode nextNode = ((GrowingTreeNode )nodes.get((int)Math.floor(currentLocation)));
// Restore settings
while (nextNode.isSettingsSaved()) {
nextNode.restoreSettings();
}
//nextNode.eraseNodeAndLink();
//nextNode.drawNodeAndLink();
if(nextNode.getRightNodeInternal() == currentNode ) {
setElementCount(getElementCount() + nextNode.getLeftNodeInternal().size() + 1);
}
currentNode = nextNode;
}
// The beginning node of the selection, if the selection is not of that node.
if (currentNode == nodes.getFirst()) {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeFirstNode = (AffineTransform)currentTransform.clone();
enlargeFirstNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeFirstNode);
enlargeTransforms.set(2,currentTransform);
currentNode.drawNodeAndLink(g2);
currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
// If the selection is at the final node
else if (currentNode == nodes.getLast()) {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeLastNode);
enlargeTransforms.set(2,enlargeLastNode);
currentNode.drawNodeAndLink(g2);
currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
// In the middle of the selection
else {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);
enlargeTransforms.set(0,currentTransform);
enlargeTransforms.set(1,enlargeTransform);
enlargeTransforms.set(2,currentTransform);
// Draw just the node and links.
currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
// Draw just the node without links.
currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
}
else {
AffineTransform currentTransform = currentNode.getCurrentTransform();
AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);
currentNode.drawNode(g2, enlargeTransform);
}
}
// PAUSE status
if (getStatus().equals(Animation.PAUSE)) {
messageAction(Animation.PAUSE);
// Draw node where it is.
currentNode.drawNodeAndLink(g2);
}
// STOP status
if (getStatus().equals(Animation.STOP)) {
messageAction(Animation.STOP);
}
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
messageAction(Animation.FINISH);
messageAction("*----Selection Element Found----*\n"+originalElementCount+"th element of "+((GrowingTreeNode )nodes.getFirst()).getKey().toString()+"\nElement found at "+currentNode.getKey().toString());
animationAction();
restore();
return;
}
// Call listeners
animationAction();
}
/**
* Restores the settings of all nodes encountered during the animation. Usually called at
* the end of the animation (Animation.FINISH) to restore all settings changed throughout
* the animation. This also restores the animator node.
*/
private void restore() {
//int size = nodes.size();
for(int i=0; i < nodes.size(); i++) {
GrowingTreeNode currentNode = ((GrowingTreeNode )nodes.get(i));
while (currentNode.isSettingsSaved()) {
currentNode.restoreSettings();
}
while (((DrawableKey)currentNode.getValue()).isSettingsSaved()) {
((DrawableKey)currentNode.getValue()).restoreSettings();
}
}
}
/**
* 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 NodeSettings
associated with a color scheme according to NodeSettings for the left Animation.
* @param AnimationSchemeRight the NodeSettings
associated with a color scheme according to NodeSettings for the right Animation.
* @param KeyAnimatorScheme the KeySettings
associated with a color scheme according to KeySettings.
* @param startingCmd the Animation command that this should start.
* @param stepTime the time for each step of the Animation. Sets the initial value.
*/
public SelectionBSTAnimation(int elementCount, NodeSettings AnimationSchemeLeft, NodeSettings AnimationSchemeRight, NodeSettings AnimatorScheme, KeySettings KeyAnimatorScheme, String startingCmd, int stepTime) {
super();
// Set defaults if no color schemes exist
if (AnimationSchemeLeft == null) {
AnimationSchemeLeft = new NodeSettings();
}
if (AnimationSchemeRight == null) {
AnimationSchemeRight = new NodeSettings();
}
if (AnimatorScheme == null) {
AnimatorScheme = new NodeSettings();
}
if (KeyAnimatorScheme == null) {
KeyAnimatorScheme = new KeySettings();
}
enlargeTransforms = new AffineTransformList();
nodes = new LinkedListanimationEventPerformed
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.SELECTION_BST_ANIMATION, cmd, description, currentLocation / (double)nodes.size());
}
}