The most elegant way to get around this polymorphism question

Question

EDIT: I work with C ++.

So, I create methods / functions for checking intersection between shapes. I have it:

class Shape {}; class Rectangle : public Shape {}; class Circle : public Shape {}; class Line : public Shape {}; 

Now I need to decide how best to write the actual methods / functions for checking the intersection. But all my figures will be saved in the list of Shape pointers, so I will call the method / function of the base shape:

 bool intersects (Shape* a, Shape* b); 

At this point, I need to determine which types of shapes are “a” and “b,” so I can correctly detect collisions. I can easily do one of them simply using some virtual methods:

 class Shape { virtual bool intersects (Shape* b) = 0; } 

This will define one of the forms (now 'a' 'this'). However, I still need to get type "b". The obvious solution is to give Shape the variable 'id' to classify which shape it is, and then “switch” through these and then use dynamic_cast. However, it is not very elegant, and it seems that this requires more OO features.

Any suggestions?

Answer 1

As @Mandarse pointed out, this is a typical dual submit problem. In object-oriented languages ​​or in C ++ languages ​​that can implement object-oriented concepts, this is usually solved using the Visitor Pattern.

The Visitor interface itself defines one callback for a particular type.

 class Circle; class Rectangle; class Square; class Visitor { public: virtual void visit(Circle const& c) = 0; virtual void visit(Rectangle const& r) = 0; virtual void visit(Square const& s) = 0; }; 

Then the Shape hierarchy is adapted for this. We need two methods: one to receive any type of visitor, the other to create a “suitable” visitor intersection.

 class Visitor; class Intersecter; class Shape { public: virtual void accept(Visitor&) const = 0; // generic virtual Intersecter* intersecter() const = 0; }; 

Intersector is simple:

 #include "project/Visitor.hpp" class Intersecter: public Visitor { public: Intersecter(): result(false) {} bool result; }; 

For example, for Circle this will give:

 #include "project/Intersecter.hpp" #include "project/Shape.hpp" class Circle; class CircleIntersecter: public Intersecter { public: explicit CircleIntersecter(Circle const& c): _left(c) {} virtual void visit(Circle const& c); // left is Circle, right is Circle virtual void visit(Rectangle const& r); // left is Circle, right is Rectangle virtual void visit(Square const& s); // left is Circle, right is Square private: Circle const& _left; }; // class CircleIntersecter class Circle: public Shape { public: virtual void accept(Visitor& v) const { v.visit(*this); } virtual CircleIntersecter* intersecter() const { return new CircleIntersecter(*this); } }; 

And use:

 #include "project/Intersecter.hpp" #include "project/Shape.hpp" bool intersects(Shape const& left, Shape const& right) { boost::scope_ptr<Intersecter> intersecter(left.intersecter()); right.accept(*intersecter); return intersecter->result; }; 

If other methods need a double dispatch mechanism, all you have to do is create another class like Intersecter that wraps the result and inherits from Visitor and the new Factory method embedded in Shape , which is overridden by derived classes to provide corresponding operation. It is a little long, but it works.

Note: it is reasonable to exclude intersect(circle, rectangle) and intersect(rectangle, circle) to get the same result. You can encode the code using some methods and have CircleIntersecter::visit delegates for a specific implementation. This avoids code duplication.

Answer 2

Andrei Alexandrescu described this issue in detail in his classic C ++ Modern Design . The Loki companion library contains an implementation for several methods .

Update

Loki provides three implementations of Multi-Methods, depending on the needs of the user. Some are designed for simplicity, some for speed, some are good for low grip, and some provide more security than others. The chapter in the book covers about 40 pages, and it is assumed that the reader is familiar with many concepts of the book - if it is convenient for you to use boost, then Loki may be along your alley. I really can't give this an acceptable SO answer, but I pointed you to a better explanation of the C ++ topic that I know of.

Answer 3

C ++ run-time polymorphism has one dispatch (vtable base class).

There are various solutions to your problem, but none of them are "elegant" because they all try to get the language to do more than it can support (Alexandrescu Loki multimethods is a very well hidden set of hacks: it encapsulates "bad things", but not doing well then)

The concept here is that you need to write all the functions of N ² possible combinations and find a way to call them based on the actual type of the TWO type of runtime. The “visitor pattern” (calling a virtual link from another virtual function), the “mutimethod” technique (use the shared dspatch table), the “dynamic conversion” to a virtual function, or the “dual dynamic_cast” of all functions all do the same thing: call the function after two indirect actions. None of them can technically be defined as “better than the other,” since the resulting performance is basically the same.

But some of them cost more than others in writing code, while others are more expensive to maintain code. Most likely, you will try to assess in your case what a compromise is. How many other classes do you think you need to add in the future?

Answer 4

You can add a shapeType field to each Shape

For example:

 class Shape { virtual shapetype_t getShapeType() const; // ... }