Decision Tables

I still see a lot of code with complicated if-then-else conditions that can be simplified quite a bit by the simple technique of using decision tables. A decision table is a compact yet exhaustive way of encoding conditions and the actions to be taken under those conditions. The rows and columns of a decision table denote the conditions and the cells denote the actions. Since it simplifies complicated conditional logic, it can make your code a lot easier to maintain and a lot less error-prone.

Decision tables come in many forms. The exact structure of an optimal decision table will depend on the particular problem being solved. For example, if you are writing an interpreter for a virtual machine with single-byte opcodes where most of the 255 possible values stand for valid instructions, you can simply construct a table with 255 pointers to instruction-specific interpreter functions. In this case, if you have written the interpretAdd( ) function to interpret the ADD instruction with opcode, say, "23", the 23^rd position in the decision table (counting from 0) will be a pointer to the interpretAdd( ) function. The core of the interpreter loop then simply fetches the next byte and calls the function at the position in the decision table indicated by the value of the byte.

Let us consider another example (taken from the task description for ICFPC 2008). Suppose you are writing the steering-control logic for a Martian rover in Java. The rover moves around on Mars avoiding boulders, craters and evil Martians with a goal of reaching its home base as quickly as possible. The steering-control logic for the rover has to compute the desired direction of motion relative to the current direction of motion and turn the axle accordingly.

The axle of the rover could be in one of the following possible orientations:

private static final int TURN_STATE_HARD_LEFT = 0;
private static final int TURN_STATE_LEFT = 1;
private static final int TURN_STATE_STRAIGHT = 2;
private static final int TURN_STATE_RIGHT = 3;
private static final int TURN_STATE_HARD_RIGHT = 4;

Based on the environment and the goal, your steering-control logic determines one of the following courses of action to move in the desired direction relative to the current direction of motion:

private static final int STEER_LEFT = 0;
private static final int STEER_FORWARD = 1;
private static final int STEER_RIGHT = 2;
private static final int STEER_BACKWARD = 3;

The output of your steering-control logic has to be one of "l", "-" or "r" denoting a command to "turn the axle further left", "not change the axle orientation" or "turn the axle further right" respectively. You can then construct a decision table like the following to get an appropriate command based on the current orientation of the axle and the desired direction of motion:

private char[][] steerDecTable
= {
/* LEFT, FORWARD, RIGHT, BACKWARD */
/* HARD_LEFT */  {   '-',   'r',     'r',   '-'},
/* LEFT */       {   '-',   'r',     'r',   'l'},
/* STRAIGHT */   {   'l',   '-',     'r',   'r'},
/* RIGHT */      {   'l',   'l',     '-',   'r'},
/* HARD_RIGHT */ {   'l',   'l',     '-',   '-'},
};

The rows of this table denote the current orientation of the axle and the columns denote the desired direction of motion. Note that the values of our named constants have been selected to match the corresponding indices in this table.

With this decision table in hand, the core of our steering-control logic simply becomes:

char steerChar = steerDecTable[curTurnState][steer];

"curTurnState" denotes the current orientation of the axle and has one of the values denoted by the "TURN_STATE_XXX" named constants. "steer" denotes the desired direction of motion and has one of the values denoted by the "STEER_XXX" named constants.

Think about how you would have written this logic without using a decision table.

Update (2010-02-24): The chapter on table-driven methods in the book "Code Complete" by Steve McConnell contains more details on this technique.

Tweet