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&: 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>( 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 | |
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( r&: *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( x: n ); |
150 | } |
151 | |
152 | inline void tree::remove( iterator n ) |
153 | { |
154 | BOOST_ASSERT( n != nodes.end() ); |
155 | nodes.erase( x: 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( 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> |
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 | |
280 | |