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
nodenode31 node(const std::string& v):
32 left(), right(), value(v)
33 {}
34 // construct nonleaf
nodenode35 node(ptr_t l, const std::string& v, ptr_t r):
36 left(l), right(r), value(v)
37 {}
38
createnode39 static ptr_t create(const std::string& v)
40 {
41 return ptr_t(new node(v));
42 }
43
createnode44 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
create_left_tree_from(const std::string & root)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
create_right_tree_from(const std::string & root)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
traverse(node::ptr_t n,boost::coroutines::asymmetric_coroutine<std::string>::push_type & out)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
main()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 }
163