11.3 Double Switch-on-Type: Brute Force

The most straightforward approach to a double dispatch implementation is to implement a double switch-on-type. You try to dynamic cast the first object against each of the possible left-hand types in succession. For each branch, you do the same with the second argument. When you have discovered the types of both objects, you know which function to call. The code looks like this:

// various intersection algorithms


void DoHatchArea1(Rectangle&, Rectangle&);


void DoHatchArea2(Rectangle&, Ellipse&);


void DoHatchArea3(Rectangle&, Poly&);


void DoHatchArea4(Ellipse&, Poly&);


void DoHatchArea5(Ellipse&, Ellipse&);


void DoHatchArea6(Poly&, Poly&);





void DoubleDispatch(Shape& lhs, Shape& rhs)


{


   if (Rectangle* p1 = dynamic_cast<Rectangle*>(&lhs))


   {


      if (Rectangle* p2 = dynamic_cast<Rectangle*>(&rhs))


         DoHatchArea1(*p1, *p2);


      else if (Ellipse p2 = dynamic_cast<Ellipse*>(&rhs))


         DoHatchArea2(*p1, *p2);


      else if (Poly p2 = dynamic_cast<Poly*>(&rhs))


         DoHatchArea3(*p1, *p2);


      else


         Error("Undefined Intersection");


   }


   else if (Ellipse* p1 = dynamic_cast<Ellipse*>(&lhs))


   {


      if (Rectangle* p2 = dynamic_cast<Rectangle*>(&rhs))


         DoHatchArea2(*p2, *p1);


      else if (Ellipse* p2 = dynamic_cast<Ellipse*>(&rhs))


         DoHatchArea5(*p1, *p2);


      else if (Poly* p2 = dynamic_cast<Poly*>(&rhs))


         DoHatchArea4(*p1, *p2);


      else


         Error("Undefined Intersection");


   }


   else if (Poly* p1 = dynamic_cast<Poly*>(&lhs))


   {


      if (Rectangle* p2 = dynamic_cast<Rectangle*>(&rhs))


         DoHatchArea2(*p2, *p1);


      else if (Ellipse* p2 = dynamic_cast<Ellipse*>(&rhs))


         DoHatchArea4(*p2, *p1);


      else if (Poly* p2 = dynamic_cast<Poly*>(&rhs))


         DoHatchArea6(*p1, *p2);


      else


         Error("Undefined Intersection");


   }


   else


   {


      Error("Undefined Intersection");


   }


}

Whew! It's been quite a few lines. As you can see, the brute-force approach asks you to write a lot of (allegedly trivial) code. You can count on any dependable C++ programmer to put together the appropriate web of if statements. In addition, the solution has the advantage of being fast if the number of possible classes is not too high. From a speed perspective, DoubleDispatch implements a linear search in the set of possible types. Because the search is unrolled—a succession of if-else statements as opposed to a loop—the speed is very good for small sets.

One problem with the brute-force approach is sheer code size, which makes the code unmaintainable as the number of classes grows. The code just given deals with only three classes, yet it's already of considerable size. The size grows exponentially as you add more classes. Imagine how the code of DoubleDispatch would look for a hierarchy of 20 classes!

Another problem is that DoubleDispatch is a dependency bottleneck—its implementation must know of the existence of all classes in a hierarchy. It is best to keep the dependency net as loose as possible, and DoubleDispatch is a dependency hog.

The third problem with DoubleDispatch is that the order of the if statements matters. This is a very subtle and dangerous problem. Imagine, for instance, you derive class RoundedRectangle (a rectangle with rounded corners) from Rectangle. You then edit DoubleDispatch and insert the additional if statement at the end of each if-else statement, right before the Error call. You have just introduced a bug.

The reason is that if you pass DoubleDispatch a pointer to a RoundedRectangle, the dynamic_cast<Rectangle*> succeeds. Because that test is before the test for dynamic_cast<RoundedRectangle*>, the first test will "eat" both Rectangles and Rounded Rectangles. The second test will never get a chance. Most compilers don't warn about this.

A candidate solution would be to change the tests as follows:

void DoubleDispatch(Shape& lhs, Shape& rhs)


{


   if (typeid(lhs) == typeid(Rectangle))


   {


      Rectangle* p1 = dynamic_cast<Rectangle*>(&lhs);


      ...


   }


   else ...


}

The tests are now for the exact type instead of the exact or derived type. The typeid comparison shown in this code fails if lhs is a RoundedRectangle, so the tests continue. Ultimately, the test against typeid(RoundedRectangle) succeeds.

Alas, this fixes one aspect but breaks another: DoubleDispatch is too rigid now. If you didn't add support for a type in DoubleDispatch, you would like DoubleDispatch to fire on the closest base type. This is what you'd normally expect when using inheritance—by default, derived objects do what base objects do unless you override some behavior. The problem is that the typeid-based implementation of DoubleDispatch fails to preserve this property. The rule of thumb that results from this fact is that you must still use dynamic_cast in DoubleDispatch and "sort" the if tests so that the most derived classes are tried first.

This adds two more disadvantages to the brute-force implementation of multimethods. First, the dependency between DoubleDispatch and the Shape hierarchy deepens—DoubleDispatch must know about not only classes but also the inheritance relationships between classes. Second, maintaining the appropriate ordering of dynamic casts puts a supplemental burden on the shoulders of the maintainer.