• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 
2 //          Copyright Oliver Kowalke 2014.
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 <cstddef>
11 #include <string>
12 
13 #include <boost/assert.hpp>
14 #include <boost/config.hpp>
15 #include <boost/intrusive_ptr.hpp>
16 
17 #if defined(_MSC_VER)
18 # pragma warning(push)
19 # pragma warning(disable:4355)
20 #endif
21 
22 struct branch;
23 struct leaf;
24 
25 struct visitor
26 {
~visitorvisitor27     virtual ~visitor() {};
28 
29     virtual void visit( branch & b) = 0;
30     virtual void visit( leaf & l) = 0;
31 };
32 
33 struct node
34 {
35     typedef boost::intrusive_ptr< node >    ptr_t;
36 
37     std::size_t     use_count;
38 
nodenode39     node() :
40         use_count( 0)
41     {}
42 
~nodenode43     virtual ~node() {}
44 
45     virtual void accept( visitor & v) = 0;
46 
intrusive_ptr_add_refnode47     friend inline void intrusive_ptr_add_ref( node * p)
48     { ++p->use_count; }
49 
intrusive_ptr_releasenode50     friend inline void intrusive_ptr_release( node * p)
51     { if ( 0 == --p->use_count) delete p; }
52 };
53 
54 struct branch : public node
55 {
56     node::ptr_t     left;
57     node::ptr_t     right;
58 
createbranch59     static ptr_t create( node::ptr_t left_, node::ptr_t right_)
60     { return ptr_t( new branch( left_, right_) ); }
61 
branchbranch62     branch( node::ptr_t left_, node::ptr_t right_) :
63         left( left_), right( right_)
64     {}
65 
acceptbranch66     void accept( visitor & v)
67     { v.visit( * this); }
68 };
69 
70 struct leaf : public node
71 {
72     std::string     value;
73 
createleaf74     static ptr_t create( std::string const& value_)
75     { return ptr_t( new leaf( value_) ); }
76 
leafleaf77     leaf( std::string const& value_) :
78         value( value_)
79     {}
80 
acceptleaf81     void accept( visitor & v)
82     { v.visit( * this); }
83 };
84 
85 inline
86 bool operator==( leaf const& l, leaf  const& r)
87 { return l.value == r.value; }
88 
89 inline
90 bool operator!=( leaf const& l, leaf  const& r)
91 { return l.value != r.value; }
92 
93 #if defined(_MSC_VER)
94 # pragma warning(pop)
95 #endif
96 
97 #endif // TREE_H
98