fixed permissions for stlplus files
[chaz/yoink] / src / Moof / stlplus / ntree.hpp
1 #ifndef STLPLUS_NTREE
2 #define STLPLUS_NTREE
3 ////////////////////////////////////////////////////////////////////////////////
4
5 // Author: Andy Rushton
6 // Copyright: (c) Southampton University 1999-2004
7 // (c) Andy Rushton 2004-2009
8 // License: BSD License, see ../docs/license.html
9
10 // A templated n-ary tree data structure. STL-like but the definition of
11 // iterators is really only applicable to one-dimensional structures. I use
12 // iterators to access tree nodes, but there is no increment or decrement
13 // operators for them. I also define prefix and postfix traversal iterators
14 // which do have increment.
15
16 ////////////////////////////////////////////////////////////////////////////////
17 #include "containers_fixes.hpp"
18 #include "exceptions.hpp"
19 #include "safe_iterator.hpp"
20
21 namespace stlplus
22 {
23
24 ////////////////////////////////////////////////////////////////////////////////
25 // Internals
26
27 template<typename T> class ntree_node;
28 template<typename T> class ntree;
29 template<typename T, typename TRef, typename TPtr> class ntree_iterator;
30 template<typename T, typename TRef, typename TPtr> class ntree_prefix_iterator;
31 template<typename T, typename TRef, typename TPtr> class ntree_postfix_iterator;
32
33 ////////////////////////////////////////////////////////////////////////////////
34 // Iterators
35
36 // Simple iterators which are just used as pointers to tree nodes. These have
37 // no increment or decrement operations defined. An uninitialised iterator is
38 // null - similarly, if you ask for the root of an empty tree or the parent of
39 // the root node then you get a null iterator.
40
41 template<typename T, typename TRef, typename TPtr>
42 class ntree_iterator : public safe_iterator<ntree<T>,ntree_node<T> >
43 {
44 public:
45 // local type definitions
46 // an iterator points to an object whilst a const_iterator points to a const object
47 typedef ntree_iterator<T,T&,T*> iterator;
48 typedef ntree_iterator<T,const T&,const T*> const_iterator;
49 typedef ntree_iterator<T,TRef,TPtr> this_iterator;
50 typedef TRef reference;
51 typedef TPtr pointer;
52
53 // constructor to create a null iterator - you must assign a valid value to this iterator before using it
54 ntree_iterator(void);
55 ~ntree_iterator(void);
56
57 // Type conversion methods allow const_iterator and iterator to be converted
58 const_iterator constify(void) const;
59 iterator deconstify(void) const;
60
61 // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
62 bool operator == (const this_iterator& r) const;
63 bool operator != (const this_iterator& r) const;
64 bool operator < (const this_iterator& r) const;
65
66 // access the node data - a const_iterator gives you a const element, an iterator a non-const element
67 // it is illegal to dereference an invalid (i.e. null or end) iterator
68 reference operator*(void) const
69 throw(null_dereference,end_dereference);
70 pointer operator->(void) const
71 throw(null_dereference,end_dereference);
72
73 friend class ntree<T>;
74 friend class ntree_prefix_iterator<T,TRef,TPtr>;
75 friend class ntree_postfix_iterator<T,TRef,TPtr>;
76
77 public:
78 // Note: I had to make this public to get round a compiler problem - it should be private
79 // you cannot create a valid iterator except by calling an ntree method that returns one
80 // constructor used by ntree to create a non-null iterator
81 explicit ntree_iterator(ntree_node<T>* node);
82 // constructor used by ntree to create an end iterator
83 explicit ntree_iterator(const ntree<T>* owner);
84 // used to create an alias of an iterator
85 explicit ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator);
86 };
87
88 // Traversal iterators are like iterators but they have increment operators (++)
89 // - prefix_iterator visits the nodes of the tree in prefix order
90 // - postfix_iterator visits the nodes of the tree in postfix order.
91 // There is no such thing as infix order for an n-ary tree and you cannot
92 // traverse backwards with these iterators. These follow the STL convention in
93 // that you iterate from a begin to an end - in this case ntree exports
94 // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can
95 // simplify these iterators to the basic iterator above for functions that
96 // require a simple iterator.
97
98 template<typename T, typename TRef, typename TPtr>
99 class ntree_prefix_iterator
100 {
101 public:
102 typedef ntree_prefix_iterator<T,T&,T*> iterator;
103 typedef ntree_prefix_iterator<T,const T&,const T*> const_iterator;
104 typedef ntree_prefix_iterator<T,TRef,TPtr> this_iterator;
105 typedef ntree_iterator<T,TRef,TPtr> simple_iterator;
106 typedef TRef reference;
107 typedef TPtr pointer;
108
109 // constructor to create a null iterator - you must assign a valid value to this iterator before using it
110 ntree_prefix_iterator(void);
111 ~ntree_prefix_iterator(void);
112
113 // tests
114 // a null iterator is one that has not been initialised with a value yet
115 // i.e. you just declared it but didn't assign to it
116 bool null(void) const;
117 // an end iterator is one that points to the end element of the list of nodes
118 // in STL conventions this is one past the last valid element and must not be dereferenced
119 bool end(void) const;
120 // a valid iterator is one that can be dereferenced
121 // i.e. non-null and non-end
122 bool valid(void) const;
123
124 // Type conversion methods allow const_iterator and iterator to be converted
125 // convert an iterator/const_iterator to a const_iterator
126 const_iterator constify(void) const;
127 iterator deconstify(void) const;
128
129 // generate a simple iterator from a traversal iterator
130 ntree_iterator<T,TRef,TPtr> simplify(void) const;
131
132 // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
133 bool operator == (const this_iterator& r) const;
134 bool operator != (const this_iterator& r) const;
135 bool operator < (const this_iterator& r) const;
136
137 // increment/decrement operators used to step through the set of all nodes in a graph
138 // it is only legal to increment a valid iterator
139 // pre-increment
140 this_iterator& operator ++ (void)
141 throw(null_dereference,end_dereference);
142 // post-increment
143 this_iterator operator ++ (int)
144 throw(null_dereference,end_dereference);
145
146 // access the node data - a const_iterator gives you a const element, an iterator a non-const element
147 // it is illegal to dereference an invalid (i.e. null or end) iterator
148 reference operator*(void) const
149 throw(null_dereference,end_dereference);
150 pointer operator->(void) const
151 throw(null_dereference,end_dereference);
152
153 friend class ntree<T>;
154 friend class ntree_iterator<T,TRef,TPtr>;
155
156 private:
157 ntree_iterator<T,TRef,TPtr> m_iterator;
158
159 explicit ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
160 const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
161 ntree_iterator<T,TRef,TPtr>& get_iterator(void);
162 };
163
164 ////////////////////////////////////////////////////////////////////////////////
165
166 template<typename T, typename TRef, typename TPtr>
167 class ntree_postfix_iterator
168 {
169 public:
170 typedef ntree_postfix_iterator<T,T&,T*> iterator;
171 typedef ntree_postfix_iterator<T,const T&,const T*> const_iterator;
172 typedef ntree_postfix_iterator<T,TRef,TPtr> this_iterator;
173 typedef ntree_iterator<T,TRef,TPtr> simple_iterator;
174 typedef TRef reference;
175 typedef TPtr pointer;
176
177 // constructor to create a null iterator - you must assign a valid value to this iterator before using it
178 ntree_postfix_iterator(void);
179 ~ntree_postfix_iterator(void);
180
181 // tests
182 // a null iterator is one that has not been initialised with a value yet
183 // i.e. you just declared it but didn't assign to it
184 bool null(void) const;
185 // an end iterator is one that points to the end element of the list of nodes
186 // in STL conventions this is one past the last valid element and must not be dereferenced
187 bool end(void) const;
188 // a valid iterator is one that can be dereferenced
189 // i.e. non-null and non-end
190 bool valid(void) const;
191
192 // Type conversion methods allow const_iterator and iterator to be converted
193 // convert an iterator/const_iterator to a const_iterator
194 const_iterator constify(void) const;
195 iterator deconstify(void) const;
196
197 // generate a simple iterator from a traversal iterator
198 ntree_iterator<T,TRef,TPtr> simplify(void) const;
199
200 // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
201 bool operator == (const this_iterator& r) const;
202 bool operator != (const this_iterator& r) const;
203 bool operator < (const this_iterator& r) const;
204
205 // increment/decrement operators used to step through the set of all nodes in a graph
206 // it is only legal to increment a valid iterator
207 // pre-increment
208 this_iterator& operator ++ (void)
209 throw(null_dereference,end_dereference);
210 // post-increment
211 this_iterator operator ++ (int)
212 throw(null_dereference,end_dereference);
213
214 // access the node data - a const_iterator gives you a const element, an iterator a non-const element
215 // it is illegal to dereference an invalid (i.e. null or end) iterator
216 reference operator*(void) const
217 throw(null_dereference,end_dereference);
218 pointer operator->(void) const
219 throw(null_dereference,end_dereference);
220
221 friend class ntree<T>;
222 friend class ntree_iterator<T,TRef,TPtr>;
223
224 private:
225 ntree_iterator<T,TRef,TPtr> m_iterator;
226
227 explicit ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
228 const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
229 ntree_iterator<T,TRef,TPtr>& get_iterator(void);
230 };
231
232 ////////////////////////////////////////////////////////////////////////////////
233 // The Ntree class
234 ////////////////////////////////////////////////////////////////////////////////
235
236 template<typename T>
237 class ntree
238 {
239 public:
240 // STL-like typedefs for the types and iterators
241 typedef T value_type;
242
243 typedef ntree_iterator<T,T&,T*> iterator;
244 typedef ntree_iterator<T,const T&,const T*> const_iterator;
245
246 typedef ntree_prefix_iterator<T,T&,T*> prefix_iterator;
247 typedef ntree_prefix_iterator<T,const T&,const T*> const_prefix_iterator;
248
249 typedef ntree_postfix_iterator<T,T&,T*> postfix_iterator;
250 typedef ntree_postfix_iterator<T,const T&,const T*> const_postfix_iterator;
251
252 //////////////////////////////////////////////////////////////////////////////
253 // Constructors, destructors and copies
254
255 ntree(void);
256 ~ntree(void);
257
258 // copy constructor and assignment both copy the tree
259 ntree(const ntree<T>&);
260 ntree<T>& operator=(const ntree<T>&);
261
262 //////////////////////////////////////////////////////////////////////////////
263 // size tests
264
265 // tests on whole tree
266 bool empty(void) const;
267 unsigned size(void) const;
268
269 // tests for number of nodes in subtree starting at node
270 unsigned size(const const_iterator& node) const
271 throw(wrong_object,null_dereference,end_dereference);
272 unsigned size(const iterator& node)
273 throw(wrong_object,null_dereference,end_dereference);
274
275 // test for depth of tree from root to node
276 unsigned depth(const const_iterator& node) const
277 throw(wrong_object,null_dereference,end_dereference);
278 unsigned depth(const iterator& node)
279 throw(wrong_object,null_dereference,end_dereference);
280
281 //////////////////////////////////////////////////////////////////////////////
282 // direct traversal
283
284 const_iterator root(void) const;
285 iterator root(void);
286
287 unsigned children(const const_iterator& node) const
288 throw(wrong_object,null_dereference,end_dereference);
289 unsigned children(const iterator& node)
290 throw(wrong_object,null_dereference,end_dereference);
291
292 const_iterator child(const const_iterator& node, unsigned child) const
293 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
294 iterator child(const iterator& node, unsigned child)
295 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
296
297 const_iterator parent(const const_iterator& node) const
298 throw(wrong_object,null_dereference,end_dereference);
299 iterator parent(const iterator& node)
300 throw(wrong_object,null_dereference,end_dereference);
301
302 //////////////////////////////////////////////////////////////////////////////
303 // iterator traversal
304
305 const_prefix_iterator prefix_begin(void) const;
306 prefix_iterator prefix_begin(void);
307 const_prefix_iterator prefix_end(void) const;
308 prefix_iterator prefix_end(void);
309
310 const_postfix_iterator postfix_begin(void) const;
311 postfix_iterator postfix_begin(void);
312 const_postfix_iterator postfix_end(void) const;
313 postfix_iterator postfix_end(void);
314
315 //////////////////////////////////////////////////////////////////////////////
316 // modification
317
318 iterator insert(const T&);
319
320 iterator insert(const iterator& node, unsigned child, const T&)
321 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
322 iterator append(const iterator& node, const T&)
323 throw(wrong_object,null_dereference,end_dereference);
324
325 iterator insert(const iterator& node, unsigned child, const ntree<T>&)
326 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
327 iterator append(const iterator& node, const ntree<T>&)
328 throw(wrong_object,null_dereference,end_dereference);
329
330 iterator push(const iterator& node, const T&)
331 throw(wrong_object,null_dereference,end_dereference);
332 void pop(const iterator& node, unsigned child)
333 throw(wrong_object,null_dereference,end_dereference);
334
335 void erase(void);
336 void erase(const iterator& node)
337 throw(wrong_object,null_dereference,end_dereference);
338 void erase(const iterator& node, unsigned child)
339 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
340
341 ntree<T> subtree(void);
342 ntree<T> subtree(const iterator& node)
343 throw(wrong_object,null_dereference,end_dereference);
344 ntree<T> subtree(const iterator& node, unsigned child)
345 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
346
347 ntree<T> cut(void);
348 ntree<T> cut(const iterator& node)
349 throw(wrong_object,null_dereference,end_dereference);
350 ntree<T> cut(const iterator& node, unsigned child)
351 throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
352
353 //////////////////////////////////////////////////////////////////////////////
354
355 private:
356 ntree_node<T>* m_root;
357 };
358
359 ////////////////////////////////////////////////////////////////////////////////
360
361 } // end namespace stlplus
362
363 #include "ntree.tpp"
364 #endif
This page took 0.049436 seconds and 4 git commands to generate.