Multiple
dispatching
The
above design is certainly satisfactory. Adding new types to the system consists
of adding or modifying distinct classes without causing code changes to be
propagated throughout the system. In addition, RTTI is not
“misused” as it was in
RecycleA.java.
However, it’s possible to go one step further and take a purist viewpoint
about RTTI
and say that it should be eliminated altogether from the operation of sorting
the trash into bins.
To
accomplish this, you must first take the perspective that all type-dependent
activities – such as detecting the type of a piece of trash and putting
it into the appropriate bin – should be controlled through polymorphism
and dynamic binding.
The
previous examples first sorted by type, then acted on sequences of elements
that were all of a particular type. But whenever you find yourself picking out
particular types, stop and think. The whole idea of polymorphism
(dynamically-bound method calls) is to handle type-specific information for
you. So why are you hunting for types?
The
answer is something you probably don’t think about: Java performs only
single dispatching. That is, if you are performing an operation on more than
one object whose type is unknown, Java will invoke the dynamic binding
mechanism on only one of those types. This doesn’t solve the problem, so
you end up detecting some types manually and effectively producing your own
dynamic binding behavior.
The
solution is called multiple
dispatching
,
which means setting up a configuration such that a single method call produces
more than one dynamic method call and thus determines more than one type in the
process. To get this effect, you need to work with more than one type
hierarchy: you’ll need a type hierarchy for each dispatch. The following
example works with two hierarchies: the existing
Trash
family and a hierarchy of the types of trash bins that the trash will be placed
into. This second hierarchy isn’t always obvious and in this case it
needed to be created in order to produce multiple dispatching (in this case
there will be only two dispatches, which is referred to as double
dispatching
).
Implementing
the double dispatch
Remember
that polymorphism can occur only via method calls, so if you want double
dispatching to occur, there must be two method calls: one used to determine the
type within each hierarchy. In the
Trash
hierarchy there will be a new method called
addToBin( ),
which takes an argument of an array of
TypedBin.
It uses this array to step through and try to add itself to the appropriate
bin, and this is where you’ll see the double dispatch.
The
new hierarchy is
TypedBin,
and it contains its own method called
add( )
that is also used polymorphically. But here’s an additional twist:
add( )
is
overloaded
to take arguments of the different types of trash. So an essential part of the
double dispatching scheme also involves overloading.
Redesigning
the program produces a dilemma: it’s now necessary for the base class
Trash
to contain an
addToBin( )
method. One approach is to copy all of the code and change the base class.
Another approach, which you can take when you don’t have control of the
source code, is to put the
addToBin( )
method into an
interface,
leave
Trash
alone, and inherit new specific types of
Aluminum,
Paper,
Glass,
and
Cardboard.
This is the approach that will be taken here.
Most
of the classes in this design must be
public,
so they are placed in their own files. Here’s the interface:
//: TypedBinMember.java
// An interface for adding the double dispatching
// method to the trash hierarchy without
// modifying the original hierarchy.
package c16.doubledispatch;
interface TypedBinMember {
// The new method:
boolean addToBin(TypedBin[] tb);
} ///:~
In
each particular subtype of
Aluminum,
Paper,
Glass,
and
Cardboard,
the
addToBin( )
method in the
interface
TypedBinMember
is implemented,, but it
looks
like the code is exactly the same in each case:
//: DDAluminum.java
// Aluminum for double dispatching
package c16.doubledispatch;
import c16.trash.*;
public class DDAluminum extends Aluminum
implements TypedBinMember {
public DDAluminum(double wt) { super(wt); }
public boolean addToBin(TypedBin[] tb) {
for(int i = 0; i < tb.length; i++)
if(tb[i].add(this))
return true;
return false;
}
} ///:~
//: DDPaper.java
// Paper for double dispatching
package c16.doubledispatch;
import c16.trash.*;
public class DDPaper extends Paper
implements TypedBinMember {
public DDPaper(double wt) { super(wt); }
public boolean addToBin(TypedBin[] tb) {
for(int i = 0; i < tb.length; i++)
if(tb[i].add(this))
return true;
return false;
}
} ///:~
//: DDGlass.java
// Glass for double dispatching
package c16.doubledispatch;
import c16.trash.*;
public class DDGlass extends Glass
implements TypedBinMember {
public DDGlass(double wt) { super(wt); }
public boolean addToBin(TypedBin[] tb) {
for(int i = 0; i < tb.length; i++)
if(tb[i].add(this))
return true;
return false;
}
} ///:~
//: DDCardboard.java
// Cardboard for double dispatching
package c16.doubledispatch;
import c16.trash.*;
public class DDCardboard extends Cardboard
implements TypedBinMember {
public DDCardboard(double wt) { super(wt); }
public boolean addToBin(TypedBin[] tb) {
for(int i = 0; i < tb.length; i++)
if(tb[i].add(this))
return true;
return false;
}
} ///:~
The
code in each
addToBin( )
calls
add( )
for each
TypedBin
object in the array. But notice the argument:
this.
The type of
this
is different for each subclass of
Trash,
so the code is different. (Although this code will benefit if a parameterized
type mechanism is ever added to Java.) So this is the first part of the double
dispatch, because once you’re inside this method you know you’re
Aluminum,
or
Paper,
etc. During the call to
add( ),
this information is passed via the type of
this.
The compiler resolves the call to the proper overloaded version of
add( ).
But
since
tb[i]
produces a handle to the base type
TypedBin,
this
call will end up calling a different method depending on the type of
TypedBin
that’s currently selected. That is the second dispatch.
Here’s
the base class for
TypedBin:
//: TypedBin.java
// Vector that knows how to grab the right type
package c16.doubledispatch;
import c16.trash.*;
import java.util.*;
public abstract class TypedBin {
Vector v = new Vector();
protected boolean addIt(Trash t) {
v.addElement(t);
return true;
}
public Enumeration elements() {
return v.elements();
}
public boolean add(DDAluminum a) {
return false;
}
public boolean add(DDPaper a) {
return false;
}
public boolean add(DDGlass a) {
return false;
}
public boolean add(DDCardboard a) {
return false;
}
} ///:~
You
can see that the overloaded
add( )
methods all return
false.
If the method is not overloaded in a derived class, it will continue to return
false,
and the caller (
addToBin( ),
in this case) will assume that the current
Trash
object has not been added successfully to a collection, and continue searching
for the right collection.
In
each of the subclasses of
TypedBin,
only one overloaded method is overridden, according to the type of bin
that’s being created. For example,
CardboardBin
overrides
add(DDCardboard).
The overridden method adds the trash object to its collection and returns
true,
while all the rest of the
add( )
methods
in
CardboardBin
continue
to return
false,
since they haven’t been overridden. This is another case in which a
parameterized type mechanism in Java would allow automatic generation of code.
(With C++
templates,
you wouldn’t have to explicitly write the subclasses or place the
addToBin( )
method in
Trash.)
Since
for this example the trash types have been customized and placed in a different
directory, you’ll need a different trash data file to make it work.
Here’s a possible
DDTrash.dat:
c16.DoubleDispatch.DDGlass:54
c16.DoubleDispatch.DDPaper:22
c16.DoubleDispatch.DDPaper:11
c16.DoubleDispatch.DDGlass:17
c16.DoubleDispatch.DDAluminum:89
c16.DoubleDispatch.DDPaper:88
c16.DoubleDispatch.DDAluminum:76
c16.DoubleDispatch.DDCardboard:96
c16.DoubleDispatch.DDAluminum:25
c16.DoubleDispatch.DDAluminum:34
c16.DoubleDispatch.DDGlass:11
c16.DoubleDispatch.DDGlass:68
c16.DoubleDispatch.DDGlass:43
c16.DoubleDispatch.DDAluminum:27
c16.DoubleDispatch.DDCardboard:44
c16.DoubleDispatch.DDAluminum:18
c16.DoubleDispatch.DDPaper:91
c16.DoubleDispatch.DDGlass:63
c16.DoubleDispatch.DDGlass:50
c16.DoubleDispatch.DDGlass:80
c16.DoubleDispatch.DDAluminum:81
c16.DoubleDispatch.DDCardboard:12
c16.DoubleDispatch.DDGlass:12
c16.DoubleDispatch.DDGlass:54
c16.DoubleDispatch.DDAluminum:36
c16.DoubleDispatch.DDAluminum:93
c16.DoubleDispatch.DDGlass:93
c16.DoubleDispatch.DDPaper:80
c16.DoubleDispatch.DDGlass:36
c16.DoubleDispatch.DDGlass:12
c16.DoubleDispatch.DDGlass:60
c16.DoubleDispatch.DDPaper:66
c16.DoubleDispatch.DDAluminum:36
c16.DoubleDispatch.DDCardboard:22
Here’s
the rest of the program:
//: DoubleDispatch.java
// Using multiple dispatching to handle more
// than one unknown type during a method call.
package c16.doubledispatch;
import c16.trash.*;
import java.util.*;
class AluminumBin extends TypedBin {
public boolean add(DDAluminum a) {
return addIt(a);
}
}
class PaperBin extends TypedBin {
public boolean add(DDPaper a) {
return addIt(a);
}
}
class GlassBin extends TypedBin {
public boolean add(DDGlass a) {
return addIt(a);
}
}
class CardboardBin extends TypedBin {
public boolean add(DDCardboard a) {
return addIt(a);
}
}
class TrashBinSet {
private TypedBin[] binSet = {
new AluminumBin(),
new PaperBin(),
new GlassBin(),
new CardboardBin()
};
public void sortIntoBins(Vector bin) {
Enumeration e = bin.elements();
while(e.hasMoreElements()) {
TypedBinMember t =
(TypedBinMember)e.nextElement();
if(!t.addToBin(binSet))
System.err.println("Couldn't add " + t);
}
}
public TypedBin[] binSet() { return binSet; }
}
public class DoubleDispatch {
public static void main(String[] args) {
Vector bin = new Vector();
TrashBinSet bins = new TrashBinSet();
// ParseTrash still works, without changes:
ParseTrash.fillBin("DDTrash.dat", bin);
// Sort from the master bin into the
// individually-typed bins:
bins.sortIntoBins(bin);
TypedBin[] tb = bins.binSet();
// Perform sumValue for each bin...
for(int i = 0; i < tb.length; i++)
Trash.sumValue(tb[i].v);
// ... and for the master bin
Trash.sumValue(bin);
}
} ///:~
TrashBinSet
encapsulates all of the different types of
TypedBins,
along with the
sortIntoBins( )
method, which is where all the double dispatching takes place. You can see that
once the structure is set up, sorting into the various
TypedBins
is remarkably easy. In addition, the efficiency of two dynamic method calls is
probably better than any other way you could sort.
Notice
the ease of use of this system in
main( ),
as well as the complete independence of any specific type information within
main( ).
All other methods that talk only to the
Trash
base-class interface will be equally invulnerable to changes in
Trash
types.
The
changes necessary to add a new type are relatively isolated: you inherit the
new type of
Trash
with its
addToBin( )
method, then you inherit a new
TypedBin
(this is really just a copy and simple edit), and finally you add a new type
into the aggregate initialization for
TrashBinSet.