Title: An Implementation of Double Dispatch in Java

Dynamic binding in an object oriented language means that method calls are bound at run-time. Therefore an object's dynamic type can be different from the static type at compilation time. In C++ each object has a virtual table also known as the vtable. This table contains pointers virtual methods. Java has a similar method table since all non-static methods within the Java language are virtual methods, by definition. Whenever a virtual method is invoked this vtable determines the method actually called at run-time.

For languages like C++ and Java only the class type of the receiving object determines the virtual table and thus the method that is invoked in the class virtual table. We say that Java and C++ are single dispatch languages. Sometimes there are certain sets of applications where it would greatly help if the actual virtual method selected is determined by looking at the types of two or even more classes. C++ and Java do not directly support this idea of multiple dispatch. There would be all sorts of permutations and difficulties for implementers if the Java and C++ language were to support multiple dispatching directly. Not to mention making sure that any new features are all backward compatible. (This is not to say that such an implementation is impossible.) There is one set of applications where object design would be simplified to a large degree if we could apply multiple dispatch techniques in both our favourite languages.

Most of you may be familiar with the concept of arcade video games. The games that you see out there in the real world, inside a shopping mall, or just down the road, around corner at your favourite pub, will have many moving sprite characters. You may see the two-dimensional platform style variety or, more likely in today's competitive games-console driven market, be entirely in three dimensions. There will be certainly a high degree of human user interaction, a tremendous amount of event-driven input, and visual feed back about the state of the game's engine. The action may be fast and furious, or it might be at slow leisurely (golfing) pace to suit a role-playing adventurer. Whatever the style of the game there will be definitely be interaction between various sprites that are interacting with computer generated characters.

Now let us suppose that we were writing our very own video game. Let us also assume our moving entities (Sprites) are represented as Java objects in a one-to-one design relationship in the video game. Sprites in our video game will collide with each other at some point in the game. It would be extremely useful to call a virtual method that is dependent on the dynamic type of at least two objects. Whenever a collision takes place between our sprites a method call is double-dispatched. (See Figure1 WorldObject object class UML below.)

Figure 1. WorldObject object class UML

One of the first things to do, in fact the easier task to complete before we get started, is to write the collision detection routines. We assume that we have a ready-made arcade GameEngine to hand. The engine controls the animation loop and how the game starts and ends. More importantly it manages the list of sprites in our game. We can add to and remove sprites from the game engine at any time. The engine is also responsible for displaying the sprite graphics on a window.

Figure 2. Sprite object class diagram (simplified)

Our comprehensive, but simple, game engine has a java.util.Vector that is container for the WorldObjects interacting in our game. The checkCollision() is O(N2) loop that checks if the rectangular boundaries of one sprite has intersected with the bounds of another sprite. Please ignore the fact that this is not the most efficient for-do-loop collision algorithm. If the condition tests true then we have a collision between two sprites. But the question is now, how do we implement collide?

Looking at the UML class design and knowing through inspection what the Java language provides we could run time type identification. A Naïve implementation of the double dispatch would use the instanceof reserved word and switching statement; namely the ubiquitous "if / then / elseif / then" series of compound statements. It is as if we were working backwards to come up the solution to writing a collision detection algorithm, which we are.

Figure 3. Much more comprehensive sprite object diagram

public class GameEngine {
  Vector spriteList;
  ...
  public void checkCollision() {
    Enumeration etor1 = spriteList.elements();
    Enumeration etor2 = spriteList.elements();
  ...
    while ( etor1.hasMoreElements() ) {
      Sprite sprite1 = 
              Sprite)etor.nextElement();
      rect1 = sprite1.getBounds();
      while ( etor2.hasMoreElements() ) {
        Sprite sprite2 = 
              (Sprite)etor.nextElement();
        if( sprite1 == sprite2 ) continue;
        rect2 = sprite2.getBounds();
        if ( rect1.intersects(rect2) ) {
// Help? Need double dispatch in Java
// collide(sprite1,sprite2);
        }
      }
    }
  }
  ...
}

