Improve company productivity with a Business Account.Sign Up


looking for a c++ design pattern

Posted on 1999-01-18
Medium Priority
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 200 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.
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

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.

Join & Write a Comment

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…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

606 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