[ 2003-November-24 12:25 ]

Much as programming in Java has improved my C++ and my grasp of object-oriented concepts, programming in dynamic languages (of which Perl and Python are my favourites) has also taught me some lessons. Today I'm going to delve into one: lookup tables.

One of the prime advantages to dynamic languages are their rich datatypes. My favourite is the dictionary, hash table, or associative array, depending on which language you come from. These are key/value pair containers. I use them constantly in dynamic languages to determine if something has already been processed, to store a number of named parameters like a structure or to store a bunch of predefined values. However, one use which is fairly specific to dynamic languages is to use them as a lookup table to implement a certain function, instead of using some big switch or if statement.

As an example, I've recently written a Python script which generates some C code for displaying some text and graphics onscreen using OpenGL. This script parses an XML description of the graphics and text, then outputs a function with the appropriate C calls. One way of handling the parsing is to use a big if-else statement like this:

if node.nodeName == 'text':
	# Do stuff
elif node.nodeName == 'img':
	# Do other stuff
else:
	# Raise exception

Instead of doing that, I've chosen to create a "dispatchTable" dictionary which maps node names onto functions. Now my code looks like this:

dispatchTable = { 'text' : handleText, 'img' : handleImg }

if dispatchTable.has_key( node.nodeName ):
	# Call the function
	dispatchTable[ node.nodeName ]( node )
else:
	# Raise exception

I think this is clearer and more readable. I also like that you can just add additional items to the data structure and it all "just works". As a result, I've started using this practice in my C++ projects. Since I can't easily map any type to any other type, I've been using arrays. The challenge is to find a simple and understandable mapping from your key type to an array index. As an example, I just wrote some code to rotate points 90 degrees on a 3x3 grid, with the centre defined as (0, 0), and the edges defined as (+/-1, +/-1). It looks like this:

const uint8_t rotationsX[] = {
	1, // ( -1, -1 )
	0, // ( -1, 0 )
	-1, // ( -1, 1 )
	
	1, // ( 0, -1 )
	0, // ( 0, 0 )
	-1, // ( 0, 1 )
	
	1, // ( 1, -1 )
	0, // ( 1, 0 )
	-1, // ( 1, 1 )
};

// Maps index -> new Y value
const uint8_t rotationsY[] = {
	-1, // ( -1, -1 )
	-1, // ( -1, 0 )
	-1, // ( -1, 1 )
	
	0, // ( 0, -1 )
	0, // ( 0, 0 )
	0, // ( 0, 1 )
	
	1, // ( 1, -1 )
	1, // ( 1, 0 )
	1, // ( 1, 1 )
};

int index = point.getX() * 3 + point.gety() + 4;

point.setX( rotationsX[index] );
point.setY( rotationsY[index] );

Maybe I'm being too clever, but I think this is easier to read, understand and to fix than a massive if-else, which is what I almost started writing. Best of all, after creating the rotation arrays, I was able to spot a pattern and reduce these lines of code to this:

int index = point.getX() * 3 + point.getY() + 4;

int nextY = index/3 - 1;
int nextX = 4 + 3*nextY - index;

point.setX( nextX );
point.setY( nextY );

Now, this is definitely too clever, and anyone else who reads this will struggle figure it out. However, the original technique is a good one, and I would never have discovered the formula if it wasn't for using dynamic languages and lookup tables.