ceph/src/boost/libs/ptr_container/test/tree_test.cpp

   1 //
   2 // Boost.Pointer Container
   3 //
   4 //  Copyright Thorsten Ottosen 2003-2005. Use, modification and
   5 //  distribution is subject to the Boost Software License, Version
   6 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // For more information, see http://www.boost.org/libs/ptr_container/
  10 //
  11
  12 #include "test_data.hpp"
  13 #include <boost/ptr_container/ptr_vector.hpp>
  14 #include <boost/utility.hpp>
  15 #include <boost/lexical_cast.hpp>
  16 #include <algorithm>
  17 #include <iostream>
  18 #include <cstddef>
  19 #include <string>
  20
  21 using namespace std;
  22 using namespace boost;
  23
  24 class node;
  25
  26 class tree
  27 {
  28     typedef ptr_vector<node> nodes_t;
  29     nodes_t nodes;
  30
  31 protected:
  32         void swap( tree& r )
  33             { nodes.swap( r.nodes ); }
  34
  35 public:
  36     typedef nodes_t::iterator       iterator;
  37     typedef nodes_t::const_iterator const_iterator;
  38
  39 public:
  40     void            add_child( node* n );
  41     void            remove( iterator n );
  42     void            write_tree( ostream& os ) const;
  43     size_t          size() const;
  44     node&           child( size_t idx );
  45     const node&     child( size_t idx ) const;
  46     iterator        child_begin();
  47     const_iterator  child_begin() const;
  48     iterator        child_end();
  49     const_iterator  child_end() const;
  50     iterator        find( const string& match );
  51 };
  52
  53
  54
  55 class node : noncopyable
  56 {
  57     virtual size_t  do_node_size() const = 0;
  58     virtual string  do_description() const = 0;
  59     virtual void    do_write_value( ostream& os ) const = 0;
  60
  61 public:
  62     virtual  ~node()                           { }
  63     size_t   node_size() const                 { return do_node_size(); }
  64     string   description() const               { return do_description(); }
  65     void     write_value( ostream& os ) const  { do_write_value( os ); }
  66 };
  67
  68
  69
  70 class inner_node : public node, public tree
  71 {
  72     string name;
  73
  74     virtual size_t do_node_size() const
  75     {
  76         return tree::size();
  77     }
  78
  79     virtual string do_description() const
  80     {
  81         return lexical_cast<string>( name );
  82     }
  83
  84     virtual void do_write_value( ostream& os ) const
  85     {
  86         os << " inner node: " << name;
  87     }
  88
  89     void swap( inner_node& r )
  90     {
  91         name.swap( r.name );
  92         tree::swap( r );
  93     }
  94
  95 public:
  96     inner_node() : name("inner node")
  97     { }
  98
  99     inner_node( const string& r ) : name(r)
 100     { }
 101
 102     inner_node* release()
 103     {
 104         inner_node* ptr( new inner_node );
 105         ptr->swap( *this );
 106         return ptr;
 107     }
 108 };
 109
 110
 111
 112 template< class T >
 113 class leaf : public node
 114 {
 115     T data;
 116
 117     virtual size_t do_node_size() const
 118     {
 119         return 1;
 120     }
 121
 122     virtual string do_description() const
 123     {
 124         return lexical_cast<string>( data );
 125     }
 126
 127     virtual void do_write_value( ostream& os ) const
 128     {
 129         os << " leaf: " << data;
 130     }
 131
 132 public:
 133     leaf() : data( T() )
 134     { }
 135
 136     leaf( const T& r ) : data(r)
 137     { }
 138
 139     void set_data( const T& r )
 140     { data = r; }
 141 };
 142
 143 /////////////////////////////////////////////////////////////////////////
 144 // tree implementation
 145 /////////////////////////////////////////////////////////////////////////
 146
 147 inline void tree::add_child( node* n )
 148 {
 149     nodes.push_back( n );
 150 }
 151
 152 inline void tree::remove( iterator n )
 153 {
 154     BOOST_ASSERT( n != nodes.end() );
 155     nodes.erase( n );
 156 }
 157
 158 void tree::write_tree( ostream& os ) const
 159 {
 160     for( const_iterator i = nodes.begin(),
 161                         e = nodes.end();
 162          i != e; ++i )
 163     {
 164         i->write_value( os );
 165         if( const inner_node* p = dynamic_cast<const inner_node*>( &*i ) )
 166             p->write_tree( os );
 167     }
 168 }
 169
 170 size_t tree::size() const
 171 {
 172     size_t res = 1;
 173
 174     for( const_iterator i = nodes.begin(),
 175                         e = nodes.end();
 176          i != e; ++i )
 177     {
 178         res += i->node_size();
 179     }
 180
 181     return res;
 182 }
 183
 184 inline node& tree::child( size_t idx )
 185 {
 186     return nodes[idx];
 187 }
 188
 189 inline const node& tree::child( size_t idx ) const
 190 {
 191     return nodes[idx];
 192 }
 193
 194 inline tree::iterator tree::child_begin()
 195 {
 196     return nodes.begin();
 197 }
 198
 199 inline tree::const_iterator tree::child_begin() const
 200 {
 201     return nodes.begin();
 202 }
 203
 204 inline tree::iterator tree::child_end()
 205 {
 206     return nodes.end();
 207 }
 208
 209 inline tree::const_iterator tree::child_end() const
 210 {
 211     return nodes.end();
 212 }
 213
 214 tree::iterator tree::find( const string& match )
 215 {
 216     for( iterator i = nodes.begin(),
 217                   e = nodes.end();
 218          i != e; ++i )
 219     {
 220         if( i->description() == match )
 221             return i;
 222
 223         if( inner_node* p = dynamic_cast<inner_node*>( &*i ) )
 224         {
 225             iterator j = p->find( match );
 226             if( j != p->child_end() )
 227                 return j;
 228         }
 229
 230     }
 231
 232     return child_end();
 233 }
 234
 235 /////////////////////////////////////////////////////////////////////////
 236 // test case
 237 /////////////////////////////////////////////////////////////////////////
 238
 239 void test_tree()
 240 {
 241     tree root;
 242     BOOST_CHECK_EQUAL( root.size(), 1u );
 243     inner_node node1( "node 1" );
 244     node1.add_child( new leaf<string>( "leaf 1" ) );
 245     node1.add_child( new leaf<int>( 42 ) );
 246     inner_node node2( "node 2" );
 247     node2.add_child( new leaf<float>( 42.0f ) );
 248     node2.add_child( new leaf<string>( "leaf 4" ) );
 249
 250     root.add_child( node1.release() );
 251     BOOST_CHECK_EQUAL( root.size(), 4u );
 252     root.add_child( node2.release() );
 253     root.add_child( new inner_node( "node 3" ) );
 254     BOOST_CHECK_EQUAL( root.size(), 8u );
 255     root.add_child( new leaf<string>( "leaf 5" ) );
 256     BOOST_CHECK_EQUAL( root.size(), 9u );
 257
 258     root.write_tree( cout );
 259     tree::iterator a_leaf = root.find( "42" );
 260     BOOST_CHECK_EQUAL( a_leaf->description(), "42" );
 261     leaf<int>& the_leaf = dynamic_cast< leaf<int>& >( *a_leaf );
 262     the_leaf.set_data( 2*42 );
 263     BOOST_CHECK_EQUAL( a_leaf->description(), "84" );
 264
 265 }
 266
 267 #include <boost/test/unit_test.hpp>
 268 using boost::unit_test::test_suite;
 269
 270 test_suite* init_unit_test_suite( int argc, char* argv[] )
 271 {
 272     test_suite* test = BOOST_TEST_SUITE( "Pointer Container Test Suite" );
 273
 274     test->add( BOOST_TEST_CASE( &test_tree ) );
 275
 276     return test;
 277 }
 278
 279