[Home]CPPTM Answers - Exercise 5-10

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

This implements only one of the three views suggested in the excersize.


  // by Jordan DeLong?
  // This is in the public domain.
  #include <boost/mpl/or.hpp>
  #include <boost/mpl/assert.hpp>
  #include <boost/mpl/begin.hpp>
  #include <boost/mpl/bool.hpp>
  #include <boost/mpl/int.hpp>
  #include <boost/mpl/if.hpp>
  #include <boost/mpl/iterator_tags.hpp>
  #include <boost/mpl/not.hpp>
  #include <boost/mpl/eval_if.hpp>
  #include <boost/mpl/identity.hpp>
  #include <boost/mpl/print.hpp>
  #include <boost/type_traits.hpp>

  namespace mpl = boost::mpl;

  //////////////////////////////////////////////////////////////////////

  namespace btrees {

      template<class Node, class Left, class Right>
      struct btree {
          typedef btree    type;
          typedef Node    node_type;
          typedef Left    left_type;
          typedef Right    right_type;
      };

      // Predicate for determining whether a given argument is a btree<>
      // or not.
      template<class T>
      struct is_tree : mpl::false_ {};
      template<class Node, class Left, class Right>
      struct is_tree<btree<Node, Left, Right> > : mpl::true_ {};

      // Values for Which; indicate one of the three values in a btree
      // node.
      struct vlhs {};
      struct vtop {};
      struct vrhs {};

      // Select a type out of a btree using one of the above.
      template<class Tree, class Which>
      struct select {
          BOOST_MPL_ASSERT((
              mpl::or_<
                  boost::is_same<Which, vlhs>,
                  boost::is_same<Which, vtop>,
                  boost::is_same<Which, vrhs>
              >
          ));

          typedef typename mpl::eval_if<
              boost::is_same<Which, vlhs>,
              mpl::identity<typename Tree::left_type>,
              mpl::if_<
                  boost::is_same<Which, vtop>,
                  typename Tree::node_type,
                  typename Tree::right_type
              >
          >::type type;
      };

      //////////////////////////////////////////////////////////////////////

      struct inorder_tag {};

      template<class Tree>
      struct inorder_view {
          typedef Tree            tree_type;
          typedef inorder_tag        tag;
      };

      struct inorder_iter_end {
          typedef mpl::forward_iterator_tag category;
      };
      template<class Tree, class ChainUp?, class Which>
      struct inorder_iter;

      template<class Tree,
          class ChainUp? = inorder_iter_end,
          class Which = vlhs>
      struct get_inorder_begin {
          BOOST_MPL_ASSERT_NOT((boost::is_same<Which, vtop>));

          typedef typename select<Tree, Which>::type branch_type;
          typedef typename mpl::eval_if<
              mpl::not_<is_tree<branch_type> >,
              mpl::identity<inorder_iter<Tree, ChainUp?, Which> >,
              get_inorder_begin<
                  branch_type,
                  typename mpl::if_<
                      boost::is_same<Which, vlhs>,
                      inorder_iter<
                          Tree,
                          ChainUp?,
                          vtop
                      >,
                      ChainUp?
                  >::type
              >
          >::type type;
      };

      template<class Tree, class ChainUp?, class Which>
      struct inorder_iter : select<Tree, Which> {
          typedef mpl::forward_iterator_tag category;
          typedef typename mpl::if_<
              boost::is_same<Which, vrhs>,
              ChainUp?,
              typename mpl::if_<
                  boost::is_same<Which, vlhs>,
                  inorder_iter<Tree, ChainUp?, vtop>,
                  typename get_inorder_begin<Tree, ChainUp?, vrhs>::type
              >::type
          >::type next;
      };

      //////////////////////////////////////////////////////////////////////

      /*
       * TODO: implement pre-order and post-order views.
       */
  }

  namespace boost { namespace mpl {

      template<>
      struct begin_impl<btrees::inorder_tag> {
          template<class View>
          struct apply :
              btrees::get_inorder_begin<
                  typename View::tree_type,
                  typename mpl::end<View>::type,
                  btrees::vlhs
              >
          {};
      };

      template<>
      struct end_impl<btrees::inorder_tag> {
          template<class View>
          struct apply : mpl::identity<btrees::inorder_iter_end> {};
      };
  }}

  using btrees::btree;

  //////////////////////////////////////////////////////////////////////
  // Test code.

  #include <iostream>
  #include <boost/static_assert.hpp>
  #include <boost/mpl/deref.hpp>
  #include <boost/mpl/for_each.hpp>
  #include <boost/mpl/placeholders.hpp>
  #include <boost/mpl/vector.hpp>
  #include <boost/mpl/back_inserter.hpp>
  #include <boost/mpl/copy.hpp>
  #include <boost/mpl/transform.hpp>
  #include <boost/mpl/equal.hpp>

  using namespace mpl::placeholders;

  //////////////////////////////////////////////////////////////////////

  namespace {

      template<class T>
      struct wrap {};

      struct print_type {
          template<class T>
          void
          operator()(wrap<T>)
          {
              std::cout << typeid(T).name() << '\n';
          }
      };

  }

  int
  main()
  {
      typedef btree<void*, int, long>
              contained_tree;
      typedef btree<double, contained_tree, char>
              my_tree;
      typedef btrees::inorder_view<my_tree>
              in_order;

      // Testing that btrees::is_tree actually works.
      BOOST_STATIC_ASSERT((btrees::is_tree<my_tree>::value == 1));
      BOOST_STATIC_ASSERT((btrees::is_tree<in_order>::value == 0));
      BOOST_STATIC_ASSERT((btrees::is_tree<my_tree::left_type>::value == 1));
      BOOST_STATIC_ASSERT((
          btrees::is_tree<my_tree::left_type::left_type>::value == 0
      ));

      // Compile time test of the sequence.
      BOOST_STATIC_ASSERT((
          mpl::equal<
              btrees::inorder_view<my_tree>,
              mpl::vector<int, void*, long, double, char>
          >::value
      ));

      // Runtime tests of the sequence.
      std::cout << "Printing inorder view:\n";
      typedef mpl::transform<
          btrees::inorder_view<
              btree<
                  int,
                  btree<void*, char, long>,
                  btree<
                      void*,
                      btree<int, btree<long, double, char*>, double>,
                      btree<int, char[2][4], wrap<char *[]> >
                  >
              >
          >,
          wrap<_>,
          mpl::back_inserter<mpl::vector<> >
      >::type vec;
      mpl::for_each<vec>(print_type());
  }

  // ##############################################################
  // Here is another implementation of preorder_view (by xinyu zhu)
  // ##############################################################

  #include <boost/mpl/or.hpp>
  #include "boost/mpl/eval_if.hpp"
  #include <boost/mpl/vector.hpp>
  #include "boost/mpl/push_back.hpp"

  template <class T1, class T2, class T3>
  struct tree
  {
	typedef tree type;

	typedef T1 root;
	typedef T2 left;
	typedef T3 right;
  };

  template<class T>
  struct is_leaf : mpl::true_
  {};

  template<class T1, class T2, class T3>
  struct is_leaf<tree<T1, T2, T3> > : mpl::false_
  {};

  template <class seq, class tree_seq>
  struct pv
  {
	typedef typename tree_seq::root root;
	typedef typename tree_seq::left left;
	typedef typename tree_seq::right right;

	typedef typename mpl::eval_if< is_leaf<root>, mpl::push_back<seq, root>, pv<seq, root> >::type type1;
	typedef typename mpl::eval_if< is_leaf<left>, mpl::push_back<type1, left>, pv<type1, left> >::type type2;
	typedef typename mpl::eval_if< is_leaf<right>, mpl::push_back<type2, right>, pv<type2, right> >::type type;
  };

  template<class tree_seq>
  struct preorder_view
  {
	typedef mpl::vector<> seq;
	typedef typename pv<seq, tree_seq>::type type;
  };

BOOST WIKI | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited June 14, 2007 9:25 am (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers