looking for a c++ design pattern

i am looking for a c++ design pattern that should deal with the next scenario :
there are few objects
Rectangle , Triangle , Circle etc ...
all derived from AbstractShape class
these objects should be used in a generic algorithem
( using * AbstractShape )
and answer the question whether two objects collides.
I looked through the design patterns book and didn't find anything suitable.

Who is Participating?
There is a procedure called double dispatching that does this, but it has the limitation that the class hierarchy has to be "defined" at the base.  i,e, when you add a class to the hierarchy, you have to change the base class and all other classes.  (Which makes it unsuitable for library development.)

details follow.
Provide each class with a virtual function that "fills in" their shape, that is, it fills a rectangular array of bool (or something) with values that indicate the positions it occupies and doesn't occupy.  Use this procedure to fill in two such arrays (one for each object that you are testing).  Then look to see if there is any position that is present in both objects.

Let me know if you have any questions.
hedAuthor Commented:
I might misexplained my question.
the collide is just an example of an interaction between two
The design pattern is needed for getting to the correct function
based on two object types ( instead of just one as in virtual ).
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Lets stick with your example of shapes, it is a good one.  The base class would need the following virtual functions that all the classes would have to define.  (I'm using the term intersect, rather than collide).

virtual bool Intersect(const Shape &S);
virtual bool IntersectWithRect(const Rectangle &S);
virtual bool IntersectWithTriangle(const Triangle &S);
virtual bool IntersectWithCircle(const Circle &S);

Now lets follow an example to see how this helps, we begin with two objects, derived from shape, but we don't "know"  what shape they are, we just know they are shapes.  So we can't call IntesectwithXXXXX, because we don't know if either of them is a rect, triangle or circle.  so instead, we call the generic intersect, Intersect()  That is we do.

bool B = Shape1.Intersect(Shape2);

That is a virtual function that each class overides.  So that function "takes us" to one of three functions, either "Rectangle::Intersect()", "Circle::Intersect()", or "Triangle::Intersect()".  In other words,  Inside the function we reach, we know what one of the shapes is.  The shape for which the function was called, is know because of the virtual function.  Make sense?  

Now that was the first dispatch and it resolved the first object type.  But we still don't know what the parameter is.  It is an unknown shape.  For example, we might now know that shape1 is a rectangle, but shape2 is not known so we still can't decide if they intersect.  A second dispatch is needed.  Since we know that "this" is a rectangle (or other specific shape).  We can call one of the "specific" intersection functions with the "object and parameter reversed"  i.e in Rectangle::Intersect() we do.


(This is reversing which object was "the this object" and whichh was the parameter in the first dispatch.)  The function that is called will be able to handle the intersection calculation, because it will "know" what it is and it wil "know:" what the parameter is.  Make sense?

This is actually only the tip of the Iceburg, you can have highler levels of dispatch, like triple or qaudruple dispatch, but it begins to lead to many functions.  It is a good technique for simple cases with small numbers of classes and to which you know there will be no need to add future classes.

hedAuthor Commented:
truth is i"ve known this method ( didn't know it was named double dispatch )
I thaught maybe i"ll get some other ideas. ( it has some flaws this method )

Double dispatch is the only method that I've ever seen that can be applied to any problem where you need an algorithm that depends on the types of two operands.  For some problems there may be better algorithms, but none (that I'm aware of) that can be applied to any problem.
I would say this, If there are other (general) techniques, I feel certain they would also have the same weaknesses that double dispatch does.  Namely that the classes would have to have code that would work with specific members of the class hierarchy, thus making it harder to add new members to the class hierarchy.  That limitation can't be removed in general.  It can be removed for certain problems and that often leads to improved algorithms.  (Take my first solution for example.  In terms of computer efficiency it is not likely to be an improvement, but in terms of the ease in which new classes can be added, it is an improvement.)
hedAuthor Commented:
theoretically. what we are looking for is some sort of a double indexed virtual table.
i havn't given it taught, but it seems feasable to implement in an imaganary programming language.
and if it's feasble that way it can be programmed in C++ as well.
but i agree it hell of an overkill.
Essentually that is what double dispatch gives you.  Conceptually the VT it provides is a 2D array instead of a 1D array.  The first dispatch seems to pick a row of the 2D table, actually what it is doing is picking the 1D table of one of the objects.  Then the 2nd dispatch picks the final function from the row.  Now the language could provide a mechansim that did the double dispatching, that is, it could allow for functions that are virtual based on two types, but that doesn't really improve things, because you are still stuck with the problem that if a new class is added, functions need to be added to the existing classes.  That is inherent in the problem.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.