/*
This file is part of the algoviz@vt collection of algorithm
visualizations.
This program is free software: you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this distribution. If not, see
.
*/
package splayTree;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.util.*;
import javax.swing.Timer;
/**
* A collection of virtual states. This corresponds to the states
* generated by inserting, finding or deleting a single node. It also
* handles animating between virtual states.
*
* @author Andy Street, alstreet@vt.edu
* @version Feb 11, 2009
*
*/
public class VirtualStateCollection
{
/**
* The number of states in an animation
*/
private final int STEPS = 25;
private final Color ALERT = Color.red;
private LinkedList states = new LinkedList();
private int currentState = 0;
private Timer animationTimer = null;
private int x = 0, y = 0;
private int width = TreeApplet.WIDTH, height = TreeApplet.HEIGHT;
private Image buffer = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
public int delay=3;
private VirtualState prev,next;
private TreePanel tp;
private int newState;
private Color background;
private Graphics treeGraphics,g;
public void setDelay(int time){
delay=time;
//System.out.println("time delay is "+delay);
}
/**
* Returns what state number was added.
*/
public int addState(VirtualState vs)
{
states.add(vs);
return states.size() - 1;
}
/**
* Animates between two VirtualStates, indicated by number
*
* @param tp
* @param stateNumber
* @param i
*/
public void animate(final TreePanel tp, int prevState, final int newState)
{
this.tp=tp;
this.newState=newState;
g = buffer.getGraphics();
TreePanel._AntiAliasOn(g);
treeGraphics = tp.getGraphics();
TreePanel._AntiAliasOn(treeGraphics);
background = tp.getBackground();
prev = states.get(prevState);
next = states.get(newState);
tp.enableButtons(false);
animationTimer = new Timer(1, new listener());
animationTimer.start();
}
public class listener implements ActionListener{
private int step = isDifference(prev, next) ? 0 : STEPS;
/**
* @see java.awt.event.ActionListener#actionPerformed(java.awt.event.ActionEvent)
*/
public void actionPerformed(ActionEvent e)
{
if(step > STEPS)
{
animationTimer.stop();
currentState = newState;
tp.enableButtons(true);
return;
}
g.setColor(background);
g.fillRect(x, y, width, height);
drawInterpolatedState(g, prev, next, step);
treeGraphics.drawImage(buffer, 0, 0, null);
step++;
}
}
/**
* Interpolates and draws all the VNodes and Lines based on the current state number.
*/
public void drawInterpolatedState(Graphics g, VirtualState prev, VirtualState next, int step)
{
boolean nodesAreMoving = prev.getNodesMoving() || next.getNodesMoving();
for(int id : next.lineIds())
{
Line p = prev.getLine(id);
Line n = next.getLine(id);
drawLine(g, getInterpolatedLine(p, n, step, nodesAreMoving));
}
for(int id : next.nodeIds())
{
VNode p = prev.getNode(id);
VNode n = next.getNode(id);
drawNode(g, getInterpolatedNode(p, n, step));
}
}
public int interpolate(int startVal, int endVal, int end, int current)
{
return (startVal * (end - current) + endVal * (current)) / end;
}
private VNode getInterpolatedNode(VNode old, VNode now, int step)
{
if(now == null) return old;
VNode ret = new VNode();
ret.id = now.id;
ret.x = interpolate(old == null ? now.x + now.size / 2 : old.x, now.x, STEPS, step);
ret.y = interpolate(old == null ? now.y + now.size / 2 : old.y, now.y, STEPS, step);
ret.size = interpolate(old == null ? 0 : old.size, now.size, STEPS, step);
ret.left = now.left;
ret.right = now.right;
ret.height = now.height;
ret.isPlaceholder = now.isPlaceholder;
ret.outline = now.outline;
ret.fill = now.fill;
ret.text = (old == null && step < STEPS) ? null : now.text;
return ret;
}
private Location getInterpolatedLocation(Location old, Location now, int step)
{
return new Location(interpolate(old.x, now.x, STEPS, step), interpolate(old.y, now.y, STEPS, step));
}
private Line getInterpolatedLine(Line old, Line now, int step, boolean nodesAreMoving)//, VNode childNode)
{
if(old == null)
{
now.goingForward = true;
return now;
}
if(now == null)
{
old.goingForward = false;
return old;
}
if(old.equals(now)) return old;
Location start = getInterpolatedLocation(old.start, now.start, step);
Location end = getInterpolatedLocation(old.end, now.end, step);
Line ret = new Line(start, end);
ret.color = now.color;
if(!nodesAreMoving && step < STEPS)
ret.color = ALERT;
//childNode.outline = ALERT;
ret.id = old.id;
return ret;
}
public void drawNode(Graphics g, VNode v)
{
// Add in placeholder nodes
g.setColor(v.fill);
g.fillOval(v.x, v.y, v.size, v.size);
g.setColor(v.outline);
g.drawOval(v.x, v.y, v.size, v.size);
if(v.text != null)
{
g.setColor(v.outline);
((Graphics2D)g).drawString(v.text, (float) (v.x + GraphicalNode.NODE_WIDTH / 3.2),
(float) (v.y + GraphicalNode.NODE_HEIGHT / 1.7));
}
}
public void drawLine(Graphics g, Line l)
{
if((l.goingForward && l.hideGoingForward) || (!l.goingForward && l.hideGoingBackward)) return;
g.setColor(l.color);
int x1=l.start.x,y1= l.start.y,x2= l.end.x,y2= l.end.y;
g.drawLine(l.start.x + GraphicalNode.NODE_WIDTH / 2, l.start.y + GraphicalNode.NODE_HEIGHT / 2, l.end.x + GraphicalNode.NODE_WIDTH / 2, l.end.y + GraphicalNode.NODE_WIDTH / 2);
int[] p1,p2;
p1=new int[3];
p2=new int[3];
int constantx=10,constanty=20;
double phi;
if(l.end.x-l.start.x!=0)
phi=Math.atan(l.end.y-l.start.y/(l.end.x-l.start.x));
else
phi=Math.PI/2;
/* drawing pointing triangle with each line*/
double theta=Math.PI/6;
if(l.start.x>l.end.x&&l.start.yl.end.y){
p1[0]=l.end.x+13;
p1[1]=p1[0]+(int)(constantx*Math.cos(theta));
p1[2]=p1[0]-(int)(constantx*Math.cos(theta));
p2[0]=l.end.y+30;
p2[1]=p2[0]+(int)(constanty*Math.sin(theta));
p2[2]=p2[0]+(int)(constanty*Math.sin(theta));
g.fillPolygon(p1, p2, 3);
}
else if(l.start.x