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