As a continuation to the discussion on Purpose of Pointers to Functions, let’s step up the complexity and have an array of function pointers. This time, we’ll use C++ because we’ll need the inheritance  for demonstration 🙂

Array of Callbacks

What’s the purpose of having an array of function pointers?

Let’s say you’re building a physics simulator that needs to check for collision between different geometric objects. Let’s say our objects are: point, square, circle. We can have simple declarations for these like so:

The virtual destructor is necessary to indicate that GeometricObject is a polymorphic class. It’s a requirement in order to use dynamic_cast<>, though we will not demonstrate it here in this post.

The destructor doesn’t do anything, for now. The GetType() is just a getter for the private member, type.

Let’s say we store all the objects in a container (like std::vector).

We add some elements in some part of our code and we do brute force collision testing.

The collision test above is brute force because it checks if every pair of geometric objects are colliding. If I had 4 object instances; A, B, C, and D, there will be a total of 6 collision tests: A-B, A-C, A-D, B-C, B-D, C-D. There are optimizations for this but it’s not the point of this post. The TestCollision() function returns non-zero (true) when the two objects are colliding.

Knowing that there are 3 geometric object types, we’ll need to implement 9 different collision tests for each pair of types.

	Point	Rect	Circle
Point	PtPt	PtRect	PtCircle
Rect	RectPt	RectRect	RectCircle
Circle	CirclePt	CircleRect	CircleCircle

I know what you’re thinking, there are duplicate functions. For example, PtRect and RectPt should be the same. Technically, they are indeed the same. The only difference is the order of the parameters. Basically, you just need to implement one, let’s say PtRect, and RectPt will call PtRect with flipped parameters. Same goes with PtCircle/CirclePt and RectCircle/CircleRect. We only need 6 collision test functionalities but we need 9 for implementation.

Let’s go back to the TestCollision() function. The intuitive way to implement the function is to have a nested if-else-if  or switch statement. The outer switch statement would check the type of the first parameter and the inner switch statement would check the type of the second parameter.

Actually, it’s already optimized but it’s just not obvious.

Instead of having the TestCollision() function, we could have a collision test map. The collision test map is a 2D array of pointers to functions. This way, the table above would be more intuitive to update when the need for additional Geometric Objects arise.

This is called a jump table. Instead of having conditions to determine which function to execute, you store the functions in an array and use the index as the “condition”. Notice how the assignment of the collision test functions resemble the table above? This makes updating easier when new geometric objects come about. We don’t need to change the size of the 2D array, we just need to include additional elements into the enum.

Now that we have the jump table, instead of checking via the TestCollision() function, we call the appropriate collision test based on the type.

This guarantees that no conditions need to be checked.

Now, one might ask themselves, isn’t the switch statement automatically converted to a jump table? The answer is no. A switch statement only becomes a jump table when the perfect conditions are met. The conditions are:

• No fall through (all cases end with a break)
• Case expressions are beautifully enumerated (starts with 0, increments by one)

In our case above, we set the enum GeometricObject_t to start with 0 and the succeeding values are 1 greater than the previous. Which means, we have a perfect switch statement!

In other words, I just demonstrated to you how the C/C++ compiler optimizes a perfect switch statement to a jump table.

Jump Map

What if you don’t have an ideal switch statement? Your next best bet would be a Jump Map. A jump map uses the STL container <map> instead of arrays. For single dimension, it would look like this:

For more than 1 dimension, it gets a bit tricky.

It’s not pretty but this allows non-consecutive, non-zero-based indices. Running time isn’t constant like the 2D arrays but log n * log n is still fast.