[Home]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>
 #include <boost/mpl/advance.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
Edit text of this page | View other revisions
Last edited June 6, 2005 9:15 pm (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers