ceph/src/boost/libs/coroutine/example/asymmetric/same_fringe.cpp

   1
   2 //          Copyright Nat Goodspeed 2013.
   3 // Distributed under the Boost Software License, Version 1.0.
   4 //    (See accompanying file LICENSE_1_0.txt or copy at
   5 //          http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <cstddef>
   8 #include <cstdlib>
   9 #include <iostream>
  10 #include <iterator>
  11 #include <string>
  12 #include <utility>
  13
  14 #include <boost/bind.hpp>
  15 #include <boost/range.hpp>
  16 #include <boost/shared_ptr.hpp>
  17 #include <boost/coroutine/all.hpp>
  18
  19 struct node
  20 {
  21     typedef boost::shared_ptr< node >    ptr_t;
  22
  23     // Each tree node has an optional left subtree, an optional right subtree
  24     // and a value of its own. The value is considered to be between the left
  25     // subtree and the right.
  26     ptr_t left, right;
  27     std::string value;
  28
  29     // construct leaf
  30     node(const std::string& v):
  31         left(), right(), value(v)
  32     {}
  33     // construct nonleaf
  34     node(ptr_t l, const std::string& v, ptr_t r):
  35         left(l), right(r), value(v)
  36     {}
  37
  38     static ptr_t create(const std::string& v)
  39     {
  40         return ptr_t(new node(v));
  41     }
  42
  43     static ptr_t create(ptr_t l, const std::string& v, ptr_t r)
  44     {
  45         return ptr_t(new node(l, v, r));
  46     }
  47 };
  48
  49 node::ptr_t create_left_tree_from(const std::string& root)
  50 {
  51     /* --------
  52          root
  53          / \
  54         b   e
  55        / \
  56       a   c
  57      -------- */
  58     return node::create(
  59             node::create(
  60                 node::create("a"),
  61                 "b",
  62                 node::create("c")),
  63             root,
  64             node::create("e"));
  65 }
  66
  67 node::ptr_t create_right_tree_from(const std::string& root)
  68 {
  69     /* --------
  70          root
  71          / \
  72         a   d
  73            / \
  74           c   e
  75        -------- */
  76     return node::create(
  77             node::create("a"),
  78             root,
  79             node::create(
  80                 node::create("c"),
  81                 "d",
  82                 node::create("e")));
  83 }
  84
  85 // recursively walk the tree, delivering values in order
  86 void traverse(node::ptr_t n,boost::coroutines::asymmetric_coroutine<std::string>::push_type& out)
  87 {
  88     if (n->left) traverse(n->left,out);
  89     out(n->value);
  90     if (n->right) traverse(n->right,out);
  91 }
  92
  93 int main()
  94 {
  95     {
  96         node::ptr_t left_d(create_left_tree_from("d"));
  97         boost::coroutines::asymmetric_coroutine<std::string>::pull_type left_d_reader(
  98             boost::bind(traverse, left_d, _1));
  99         std::cout << "left tree from d:\n";
 100         std::copy(boost::begin(left_d_reader),
 101                   boost::end(left_d_reader),
 102                   std::ostream_iterator<std::string>(std::cout, " "));
 103         std::cout << std::endl;
 104
 105         node::ptr_t right_b(create_right_tree_from("b"));
 106         boost::coroutines::asymmetric_coroutine<std::string>::pull_type right_b_reader(
 107             boost::bind(traverse, right_b, _1));
 108         std::cout << "right tree from b:\n";
 109         std::copy(boost::begin(right_b_reader),
 110                   boost::end(right_b_reader),
 111                   std::ostream_iterator<std::string>(std::cout, " "));
 112         std::cout << std::endl;
 113
 114         node::ptr_t right_x(create_right_tree_from("x"));
 115         boost::coroutines::asymmetric_coroutine<std::string>::pull_type right_x_reader(
 116             boost::bind(traverse, right_x, _1));
 117         std::cout << "right tree from x:\n";
 118         std::copy(boost::begin(right_x_reader),
 119                   boost::end(right_x_reader),
 120                   std::ostream_iterator<std::string>(std::cout, " "));
 121         std::cout << std::endl;
 122     }
 123
 124     {
 125         node::ptr_t left_d(create_left_tree_from("d"));
 126         boost::coroutines::asymmetric_coroutine<std::string>::pull_type left_d_reader(
 127             boost::bind(traverse, left_d, _1));
 128
 129         node::ptr_t right_b(create_right_tree_from("b"));
 130         boost::coroutines::asymmetric_coroutine<std::string>::pull_type right_b_reader(
 131             boost::bind(traverse, right_b, _1));
 132
 133         std::cout << "left tree from d == right tree from b? "
 134                   << std::boolalpha
 135                   << std::equal(boost::begin(left_d_reader),
 136                                 boost::end(left_d_reader),
 137                                 boost::begin(right_b_reader))
 138                   << std::endl;
 139     }
 140
 141     {
 142         node::ptr_t left_d(create_left_tree_from("d"));
 143         boost::coroutines::asymmetric_coroutine<std::string>::pull_type left_d_reader(
 144             boost::bind(traverse, left_d, _1));
 145
 146         node::ptr_t right_x(create_right_tree_from("x"));
 147         boost::coroutines::asymmetric_coroutine<std::string>::pull_type right_x_reader(
 148             boost::bind(traverse, right_x, _1));
 149
 150         std::cout << "left tree from d == right tree from x? "
 151                   << std::boolalpha
 152                   << std::equal(boost::begin(left_d_reader),
 153                                 boost::end(left_d_reader),
 154                                 boost::begin(right_x_reader))
 155                   << std::endl;
 156     }
 157
 158     std::cout << "Done" << std::endl;
 159
 160     return EXIT_SUCCESS;
 161 }