Red Black Tree Visualization using HTML5 Canvas and GWT

I created a sample app, which demonstrates HTML5 Canvas usage from Java through GWT. I think GWT is a great tool for migrating desktop apps into Web nowadays, especially for Java developers. So it's worth to give it a try.

Google has made great progress on migrating desktop apps into Web during last year. They propagated trend for HTML5 support and Javascript JIT compilers among modern browsers. So it's possible to run Quake 2 or CAD software directly in browser at decent speed.

Red Black Tree is a balanced BST tree. Details are described on Wikipedia.
You can run this sample app directly on appspot (it works on iPhone too :-) )
Sample code can be found here: Browse on GitHub.


Let's start from initialization.
First, we need to create Canvas element and add it to HTML. getContext2D is called to obtain drawing context.
We register a timer to redraw frames frequently:

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

view raw init.java hosted with ❤ by GitHub

So doUpdate is called every 50 ms and whenever redrawFrame is set to true, it redraws Canvas contents.
In autoplay mode, we call processFrame in while loop. So whenever redraw procedure takes too long, we will process frames without redrawing them. This won't slow down animation on low resources.

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

view raw processFrame.java hosted with ❤ by GitHub

Then, we need to draw a tree. We use drawTree procedure, which is recursive and draws nodes along with contents and connections between them:

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

view raw drawTree.java hosted with ❤ by GitHub

The best part is that we can do regular Java unit tests on Red Black tree to verify correctness of implementation:

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

view raw test.java hosted with ❤ by GitHub

Grammar parser in C++

Recently I stumbled upon implementing a simple parser in C++. The task is very classic, however I couldn't find any good resources on the web to help me out.
I tried different tools (including ANTLR), but finally the easiest way I found was bison + flex. It's unbelievable that this technology from 1989 is still actively developed. Latest stable release is from May 14, 2011. Moreover, many important projects make use of it. Among them are Ruby, PHP, Google Go, Bash shell.
So I decided to create a minimalistic example, which works from scratch.
I published the code on github Calculator, so you can check it out.
The whole example is 88 lines long and evaluates common expressions, like 2+2*2-13*(7+19/2).
Let's start with lexer. In flex, you need to define regular expressions, which produce tokens. Such tokens are later processed by a scanner. So we have to define calculator.lex, like this:

	%{
	#include "calculator.tab.h"
	using namespace std;
	%}
	%%
	[ \t] ;
	\+ { return PLUS; }
	\- { return MINUS; }
	\* { return MUL; }
	\/ { return DIV; }
	\( { return LPAREN; }
	\) { return RPAREN; }
	[0-9]+ { yylval.ival = atoi(yytext); return INT; }
	[a-zA-Z0-9]+ {
	yylval.sval = strdup(yytext);
	return IDENT;
	}
	\n return ENDL;
	. ;
	%%

view raw calculator.lex hosted with ❤ by GitHub

Flex will generate yylex() function, which we can call later to produce tokens.
Next, we need to create a scanner (calculator.y), which specifies a grammar. It's simple like that:

	%{
	#include <cstdio>
	#include <iostream>
	using namespace std;
	int yylex();
	extern "C" int yyparse();
	extern "C" FILE *yyin;
	void yyerror(char *s);
	%}
	%union {
	int ival;
	float fval;
	char *sval;
	}
	%token ENDL PLUS MINUS MUL DIV LPAREN RPAREN
	%token <ival> INT
	%token <sval> IDENT
	%type <ival> expression1
	%type <ival> expression
	%left PLUS MINUS
	%left MUL DIV
	%%
	start:
	expressions;
	expressions:
	expressions expression1 ENDL
	| expression1 ENDL;
	expression1:
	expression { cout<<$1<<endl; };
	expression:
	expression PLUS expression { $$ = $1 + $3; }
	|expression MINUS expression { $$ = $1 - $3; }
	|expression MUL expression { $$ = $1 * $3; }
	|expression DIV expression { $$ = $1 / $3; }
	|LPAREN expression RPAREN { $$ = $2; }
	| INT { $$ = $1; };
	%%
	int main(int argc, char *argv[]) {
	if (argc!= 2) {
	cout <<"Usage: <command> filename"<<endl;
	return 1;
	}
	FILE *myfile = fopen(argv[1], "r");
	if (!myfile) {
	cout << "I can't open "<<argv[1]<< endl;
	return -1;
	}
	yyin = myfile;
	do {
	yyparse();
	} while (!feof(yyin));
	}
	void yyerror(char *s) {
	cout << "Parse error: " << s << endl;
	exit(-1);
	}

view raw calculator.y hosted with ❤ by GitHub

Here, we specify types for all tokens using C/C++ union like structure. Variable $$ is used to store result of particular reductions.
Additionally, we need to specify %left precedence for +, -, *, / operators to resolve shift / reduce conflicts between them.
And that's basically it. We have a working expression parser.
I implemented it in a way, that executable takes a file name containing expressions as an argument.
So you can try ./calculator input.txt to see the result.