Here's a question for all of you programming gurus to figure out:

I have a class, called Shape, which is the base for lots of other classes.  For some combinations of those types, I have defined interactions:

void Foo(ShapeChild1,ShapeChild2);
void Foo(ShapeChild1,ShapeChild3);
void Foo(ShapeChild1,ShapeChild4);
void Foo(ShapeChild3,ShapeChild4);

I have an interface function that takes two Shape objects as its parameters:

void Foo(Shape,Shape);

Q: What is an easy, readable, and runtime-efficient way to have Foo(Shape,Shape) figure out which of the implementations to call based on the types of the arguments?  That is, if the first Shape happens to actually be a ShapeChild1 and the second is a ShapeChild4, then I want Foo(Shape,Shape) to call Foo(ShapeChild1,ShapeChild4).

Restrictions:
1) I need to support the ability to extend this library to include new
Shape* classes...without changing the interface function
Foo(Shape,Shape).  So hard coding nested switches is NOT going to work.
2) I need to automatically detect (and throw an exception) if
Foo(Shape,Shape) is called and there is no implementation for a given
pair.  It would be even better if I could determine at init time that
there were some implementations missing.
3) I need to be able to support multiple add-ons to the library which
might not know about each other.  So making a requirement that "all
addons must know about all previous shapes" won't be workable.

Thoughts, guys?  I have come up with any number of inelegant solutions...I figure that somebody here has a better one.

Russ

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]

Russ Lewis wrote:
> Here's a question for all of you programming gurus to figure out:
> 
> I have a class, called Shape, which is the base for lots of other
> classes.  For some combinations of those types, I have defined
> interactions:
> 
> void Foo(ShapeChild1,ShapeChild2);
> void Foo(ShapeChild1,ShapeChild3);
> void Foo(ShapeChild1,ShapeChild4);
> void Foo(ShapeChild3,ShapeChild4);
> 
> I have an interface function that takes two Shape objects as its
> parameters:
> 
> void Foo(Shape,Shape);

[snip]

> Thoughts, guys?  I have come up with any number of inelegant
> solutions...I figure that somebody here has a better one.
> 
> Russ

Isn't this just a multi-method?  I doubt that there is any nice implementation in D, or C++.  We're stuck with emulating them.

I'm basically against adding them to D.  I've looked around a bit on the web, and haven't been convinced that D needs multimethods.  If you're intersted, I've commented on what I found in a couple hours of browsing.

-----------------------------------------

Multi-methods have been added to several statically compiled languages, including C++, Java, and Perl.  IMO, advocates seem to have polymorphism fevor.  Here's a web page that seems to exemplify this:

http://www.yetanother.org/damian/seminars/Multimethods.html

However, in a couple hours of searching, I couldn't find any major problems where multimethods are the only solution, or IMO the best solution.

I checked a few intro pages to the language mentioned extensions above.  I found two examples used.

The first one problems mentioned was shape merging, where we want custom merge routines for merging squares and polygons, triangles and squares, etc.  Given N shape types, you can write N*N merge routines, and call them as a multimethod.  A better solution would be to convert all shapes to a generic type (for example, a polygon), write one merge routine, and then write routines to convert them back.  That takes 2N+1 functions. If speed is the reason we're writing custom functions, then we probably need custom dispatch code as well.  For example, if 99% of our shapes are rectangles (as is the case in EDA), you want to check for merging two rectangles first.

The second problem mentioned was reading many types of documents (PDF, postscript, MS Word, etc), and rendering on multiple kinds of devices (printer, screen, ...).  Writing custom routines for each of these combinations is a terrible idea.  Anyone remember when each company writing DOS applications had to write custom printer drivers for each printer, as well as a custom screen driver?  What a nightmare.  Again, the solution is converting to a generic format (a bitmap, for example), and then writing the single format to each device.

Digging a bit deeper, I found nice papers on efficient multimethod implementations.  I looked for a "motivation" section in them, and found one for extending Java:

