libs/coroutine/example/asymmetric/tree.h

   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 {
  29     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
  41     node() :
  42         use_count( 0)
  43     {}
  44
  45     virtual ~node() {}
  46
  47     virtual void accept( visitor & v) = 0;
  48
  49     friend inline void intrusive_ptr_add_ref( node * p)
  50     { ++p->use_count; }
  51
  52     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
  61     static ptr_t create( node::ptr_t left_, node::ptr_t right_)
  62     { return ptr_t( new branch( left_, right_) ); }
  63
  64     branch( node::ptr_t left_, node::ptr_t right_) :
  65         left( left_), right( right_)
  66     {}
  67
  68     void accept( visitor & v)
  69     { v.visit( * this); }
  70 };
  71
  72 struct leaf : public node
  73 {
  74     std::string     value;
  75
  76     static ptr_t create( std::string const& value_)
  77     { return ptr_t( new leaf( value_) ); }
  78
  79     leaf( std::string const& value_) :
  80         value( value_)
  81     {}
  82
  83     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:
 101     tree_visitor( boost::coroutines::asymmetric_coroutine< leaf & >::push_type & c) :
 102         c_( c)
 103     {}
 104
 105     void visit( branch & b)
 106     {
 107         if ( b.left) b.left->accept( * this);
 108         if ( b.right) b.right->accept( * this);
 109     }
 110
 111     void visit( leaf & l)
 112     { c_( l); }
 113 };
 114
 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