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