123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279 |
- //
- // Boost.Pointer Container
- //
- // Copyright Thorsten Ottosen 2003-2005. Use, modification and
- // distribution is subject to 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)
- //
- // For more information, see http://www.boost.org/libs/ptr_container/
- //
-
- #include "test_data.hpp"
- #include <boost/ptr_container/ptr_vector.hpp>
- #include <boost/utility.hpp>
- #include <boost/lexical_cast.hpp>
- #include <algorithm>
- #include <iostream>
- #include <cstddef>
- #include <string>
- using namespace std;
- using namespace boost;
- class node;
- class tree
- {
- typedef ptr_vector<node> nodes_t;
- nodes_t nodes;
- protected:
- void swap( tree& r )
- { nodes.swap( r.nodes ); }
- public:
- typedef nodes_t::iterator iterator;
- typedef nodes_t::const_iterator const_iterator;
-
- public:
- void add_child( node* n );
- void remove( iterator n );
- void write_tree( ostream& os ) const;
- size_t size() const;
- node& child( size_t idx );
- const node& child( size_t idx ) const;
- iterator child_begin();
- const_iterator child_begin() const;
- iterator child_end();
- const_iterator child_end() const;
- iterator find( const string& match );
- };
- class node : noncopyable
- {
- virtual size_t do_node_size() const = 0;
- virtual string do_description() const = 0;
- virtual void do_write_value( ostream& os ) const = 0;
-
- public:
- virtual ~node() { }
- size_t node_size() const { return do_node_size(); }
- string description() const { return do_description(); }
- void write_value( ostream& os ) const { do_write_value( os ); }
- };
- class inner_node : public node, public tree
- {
- string name;
- virtual size_t do_node_size() const
- {
- return tree::size();
- }
-
- virtual string do_description() const
- {
- return lexical_cast<string>( name );
- }
-
- virtual void do_write_value( ostream& os ) const
- {
- os << " inner node: " << name;
- }
- void swap( inner_node& r )
- {
- name.swap( r.name );
- tree::swap( r );
- }
-
- public:
- inner_node() : name("inner node")
- { }
- inner_node( const string& r ) : name(r)
- { }
- inner_node* release()
- {
- inner_node* ptr( new inner_node );
- ptr->swap( *this );
- return ptr;
- }
- };
-
- template< class T >
- class leaf : public node
- {
- T data;
-
- virtual size_t do_node_size() const
- {
- return 1;
- }
-
- virtual string do_description() const
- {
- return lexical_cast<string>( data );
- }
- virtual void do_write_value( ostream& os ) const
- {
- os << " leaf: " << data;
- }
- public:
- leaf() : data( T() )
- { }
- leaf( const T& r ) : data(r)
- { }
- void set_data( const T& r )
- { data = r; }
- };
- /////////////////////////////////////////////////////////////////////////
- // tree implementation
- /////////////////////////////////////////////////////////////////////////
- inline void tree::add_child( node* n )
- {
- nodes.push_back( n );
- }
- inline void tree::remove( iterator n )
- {
- BOOST_ASSERT( n != nodes.end() );
- nodes.erase( n );
- }
- void tree::write_tree( ostream& os ) const
- {
- for( const_iterator i = nodes.begin(),
- e = nodes.end();
- i != e; ++i )
- {
- i->write_value( os );
- if( const inner_node* p = dynamic_cast<const inner_node*>( &*i ) )
- p->write_tree( os );
- }
- }
- size_t tree::size() const
- {
- size_t res = 1;
- for( const_iterator i = nodes.begin(),
- e = nodes.end();
- i != e; ++i )
- {
- res += i->node_size();
- }
- return res;
- }
- inline node& tree::child( size_t idx )
- {
- return nodes[idx];
- }
- inline const node& tree::child( size_t idx ) const
- {
- return nodes[idx];
- }
- inline tree::iterator tree::child_begin()
- {
- return nodes.begin();
- }
- inline tree::const_iterator tree::child_begin() const
- {
- return nodes.begin();
- }
- inline tree::iterator tree::child_end()
- {
- return nodes.end();
- }
- inline tree::const_iterator tree::child_end() const
- {
- return nodes.end();
- }
- tree::iterator tree::find( const string& match )
- {
- for( iterator i = nodes.begin(),
- e = nodes.end();
- i != e; ++i )
- {
- if( i->description() == match )
- return i;
- if( inner_node* p = dynamic_cast<inner_node*>( &*i ) )
- {
- iterator j = p->find( match );
- if( j != p->child_end() )
- return j;
- }
-
- }
- return child_end();
- }
- /////////////////////////////////////////////////////////////////////////
- // test case
- /////////////////////////////////////////////////////////////////////////
- void test_tree()
- {
- tree root;
- BOOST_CHECK_EQUAL( root.size(), 1u );
- inner_node node1( "node 1" );
- node1.add_child( new leaf<string>( "leaf 1" ) );
- node1.add_child( new leaf<int>( 42 ) );
- inner_node node2( "node 2" );
- node2.add_child( new leaf<float>( 42.0f ) );
- node2.add_child( new leaf<string>( "leaf 4" ) );
-
- root.add_child( node1.release() );
- BOOST_CHECK_EQUAL( root.size(), 4u );
- root.add_child( node2.release() );
- root.add_child( new inner_node( "node 3" ) );
- BOOST_CHECK_EQUAL( root.size(), 8u );
- root.add_child( new leaf<string>( "leaf 5" ) );
- BOOST_CHECK_EQUAL( root.size(), 9u );
- root.write_tree( cout );
- tree::iterator a_leaf = root.find( "42" );
- BOOST_CHECK_EQUAL( a_leaf->description(), "42" );
- leaf<int>& the_leaf = dynamic_cast< leaf<int>& >( *a_leaf );
- the_leaf.set_data( 2*42 );
- BOOST_CHECK_EQUAL( a_leaf->description(), "84" );
- }
- #include <boost/test/unit_test.hpp>
- using boost::unit_test::test_suite;
- test_suite* init_unit_test_suite( int argc, char* argv[] )
- {
- test_suite* test = BOOST_TEST_SUITE( "Pointer Container Test Suite" );
- test->add( BOOST_TEST_CASE( &test_tree ) );
- return test;
- }
|