Advanced improvement

[Danil]

We can improve initial solution:
- dispatchers can be generated from typelists.
- no dynamic memory allocation (via new or malloc) is performed during
multimethod call.

Example is provided below:

/*
Copyright (C) 2004
Danil G. Shopyrin

Permission to use, copy, modify, distribute and sell this software
and its documentation for any purpose is hereby granted without fee,
provided that the above copyright notice appear in all copies and
that both that copyright notice and this permission notice appear
in supporting documentation. Danil G. Shopyrin makes no
representations
about the suitability of this software for any purpose.
It is provided "as is" without express or implied warranty.

MultiMethods Implementation via Deferred Dispatcher Generation

Danil Shopyrin
Special thanks to:
- Alexander Evdokimov
- Michael Litvinov

Below you can find a solution to a well known problem of multimethods.
It will be demonstrated using famous "crossing shapes example".

This solution is an improved version of "MultiMethods Implementation
via
Deferred Dispatching". (The idea of this improvement is provided by
Michael Litvinov). In this solution Dispatcher_ is generated from
typelist
that contains types of used shapes.

The main merits of the proposed solution are:
- no use of type casts of any kind (dynamic, static, reinterpret,
const or C-style);
- no use of RTTI;
- no use of preprocessor;
- strong type safety;
- constant time of multimethod execution (two virtual method calls
plus trivial constructor);
- no dynamic memory allocation (via new or malloc) is performed
during multimethod call;
- compiler doing all the work;
- use of only standard C++ features.

This approach makes it possible for user to write quite readable code.
Suppose, we have the following hierarchy of shapes:

---- Shape_ ------
| | |
Circle_ Rect_ Triangle_
|
Square_

Then user can write code like this:
Shape_* circle = new Circle_( Point_( 5, 5 ), 3 );
Shape_* rect = new Rect_( Point_( 5, 5 ), Point_( 10, 10 ) );
bool cross1 = circle->Cross( rect );
bool cross2 = rect->Cross( circle );

Multimethod is called in following form:
(arg0)->Cross( arg1 )
where types of both arg0 and arg1 (TArg0 and TArg1, respectively) are
unknown at compile time.
At runtime the TArg0 type is detected via virtual method call (method
Cross) and the TArg1 -
via use of 'deferred dispatching' pattern (Visitor-like pattern, where
nodes can be declared
independently of visitor).

User is responsible for providing implementation of crossing detection
code
for situations where types TArg0 and TArg1 are known.
Implementations are provided in the form of template class
specialization.
For example:
template <>
struct Crossing_< Circle_, Rect_ >
{
//implementation
};

One can provide some (or all) of the following:
- fully specialized versions of Crossing_ (circles against
rectangles, for example),
- symmetric versions of Crossing_ (rectangles against circles via
circles against rectangles crossing, for example),
- hierarchy depended versions (crossing of two rectangular shapes,
for example),
- fully specialized homogeneous versions (crossing of two circles,
for example),
- etc.

The details are provided below in the form of well-commented code.
Keep in mind that some obvious improvements are missed to keep
readability.

Dependencies:
- standard compliant C++ compiler,
- boost-1.30.2.

*/

//we need some Boost classes
#include <boost/mpl/if.hpp>
#include <boost/mpl/list.hpp>
#include <boost/mpl/insert.hpp>

#include <boost/type_traits.hpp>

//we need std::auto_ptr
#include <memory>

//Deferred Dispatchers Generator

//Elementary unit of deferred dispatcher interface
template <typename TArg1>
struct IDispatchPart_ {
virtual bool Dispatch( TArg1& _arg1 ) = 0;
};

/*
Interface of deferred dispatcher.
When some IDispatcher_<TShapes> instantiated and
TShapes is boost::mpl::list<T0, T1,...>,
the following hierarchy is generated:

IDispatcher_<boost::mpl::null_node>
..../
/
IDispatchPart_<T1> /
| /
IDispatcher_<TShapes::next>
/
IDispatchPart_<T0> /
| /
IDispatcher_<TShapes>
*/
template <typename TShapes>
struct IDispatcher_
: public IDispatchPart_< typename TShapes::item >
, public IDispatcher_< typename TShapes::next > {};

