import java.io.*;
import java.util.*;
import java.awt.*;
class Dot {
int level; // 0 is top, 1 is next, etc.
int indent; // 0 is leftmost, 1 is next, etc.
float left; // pixels in from left
float top; // pixels in from top
Dot leftTree;
Dot rightTree;
int number;
Dot shadow;
Color color;
public Dot(int n, Color clr) {
number = n;
color = clr;
leftTree = null;
rightTree = null;
shadow = null;
}
int numberOf() { return number; }
float setLeft(float lf) { return left = lf; }
float setTop(float tp) { return top = tp; }
void setLevel(int lv) { level = lv; }
void setIndent(int in) { indent = in; }
void setShadow(Dot d) { shadow = d; }
void setNumber(int n) { number = n; }
void setLefttree (Dot lt) {
leftTree = lt;
lt.setIndent(2*indent);
lt.setLevel(level+1);
}
void setLeftTree (Dot lt) { leftTree = lt; }
void setRightTree (Dot rt) { rightTree = rt; }
void setRighttree (Dot rt) {
rightTree = rt;
rt.setIndent(2*indent+1);
rt.setLevel(level+1);
}
void setColor(Color c) { color = c; }
Dot shadowOf() { return shadow; }
Dot rightTreeOf() { return rightTree; }
Dot leftTreeOf() { return leftTree; }
float leftOf() { return left; }
float topOf() { return top; }
int levelOf() { return level; }
int indentOf() { return indent; }
Color colorOf() { return color; }
}
class DotPanel extends Panel implements Runnable {
RB graph;
Thread relaxer;
Dot pick, saved_pick = null;
Dot deletingNode;
Color deletingSaveColor;
boolean deleteNode = false, removingNode = false;
DotPanel(RB graph) { this.graph = graph; }
public void run() {
while (true) {
repaint();
try { Thread.sleep(100 + graph.getNDots()); }
catch (InterruptedException e) { break; }
}
}
Image offscreen;
Dimension offscreensize;
Graphics offgraphics;
int left (Dot dot) {
Dimension d = size();
double wid = (double)d.width/(1+(1 << dot.levelOf()));
return (int)(wid*(dot.indentOf()+1)) + 15;
}
int top(Dot dot) { return 20+dot.levelOf()*50 + 15; }
int offset = 28;
public void paintDot(Graphics g, Dot dot, FontMetrics fm, int ox, int oy) {
if (dot == null) return;
int x = left(dot);
int y = top(dot);
int tx = (int)dot.leftOf();
int ty = (int)dot.topOf();
String lbl = String.valueOf(dot.numberOf());
int w = fm.stringWidth(lbl);
int h = fm.getHeight();
g.setColor(dot.colorOf());
g.fillOval(tx+ox-offset, ty+oy, 30, 30);
g.setColor(Color.white);
g.drawString(lbl, tx+ox-offset-w/2+15, ty+oy+12+h/2);
dot.setLeft((float)(.75*(dot.leftOf()-x) + x));
dot.setTop((float)(.75*(dot.topOf()-y) + y));
}
public void paintPickedDot(Graphics g, Dot dot, FontMetrics fm) {
if (dot == null) return;
int tx = (int)dot.leftOf();
int ty = (int)dot.topOf();
String lbl = String.valueOf(dot.numberOf());
int w = fm.stringWidth(lbl);
int h = fm.getHeight();
g.setColor(dot.colorOf());
g.fillOval(tx-offset, ty, 30, 30);
g.setColor(Color.white);
g.drawString(lbl, tx-offset-w/2+15, ty+12+h/2);
}
public void paintEdgesOfDot(Graphics g, Dot dot) {
if (dot == null) return;
g.setColor(Color.black);
int x = (int)dot.leftOf()+15;
int y = (int)dot.topOf()+15;
if (dot.leftTreeOf() != null) {
int lx = (int)dot.leftTreeOf().leftOf()+15;
int ly = (int)dot.leftTreeOf().topOf()+15;
g.drawLine(x-offset,y,lx-offset,ly);
}
if (dot.rightTreeOf() != null) {
int rx = (int)dot.rightTreeOf().leftOf()+15;
int ry = (int)dot.rightTreeOf().topOf()+15;
g.drawLine(x-offset,y,rx-offset,ry);
}
}
public void update(Graphics g) {
Dimension d = size();
if ((offscreen == null) || (d.width != offscreensize.width) ||
(d.height != offscreensize.height)) {
offscreen = createImage(d.width, d.height);
offscreensize = d;
offgraphics = offscreen.getGraphics();
offgraphics.setFont(getFont());
}
offgraphics.setColor(graph.getColor());
offgraphics.fillRect(0, 0, d.width, d.height);
FontMetrics fm = offgraphics.getFontMetrics();
Dot dt[] = graph.getDots();
int nd = graph.getNDots();
for (int i=0 ; i < nd ; i++)
paintEdgesOfDot(offgraphics, dt[i]);
for (int i=0 ; i < nd ; i++)
if (dt[i] != pick) paintDot(offgraphics, dt[i], fm, 0, 0);
else paintPickedDot(offgraphics, dt[i], fm);
if (graph.getNewest() != null)
paintDot(offgraphics, graph.getNewest(), fm, -30, -15);
g.drawImage(offscreen, 0, 0, null);
}
public boolean mouseDown(Event evt, int x, int y) {
Dot dot[] = graph.getDots();
for (int i=0 ; i < graph.getNDots() ; i++) {
if (dot[i] == null) continue;
if (x-dot[i].leftOf() < 0 && y-dot[i].topOf() < 30 &&
x > dot[i].leftOf()-30 && y > dot[i].topOf()) {
saved_pick = pick = dot[i];
if (deleteNode == true) {
deleteNode = false;
deletingNode = pick;
deletingSaveColor = deletingNode.colorOf();
deletingNode.setColor(Color.green);
removingNode = true;
}
return true;
}
}
return true;
}
public boolean mouseDrag(Event evt, int x, int y) {
if (pick != null) {
pick.setLeft(x+20);
pick.setTop(y-10);
}
return true;
}
public boolean mouseUp(Event evt, int x, int y) {
pick = null;
return true;
}
public void start() { relaxer = new Thread(this); relaxer.start(); }
public void stop() { relaxer.stop(); }
public void setValue(boolean v) { deleteNode = v; }
public boolean removingOf() { return removingNode; }
public Dot dotOf() { return deletingNode; }
public Color saveColorOf() { return deletingSaveColor; }
public void setRemoving(boolean v) { removingNode = v; }
}
public class RB extends java.applet.Applet {
DotPanel panel;
Dot shadow;
int sysLock = 0;
Dot cdot[] = new Dot[100];
int cndots = 0;
Dot dot[] = new Dot[100];
int ndots = 0;
Dot ss[] = new Dot[100];
Dot rev1 = null, rev2 = null, rev3 = null;
int ssindex = 0;
Dot head = null;
Dot chead = null;
Dot temp = null;
Dot newest = null;
Dot stopdot = new Dot(0, Color.black);
Dot pushdownward;
Dot pushupward;
Dot t_dot;
Button addbutton, nextbutton, undobutton, startbutton,
tempbutton, delbutton, colorit;
TextField val;
Panel p;
Color bgcolor = new Color(190,190,190);
Color downSaveColor;
int step = 0;
boolean inserting = false;
Dot[] getDots() { return dot; }
int getNDots() { return ndots; }
Dot getNewest() { return newest; }
Color getColor() {
if (rev1 == null && rev2 == null && rev3 == null &&
!panel.removingOf() &&
temp == null && !(head == null && newest != null) &&
ssindex == 0 && (head != null && head.colorOf() == Color.black)) {
bgcolor = new Color(190,190,190);
inserting = false;
} else if (panel.removingOf())
bgcolor = new Color(0,190,190);
return bgcolor;
}
public void init() {
setLayout(new BorderLayout());
panel = new DotPanel(this);
add("Center", panel);
p = new Panel();
add("South", p);
p.add(startbutton = new Button("Restart"));
p.add(undobutton = new Button("Undo"));
p.add(val = new TextField(5));
p.add(addbutton = new Button("Add Node"));
p.add(nextbutton = new Button("Next Step"));
p.add(delbutton = new Button("Delete Node"));
