// 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 #include #include #include #include #include #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