/////////////////////////////////////////////////////////////////////////////// | |
/// \file fold_tree.hpp | |
/// Contains definition of the fold_tree<> and reverse_fold_tree<> transforms. | |
// | |
// Copyright 2008 Eric Niebler. Distributed under the Boost | |
// Software License, Version 1.0. (See accompanying file | |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
#ifndef BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007 | |
#define BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007 | |
#include <boost/type_traits/is_same.hpp> | |
#include <boost/proto/proto_fwd.hpp> | |
#include <boost/proto/traits.hpp> | |
#include <boost/proto/matches.hpp> | |
#include <boost/proto/transform/fold.hpp> | |
#include <boost/proto/transform/impl.hpp> | |
namespace boost { namespace proto | |
{ | |
namespace detail | |
{ | |
template<typename Tag> | |
struct has_tag | |
{ | |
template<typename Expr, typename State, typename Data, typename EnableIf = Tag> | |
struct impl | |
{ | |
typedef mpl::false_ result_type; | |
}; | |
template<typename Expr, typename State, typename Data> | |
struct impl<Expr, State, Data, typename Expr::proto_tag> | |
{ | |
typedef mpl::true_ result_type; | |
}; | |
template<typename Expr, typename State, typename Data> | |
struct impl<Expr &, State, Data, typename Expr::proto_tag> | |
{ | |
typedef mpl::true_ result_type; | |
}; | |
}; | |
template<typename Tag, typename Fun> | |
struct fold_tree_ | |
: if_<has_tag<Tag>, fold<_, _state, fold_tree_<Tag, Fun> >, Fun> | |
{}; | |
template<typename Tag, typename Fun> | |
struct reverse_fold_tree_ | |
: if_<has_tag<Tag>, reverse_fold<_, _state, reverse_fold_tree_<Tag, Fun> >, Fun> | |
{}; | |
} | |
/// \brief A PrimitiveTransform that recursively applies the | |
/// <tt>fold\<\></tt> transform to sub-trees that all share a common | |
/// tag type. | |
/// | |
/// <tt>fold_tree\<\></tt> is useful for flattening trees into lists; | |
/// for example, you might use <tt>fold_tree\<\></tt> to flatten an | |
/// expression tree like <tt>a | b | c</tt> into a Fusion list like | |
/// <tt>cons(c, cons(b, cons(a)))</tt>. | |
/// | |
/// <tt>fold_tree\<\></tt> is easily understood in terms of a | |
/// <tt>recurse_if_\<\></tt> helper, defined as follows: | |
/// | |
/// \code | |
/// template<typename Tag, typename Fun> | |
/// struct recurse_if_ | |
/// : if_< | |
/// // If the current node has type type "Tag" ... | |
/// is_same<tag_of<_>, Tag>() | |
/// // ... recurse, otherwise ... | |
/// , fold<_, _state, recurse_if_<Tag, Fun> > | |
/// // ... apply the Fun transform. | |
/// , Fun | |
/// > | |
/// {}; | |
/// \endcode | |
/// | |
/// With <tt>recurse_if_\<\></tt> as defined above, | |
/// <tt>fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is | |
/// equivalent to | |
/// <tt>fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt> | |
/// It has the effect of folding a tree front-to-back, recursing into | |
/// child nodes that share a tag type with the parent node. | |
template<typename Sequence, typename State0, typename Fun> | |
struct fold_tree | |
: transform<fold_tree<Sequence, State0, Fun> > | |
{ | |
template<typename Expr, typename State, typename Data> | |
struct impl | |
: fold< | |
Sequence | |
, State0 | |
, detail::fold_tree_<typename Expr::proto_tag, Fun> | |
>::template impl<Expr, State, Data> | |
{}; | |
template<typename Expr, typename State, typename Data> | |
struct impl<Expr &, State, Data> | |
: fold< | |
Sequence | |
, State0 | |
, detail::fold_tree_<typename Expr::proto_tag, Fun> | |
>::template impl<Expr &, State, Data> | |
{}; | |
}; | |
/// \brief A PrimitiveTransform that recursively applies the | |
/// <tt>reverse_fold\<\></tt> transform to sub-trees that all share | |
/// a common tag type. | |
/// | |
/// <tt>reverse_fold_tree\<\></tt> is useful for flattening trees into | |
/// lists; for example, you might use <tt>reverse_fold_tree\<\></tt> to | |
/// flatten an expression tree like <tt>a | b | c</tt> into a Fusion list | |
/// like <tt>cons(a, cons(b, cons(c)))</tt>. | |
/// | |
/// <tt>reverse_fold_tree\<\></tt> is easily understood in terms of a | |
/// <tt>recurse_if_\<\></tt> helper, defined as follows: | |
/// | |
/// \code | |
/// template<typename Tag, typename Fun> | |
/// struct recurse_if_ | |
/// : if_< | |
/// // If the current node has type type "Tag" ... | |
/// is_same<tag_of<_>, Tag>() | |
/// // ... recurse, otherwise ... | |
/// , reverse_fold<_, _state, recurse_if_<Tag, Fun> > | |
/// // ... apply the Fun transform. | |
/// , Fun | |
/// > | |
/// {}; | |
/// \endcode | |
/// | |
/// With <tt>recurse_if_\<\></tt> as defined above, | |
/// <tt>reverse_fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is | |
/// equivalent to | |
/// <tt>reverse_fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt> | |
/// It has the effect of folding a tree back-to-front, recursing into | |
/// child nodes that share a tag type with the parent node. | |
template<typename Sequence, typename State0, typename Fun> | |
struct reverse_fold_tree | |
: transform<reverse_fold_tree<Sequence, State0, Fun> > | |
{ | |
template<typename Expr, typename State, typename Data> | |
struct impl | |
: reverse_fold< | |
Sequence | |
, State0 | |
, detail::reverse_fold_tree_<typename Expr::proto_tag, Fun> | |
>::template impl<Expr, State, Data> | |
{}; | |
template<typename Expr, typename State, typename Data> | |
struct impl<Expr &, State, Data> | |
: reverse_fold< | |
Sequence | |
, State0 | |
, detail::reverse_fold_tree_<typename Expr::proto_tag, Fun> | |
>::template impl<Expr &, State, Data> | |
{}; | |
}; | |
/// INTERNAL ONLY | |
/// | |
template<typename Sequence, typename State0, typename Fun> | |
struct is_callable<fold_tree<Sequence, State0, Fun> > | |
: mpl::true_ | |
{}; | |
/// INTERNAL ONLY | |
/// | |
template<typename Sequence, typename State0, typename Fun> | |
struct is_callable<reverse_fold_tree<Sequence, State0, Fun> > | |
: mpl::true_ | |
{}; | |
}} | |
#endif |