Skip to content

Instantly share code, notes, and snippets.

@rafalrusin
Created October 16, 2011 12:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rafalrusin/1290819 to your computer and use it in GitHub Desktop.
Save rafalrusin/1290819 to your computer and use it in GitHub Desktop.
rbvis
private void drawTree(RBNode n, float x1, float x2, float y1, float y2) {
if (n != null) {
if (n.left != null) {
drawConnection((x1 + x2)/2.0f, y1, (x2 - x1)*1.f/4.0f + x1, y2);
}
if (n.right != null) {
drawConnection((x1 + x2)/2.0f, y1, (x2 - x1)*3.f/4.0f + x1, y2);
}
drawNode("" + n.value, n.isBlack, (x1 + x2)/2.0f, y1);
drawTree(n.left, (x2 - x1)*0.f/4.0f + x1, (x2 - x1)*2.f/4.0f + x1, y2, y2 + (y2-y1));
drawTree(n.right, (x2 - x1)*2.f/4.0f + x1, (x2 - x1)*4.f/4.0f + x1, y2, y2 + (y2-y1));
}
}
private void drawConnection(float x1, float y1, float x2, float y2) {
contextScreen.setStrokeStyle(drawColor);
contextScreen.beginPath();
contextScreen.moveTo(x1, y1);
contextScreen.lineTo(x2, y2);
contextScreen.closePath();
contextScreen.stroke();
}
private void drawNode(String label, boolean isBlack, float x, float y) {
contextScreen.beginPath();
contextScreen.arc(x, y, 15, 0, 2*Math.PI);
contextScreen.closePath();
contextScreen.setFillStyle(isBlack ? blackColor : redColor);
contextScreen.fill();
contextScreen.setStrokeStyle(drawColor);
contextScreen.stroke();
contextScreen.setFillStyle(isBlack ? backgroundColor : blackColor);
contextScreen.fillText(label, x - label.length() * 4 + 2, y + 4);
}
public void onModuleLoad() {
canvasScreen = Canvas.createIfSupported();
if (canvasScreen == null) {
RootPanel.get().add(new Label("Sorry, your browser doesn't support the HTML5 Canvas element"));
return;
}
canvasScreen.setCoordinateSpaceHeight(height);
canvasScreen.setCoordinateSpaceWidth(width);
canvasScreen.setSize(width + "px", height + "px");
contextScreen = canvasScreen.getContext2d();
RootPanel.get().add(canvasScreen);
final Timer timer = new Timer() {
@Override
public void run() {
doUpdate();
}
};
timer.scheduleRepeating(50);
}
private void doUpdate() {
long currentTime = new Date().getTime();
if (autoplay) {
while (frameTime < currentTime) {
processFrame();
frameTime += 200;
}
}
if (refreshFrame) {
refreshFrame = false;
contextScreen.setFillStyle(backgroundColor);
contextScreen.fillRect(0, 0, width, height);
drawTree(tree.getRoot(), 20, width-20, 40, 75);
contextScreen.setFillStyle(blackColor);
contextScreen.fillText(message, 10, 10);
}
}
private void processFrame() {
int range = 64;
i = (i + 1)%range;
if (i < range/2) {
tree.insert(i);
message = "Insert " + i;
} else {
int j = i - range/2;
tree.remove(j);
message = "Remove " + j;
}
message = message + " Time: " + (frameTime - startTime);
refreshFrame = true;
}
public class RBTreeCorrectnessTest extends TestCase {
private int testSize = 1000;
public void testInsert() {
Comparator comparator = new Comparator() {
public int compare(Object o1, Object o2) {
return ((Integer) o1).compareTo((Integer) o2);
}
};
RBTree tree = new RBTree(comparator);
for (int i = 1; i < testSize; i++) {
tree.insert(i);
tree.verifyRedBlack();
}
System.out.println(tree.verifyRedBlack());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment