*
* @author Corey Sanders
* @version 1.2 9/15/01
*/
public class InsertRedBlackAnimation extends InsertBSTAnimation implements AnimationListener {
/**
* The location for the rotations to begin.
*/
private double WAITING_ROTATIONS;
/**
* The location for beginning of checking rotations.
*/
protected static final int BEGIN_CHECK = 0;
/**
* The location for the left checking of rotations.
*/
protected static final int LEFT_CHECK = 1;
/**
* The location for the right checking of rotations.
*/
protected static final int RIGHT_CHECK = 2;
/**
* The location for the rotations to check.
*/
private int rotationCheck;
/**
* Holds the links that must be changed to red.
*/
LinkedList redChangeLinks = new LinkedList();
/**
* Holds the links that must be changed to black.
*/
LinkedList blackChangeLinks = new LinkedList();
/**
* The location for the rotations to begin.
*/
private int ROTATIONS;
/**
* Refers to the current Rotation being drawn.
*/
RotationBSTAnimation currentRotation = null;
/**
* The current index of the search through the tree.
*/
private int currentIndexSearch;
/**
* 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 node the BSTTree which is animated during the animation.
* @param AnimationSchemeLeft 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 AnimatorScheme the NodeSettings associated with a color scheme according to NodeSettings.
* @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 InsertRedBlackAnimation(BSTTree node, NodeSettings AnimationSchemeLeft, NodeSettings AnimationSchemeRight, NodeSettings AnimatorScheme, KeySettings KeyAnimatorScheme, String startingCmd, int stepTime) {
super(node, AnimationSchemeLeft, AnimationSchemeRight, AnimatorScheme, KeyAnimatorScheme, startingCmd, stepTime);
}
/**
* The constructor which initiates the status and sets the colorSchemes to null. No colors
* will be change using this animation. The node
* which is animating must be passed. The first step added is the identity step.
*
* @param node the BSTTree which is animated during the animation.
*/
public InsertRedBlackAnimation(BSTTree node) {
this(node, null, null, null , null , Animation.PLAY, DEFAULT_STEP);
}
/*********************/
/* 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);
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
if (getCurrentLocation() < WAITING_ROTATIONS) {
int size = getNodeMovements().size();
for(int i = (int)Math.floor(getCurrentLocation()); i < size; i++) {
RedBlackTree currentNode = ((RedBlackTree)getNodeMovements().get(i));
if (currentNode != null) {
// Fixes 4-nodes
if (((RedBlackTree)currentNode.getLeftTree()).isRedLink() && ((RedBlackTree)currentNode.getRightTree()).isRedLink()) {
currentNode.setRedLink(true);
((RedBlackTree)currentNode.getLeftTree()).setRedLink(false);
((RedBlackTree)currentNode.getRightTree()).setRedLink(false);
}
}
}
restore();
setCurrentLocation(ROTATIONS);
currentRotation = null;
currentIndexSearch = (getNodeMovements().size()-1);
rotationCheck = BEGIN_CHECK;
messageAction(Animation.REDRAW);
setBlackChangeLinks();
setRedChangeLinks();
}
if (currentRotation != null) {
currentRotation.setStatus(Animation.FINISH);
currentRotation.drawAnimation(g2, Animation.FINISH);
setBlackChangeLinks();
setRedChangeLinks();
}
while(true) {
for( ; currentIndexSearch>=0; currentIndexSearch--) {
if (getNodeMovements().get(currentIndexSearch) != null) {
makeCurrentRotation((RedBlackTree)getInsertNode(), (RedBlackTree)getNodeMovements().get(currentIndexSearch));
}
}
animationAction();
return;
}
}
// BEGIN status
if (getStatus().equals(Animation.BEGIN)) {
setCurrentLocation(0);
setPreviousLocation(0);
//animator scheme exists
getInsertNode().saveSettings();
getInsertNode().setNodeSettings(getAnimatorScheme());
((DrawingKey)getInsertNode().getValue()).saveSettings();
((DrawingKey)getInsertNode().getValue()).setKeySettings(getKeyAnimatorScheme());
animationAction();
messageAction(Animation.BEGIN + " Insertion of "+getInsertNode().getKey().toString());
// set starting status
setStatus(getStartingCommand());
WAITING_ROTATIONS = getMovements().size();
ROTATIONS = getMovements().size() + 1;
return;
}
// Currently on a step and no changes have occured. Return to starting command
if (getStatus().equals(Animation.STEP)) {
setStatus(getStartingCommand());
}
// PLAY status
if (getStatus().equals(Animation.PLAY)) {
messageAction(Animation.PLAY);
setPreviousLocation(getCurrentLocation());
if (getCurrentLocation() < WAITING_ROTATIONS) {
if(getStep()) { // Skip middle animation steps.
setCurrentLocation(Math.ceil(getCurrentLocation()) + getStepSize());
}
else { // Normal step
setCurrentLocation(getCurrentLocation() + getStepSize());
}
// Set node positions.
nextNodeIndex = (int)Math.ceil(getCurrentLocation());
previousNodeIndex = (int)Math.floor(getCurrentLocation());
// Completed Animation
if (getCurrentLocation() >= (getMovements().size()-1)) {
setStatus(Animation.STEP);
restore();
messageAction(Animation.REDRAW);
currentIndexSearch = (getNodeMovements().size()-1);
setCurrentLocation(WAITING_ROTATIONS);
rotationCheck = BEGIN_CHECK;
}
else {
// Finished a step in the Animation.
if (Math.ceil(getPreviousLocation()) == Math.floor(getCurrentLocation()) && getPreviousLocation() != 0) {
setStatus(Animation.STEP);
comparisonCount++;
RedBlackTree previousNode = ((RedBlackTree)getNodeMovements().get(previousNodeIndex));
if (previousNode != null) {
// Fixes 4-nodes
if (((RedBlackTree)previousNode.getLeftTree()).isRedLink() && ((RedBlackTree)previousNode.getRightTree()).isRedLink()) {
previousNode.setRedLink(true);
((RedBlackTree)previousNode.getLeftTree()).setRedLink(false);
((RedBlackTree)previousNode.getRightTree()).setRedLink(false);
messageAction(Animation.REDRAW);
messageAction("Four-node split, by setting the parent red bit.");
}
}
}
// Set movements
getMovements().set(previousNodeIndex, resetPosition(previousNodeIndex));
getMovements().set(nextNodeIndex, resetPosition(nextNodeIndex));
// Draw just the node without links.
getInsertNode().drawNode(g2, getMovements().getTransformStep(getCurrentLocation()));
}
}
if (getCurrentLocation() < ROTATIONS && getCurrentLocation() >= WAITING_ROTATIONS) {
if(getStep()) { // Skip middle animation steps.
setCurrentLocation(ROTATIONS);
}
else { // Normal step
setCurrentLocation(getCurrentLocation() + getStepSize());
}
}
if (getCurrentLocation() >= ROTATIONS) {
if (getPreviousLocation() < ROTATIONS) {
for( ; currentIndexSearch>=0; currentIndexSearch--) {
if (getNodeMovements().get(currentIndexSearch) != null) {
makeCurrentRotation((RedBlackTree)getInsertNode(), (RedBlackTree)getNodeMovements().get(currentIndexSearch));
if (currentRotation != null)
break;
}
}
if (currentIndexSearch < 0) {
setStatus(Animation.FINISH);
}
else {
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.PLAY);
messageAction(Animation.REDRAW);
currentRotation.addAnimationListener(this);
if (rotationCheck == BEGIN_CHECK) {
currentIndexSearch--;
}
}
}
else {
// 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)) {
setBlackChangeLinks();
setRedChangeLinks();
messageAction(Animation.REDRAW);
setCurrentLocation(WAITING_ROTATIONS);
currentRotation.removeAnimationListener(this);
currentRotation = null;
}
}
}
}
// REWIND status
if (getStatus().equals(Animation.REWIND)) {
messageAction(Animation.REWIND);
setPreviousLocation(getCurrentLocation());
if (getCurrentLocation() < WAITING_ROTATIONS) {
if(getStep()) { // Skip middle animation steps.
setCurrentLocation(Math.floor(getCurrentLocation()) - getStepSize());
}
else { // Normal step
setCurrentLocation(getCurrentLocation() - getStepSize());
}
// Set node positions.
nextNodeIndex = (int)Math.ceil(getCurrentLocation());
previousNodeIndex = (int)Math.floor(getCurrentLocation());
// Beginning of Animation
if (getCurrentLocation() <= 0) {
setStatus(Animation.PAUSE);
setCurrentLocation(0);
animationAction();
return;
}
// Finished a step in the Animation.
if (Math.ceil(getPreviousLocation()) == Math.floor(getCurrentLocation()) && getPreviousLocation() != 0) {
setStatus(Animation.STEP);
comparisonCount--;
}
// Set movements
getMovements().set(previousNodeIndex, resetPosition(previousNodeIndex));
getMovements().set(nextNodeIndex, resetPosition(nextNodeIndex));
// Draw just the node without links.
getInsertNode().drawNode(g2, getMovements().getTransformStep(getCurrentLocation()));
}
if (getCurrentLocation() < ROTATIONS && getCurrentLocation() >= WAITING_ROTATIONS) {
messageAction("Cannot Rewind : Beginning of Rotation");
setCurrentLocation(getPreviousLocation());
// Pause status
setStatus(Animation.PAUSE);
}
if (getCurrentLocation() >= ROTATIONS) {
// 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 (getCurrentLocation() < WAITING_ROTATIONS) {
nextNodeIndex = (int)Math.ceil(getCurrentLocation());
previousNodeIndex = (int)Math.floor(getCurrentLocation());
// Set movements
getMovements().set(previousNodeIndex, resetPosition(previousNodeIndex));
getMovements().set(nextNodeIndex, resetPosition(nextNodeIndex));
// Draw just the node without links.
getInsertNode().drawNode(g2, getMovements().getTransformStep(getCurrentLocation()));
}
if (getCurrentLocation() < ROTATIONS && getCurrentLocation() >= WAITING_ROTATIONS) {
}
if (getCurrentLocation() >= ROTATIONS) {
// Set play status
currentRotation.setStatus(Animation.PAUSE);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.PAUSE);
}
messageAction(Animation.PAUSE);
}
// STOP status
if (getStatus().equals(Animation.STOP)) {
if (getCurrentLocation() < WAITING_ROTATIONS) {
}
if (getCurrentLocation() < ROTATIONS && getCurrentLocation() >= WAITING_ROTATIONS) {
}
if (getCurrentLocation() >= ROTATIONS) {
// Set play status
currentRotation.setStatus(Animation.STOP);
// Draw rotation animation
currentRotation.drawAnimation(g2, Animation.STOP);
}
messageAction(Animation.STOP);
}
// FINISH status
if (getStatus().equals(Animation.FINISH)) {
NumberFormat nf = NumberFormat.getNumberInstance();
nf.setMaximumFractionDigits(3);
messageAction(Animation.FINISH);
messageAction("*--------Insertion of "+getInsertNode().getKey().toString()+"--------*\n Comparisons: "+
comparisonCount+"\n Average Insertion: "+nf.format(((BSTTreeHead)getInsertNode().getHead()).averageInsertion(insertionSize))+
"\n Worst Case Insertion: "+nf.format(((BSTTreeHead)getInsertNode().getHead()).worstCaseInsertion(insertionSize) ));
animationAction();
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. It also passes the animation action
* to all nodes of Animation.FINISH.
*/
protected void restore() {
super.restore();
AnimationEvent animationEvent = new AnimationEvent(this, AnimationEvent.INSERT_RED_BLACK_ANIMATION, Animation.FINISH);
((RedBlackTree)getInsertNode()).animationEventPerformed(animationEvent);
((RedBlackTree)getInsertNode()).setRedLink(true);
messageAction("New Nodes have red bit set upon insertion.");
}
/**
* Constructs the current Rotation according to the current tree, and the defined rotationCheck.
* This method called out of context results in unforeseen errors.
*
* @param newTree RedBlackTree that represents the newly added node.
* @param node RedBlackTree that represents the current checking node.
*
*/
protected void makeCurrentRotation(RedBlackTree newTree, RedBlackTree node) {
if (rotationCheck == BEGIN_CHECK) {
// Keeps Red-Link integrity
if ((newTree.getKey()).compareTo(node.getKey()) < 0) { // Go to the left
rotationCheck = LEFT_CHECK;
if (node != node.getHead().getChild()) {
// Two consequetive red links.
if ((node.isRedLink()) && (((RedBlackTree)node.getLeftTree()).isRedLink())) {
// Same Direction
if (node != ((RedBlackTree)node.getParentTree()).getLeftTree()) {
currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)node.getHead()).makeRotationAnimation((RedBlackTree)node.getLeftTree());
if (currentRotation == null) {
((RedBlackTreeHead)node.getHead()).rotateUpTreeType((RedBlackTree)node.getLeftTree());
messageAction(Animation.REDRAW);
}
else {
return;
}
}
}
}
}
else {
rotationCheck = RIGHT_CHECK;
if (node != node.getHead().getChild()) {
// Two consequetive red links.
if ((node.isRedLink()) && (((RedBlackTree)node.getRightTree()).isRedLink())) {
// Same Direction
if (node != ((RedBlackTree)node.getParentTree()).getRightTree()) {
currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)node.getHead()).makeRotationAnimation((RedBlackTree)node.getRightTree());
if (currentRotation == null) {
((RedBlackTreeHead)node.getHead()).rotateUpTreeType((RedBlackTree)node.getRightTree());
messageAction(Animation.REDRAW);
}
else {
return;
}
}
}
}
}
}
if (rotationCheck == LEFT_CHECK) {
rotationCheck = BEGIN_CHECK;
if (!node.getLeftTree().isEmpty()) {
if ((((RedBlackTree)node.getLeftTree()).isRedLink()) && (((RedBlackTree)node.getLeftTree().getLeftTree()).isRedLink()) ) {
// Reference to rotated up parent.
RedBlackTree newParent = (RedBlackTree)node.getLeftTree();
currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)node.getHead()).makeRotationAnimation((RedBlackTree)node.getLeftTree());
blackChangeLinks.add(newParent);
redChangeLinks.add(node);
if (currentRotation == null) {
((RedBlackTreeHead)node.getHead()).rotateUpTreeType((RedBlackTree)node.getLeftTree());
setBlackChangeLinks();
setRedChangeLinks();
messageAction(Animation.REDRAW);
}
}
}
}
if (rotationCheck == RIGHT_CHECK) {
rotationCheck = BEGIN_CHECK;
if (!node.getRightTree().isEmpty()) {
if ((((RedBlackTree)node.getRightTree()).isRedLink()) && (((RedBlackTree)node.getRightTree().getRightTree()).isRedLink()) ) {
// Reference to rotated up parent.
RedBlackTree newParent = (RedBlackTree)node.getRightTree();
currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)node.getHead()).makeRotationAnimation((RedBlackTree)node.getRightTree());
blackChangeLinks.add(newParent);
redChangeLinks.add(node);
if (currentRotation == null) {
((RedBlackTreeHead)node.getHead()).rotateUpTreeType((RedBlackTree)node.getRightTree());
setBlackChangeLinks();
setRedChangeLinks();
messageAction(Animation.REDRAW);
}
}
}
}
}
/**
* Fixes the redChangeLinks by settings all the nodes links within the list to red. Then
* the nodes are removed from the list, always leaving it clear after this call.
*/
public void setRedChangeLinks() {
ListIterator list = redChangeLinks.listIterator(0);
while (list.hasNext()) {
RedBlackTree currentNode = (RedBlackTree)list.next();
if (!currentNode.isEmpty()) {
// Reverses the link
currentNode.setRedLink(true);
}
}
redChangeLinks.clear();
}
/**
* Fixes the blackChangeLinks by settings all the nodes links within the list to black. Then
* the nodes are removed from the list, always leaving it clear after this call.
*/
public void setBlackChangeLinks() {
ListIterator list = blackChangeLinks.listIterator(0);
while (list.hasNext()) {
RedBlackTree currentNode = (RedBlackTree)list.next();
if (!currentNode.isEmpty()) {
// Reverses the link
currentNode.setRedLink(false);
}
}
blackChangeLinks.clear();
}
/**
* 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);
}
}
/**
* 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.INSERT_RED_BLACK_ANIMATION, cmd, description, getCurrentLocation() / (double)getMovements().size());
}
}