Solved

looking for a c++ design pattern

Posted on 1999-01-18
9
242 Views
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.

0
Comment
Question by:hed
  • 6
  • 3
9 Comments
 
LVL 22

Expert Comment

by:nietod
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.
0
 

Author Comment

by:hed
ID: 1184446
I might misexplained my question.
the collide is just an example of an interaction between two
objects.
The design pattern is needed for getting to the correct function
based on two object types ( instead of just one as in virtual ).
0
 
LVL 22

Accepted Solution

by:
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.
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

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.

 
LVL 22

Expert Comment

by:nietod
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.

S.IntersectWithRect(*this);

(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.

Questions?
0
 

Author Comment

by:hed
ID: 1184449
thanks.
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 )

0
 
LVL 22

Expert Comment

by:nietod
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.
0
 
LVL 22

Expert Comment

by:nietod
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.)
0
 

Author Comment

by:hed
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.
0
 
LVL 22

Expert Comment

by:nietod
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.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

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.

Question has a verified solution.

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

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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 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.

861 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