//Deferred dispatcher interface stub.
template <>
struct IDispatcher_< boost::mpl::null_node > {};

/*
Implementation of deferred dispatcher.
Each DispatcherImpl_<TShapesNode, TShapes, TArg0> implements
method Dispatch() for TShapesNode::item type and inherited from
DispatcherImpl_<TShapesNode::next, TShapes, TArg0>.
*/
template < typename TShapesNode, typename TShapes, typename TArg0 >
class DispatcherImpl_
: public DispatcherImpl_< typename TShapesNode::next, TShapes, TArg0
>
{
typedef DispatcherImpl_< typename TShapesNode::next, TShapes, TArg0
> TBase;
typedef typename TShapesNode::item TArg1;

virtual bool Dispatch( TArg1& _arg1 ) {
return Crossing_< TArg0, TArg1 >::TImpl::Crossing(
TBase::GetArg0(), _arg1 );
}
protected:
DispatcherImpl_( TArg0& _arg0 ) : TBase( _arg0 ) {}
};

/*
Deferred dispatcher implementation stub.
This stub inherited from IDispatcher_< TShapes >.
*/
template < typename TShapes, typename TArg0 >
class DispatcherImpl_<boost::mpl::null_node, TShapes, TArg0 >
: public IDispatcher_< TShapes >
{
TArg0& arg0;
protected:
TArg0& GetArg0() { return arg0; }

DispatcherImpl_( TArg0& _arg0 ) : arg0( _arg0 ) {}
};

/*
Deferred dispatcher.
When some Dispatcher_<TShapes, TArg0> instantiated
the following hierarchy is generated:

IDispatcher_< TShapes >
|
DispatcherImpl_< boost::mpl::null_node, TShapes, TArg0 >
|
...
|
DispatcherImpl_< TShapes::next, TShapes, TArg0 >
|
DispatcherImpl_< TShapes, TShapes, TArg0 >
|
Dispatcher_<TShapes, TArg0>
*/
template < typename TShapes, typename TArg0 >
class Dispatcher_ : public DispatcherImpl_< TShapes, TShapes, TArg0 >
{
typedef DispatcherImpl_< TShapes, TShapes, TArg0 > TBase;
public:
Dispatcher_( TArg0& _arg0 ) : TBase( _arg0 ) {}
};

// This is a very unimportant class used only for demonstration
purposes.
class Bitmap_ {};

/*
The base class of our shapes hierarchy.
ShapeNode_ is a base class for nodes in our 'deferred dispatching'
pattern
*/
template < typename TShapes >
class ShapeNode_
{
public:
//Dispatch facility
virtual bool Accept( IDispatcher_<TShapes>& _dispatcher ) = 0;

//This is a multimethod gateway!!!
virtual bool Cross( ShapeNode_<TShapes>& _shape ) = 0;

// This is a very unimportant method used only for demonstration
purposes.
virtual Draw( Bitmap_& _bmp, int _color ) = 0;
};

// This is a very unimportant class used only for demonstration
purposes.
struct Point_ {
int x;
int y;

Point_() : x( 0 ), y( 0 ) {}
Point_( int _x, int _y ) : x( _x ), y( _y ) {}
};

//Implementation of Circle_
//Circle_ is a concrete node in our 'deferred dispatching' pattern
template < typename TShapes >
class CircleNode_
: public ShapeNode_< TShapes >
{
typedef CircleNode_<TShapes> TSelf;

Point_ center;
int radius;
public:
//useful constructor for circles
CircleNode_( Point_ const& _center, int _radius ) : center( _center
), radius( _radius ) {}

//useful accessors
const Point_& GetCenter() { return center; }
int GetRadius() { return radius; }

//dispatching (see Visitor pattern)
virtual bool Accept( IDispatcher_<TShapes>& _dispatcher ) {
IDispatchPart_<TSelf>& dpart = _dispatcher;
return dpart.Dispatch( *this );
}

//Here we know TArg0 type and have Dispatcher_ that can determine
TArg1 type.
virtual bool Cross( ShapeNode_<TShapes>& _shape ) {
Dispatcher_< TShapes, TSelf > disp( *this );
return _shape.Accept( disp );
}

// This is very unimportant method. Used only in demonstrative
goals.
virtual Draw( Bitmap_& /*_bmp*/, int /*_color*/ ) { /*draw circle*/
}
};