public class Player {
  public void playerAlien(WorldObject p,
                      WorldObject a ){
    if(!(p instanceof Player && 
              a instanceof EnemyObject))
      return;
    Player player = (Player)p; 
    if( p instance Mantra )
                  player.playerDied();
    else if ( p instance Wriggler )
              player.increaseShields(-3);
    else if ( p instance Asteroid )
              player.increaseShields(-1);
// More code
  }
}

However, we know that a long list of switching compound statements is flawed design practice in the long run. This was what the concept of inheritance and virtual methods was supposed to help us avoid, after all. When the dispatch order of magnitude equals two, then handling the parameters is manageable. However, when the dispatch order is greater than two orders, it takes a whole lot more to code write a complete method that encompasses every single collision permutation. Plus the fact is there is a going be tremendous amount of code maintenance if we add several more characters to our game. Also note the difficulties involved, when the language does not support directly multiple-dispatching. Observe how ugly the type casting gets. It certainly is not ideal. The input parameters have to be in terms of the super class WorldObject. Additionally, before we could write such laborious code, even if we want to write it, we need find out the answer to a vital question: in which class do you place the double dispatch method? Does the playerAlien() method belong in the Player class or one of the many Alien classes? Or perhaps, more than reasonably likely, it belongs in neither class. [Editoral note from Mike Woolley: That's what happens in CLOS (the only language I'm familiar with that supports multiple dispatch). "Generic Functions" don't "belong" to any particular class.]

Instead of a convoluted series of if/then/else statements, let us use a table of method pointers, just like C++ implementations do with internal virtual method tables. Java allows us obtain a reference to the java.lang.Class object. The java.lang.Class class is a template for all Java object instances. Therefore, its Class object can identify the type of an object instance. The Class class has an instance method called getName() that returns a String object. This will be the class name and, of course, it is guaranteed to be unique (Assuming the class have been loaded through the same ClassLoader).^[1]

If we take a database approach to the double-dispatching problem it is apparent that we querying on to three columns that are primary keys. This table provides a huge clue to how double dispatch could be implemented! Each tuple of these data rows is guaranteed to be unique. The tool to hand is a basic associative array (java.util.Hashtable). We can combine the first two columns, the colliding (Sprite) class names, and combine both of them as the key into the Hashtable container. We store the method as the value in the Hashtable referring to it with our doctored key. But how do we store a method in Java? Are you thinking we should really use the Java Reflection API to get the java.lang.reflect.Method? Oh no, you don't! Although callbacks are great for C++ and C languages it can be shown that it is always better to use a class or interface to represent a callable method rather than a method itself, especially in Java. In fact the power of the interface concept allows us to declare a programming abstraction that directly conceptualizes what we are trying to achieve.

public interface CollisionListener {
  public void collisionDetected( 
    WorldObject obj1, 
    WorldObject obj2 );
}

The interface CollisionInterface contains a method that has a signature for a method that accepts two objects that have collided, where obj1 is the first object that collided and obj2 the second object that collided. All we need to do then is write functor objects that implement the CollisionDetected public method.

So instead of storing a method in our Hashtable we store a listener object, in the exact same fashion as a java.awt.ActionListener is registered with a java.awt.Button component. (It will be familiar to those of you who programmed with the Java Abstract Window Toolkit.) At registration we require the two classes to complete a key to store our CollisionListener value in the Hashtable.

The next listing shows the full source to a double dispatcher CollisionMapDispatcher. This Java class is a singleton object although it does not necessarily have to be one. An application can only get a reference to the dispatcher by calling the static method getInstance() since the constructor for the class is private. The interesting method is addCollisionListener that takes references to the two colliding classes and a CollisionListener. The method generates a key for the Hashtable by using an arbitrary separator string and puts the listener into the Hashtable using the key. The method called fireCollisionEvent() is exactly the method collide() that we were trying build in the example at the beginning of this article. It takes two object classes and builds a key with the separator string. If there is matching key in the Hashtable then that collision listener is called with the two-class parameter. Notice that there is a trivial search optimisation going on here. If there is no such value V in the Hashtable H for a key K(s1,s2) then try the key K(s2,s1). In other words a Player that collides with a Mantra has the same outcome as a Mantra that collides with Player: instant death of the Player. This is fine if the order of dispatch equals two and we don't care about of the order of the collision parameters.

