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