rbvis

drawTree.java

        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);
	}

init.java

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);
}

processFrame.java

        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;
	}

test.java

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());
    }
}