public final class CollisionMapDispatcher { 
  private final static String SEPARATOR="<+>"; 
  private Hashtable map;
  
  private static CollisionMapDispatcher
 dispatcher = new CollisionMapDispatcher();

  private CollisionMapDispatcher() {
    map = new Hashtable();
  }

  public static 
  CollisionMapDispatcher getInstance(){
     return(dispatcher);
  }
  
  public void addCollisionListener( 
    Class class1, 
    Class class2, 
    CollisionListener listener){
// FIXME: should check the classes are
// WorldObject type.
    String s1 = class1.getName();
    String s2 = class2.getName();
    CollisionTuple tuple = 
      new CollisionTuple( s1, s2, listener);
    map.put( s1 + SEPARATOR + s2, tuple);
  }

  public void fireCollisionEvent(WorldObject obj1,
                    WorldObject obj2) {
    String s1 = obj1.getClass().getName();
    String s2 = obj2.getClass().getName();
    CollisionTuple tuple = 
    (CollisionTuple)map.get(
                     s1 + SEPARATOR + s2);
    if(tuple != null) {
// Call the collision listener object
    tuple.listener.collisionDetected(obj1,
                        obj2);
    }
    else {
// Reverse the order
    tuple =(CollisionTuple)map.get( 
                  s2 + SEPARATOR + s1);
    if(tuple != null) {
// Call the collision listener object
      tuple.listener.collisionDetected(obj2,
                          obj1);
    }
    else {
// throw new InternalError("cannot handle 
// collision between classes `"+ s1+"' and 
// `"+s2+"'");
      return;
    }
  }
}
// ---------------------------
// I N N E R  C L A S S E S
// ---------------------------
  private static class CollisionTuple {
     String objectClass1;
    String objectClass2;
    CollisionListener listener;

    public CollisionTuple(String class1,
                      String class2, 
             CollisionListener listener) {
      this.objectClass1 = class1;
      this.objectClass2 = class2;
      this.listener = listener;
    }
  }
}

The CollisionMapDispatcher uses a private inner class to store a tuple (all of the columns of data to make up one row of data in a relational database table). Now that we have our double dispatcher we can use it directly in our video game application.

public class CollisionHandler {
  public final static EmptyListener
      EMPTY_LISTENER = new EmptyListener();
  private CollisionMapDispatcher dispatcher
     = CollisionMapDispatcher.getInstance();
  public static void starshipAndAlien( 
  WorldObject player, WorldObject alien)   {
// Player crashed into a Mantra; instant death

    Player p =(WorldObject)Player;
    p.playerDied();
    p.destroy();
    alien.destroyed();
  }
  ...
  public static void registerAllCollisions(){
    dispatcher.addCollisionListener(
        Player.class, Mantra.class,
        new CollisionListener() {
          public void collisionDetected( 
                     WorldObject obj1,
                   WorldObject obj2) {
            playerAndAlien( obj1, obj2);
          }
        } );
  ...
// More collisions registered here
  }
// ---------------------------
// I N N E R  C L A S S E S
// ---------------------------
  public static class EmptyListener 
  implements CollisionListener {
    public void collisionDetected( 
       WorldObject obj1, WorldObject obj2) {
// Do nothing
    }
  }
}

The most confusing aspect of the above code is in the registerAllCollision() method. We are creating in-line Java object classes, here, so called anonymous class. The Java compiler builds an unnamed object that implements the CollisionListener interface and has, by definition a public collisionDetected() method. This method is a wrapper that calls the handler's static collision method. The long-winded less efficient implementation would be functionally equivalent to the following code:

public class CollisionHandler {
    ...
    public static void registerAllCollisions(){
      dispatcher.addCollisionListener(
        Player.class, Mantra.class,
        new __JavaC_Anonymous_450971() );
// More collisions registered here ...
    }
// Compiler made up
    private class __JavaC_Anonymous_450971
    extends Object
    implements CollisionListener(){
      public void collisionDetected( 
       WorldObject obj1, WorldObject obj2 ){
            playerAndAlien( obj1, obj2 );
      }
    }
    ...
}