• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 
2 //          Copyright Oliver Kowalke 2009.
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 #ifndef TREE_H
8 #define TREE_H
9 
10 #include <boost/coroutine/all.hpp>
11 
12 #include <cstddef>
13 #include <string>
14 
15 #include <boost/assert.hpp>
16 #include <boost/config.hpp>
17 #include <boost/intrusive_ptr.hpp>
18 
19 #if defined(_MSC_VER)
20 # pragma warning(push)
21 # pragma warning(disable:4355)
22 #endif
23 
24 struct branch;
25 struct leaf;
26 
27 struct visitor
28 {
~visitorvisitor29     virtual ~visitor() {};
30 
31     virtual void visit( branch & b) = 0;
32     virtual void visit( leaf & l) = 0;
33 };
34 
35 struct node
36 {
37     typedef boost::intrusive_ptr< node >    ptr_t;
38 
39     std::size_t     use_count;
40 
nodenode41     node() :
42         use_count( 0)
43     {}
44 
~nodenode45     virtual ~node() {}
46 
47     virtual void accept( visitor & v) = 0;
48 
intrusive_ptr_add_refnode49     friend inline void intrusive_ptr_add_ref( node * p)
50     { ++p->use_count; }
51 
intrusive_ptr_releasenode52     friend inline void intrusive_ptr_release( node * p)
53     { if ( 0 == --p->use_count) delete p; }
54 };
55 
56 struct branch : public node
57 {
58     node::ptr_t     left;
59     node::ptr_t     right;
60 
createbranch61     static ptr_t create( node::ptr_t left_, node::ptr_t right_)
62     { return ptr_t( new branch( left_, right_) ); }
63 
branchbranch64     branch( node::ptr_t left_, node::ptr_t right_) :
65         left( left_), right( right_)
66     {}
67 
acceptbranch68     void accept( visitor & v)
69     { v.visit( * this); }
70 };
71 
72 struct leaf : public node
73 {
74     std::string     value;
75 
createleaf76     static ptr_t create( std::string const& value_)
77     { return ptr_t( new leaf( value_) ); }
78 
leafleaf79     leaf( std::string const& value_) :
80         value( value_)
81     {}
82 
acceptleaf83     void accept( visitor & v)
84     { v.visit( * this); }
85 };
86 
87 inline
88 bool operator==( leaf const& l, leaf  const& r)
89 { return l.value == r.value; }
90 
91 inline
92 bool operator!=( leaf const& l, leaf  const& r)
93 { return l.value != r.value; }
94 
95 class tree_visitor : public visitor
96 {
97 private:
98     boost::coroutines::asymmetric_coroutine< leaf & >::push_type  &   c_;
99 
100 public:
tree_visitor(boost::coroutines::asymmetric_coroutine<leaf &>::push_type & c)101     tree_visitor( boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c) :
102         c_( c)
103     {}
104 
visit(branch & b)105     void visit( branch & b)
106     {
107         if ( b.left) b.left->accept( * this);
108         if ( b.right) b.right->accept( * this);
109     }
110 
visit(leaf & l)111     void visit( leaf & l)
112     { c_( l); }
113 };
114 
enumerate_leafs(boost::coroutines::asymmetric_coroutine<leaf &>::push_type & c,node::ptr_t root)115 void enumerate_leafs( boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c, node::ptr_t root)
116 {
117     tree_visitor v( c);
118     root->accept( v);
119 }
120 
121 #if defined(_MSC_VER)
122 # pragma warning(pop)
123 #endif
124 
125 #endif // TREE_H
126