Re: [boost] switch-based runtime type selection (for variant)

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2003-08-06 03:31:50

Brian Simpson wrote:
> The implementation reasoning runs like this:  It seems that the problem
with
> building a switch statement to implement type selection is that a switch
> statement can't be built incrementally--it is a syntactic construct.  (The
> currently accepted solution builds an else-if-then statement incrementally
> by means of a recursive function template instantiation.)  But what if you
> could give a template the number of types among which you want to select
in
> addition to the sequence?  Could it then implement a switch-based
selection
> on the first 'n' types in the sequence?  The answer turns out to be yes,
up
> to a point.  The mechanism, in this case, is partial template
> specialization.
> Let us define a template class:
> template <typename Sequence, long n>
> class n_ary_rtts_invoker;
> How does it produce a switch statement based on 'n'?  Well, if we limit
> ourselves to a specific value of 'n', we can express it.  For example,
here
> is a specialization for 'n'==3:
> <code>
> template <typename Sequence>
> class rtts_invoker<Sequence, 3>
> {
> public:
>    template <typename Operator, typename StoragePtr>
>    static
>    BOOST_DEDUCED_TYPENAME Operator::result_type
>    invoke(Operator & op, StoragePtr storage, long index)
>    {
>       switch (index)
>       {
>          case 0:
>             return op(*(static_cast<mpl::at_c<Sequence, 0>::type
> *>(storage)));
>          case 1:
>             return op(*(static_cast<mpl::at_c<Sequence, 1>::type
> *>(storage)));
>          case 2:
>             return op(*(static_cast<mpl::at_c<Sequence, 2>::type
> *>(storage)));
>       }
>    }
> };
> </code>
> Given this specialization of n_ary_rtts_invoker, we can setup runtime type
> selection on the first three types in a sequence.  To be more specific, if
> we instantiate a type, "n_ary_rtts_invoker<my_seq, 3>", the template
> machinery should match the above specialization, and the statement,
> "n_ary_rtts_invoker<my_seq, 3>::invoke(my_op, storage, index)", will make
a
> selection among the first three types in 'my_seq' via a switch statement
> (assuming 0<=index<3).
> If we define a similar specialization for values 1 and 2, we can setup
> selection on sequences of size 1-3.
>
> The general case devolves into an else-if-then:
> Let us assume that we have specializations up to a certain number,
> 'max_specialization_count'.  Then we know that we can get switch-based
> runtime type selection ("rtts") on any mpl::Sequence whose size is not
> greater than 'max_specialization_count'.  To provide rtts for Sequences
> whose size is greater than 'max_specialization_count', we provide a more
> general template definition.  Its "invoke" function sets up a switch-based
> selection among the first 'max_specialization_count' types, and then sets
up
> a (recursive) selection among the remaining types.

FWIW, I've used a similar technique in MPL to do recursion unrolling for the
'advance' algorithm:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/*checkout*/boost/boost/boost/mpl/aux_/preprocessed/plain/advance_forward.hpp?rev=1.4

Aleksey