//You can skip declarations of RectNode_, SquareNode_ and
TriangleNode_, because
//they are similar to CircleNode_. All of them are concrete nodes.

//Implementation of Rect_
template < typename TShapes >
class RectNode_
: public ShapeNode_< TShapes >
{
typedef RectNode_<TShapes> TSelf;

Point_ ul;
Point_ br;
public:
//useful constructor for rectangles
RectNode_( Point_ const& _ul, Point_ const& _br ) : ul( _ul ), br(
_br ) {}

//useful accessors
const Point_& GetUpLeft() { return ul; }
const Point_& GetBottomRight() { return br; }

//dispatching (see Visitor pattern)
virtual bool Accept( IDispatcher_<TShapes>& _dispatcher ) {
IDispatchPart_<TSelf>& dpart = _dispatcher;
return dpart.Dispatch( *this );
}

//Here we know TArg0 type and have Dispatcher_ that can determine
TArg1 type.
virtual bool Cross( ShapeNode_<TShapes>& _shape ) {
Dispatcher_< TShapes, TSelf > disp( *this );
return _shape.Accept( disp );
}

// This is very unimportant method. Used only in demonstrative
goals.
virtual Draw( Bitmap_& /*_bmp*/, int /*_color*/ ) { /*draw
rectangle*/ }
};

//Implementation of Square_ (Square_ is derived from Rect_)
template < typename TShapes >
class SquareNode_
: public RectNode_< TShapes >
{
typedef SquareNode_<TShapes> TSelf;

public:
//useful constructor for squares
SquareNode_( Point_ const& _ul, int _size )
: RectNode_< TShapes >( _ul, Point_( _ul.x + _size, _ul.y + _size
) ) {}

//dispatching (see Visitor pattern)
virtual bool Accept( IDispatcher_<TShapes>& _dispatcher ) {
IDispatchPart_<TSelf>& dpart = _dispatcher;
return dpart.Dispatch( *this );
}

//Here we know TArg0 type and have Dispatcher_ that can determine
TArg1 type.
virtual bool Cross( ShapeNode_<TShapes>& _shape ) {
Dispatcher_< TShapes, TSelf > disp( *this );
return _shape.Accept( disp );
}

virtual Draw( Bitmap_& /*_bmp*/, int /*_color*/ ) { /*draw square*/
}
};

//Implementation of Triangle_
template < typename TShapes >
class TriangleNode_
: public ShapeNode_< TShapes >
{
typedef TriangleNode_<TShapes> TSelf;

Point_ points[3];
public:
//useful constructor for triangles
TriangleNode_( Point_ const& _a, Point_ const& _b, Point_ const& _c
)
{
points[0] = _a;
points[1] = _b;
points[2] = _c;
}

//useful accessor
const Point_& GetPoint( int _index ) { return points[ _index ]; }

//dispatching (see Visitor pattern)
virtual bool Accept( IDispatcher_<TShapes>& _dispatcher ) {
IDispatchPart_<TSelf>& dpart = _dispatcher;
return dpart.Dispatch( *this );
}

//Here we know TArg0 type and have Dispatcher_ that can determine
TArg1 type.
virtual bool Cross( ShapeNode_<TShapes>& _shape ) {
Dispatcher_< TShapes, TSelf > disp( *this );
return _shape.Accept( disp );
}

// This is very unimportant method. Used only in demonstrative
goals.
virtual Draw( Bitmap_& /*_bmp*/, int /*_color*/ ) { /*draw
triangle*/ }
};

//Ooh! Our shapes hierarchy is finished.

