1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
// Copyright Oliver Kowalke 2009.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef TREE_H
#define TREE_H
#include <boost/coroutine/all.hpp>
#include <cstddef>
#include <string>
#include <boost/assert.hpp>
#include <boost/config.hpp>
#include <boost/intrusive_ptr.hpp>
#if defined(_MSC_VER)
# pragma warning(push)
# pragma warning(disable:4355)
#endif
struct branch;
struct leaf;
struct visitor
{
virtual ~visitor() {};
virtual void visit( branch & b) = 0;
virtual void visit( leaf & l) = 0;
};
struct node
{
typedef boost::intrusive_ptr< node > ptr_t;
std::size_t use_count;
node() :
use_count( 0)
{}
virtual ~node() {}
virtual void accept( visitor & v) = 0;
friend inline void intrusive_ptr_add_ref( node * p)
{ ++p->use_count; }
friend inline void intrusive_ptr_release( node * p)
{ if ( 0 == --p->use_count) delete p; }
};
struct branch : public node
{
node::ptr_t left;
node::ptr_t right;
static ptr_t create( node::ptr_t left_, node::ptr_t right_)
{ return ptr_t( new branch( left_, right_) ); }
branch( node::ptr_t left_, node::ptr_t right_) :
left( left_), right( right_)
{}
void accept( visitor & v)
{ v.visit( * this); }
};
struct leaf : public node
{
std::string value;
static ptr_t create( std::string const& value_)
{ return ptr_t( new leaf( value_) ); }
leaf( std::string const& value_) :
value( value_)
{}
void accept( visitor & v)
{ v.visit( * this); }
};
inline
bool operator==( leaf const& l, leaf const& r)
{ return l.value == r.value; }
inline
bool operator!=( leaf const& l, leaf const& r)
{ return l.value != r.value; }
class tree_visitor : public visitor
{
private:
boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c_;
public:
tree_visitor( boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c) :
c_( c)
{}
void visit( branch & b)
{
if ( b.left) b.left->accept( * this);
if ( b.right) b.right->accept( * this);
}
void visit( leaf & l)
{ c_( l); }
};
void enumerate_leafs( boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c, node::ptr_t root)
{
tree_visitor v( c);
root->accept( v);
}
#if defined(_MSC_VER)
# pragma warning(pop)
#endif
#endif // TREE_H
|
