[boost] Boost.MPL: "Superlinear unrolling" to avoid recursion depth limits

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-15 06:49:39

Hi,

The following is an example of using "superlinear unrolling". It compiles 
with

  gcc version 2.95.4 20011002 (Debian prerelease)

using the default settings (max template recursion depth should be 17). The 
example code essentially applies the inc template 262 times. The example 
code uses partial specialization, but it should not be extremely difficult 
to remove, if necessary.

I think that superlinear unrolling could be useful for avoiding template 
recursion depth limitations, but the technique needs further studying.

It seems to be quite tricky to reach maximal iteration counts using this 
technique. I think that others might have more insight into how to tune the 
code for maximal iteration counts.

- Vesa Karvonen

#include <iostream>
#include <typeinfo>
#include "boost/mpl/apply_if.hpp"
#include "boost/mpl/if.hpp"
#include "boost/mpl/apply.hpp"
#include "boost/mpl/bool_c.hpp"
#include "boost/mpl/int_c.hpp"
#include "boost/mpl/identity.hpp"

namespace mpl = ::boost::mpl;

template<int d, class P, class O, class X_Outer>
struct until_down {
private:
  typedef typename mpl::apply1<O,X_Outer>::type X_In;

  typedef typename mpl::apply_if<typename mpl::apply1<P,X_In>::type,
                                 mpl::identity<X_In>,
                                 until_down<d-1,P,O,X_In> >::type X_1;

  typedef typename mpl::apply_if<typename mpl::apply1<P,X_1>::type,
                                 mpl::identity<X_1>,
                                 until_down<d-1,P,O,X_1> >::type X_2;
public:
  typedef typename mpl::apply_if<typename mpl::apply1<P,X_2>::type,
                                 mpl::identity<X_2>,
                                 until_down<d-1,P,O,X_2> >::type type;
};

template<class P, class O, class X>
struct until_down<0,P,O,X> : mpl::apply1<O,X> {};

template<int d, class P, class O, class X_Outer>
struct until_up {
private:
  typedef typename mpl::apply1<O,X_Outer>::type X_In;

  typedef typename mpl::apply_if<typename mpl::apply1<P,X_In>::type,
                                 mpl::identity<X_In>,
                                 until_down<d,P,O,X_In> >::type X_1;

  typedef typename mpl::apply_if<typename mpl::apply1<P,X_1>::type,
                                 mpl::identity<X_1>,
                                 until_down<d,P,O,X_1> >::type X_2;
public:
  typedef typename mpl::apply_if<typename mpl::apply1<P,X_2>::type,
                                 mpl::identity<X_2>,
                                 until_up<d+1,P,O,X_2> >::type type;
};

template<class P, class O, class X>
struct until : mpl::apply_if<mpl::apply1<P,X>,
                             mpl::identity<X>,
                             until_up<3,P,O,X> > {};

struct inc {
  template<class T>
  struct apply {
    typedef typename T::next type;
  };
};

struct always {
  template<class T>
  struct apply {
    typedef typename mpl::bool_c<false> type;
  };
};

template<int X>
struct is {
  template<class T>
  struct apply : mpl::bool_c<(T::value == X)> {
  };
};

int main() {
  std::cerr << until<is<262>, inc, mpl::int_c<0> >::type::value << '\n';

  return 0;
}

_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online 
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963