ceph/src/boost/libs/hana/example/misc/tree.cpp

   1 // Copyright Louis Dionne 2013-2017
   2 // Distributed under the Boost Software License, Version 1.0.
   3 // (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
   4
   5 #include <boost/hana/and.hpp>
   6 #include <boost/hana/ap.hpp>
   7 #include <boost/hana/assert.hpp>
   8 #include <boost/hana/concat.hpp>
   9 #include <boost/hana/equal.hpp>
  10 #include <boost/hana/flatten.hpp>
  11 #include <boost/hana/fold_left.hpp>
  12 #include <boost/hana/lift.hpp>
  13 #include <boost/hana/sum.hpp>
  14 #include <boost/hana/transform.hpp>
  15 #include <boost/hana/tuple.hpp>
  16 namespace hana = boost::hana;
  17
  18
  19 struct tree_tag;
  20
  21 template <typename X, typename Subforest>
  22 struct node {
  23     X value;
  24     Subforest subforest;
  25
  26     using hana_tag = tree_tag;
  27 };
  28
  29 constexpr auto make_forest = hana::make_tuple;
  30
  31 template <typename X, typename Subforest>
  32 constexpr auto make_node(X x, Subforest subforest) {
  33     return node<X, Subforest>{x, subforest};
  34 }
  35
  36 namespace boost { namespace hana {
  37     //////////////////////////////////////////////////////////////////////////
  38     // Comparable
  39     //////////////////////////////////////////////////////////////////////////
  40     template <>
  41     struct equal_impl<tree_tag, tree_tag> {
  42         template <typename Node1, typename Node2>
  43         static constexpr auto apply(Node1 node1, Node2 node2) {
  44             return hana::and_(
  45                 hana::equal(node1.value, node2.value),
  46                 hana::equal(node1.subforest, node2.subforest)
  47             );
  48         }
  49     };
  50
  51     //////////////////////////////////////////////////////////////////////////
  52     // Functor
  53     //////////////////////////////////////////////////////////////////////////
  54     template <>
  55     struct transform_impl<tree_tag> {
  56         template <typename Node, typename F>
  57         static constexpr auto apply(Node node, F f) {
  58             return make_node(
  59                 f(node.value),
  60                 hana::transform(node.subforest, [=](auto subtree) {
  61                     return hana::transform(subtree, f);
  62                 })
  63             );
  64         }
  65     };
  66
  67     //////////////////////////////////////////////////////////////////////////
  68     // Applicative
  69     //////////////////////////////////////////////////////////////////////////
  70     template <>
  71     struct lift_impl<tree_tag> {
  72         template <typename X>
  73         static constexpr auto apply(X x)
  74         { return make_node(x, make_forest()); }
  75     };
  76
  77     template <>
  78     struct ap_impl<tree_tag> {
  79         template <typename F, typename X>
  80         static constexpr auto apply(F f, X x) {
  81             return make_node(
  82                 f.value(x.value),
  83                 hana::concat(
  84                     hana::transform(x.subforest, [=](auto subtree) {
  85                         return hana::transform(subtree, f.value);
  86                     }),
  87                     hana::transform(f.subforest, [=](auto subtree) {
  88                         return hana::ap(subtree, x);
  89                     })
  90                 )
  91             );
  92         }
  93     };
  94
  95     //////////////////////////////////////////////////////////////////////////
  96     // Monad
  97     //////////////////////////////////////////////////////////////////////////
  98     template <>
  99     struct flatten_impl<tree_tag> {
 100         template <typename Node>
 101         static constexpr auto apply(Node node) {
 102             return make_node(
 103                 node.value.value,
 104                 hana::concat(
 105                     node.value.subforest,
 106                     hana::transform(node.subforest, hana::flatten)
 107                 )
 108             );
 109         }
 110     };
 111
 112     //////////////////////////////////////////////////////////////////////////
 113     // Foldable
 114     //////////////////////////////////////////////////////////////////////////
 115     template <>
 116     struct fold_left_impl<tree_tag> {
 117         template <typename Node, typename State, typename F>
 118         static constexpr auto apply(Node node, State state, F f) {
 119             return hana::fold_left(node.subforest, f(state, node.value),
 120                         [=](auto state, auto subtree) {
 121                             return hana::fold_left(subtree, state, f);
 122                         });
 123         }
 124     };
 125 }}
 126
 127 int main() {
 128     constexpr auto tree = make_node(1, make_forest(
 129         make_node(2, make_forest()),
 130         make_node(3, make_forest()),
 131         make_node(4, make_forest())
 132     ));
 133
 134     BOOST_HANA_CONSTEXPR_CHECK(hana::sum<>(tree) == 10);
 135
 136     BOOST_HANA_CONSTEXPR_CHECK(hana::equal(
 137         hana::transform(tree, [](int i) { return i + 1; }),
 138         make_node(2, make_forest(
 139             make_node(3, make_forest()),
 140             make_node(4, make_forest()),
 141             make_node(5, make_forest())
 142         ))
 143     ));
 144 }