# CPPTM Answers - Exercise 5-8

BOOST WIKI | RecentChanges | Preferences | Page List | Links List

See errata for correction to exercise

``` // (by Ariel Badichi)
#include <boost/static_assert.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/prior.hpp>
#include <boost/mpl/iterator_tags.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/lower_bound.hpp>
#include <boost/mpl/int.hpp>
```

``` namespace mpl = boost::mpl;
```

``` template<int N>
struct fibonacci_gen;
```

``` template<>
struct fibonacci_gen<1> : mpl::int_<1> {};
```

``` template<>
struct fibonacci_gen<0> : mpl::int_<0> {};
```

``` template<int N>
struct fibonacci_gen
: mpl::plus<
typename fibonacci_gen<N - 1>::type,
typename fibonacci_gen<N - 2>::type
>
{
};
```

``` struct fibonacci_series_tag {};
```

``` template<typename N>
struct fibonacci_series_iterator
{
typedef mpl::forward_iterator_tag category;
typedef fibonacci_series_iterator<typename mpl::next<N>::type> next;
};
```

``` struct fibonacci_series
{
typedef fibonacci_series_tag tag;
};
```

``` namespace boost
{
namespace mpl
{
template<>
struct begin_impl<fibonacci_series_tag>
{
template<typename Sequence>
struct apply
{
typedef fibonacci_series_iterator<mpl::int_<0> > type;
};
};
```

```         /*
template<>
struct end_impl<fibonacci_series_tag>
{
template<typename Sequence>
struct apply
{
// Not really an infinite sequence: mpl::lower_bound
// will not work with an infinite sequence.
typedef fibonacci_series_iterator<mpl::int_<30> > type;
};
};
*/
```

```         template<typename N>
struct deref<fibonacci_series_iterator<N> > : fibonacci_gen<N::value> {};
}
}
```

``` int main()
{
BOOST_STATIC_ASSERT((fibonacci_gen<0>::type::value == 0));
BOOST_STATIC_ASSERT((fibonacci_gen<1>::type::value == 1));
BOOST_STATIC_ASSERT((fibonacci_gen<2>::type::value == 1));
BOOST_STATIC_ASSERT((fibonacci_gen<3>::type::value == 2));
BOOST_STATIC_ASSERT((fibonacci_gen<4>::type::value == 3));
BOOST_STATIC_ASSERT((fibonacci_gen<5>::type::value == 5));
```

```     typedef mpl::advance_c< mpl::begin<fibonacci_series>::type, 6 >::type i;
BOOST_STATIC_ASSERT( mpl::deref<i>::type::value == 8 );
```

```     typedef mpl::advance_c< i, 4 >::type j;
BOOST_STATIC_ASSERT( mpl::deref<j>::type::value == 55 );
```

```     /*
// The results given in the exercise are incorrect.
typedef mpl::lower_bound<fibonacci_series, mpl::int_<10> >::type n;
BOOST_STATIC_ASSERT((mpl::deref<n>::type::value == 13));
```

```     typedef mpl::lower_bound<fibonacci_series, mpl::int_<50> >::type m;
BOOST_STATIC_ASSERT((mpl::deref<m>::type::value == 55));
*/
```

```     return 0;
}
```

My solution was very slightly different. I figured I'd post it here since I think it may be necessary to correctly model the forward iterator concept, which page 80 seems to say requires that mpl::deref<> is compile-time O(1).

The relevant part:

``` template<long Value, long LastValue? = 0>
struct fib_iterator {
typedef
mpl::forward_iterator_tag
category;
typedef
fib_iterator<Value + LastValue?, Value>
next;
typedef
mpl::int_<Value>
type;
};
```

(You can figure out the rest. begin_impl returns a fib_iterator<1>).

BOOST WIKI | RecentChanges | Preferences | Page List | Links List