//This is a forward declaration of our dispatcher

struct Shapes_;

using namespace boost::mpl;
using namespace boost;

//Keep in mind that Crossing_'s are declared independently.
//Each of them can be declared in separate file.

//forward declaration
template <typename TArg0, typename TArg1>
struct Crossing_;

//This is used to create symmetric methods
template <typename TArg0, typename TArg1>
struct Reverse_
{
static bool Crossing( TArg0& _arg0, TArg1& _arg1 )
{
return Crossing_< TArg1, TArg0 >::TImpl::Crossing( _arg1, _arg0 );
}
};

//Full specialization to cross circle and rectangle
typedef CircleNode_< Shapes_ > Circle_;
typedef RectNode_< Shapes_ > Rect_;
template <>
struct Crossing_< Circle_, Rect_ >
{
typedef Crossing_< Circle_, Rect_ > TImpl;

static bool Crossing( Circle_& _arg0, Rect_& _arg1 )
{
//insert your own 'very high speed geometry' to cross circle and
rect
return true;
}
};

//Symmetric crossing rectangle against circle
typedef CircleNode_< Shapes_ > Circle_;
typedef RectNode_< Shapes_ > Rect_;
template <>
struct Crossing_< Rect_, Circle_ >
{
typedef Reverse_< Rect_, Circle_ > TImpl;
};

//Full specialization to cross two circles
typedef CircleNode_< Shapes_ > Circle_;
template <>
struct Crossing_< Circle_, Circle_ >
{
typedef Crossing_< Circle_, Circle_ > TImpl;

static bool Crossing( Circle_& _arg0, Circle_& _arg1 )
{
//insert your own 'very high speed geometry' to cross two circles
return true;
}
};

//Crossing of any two rectangular shapes (rectangle or square)
typedef RectNode_< Shapes_ > Rect_;
struct RectangularCrossing_
{
static bool Crossing( Rect_& _arg0, Rect_& _arg1 ) {
//insert your own 'very high speed geometry' to cross two
rectangles
return true;
}
};

//Crossing of any two shapes through drawing
//This is the default implementation
typedef ShapeNode_< Shapes_ > Shape_;
struct DumbCrossing_
{
static bool Crossing( Shape_& _arg0, Shape_& _arg1 ) {
Bitmap_ bmp;
_arg0.Draw( bmp, 0 );
_arg1.Draw( bmp, 1 );
//insert your own 'very slow bitmap analysis' to cross two
generalized shapes
return false;
}
};

//utility class
template <class T, class U>
struct BaseOrSame_
{
enum { value = boost::is_same<T,U>::value ||
boost::is_base_and_derived<T,U>::value };
};

/*
General implementation of crossing two items
Now implements following logic:
- if arg0 and arg1 are rectangular, then cross them by
RectangularCrossing_
- if arg0 and arg1 are shapes, then cross them by DumbCrossing_
- otherwise crossing is unavailable
*/
typedef ShapeNode_< Shapes_ > Shape_;
typedef RectNode_< Shapes_ > Rect_;
template <typename TArg0, typename TArg1>
struct Crossing_
{
typedef typename if_c< BaseOrSame_< Rect_, TArg0 >::value &&
BaseOrSame_< Rect_, TArg1 >::value,
RectangularCrossing_,
typename if_c< BaseOrSame_< Shape_, TArg0
>::value &&
BaseOrSame_< Shape_, TArg1
>::value,
DumbCrossing_,
Crossing_< TArg0, TArg1 >
>::type
>::type TImpl;

static bool Crossing( TArg0& _arg0, TArg1& _arg1 )
{
return false;
}
};

//Here we declare shapes, that will be used in our application.
//Attention: they aren't instantiated here!
typedef ShapeNode_< Shapes_ > Shape_;
typedef CircleNode_< Shapes_ > Circle_;
typedef RectNode_< Shapes_ > Rect_;
typedef SquareNode_< Shapes_ > Square_;
typedef TriangleNode_< Shapes_ > Triangle_;

