exercise-5-10.hpp

Go to the documentation of this file.

// ===-- chapter-5/exercise-5-10.hpp ---------------------- -*- C++ -*- --=== //
#ifndef EXERCISE_5_10
#define EXERCISE_5_10
 
#include "chapter-5-tree.hpp"
 
#include <boost/static_assert.hpp>
 
#include <boost/mpl/begin_end.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/greater.hpp>
#include <boost/mpl/iterator_tags.hpp>
#include <boost/mpl/next_prior.hpp>
 
#include <boost/type_traits/is_same.hpp>
 
 
namespace exercise_5_10 {
 
struct inorder_view_tag { };
 
template <typename T>
struct inorder_view
{
    typedef T tree_root;
    typedef inorder_view_tag tag;
    typedef boost::mpl::forward_iterator_tag category;
};
 
template <typename Cur, typename Parent, int VisitCount>
struct inorder_view_iterator
{
    typedef Cur current_tree;
    typedef Parent parent_iterator;
    static int const visit_count = VisitCount;
 
    typedef inorder_view_iterator<Cur, Parent, VisitCount> type;
};
 
typedef inorder_view_iterator<void_, void_, 0> inorder_view_iterator_end;
 
} // namespace exercise_5_10
 
 
namespace boost {
namespace mpl {
 
 
template<>
struct end_impl<exercise_5_10::inorder_view_tag>
{
    template <typename S>
    struct apply : exercise_5_10::inorder_view_iterator_end { };
};
 
template<>
struct begin_impl<exercise_5_10::inorder_view_tag>
{
    template <typename Self, typename Parent>
    struct apply_on_iterator :
        exercise_5_10::inorder_view_iterator<Self, Parent, 1> { };
 
    template <typename Cur, typename L, typename R, typename Parent>
    struct apply_on_iterator<chapter5::tree<Cur, L, R>, Parent>
        : apply_on_iterator<
            L,
            exercise_5_10::inorder_view_iterator<
                chapter5::tree<Cur, L, R>, Parent, 1>
        > { };
 
    template <typename Parent>
    struct apply_on_iterator< chapter5::tree<>, Parent >
        : boost::mpl::end<
            exercise_5_10::inorder_view< chapter5::tree<> > > { };
 
    template <typename S>
    struct apply
        : apply_on_iterator<
            typename S::tree_root,
            exercise_5_10::inorder_view_iterator_end
        > { };
};
 
template <typename Cur, typename Parent, int VisitCount>
struct next< exercise_5_10::inorder_view_iterator<Cur, Parent, VisitCount> >
    : boost::mpl::eval_if<
        boost::is_same<exercise_5_10::inorder_view_iterator_end, Parent>,
        exercise_5_10::inorder_view_iterator_end,
        next<
            exercise_5_10::inorder_view_iterator<
                typename Parent::current_tree,
                typename Parent::parent_iterator,
                Parent::visit_count>
            >
        > { };
template <typename Cur, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<Cur, Parent, 0> >
    : exercise_5_10::inorder_view_iterator<Cur, Parent, 1> { };
 
template <typename Cur, typename L, typename R, typename Parent, int VisitCount>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, VisitCount> > { };
 
template <typename Cur, typename L, typename R, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, 0> >
    : next<
        exercise_5_10::inorder_view_iterator<
            L,
            exercise_5_10::inorder_view_iterator<
                chapter5::tree<Cur, L, R>, Parent, 1>,
            0
        >
    > { };
template <typename Cur, typename R, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, void_, R>, Parent, 0> >
    : next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, void_, R>, Parent, 1> > { };
template <typename Cur, typename L, typename R, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, 1> >
    : exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, 2> { };
template <typename Cur, typename L, typename R, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, 2> >
    : next<
        exercise_5_10::inorder_view_iterator<
            R,
            exercise_5_10::inorder_view_iterator<
                chapter5::tree<Cur, L, R>, Parent, 3>,
            0
        >
    > { };
template <typename Cur, typename L, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, void_>, Parent, 2> >
    : next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, void_>, Parent, 3> > { };
template <typename Cur, typename L, typename R, typename Parent>
struct next< exercise_5_10::inorder_view_iterator<
                 chapter5::tree<Cur, L, R>, Parent, 3> >
    : boost::mpl::eval_if<
        boost::is_same<exercise_5_10::inorder_view_iterator_end, Parent>,
        exercise_5_10::inorder_view_iterator_end,
        next<
            exercise_5_10::inorder_view_iterator<
                typename Parent::current_tree,
                typename Parent::parent_iterator,
                Parent::visit_count>
            >
        > { };
 
template <typename Cur, typename Parent, int VisitCount>
struct deref< exercise_5_10::inorder_view_iterator<Cur, Parent, VisitCount> >
{
    typedef Cur type;
};
 
template <typename Cur, typename L, typename R, typename Parent, int VisitCount>
struct deref< exercise_5_10::inorder_view_iterator<
                  chapter5::tree<Cur, L, R>, Parent, VisitCount> >
{
    typedef Cur type;
};
 
 
} // namespace mpl
} // namespace boost
 
#if 0
 
template <typename T>
struct preorder_view
{
 
};
 
template <typename T>
struct postorder_view
{
 
};
 
#endif
 
#endif // EXERCISE_5_10