"Java allows a new subclass to be added to an existing class in a modular way without requiring any modifications to existing code. However, Java (along with all other single-dispatch languages of which we are aware) does not allow a new method to be added to an existing class in a modular way."

That's valid concern, but it's also solvable in other ways.  For one, we can have "compile-time reflection classes" (as the OpenC++ guyes call it).  Alternatively, we could add an extension capability that allows us to add methods to classes in separate source files.  This capability has other uses as well.

Another problem mentioned in several places is the "visitor" problem.
It seems to be a problem that comes up in visiting complex class hierarchies in Java and C++.  I read a short presentation on this problem, and at the end they suggested that another aproach to solving it is to write iterators that take call-back functions as parameters. If this seems ugly, then add enhanced iterator support so we can eliminate the call-backs.

Another problem with multi-methods is they seem very complex to implement and support in statically compiled languages.  I found multiple papers on the web describing novel ways to overcome obscure problems that come up.  It looks really hairy.

In short, the little bit of poking around I've done hasn't led me to believe multimethods belong in D.

Bill

The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes.  The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.)

It is computationally impractical to convert complex 4D shapes into polygons.  The two shapes might never intersect; they might intersect but far in the future.  Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me.

The solution, as I see it, is to work out mathematical formulas for each pair of types.  I can do that, though it will be hard.

Now, I have to figure out how to use the right formula for each pair of types.



One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both.  But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.

That's funny;  this is exactly what Geometric Algebra is good for.  Just add another dimension that squares to -1 to represent the time axis.  For shapes such as spheres and planes you need 4 dimensions.  So at minimum you're working on a 5D problem.

But GA has these nifty meet and join operations that make the intersection almost trivial to compute once you have the shapes represented as multivectors of some sufficiently high dimension.

http://www.iancgbell.clara.net/maths/geoalg1.htm#A33

If it were possible to represent any of your shapes as an array of multivectors, and were ok with getting arbitrary multivectors back, it could potentially be done with a single routine.

Sean

"Russell Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:3E6E16FD.2000600@deming-os.org...
> The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes.  The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.)
>
> It is computationally impractical to convert complex 4D shapes into polygons.  The two shapes might never intersect; they might intersect but far in the future.  Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me.
>
> The solution, as I see it, is to work out mathematical formulas for each pair of types.  I can do that, though it will be hard.
>
> Now, I have to figure out how to use the right formula for each pair of types.
>
>
>
> One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both.  But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.

Russell Lewis wrote:
> The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes.  The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.)
> 
> It is computationally impractical to convert complex 4D shapes into polygons.  The two shapes might never intersect; they might intersect but far in the future.  Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me.
> 
> The solution, as I see it, is to work out mathematical formulas for each pair of types.  I can do that, though it will be hard.
> 
> Now, I have to figure out how to use the right formula for each pair of types.
> 
> 
> 
> One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both.  But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.
> 

Ok, sounds like a real application for multimethods.  Frankly, I'd just write a big if-then-else statement by hand to do the dispatch.  Any programmer reading it will understand it right away, and maintaining it is not hard compared to writing all the functions.  To get better speed, you could do a switch on a combination of the enumerated types, although that's pretty ugly.  It C++, it would look something like:

switch((typeA << SHAPE_TYPE_BITS) | typeB) {
case SHAPE_A | SHAPE_A: return findIntersections((ShapeA *) a, (ShapeB *) b);
...
}

Bill

Russell Lewis wrote:
> One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both.  But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.

But common - the rigid-body physics library ODE does this.  You can just use ClassInfo:

   typedef Intersection delegate(Shape a, Shape b) Intersector;
   static Intersector[ClassInfo][ClassInfo] intersectList;

   static void registerIntersector(ClassInfo a, ClassInfo b, Intersector i)
   {
      intersectList[b][a] = i;
   }

   Intersection intersect(Shape other)
   {
      assert(other.classinfo in intersectList);
      assert(this.classinfo in intersectList[other.classinfo]);
      return intersectList[other.classinfo][this.classinfo];
   }

I'm on the fence.  This is a helluva painful problem when it comes up, but it's also hard to think of any solution that would envelope a broad selection of its problem scope - my criteria would be incompatible to your own, in fact.  When that happens, it indicates to me that the problem is trying to be solved at too high a level.  Bringing it down a level lands me at associative arrays of delegates with ClassInfo, with a set of functions for best-match searching - which can be implemented with my templating syntax:

   /* Breadth-first multimethod search for two arguments. */
   $Type multimethodSearch($Type[ClassInfo][ClassInfo] list, Object a, Object b)
   {
       ClassInfo ca;
       ClassInfo cb = b.classinfo;
       int bestDistance = -1;
       $Type best;
       int distance;

       for ( ; cb !== null; cb = cb.superclass, distance ++)
       {
          if (!(cb in list))
             continue;

          $Type[ClassInfo] sublist = list[cb];
          int adding;

          for (ca = a.classinfo; ca !== null; ca = ca.superclass, adding ++)
             if (ca in sublist && (bestDistance == -1 || distance + adding < bestDistance))
             {
                 bestDistance = distance + adding;
                 best = sublist[ca];
                 break;
             }
       }

       if (bestDistance == -1)
          throw new Error(a.classinfo.name ~ " and " ~ b.classinfo.name ~ " have no matching method.");
       return best;
   }

   $RType multimethodSearchCall($RType delegate($AType a, $BType b)[ClassInfo][ClassInfo] list, $AType a, $BType b)
   {
       return multimethodSearch(list, a, b)(a, b);
   }

   ...
   return multimethodSearchCall(intersectList, this, other);

Scott Meyers gives a nice overview of this issue in "More effective C++"
Item 31: "Making functions virtual w.r.t. more than one object"
See e.g. http://www.paulgrenyer.co.uk/accu/mdevelopers/effectivecpp/, but
for actual contents you need to buy the book. I have it, it's quite nice

"Sean L. Palmer" wrote:

> That's funny;  this is exactly what Geometric Algebra is good for.  Just add another dimension that squares to -1 to represent the time axis.  For shapes such as spheres and planes you need 4 dimensions.  So at minimum you're working on a 5D problem.
>
> But GA has these nifty meet and join operations that make the intersection almost trivial to compute once you have the shapes represented as multivectors of some sufficiently high dimension.

> http://www.iancgbell.clara.net/maths/geoalg1.htm#A33
>
> If it were possible to represent any of your shapes as an array of multivectors, and were ok with getting arbitrary multivectors back, it could potentially be done with a single routine.

The page is incredibly dense.  The background doesn't make things too easy to read, either.  Do you know of another, slower paced, intro to the subject?

I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types.  I certainly plan to use that in the Shape* class that handes ellipsoids.  This multivector thing sounds like the same general idea, but generalized to N dimensions.  Is that a fair analysis?

In what way are multivectors different from transform matrices?  Those, too, were sets of orthogonal vectors in a space.

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]

Russ Lewis wrote:

> I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types.

(I've also already done some research into using 5x5 matrices to model spheres & ellipsoids that move or change size over time...)

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]

From what I understand, a 5x5 matrix would be quite overspecified.

Here's a very gentle intro to some basic GA concepts:

http://sinai.mech.fukui-u.ac.jp/gcj/software/GAcindy/GAcindy.htm

And here's something about your speed:

http://carol.wins.uva.nl/~leo/clifford/sommer.pdf

There is plenty of material on the web about GA.

I haven't tackled your problem but what I've read suggests this is what GA is good at.

Check out Gaigen or boost::clifford if you want to do your own experiments.

Sean


"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:3E6F53E6.993E07A4@deming-os.org...
> Russ Lewis wrote:
>
> > I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types.
>
> (I've also already done some research into using 5x5 matrices to model
spheres &
> ellipsoids that move or change size over time...)