//Suppose we have an original typelist Shapes0_ and extends them.
typedef list< Circle_, Rect_, Square_ > Shapes0_;
typedef insert< Shapes0_, end<Shapes0_>::type, Triangle_ >::type
Shapes1_;

struct Shapes_ : public Shapes1_ {};

//have fun :-)
int main()
{
std::auto_ptr<Shape_> circle( new Circle_( Point_( 5, 5 ), 3 ) );
std::auto_ptr<Shape_> circle2( new Circle_( Point_( 4, 4 ), 6 ) );
std::auto_ptr<Shape_> rect( new Rect_( Point_( 5, 5 ), Point_( 10,
10 ) ) );
std::auto_ptr<Shape_> square( new Square_( Point_( 1, 1 ), 7 ) );
std::auto_ptr<Shape_> square2( new Square_( Point_( 1, 3 ), 7 ) );
std::auto_ptr<Shape_> triangle( new Triangle_( Point_( 1, 3 ),
Point_( 2, 3 ), Point_( 7, 12 ) ) );

bool crossed = false;
crossed = circle->Cross( *rect );
crossed = rect->Cross( *circle );

crossed = circle->Cross( *circle2 );

crossed = rect->Cross( *square );
crossed = square->Cross( *rect );
crossed = square->Cross( *square2 );

crossed = circle->Cross( *square );

crossed = triangle->Cross( *circle );
crossed = triangle->Cross( *square );

return 0;
}

/*
References:
[1] www.boost.org
[2] Andrei Alexanderscu "Modern C++ Design"
[3] David Vandevoorde, Nicolai M. Josuttis "C++ Templates: The
Complete Guide"
[4] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides "Design
Patterns: Elements of Reusable Object-Oriented Software"
*/

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Andrei Alexandrescu]

"Danil" <sds...@front.ru> wrote in message
news:4fbc288e.04032...@posting.google.com...

> We can improve initial solution:
> - dispatchers can be generated from typelists.
> - no dynamic memory allocation (via new or malloc) is performed during
> multimethod call.

[snip]

I've been looking over the code... looks interesting. An aspect that I
always want to get right is the graph of dependencies and how one should
organize their code to benefit of double dispatching.

So let me make sure I understand how your framework works.

* You have every "doubly-dispatchable" class become a template that takes a
template argument. That template argument will be the list of all classes in
the hierarchy, but fortunately, it doesn't have to be defined at the time
one defines each class. Is that correct?

* However, by the time the programmer introduces the "typedef
ShapeNode<ShapeList> Shape", the ShapeList must be declared, but not
defined. Is this the main asset of the technique?

* Any double dispatcher must have access to the ShapeList's definition, and
that's the most important dependency knot.

If the above is correct, I'd rank the technique as follows:

1. GoF style visitor: 2 virtual calls, but introduces circular dependency.

2. Acyclic Visitor: 2 virtuals + 1 dynamic_cast, gets rid of circular
dependency.

3. Danil's Double Dispatcher: 2 virtual calls, gets rid of circular
dependency, requires transforming the visited hierarchy into templates.

Is this assessment correct?

Andrei

[Danil Shopyrin]

Oh...Sorry, but I've miss this question (maybe the answer already
unnecessary).

But better late than never.

The proposed approach is currently updated.
http://www.codeproject.com/cpp/mmcppfcs.asp

Let's pretends that today is Mar 27 :-)
The answers (in order of the questions appearance):
1) Yes
2) Yes
3) Yes
4) Yes

Further, let's go back into the present.

The main differences from the past:
1) shapes aren't templates now.
2) dependency graph is better (given in
http://www.codeproject.com/cpp/mmcppfcs.asp)

I know two main disadvantages of the current approach:
1) The exponential output growing.
2) The proposed multimethods are more static than regular virtual
methods. The multimethods configuration cannot be extended in run-time,
but the virtual method configuration can. We can load an DLL in
run-time and all virtual methods in loaded classes will works properly.

I hope that the second disadvantage can be fixed by merging
"compile-time" and "run-time" double-dispatching technologies in a
single one.

--
Danil