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
21using namespace std;
22using namespace boost;
23
24class node;
25
26class tree
27{
28 typedef ptr_vector<node> nodes_t;
29 nodes_t nodes;
30
31protected:
32 void swap( tree& r )
33 { nodes.swap( r&: r.nodes ); }
34
35public:
36 typedef nodes_t::iterator iterator;
37 typedef nodes_t::const_iterator const_iterator;
38
39public:
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
55class 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
61public:
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
70class 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>( arg: 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( s&: r.name );
92 tree::swap( r );
93 }
94
95public:
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( r&: *this );
106 return ptr;
107 }
108};
109
110
111
112template< class T >
113class 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
132public:
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
147inline void tree::add_child( node* n )
148{
149 nodes.push_back( x: n );
150}
151
152inline void tree::remove( iterator n )
153{
154 BOOST_ASSERT( n != nodes.end() );
155 nodes.erase( x: n );
156}
157
158void 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
170size_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
184inline node& tree::child( size_t idx )
185{
186 return nodes[idx];
187}
188
189inline const node& tree::child( size_t idx ) const
190{
191 return nodes[idx];
192}
193
194inline tree::iterator tree::child_begin()
195{
196 return nodes.begin();
197}
198
199inline tree::const_iterator tree::child_begin() const
200{
201 return nodes.begin();
202}
203
204inline tree::iterator tree::child_end()
205{
206 return nodes.end();
207}
208
209inline tree::const_iterator tree::child_end() const
210{
211 return nodes.end();
212}
213
214tree::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
239void test_tree()
240{
241 tree root;
242 BOOST_CHECK_EQUAL( root.size(), 1u );
243 inner_node node1( "node 1" );
244 node1.add_child( n: new leaf<string>( "leaf 1" ) );
245 node1.add_child( n: new leaf<int>( 42 ) );
246 inner_node node2( "node 2" );
247 node2.add_child( n: new leaf<float>( 42.0f ) );
248 node2.add_child( n: new leaf<string>( "leaf 4" ) );
249
250 root.add_child( n: node1.release() );
251 BOOST_CHECK_EQUAL( root.size(), 4u );
252 root.add_child( n: node2.release() );
253 root.add_child( n: new inner_node( "node 3" ) );
254 BOOST_CHECK_EQUAL( root.size(), 8u );
255 root.add_child( n: new leaf<string>( "leaf 5" ) );
256 BOOST_CHECK_EQUAL( root.size(), 9u );
257
258 root.write_tree( os&: cout );
259 tree::iterator a_leaf = root.find( match: "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>
268using boost::unit_test::test_suite;
269
270test_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
280

source code of boost/libs/ptr_container/test/tree_test.cpp