looking for a c++ design pattern

Posted on 1999-01-18
Last Modified: 2010-04-16
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.

Question by:hed
  • 6
  • 3
LVL 22

Expert Comment

ID: 1184445
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.

Author Comment

ID: 1184446
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 ).
LVL 22

Accepted Solution

nietod earned 50 total points
ID: 1184447
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.
ScreenConnect 6.0 Free Trial

Discover new time-saving features in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI, app configurations and chat acknowledgement to improve customer engagement!

LVL 22

Expert Comment

ID: 1184448
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.


Author Comment

ID: 1184449
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 )

LVL 22

Expert Comment

ID: 1184450
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.
LVL 22

Expert Comment

ID: 1184451
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.)

Author Comment

ID: 1184452
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.
LVL 22

Expert Comment

ID: 1184453
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.

Featured Post

Simplifying Server Workload Migrations

This use case outlines the migration challenges that organizations face and how the Acronis AnyData Engine supports physical-to-physical (P2P), physical-to-virtual (P2V), virtual to physical (V2P), and cross-virtual (V2V) migration scenarios to address these challenges.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question