[boost] overloads: request for discussion

From: Alexander Nasonov (alnsn_at_[hidden])
Date: 2005-01-15 12:22:33

An overload set can be represented as a class with _numbered_ call operators:

    struct has_intersection
    {
        bool operator()(id<1>, Circle&,    Circle&   ) const;
        bool operator()(id<2>, Circle&,    Rectangle&) const;
        bool operator()(id<3>, Rectangle&, Circle&   ) const;
        bool operator()(id<4>, Rectangle&, Rectangle&) const;
    };

I wonder how to pass it to different kind of algorithms. Here's my brain
dump of the topic:

1. Pass an overload set, MPL sequence of positions and a predicate

    find_if< has_intersection
           , range_c<int,1,5>
           , is_same<first_arg<_>, Circle&>
           >

The find_if algorithm works with mpl sequence of positions, that is, it
takes positions and return an iterator to first found position. Unlike
mpl::find_if, the predicate takes a signature, not a position.

I used it till recently. But it's not quite an OverloadSet concept.

2. MPL-like sequence would be nice to have. Something similar to:

    mpl::vector< bool(Circle&,    Circle&   )
               , bool(Circle&,    Rectangle&)
               , bool(Rectangle&, Circle&   )
               , bool(Rectangle&, Rectangle&)
               >

or

    mpl::set< bool(Circle&,    Circle&   )
            , bool(Circle&,    Rectangle&)
            , bool(Rectangle&, Circle&   )
            , bool(Rectangle&, Rectangle&)
            >

Unfortunately, if typeof is not available, deref and some other operations
work only in deduced context (that is, inside special function).

Presumably that sequence should store pairs of id and a signature in
deduced context or id and unknown otherwise:

    pair<id<1>, bool(Circle&,Circle&) > // deduced context
    pair<id<1>, unknown>            // non-deduced context

(This reminds me of mpl::map but I'm not sure about keys and values:
id -> signature or signature -> id?)

Algorithms that accept boolean predicates will be using deduced
context (this can be extended to predicates that return integral
constants in limited range).
Question about whether to implement other algorithms is open.

This approach has an advantage on a long run. When typeof becomes
standartized, everything can be switched to the first case.

To summarize, I see it being as close to MPL sequence (I don't know
to which one, though) as possible

    typedef overload_set<has_intersection, range_c<int,1,5> > seq;

but not closer.
For example, overload_set is extensible only in a limited way: you can't
insert new overload but you can restore an overload removed by previous
algorithm or a filter. This means, in particular, that sort should work
because it only changes an order of elements. 
Note that sorting by id or signature is less important then sorting by
return or argument type and then applying unique algorithm. At best,
sorting of huge overload set can be avoided. MPL has a trick for this:

    mpl::copy<from, inserter<set<>, insert<_1,_2> > >

Something similar can be done for overload_set. Otherwise, new algorithm
should be introduced because of its high importance. It has to be very
fast at compile-time to deal efficiently with huge overload sets.
(This algorithm exists already under name "unique").

3. Fusion-like interface. Overload sets are not pure compile-time
entities as shown in this example:

    tuple<
        bool (has_intersection::*)(id<1>, Circle&,    Circle&   ) const,
        bool (has_intersection::*)(id<2>, Circle&,    Rectangle&) const,
        bool (has_intersection::*)(id<3>, Rectangle&, Circle&   ) const,
        bool (has_intersection::*)(id<4>, Rectangle&, Rectangle&) const
    > t(
        &has_intersection::operator(),
        &has_intersection::operator(),
        &has_intersection::operator(),
        &has_intersection::operator()
       );

Something like that would be great addition for overloads library.

The library is available at cpp-experiment.sf.net (please, use CVS).

-- 
Alexander Nasonov