]> Dogcows Code - chaz/yoink/blob - ntree.tpp
6fd019d9f30b7eee6fe71ebd682e9667172060c4
[chaz/yoink] / ntree.tpp
1 ////////////////////////////////////////////////////////////////////////////////
2
3 // Author: Andy Rushton
4 // Copyright: (c) Southampton University 1999-2004
5 // (c) Andy Rushton 2004-2009
6 // License: BSD License, see ../docs/license.html
7
8 ////////////////////////////////////////////////////////////////////////////////
9 #include <vector>
10 #include <algorithm>
11
12 namespace stlplus
13 {
14
15 ////////////////////////////////////////////////////////////////////////////////
16 // ntree_node
17
18 template<typename T>
19 class ntree_node
20 {
21 public:
22 master_iterator<ntree<T>, ntree_node<T> > m_master;
23 T m_data;
24 ntree_node<T>* m_parent;
25 std::vector<ntree_node<T>*> m_children;
26
27 public:
28 ntree_node(const ntree<T>* owner, const T& data = T()) :
29 m_master(owner,this), m_data(data), m_parent(0)
30 {
31 }
32
33 void change_owner(const ntree<T>* owner)
34 {
35 m_master.change_owner(owner);
36 for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
37 (*i)->change_owner(owner);
38 }
39
40 ~ntree_node(void)
41 {
42 m_parent = 0;
43 for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
44 delete *i;
45 }
46
47 };
48
49 template<typename T>
50 static ntree_node<T>* ntree_copy(const ntree<T>* new_owner, ntree_node<T>* root)
51 {
52 if (!root) return 0;
53 ntree_node<T>* new_tree = new ntree_node<T>(new_owner, root->m_data);
54 for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
55 {
56 ntree_node<T>* new_child = ntree_copy(new_owner, *i);
57 new_tree->m_children.push_back(new_child);
58 new_child->m_parent = new_tree;
59 }
60 return new_tree;
61 }
62
63 template<typename T>
64 static unsigned ntree_size(ntree_node<T>* root)
65 {
66 if (!root) return 0;
67 unsigned result = 1;
68 for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
69 result += ntree_size(*i);
70 return result;
71 }
72
73 template<typename T>
74 static unsigned ntree_depth(ntree_node<T>* root)
75 {
76 unsigned depth = 0;
77 for (ntree_node<T>* i = root; i; i = i->m_parent)
78 depth++;
79 return depth;
80 }
81
82 ////////////////////////////////////////////////////////////////////////////////
83 // ntree_iterator
84
85 // constructor to create a null iterator - you must assign a valid value to this iterator before using it
86 template<typename T, typename TRef, typename TPtr>
87 ntree_iterator<T,TRef,TPtr>::ntree_iterator(void)
88 {
89 }
90
91 // used to create an alias of an iterator
92 template<typename T, typename TRef, typename TPtr>
93 ntree_iterator<T,TRef,TPtr>::ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator) :
94 safe_iterator<ntree<T>,ntree_node<T> >(iterator)
95 {
96 }
97
98 // constructor used by ntree to create a non-null iterator
99 template<typename T, typename TRef, typename TPtr>
100 ntree_iterator<T,TRef,TPtr>::ntree_iterator(ntree_node<T>* node) :
101 safe_iterator<ntree<T>,ntree_node<T> >(node->m_master)
102 {
103 }
104
105 // constructor used by ntree to create an end iterator
106 template<typename T, typename TRef, typename TPtr>
107 ntree_iterator<T,TRef,TPtr>::ntree_iterator(const ntree<T>* owner) :
108 safe_iterator<ntree<T>,ntree_node<T> >(owner)
109 {
110 }
111
112 // destructor
113 template<typename T, typename TRef, typename TPtr>
114 ntree_iterator<T,TRef,TPtr>::~ntree_iterator(void)
115 {
116 }
117
118 template<typename T, typename TRef, typename TPtr>
119 TYPENAME ntree_iterator<T,TRef,TPtr>::const_iterator ntree_iterator<T,TRef,TPtr>::constify(void) const
120 {
121 return ntree_iterator<T,const T&,const T*>(*this);
122 }
123
124 template<typename T, typename TRef, typename TPtr>
125 TYPENAME ntree_iterator<T,TRef,TPtr>::iterator ntree_iterator<T,TRef,TPtr>::deconstify(void) const
126 {
127 return ntree_iterator<T,T&,T*>(*this);
128 }
129
130 template<typename T, typename TRef, typename TPtr>
131 bool ntree_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
132 {
133 return equal(r);
134 }
135
136 template<typename T, typename TRef, typename TPtr>
137 bool ntree_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
138 {
139 return !operator==(r);
140 }
141
142 template<typename T, typename TRef, typename TPtr>
143 bool ntree_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
144 {
145 return compare(r) < 0;
146 }
147
148 template<typename T, typename TRef, typename TPtr>
149 TYPENAME ntree_iterator<T,TRef,TPtr>::reference ntree_iterator<T,TRef,TPtr>::operator*(void) const
150 throw(null_dereference,end_dereference)
151 {
152 this->assert_valid();
153 return this->node()->m_data;
154 }
155
156 template<typename T, typename TRef, typename TPtr>
157 TYPENAME ntree_iterator<T,TRef,TPtr>::pointer ntree_iterator<T,TRef,TPtr>::operator->(void) const
158 throw(null_dereference,end_dereference)
159 {
160 return &(operator*());
161 }
162
163 ////////////////////////////////////////////////////////////////////////////////
164 // ntree_prefix_iterator
165
166 template<typename T, typename TRef, typename TPtr>
167 ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(void)
168 {
169 }
170
171 template<typename T, typename TRef, typename TPtr>
172 ntree_prefix_iterator<T,TRef,TPtr>::~ntree_prefix_iterator(void)
173 {
174 }
175
176 template<typename T, typename TRef, typename TPtr>
177 ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
178 m_iterator(i)
179 {
180 // this is initialised with the root node
181 // which is also the first node in prefix traversal order
182 }
183
184 template<typename T, typename TRef, typename TPtr>
185 bool ntree_prefix_iterator<T,TRef,TPtr>::null(void) const
186 {
187 return m_iterator.null();
188 }
189
190 template<typename T, typename TRef, typename TPtr>
191 bool ntree_prefix_iterator<T,TRef,TPtr>::end(void) const
192 {
193 return m_iterator.end();
194 }
195
196 template<typename T, typename TRef, typename TPtr>
197 bool ntree_prefix_iterator<T,TRef,TPtr>::valid(void) const
198 {
199 return m_iterator.valid();
200 }
201
202 template<typename T, typename TRef, typename TPtr>
203 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::const_iterator ntree_prefix_iterator<T,TRef,TPtr>::constify(void) const
204 {
205 return ntree_prefix_iterator<T,const T&,const T*>(m_iterator);
206 }
207
208 template<typename T, typename TRef, typename TPtr>
209 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::iterator ntree_prefix_iterator<T,TRef,TPtr>::deconstify(void) const
210 {
211 return ntree_prefix_iterator<T,T&,T*>(m_iterator);
212 }
213
214 template<typename T, typename TRef, typename TPtr>
215 ntree_iterator<T,TRef,TPtr> ntree_prefix_iterator<T,TRef,TPtr>::simplify(void) const
216 {
217 return m_iterator;
218 }
219
220 template<typename T, typename TRef, typename TPtr>
221 bool ntree_prefix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
222 {
223 return m_iterator == r.m_iterator;
224 }
225
226 template<typename T, typename TRef, typename TPtr>
227 bool ntree_prefix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
228 {
229 return m_iterator != r.m_iterator;
230 }
231
232 template<typename T, typename TRef, typename TPtr>
233 bool ntree_prefix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
234 {
235 return m_iterator < r.m_iterator;
236 }
237
238 template<typename T, typename TRef, typename TPtr>
239 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (void)
240 throw(null_dereference,end_dereference)
241 {
242 // pre-increment operator
243 // algorithm: if there are any children, visit child 0, otherwise, go to
244 // parent and deduce which child the start node was of that parent - if
245 // there are further children, go into the next one. Otherwise, go up the
246 // tree and test again for further children. Return null if there are no
247 // further nodes
248 m_iterator.assert_valid();
249 ntree_node<T>* old_node = m_iterator.node();
250 if (!old_node->m_children.empty())
251 {
252 // simply take the first child of this node
253 m_iterator.set(old_node->m_children[0]->m_master);
254 }
255 else
256 {
257 // this loop walks up the parent pointers
258 // either it will walk off the top and exit or a new node will be found and the loop will exit
259 for (;;)
260 {
261 // go up a level
262 ntree_node<T>* parent = old_node->m_parent;
263 if (!parent)
264 {
265 // we've walked off the top of the tree, so return end
266 m_iterator.set_end();
267 break;
268 }
269 else
270 {
271 // otherwise walk down the next child - if there is one
272 // find which index the old node was relative to this node
273 TYPENAME std::vector<ntree_node<T>*>::iterator found =
274 std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
275 // if this was found, then see if there is another and if so return that
276 found++;
277 if (found != parent->m_children.end())
278 {
279 // visit the next child
280 m_iterator.set((*found)->m_master);
281 break;
282 }
283 else
284 {
285 // keep going up
286 old_node = parent;
287 }
288 }
289 }
290 }
291 return *this;
292 }
293
294 template<typename T, typename TRef, typename TPtr>
295 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (int)
296 throw(null_dereference,end_dereference)
297 {
298 // post-increment is defined in terms of the pre-increment
299 ntree_prefix_iterator<T,TRef,TPtr> result(*this);
300 ++(*this);
301 return result;
302 }
303
304 template<typename T, typename TRef, typename TPtr>
305 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::reference ntree_prefix_iterator<T,TRef,TPtr>::operator*(void) const
306 throw(null_dereference,end_dereference)
307 {
308 return m_iterator.operator*();
309 }
310
311 template<typename T, typename TRef, typename TPtr>
312 TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::pointer ntree_prefix_iterator<T,TRef,TPtr>::operator->(void) const
313 throw(null_dereference,end_dereference)
314 {
315 return m_iterator.operator->();
316 }
317
318 template<typename T, typename TRef, typename TPtr>
319 const ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void) const
320 {
321 return m_iterator;
322 }
323
324 template<typename T, typename TRef, typename TPtr>
325 ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void)
326 {
327 return m_iterator;
328 }
329
330 ////////////////////////////////////////////////////////////////////////////////
331 // ntree_postfix_iterator
332
333 template<typename T, typename TRef, typename TPtr>
334 ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(void)
335 {
336 }
337
338 template<typename T, typename TRef, typename TPtr>
339 ntree_postfix_iterator<T,TRef,TPtr>::~ntree_postfix_iterator(void)
340 {
341 }
342
343 template<typename T, typename TRef, typename TPtr>
344 ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
345 m_iterator(i)
346 {
347 // this is initialised with the root node
348 // initially traverse to the first node to be visited
349 if (m_iterator.valid())
350 {
351 ntree_node<T>* node = m_iterator.node();
352 while (!node->m_children.empty())
353 node = node->m_children[0];
354 m_iterator.set(node->m_master);
355 }
356 }
357
358 template<typename T, typename TRef, typename TPtr>
359 bool ntree_postfix_iterator<T,TRef,TPtr>::null(void) const
360 {
361 return m_iterator.null();
362 }
363
364 template<typename T, typename TRef, typename TPtr>
365 bool ntree_postfix_iterator<T,TRef,TPtr>::end(void) const
366 {
367 return m_iterator.end();
368 }
369
370 template<typename T, typename TRef, typename TPtr>
371 bool ntree_postfix_iterator<T,TRef,TPtr>::valid(void) const
372 {
373 return m_iterator.valid();
374 }
375
376 template<typename T, typename TRef, typename TPtr>
377 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::const_iterator ntree_postfix_iterator<T,TRef,TPtr>::constify(void) const
378 {
379 return ntree_postfix_iterator<T,const T&,const T*>(m_iterator);
380 }
381
382 template<typename T, typename TRef, typename TPtr>
383 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::iterator ntree_postfix_iterator<T,TRef,TPtr>::deconstify(void) const
384 {
385 return ntree_postfix_iterator<T,T&,T*>(m_iterator);
386 }
387
388 template<typename T, typename TRef, typename TPtr>
389 ntree_iterator<T,TRef,TPtr> ntree_postfix_iterator<T,TRef,TPtr>::simplify(void) const
390 {
391 return m_iterator;
392 }
393
394 template<typename T, typename TRef, typename TPtr>
395 bool ntree_postfix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
396 {
397 return m_iterator == r.m_iterator;
398 }
399
400 template<typename T, typename TRef, typename TPtr>
401 bool ntree_postfix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
402 {
403 return m_iterator != r.m_iterator;
404 }
405
406 template<typename T, typename TRef, typename TPtr>
407 bool ntree_postfix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
408 {
409 return m_iterator < r.m_iterator;
410 }
411
412 template<typename T, typename TRef, typename TPtr>
413 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (void)
414 throw(null_dereference,end_dereference)
415 {
416 // pre-increment operator
417 // algorithm: this node has been visited, therefore all children must have
418 // already been visited. So go to parent. Return null if the parent is null.
419 // Otherwise deduce which child the start node was of that parent - if there
420 // are further children, go into the next one and then walk down any
421 // subsequent first-child pointers to the bottom. Otherwise, if there are no
422 // children then the parent node is the next in the traversal.
423 m_iterator.assert_valid();
424 // go up a level
425 ntree_node<T>* old_node = m_iterator.node();
426 ntree_node<T>* parent = old_node->m_parent;
427 if (!parent)
428 {
429 // we've walked off the top of the tree, so return end
430 m_iterator.set_end();
431 }
432 else
433 {
434 // otherwise find which index the old node was relative to this node
435 TYPENAME std::vector<ntree_node<T>*>::iterator found =
436 std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
437 // if this was found, then see if there is another
438 found++;
439 if (found != parent->m_children.end())
440 {
441 // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree
442 ntree_node<T>* new_node = *found;
443 while (!new_node->m_children.empty())
444 new_node = new_node->m_children[0];
445 m_iterator.set(new_node->m_master);
446 }
447 else
448 {
449 // the parent's children have all been visited - so the parent is visited
450 m_iterator.set(parent->m_master);
451 }
452 }
453 return *this;
454 }
455
456 template<typename T, typename TRef, typename TPtr>
457 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (int)
458 throw(null_dereference,end_dereference)
459 {
460 // post-increment is defined in terms of the pre-increment
461 ntree_postfix_iterator<T,TRef,TPtr> result(*this);
462 ++(*this);
463 return result;
464 }
465
466 template<typename T, typename TRef, typename TPtr>
467 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::reference ntree_postfix_iterator<T,TRef,TPtr>::operator*(void) const
468 throw(null_dereference,end_dereference)
469 {
470 return m_iterator.operator*();
471 }
472
473 template<typename T, typename TRef, typename TPtr>
474 TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::pointer ntree_postfix_iterator<T,TRef,TPtr>::operator->(void) const
475 throw(null_dereference,end_dereference)
476 {
477 return m_iterator.operator->();
478 }
479
480 template<typename T, typename TRef, typename TPtr>
481 const ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void) const
482 {
483 return m_iterator;
484 }
485
486 template<typename T, typename TRef, typename TPtr>
487 ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void)
488 {
489 return m_iterator;
490 }
491
492 ////////////////////////////////////////////////////////////////////////////////
493 ////////////////////////////////////////////////////////////////////////////////
494 // ntree
495 ////////////////////////////////////////////////////////////////////////////////
496 ////////////////////////////////////////////////////////////////////////////////
497
498 template<typename T>
499 ntree<T>::ntree(void) : m_root(0)
500 {
501 }
502
503 template<typename T>
504 ntree<T>::~ntree(void)
505 {
506 if (m_root) delete m_root;
507 }
508
509 template<typename T>
510 ntree<T>::ntree(const ntree<T>& r) : m_root(0)
511 {
512 *this = r;
513 }
514
515 template<typename T>
516 ntree<T>& ntree<T>::operator=(const ntree<T>& r)
517 {
518 if (m_root) delete m_root;
519 m_root = ntree_copy(this, r.m_root);
520 return *this;
521 }
522
523 template<typename T>
524 bool ntree<T>::empty(void) const
525 {
526 return m_root == 0;
527 }
528
529 template<typename T>
530 unsigned ntree<T>::size(void) const
531 {
532 return ntree_size(m_root);
533 }
534
535 template<typename T>
536 unsigned ntree<T>::size(const TYPENAME ntree<T>::const_iterator& i) const
537 throw(wrong_object,null_dereference,end_dereference)
538 {
539 i.assert_valid(this);
540 return ntree_size(i.node());
541 }
542
543 template<typename T>
544 unsigned ntree<T>::size(const TYPENAME ntree<T>::iterator& i)
545 throw(wrong_object,null_dereference,end_dereference)
546 {
547 i.assert_valid(this);
548 return ntree_size(i.node());
549 }
550
551 template<typename T>
552 unsigned ntree<T>::depth(const TYPENAME ntree<T>::const_iterator& i) const
553 throw(wrong_object,null_dereference,end_dereference)
554 {
555 i.assert_valid(this);
556 return ntree_depth(i.node());
557 }
558
559 template<typename T>
560 unsigned ntree<T>::depth(const TYPENAME ntree<T>::iterator& i)
561 throw(wrong_object,null_dereference,end_dereference)
562 {
563 i.assert_valid(this);
564 return ntree_depth(i.node());
565 }
566
567 template<typename T>
568 TYPENAME ntree<T>::const_iterator ntree<T>::root(void) const
569 {
570 if (!m_root) return ntree_iterator<T,const T&,const T*>(this);
571 return ntree_iterator<T,const T&,const T*>(m_root);
572 }
573
574 template<typename T>
575 TYPENAME ntree<T>::iterator ntree<T>::root(void)
576 {
577 if (!m_root) return ntree_iterator<T,T&,T*>(this);
578 return ntree_iterator<T,T&,T*>(m_root);
579 }
580
581 template<typename T>
582 unsigned ntree<T>::children(const TYPENAME ntree<T>::const_iterator& i) const
583 throw(wrong_object,null_dereference,end_dereference)
584 {
585 i.assert_valid(this);
586 return i.node()->m_children.size();
587 }
588
589 template<typename T>
590 unsigned ntree<T>::children(const ntree_iterator<T,T&,T*>& i)
591 throw(wrong_object,null_dereference,end_dereference)
592 {
593 i.assert_valid(this);
594 return i.node()->m_children.size();
595 }
596
597 template<typename T>
598 TYPENAME ntree<T>::const_iterator ntree<T>::child(const TYPENAME ntree<T>::const_iterator& i, unsigned child) const
599 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
600 {
601 i.assert_valid(this);
602 if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
603 return ntree_iterator<T,const T&,const T*>(i.node()->m_children[child]);
604 }
605
606 template<typename T>
607 TYPENAME ntree<T>::iterator ntree<T>::child(const TYPENAME ntree<T>::iterator& i, unsigned child)
608 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
609 {
610 i.assert_valid(this);
611 if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
612 return ntree_iterator<T,T&,T*>(i.node()->m_children[child]);
613 }
614
615 template<typename T>
616 TYPENAME ntree<T>::const_iterator ntree<T>::parent(const TYPENAME ntree<T>::const_iterator& i) const
617 throw(wrong_object,null_dereference,end_dereference)
618 {
619 i.assert_valid(this);
620 ntree_node<T>* parent = i.node()->m_parent;
621 if (!parent) return ntree_iterator<T,const T&,const T*>(this);
622 return ntree_iterator<T,const T&,const T*>(parent);
623 }
624
625 template<typename T>
626 TYPENAME ntree<T>::iterator ntree<T>::parent(const TYPENAME ntree<T>::iterator& i)
627 throw(wrong_object,null_dereference,end_dereference)
628 {
629 i.assert_valid(this);
630 ntree_node<T>* parent = i.node()->m_parent;
631 if (!parent) return ntree_iterator<T,T&,T*>(this);
632 return ntree_iterator<T,T&,T*>(parent);
633 }
634
635 template<typename T>
636 TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_begin(void) const
637 {
638 return ntree_prefix_iterator<T,const T&,const T*>(root());
639 }
640
641 template<typename T>
642 TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_begin(void)
643 {
644 return ntree_prefix_iterator<T,T&,T*>(root());
645 }
646
647 template<typename T>
648 TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_end(void) const
649 {
650 return ntree_prefix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
651 }
652
653 template<typename T>
654 TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_end(void)
655 {
656 return ntree_prefix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
657 }
658
659 template<typename T>
660 TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_begin(void) const
661 {
662 return ntree_postfix_iterator<T,const T&,const T*>(root());
663 }
664
665 template<typename T>
666 TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_begin(void)
667 {
668 return ntree_postfix_iterator<T,T&,T*>(root());
669 }
670
671 template<typename T>
672 TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_end(void) const
673 {
674 return ntree_postfix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
675 }
676
677 template<typename T>
678 TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_end(void)
679 {
680 return ntree_postfix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
681 }
682
683 template<typename T>
684 TYPENAME ntree<T>::iterator ntree<T>::insert(const T& data)
685 {
686 // insert a new node as the root
687 return insert(ntree_iterator<T,T&,T*>(this), 0, data);
688 }
689
690 template<typename T>
691 TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)
692 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
693 {
694 // if i is the end iterator, this means insert a new root
695 if (i.end())
696 erase();
697 else
698 {
699 i.assert_valid(this);
700 if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
701 }
702 ntree_node<T>* new_node = new ntree_node<T>(this,data);
703 if (i.end())
704 {
705 m_root = new_node;
706 }
707 else
708 {
709 i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
710 new_node->m_parent = i.node();
711 }
712 return ntree_iterator<T,T&,T*>(new_node);
713 }
714
715 template<typename T>
716 TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const T& data)
717 throw(wrong_object,null_dereference,end_dereference)
718 {
719 return insert(i, i.node()->m_children.size(), data);
720 }
721
722 template<typename T>
723 TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)
724 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
725 {
726 // insert a whole tree as a child of i
727 i.assert_valid(this);
728 if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
729 ntree_node<T>* new_node = ntree_copy(this, tree.m_root);
730 i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
731 new_node->m_parent = i.node();
732 return ntree_iterator<T,T&,T*>(new_node);
733 }
734
735 template<typename T>
736 TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)
737 throw(wrong_object,null_dereference,end_dereference)
738 {
739 return insert(i, children(i), tree);
740 }
741
742 template<typename T>
743 TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)
744 throw(wrong_object,null_dereference,end_dereference)
745 {
746 // insert a new node to replace the existing node in the tree
747 // making the original node the child of the new node
748 // i.e. (node) becomes (new)->(node)
749 // afterwards, the iterator still points to the old node, now the child
750 // returns the iterator to the new node
751 node.assert_valid(this);
752 ntree_node<T>* new_node = new ntree_node<T>(this,data);
753 if (node.node() == m_root)
754 {
755 // pushing the root node
756 m_root = new_node;
757 new_node->m_parent = 0;
758 }
759 else
760 {
761 // pushing a sub-node
762 *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;
763 new_node->m_parent = node.node()->m_parent;
764 }
765 // link up the old node as the child of the new node
766 new_node->m_children.insert(new_node->m_children.begin(),node.node());
767 node.node()->m_parent = new_node;
768 return ntree_iterator<T,T&,T*>(new_node);
769 }
770
771 template<typename T>
772 void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)
773 throw(wrong_object,null_dereference,end_dereference)
774 {
775 // inverse of push
776 // removes the specified child of the parent node, adding its children to the parent node at the same offset
777 parent.assert_valid(this);
778 ntree_node<T>* node = parent.node();
779 if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");
780 // move the grandchildren first
781 ntree_node<T>* child = parent.node()->m_children[offset];
782 while (!child->m_children.empty())
783 {
784 // remove the last grandchild and insert into node just after the child to be removed
785 ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];
786 child->m_children.pop_back();
787 node->m_children.insert(node->m_children.begin()+offset+1, grandchild);
788 grandchild->m_parent = node;
789 }
790 // now remove the child
791 node->m_children.erase(node->m_children.begin()+offset);
792 delete child;
793 }
794
795 template<typename T>
796 void ntree<T>::erase(void)
797 {
798 // erase the whole tree
799 erase(root());
800 }
801
802 template<typename T>
803 void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)
804 throw(wrong_object,null_dereference,end_dereference)
805 {
806 if (!i.end())
807 {
808 // erase this node and its subtree
809 // do this by erasing this child of its parent
810 // handle the case of erasing the root
811 i.assert_valid(this);
812 ntree_node<T>* node = i.node();
813 if (node == m_root)
814 {
815 delete m_root;
816 m_root = 0;
817 }
818 else
819 {
820 ntree_node<T>* parent = node->m_parent;
821 // impossible for parent to be null - should assert this
822 TYPENAME std::vector<ntree_node<T>*>::iterator found =
823 std::find(parent->m_children.begin(), parent->m_children.end(), node);
824 // impossible for find to fail - should assert this
825 parent->m_children.erase(found);
826 delete node;
827 }
828 }
829 }
830
831 template<typename T>
832 void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)
833 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
834 {
835 erase(child(i, offset));
836 }
837
838 template<typename T>
839 ntree<T> ntree<T>::subtree(void)
840 {
841 return subtree(root());
842 }
843
844 template<typename T>
845 ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)
846 throw(wrong_object,null_dereference,end_dereference)
847 {
848 ntree<T> result;
849 if (!i.end())
850 {
851 i.assert_valid(this);
852 result.m_root = ntree_copy(&result, i.node());
853 }
854 return result;
855 }
856
857 template<typename T>
858 ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)
859 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
860 {
861 return subtree(child(i, offset));
862 }
863
864 template<typename T>
865 ntree<T> ntree<T>::cut(void)
866 {
867 return cut(root());
868 }
869
870 template<typename T>
871 ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)
872 throw(wrong_object,null_dereference,end_dereference)
873 {
874 ntree<T> result;
875 if (!i.end())
876 {
877 i.assert_valid(this);
878 ntree_node<T>* node = i.node();
879 if (node == m_root)
880 {
881 result.m_root = m_root;
882 m_root = 0;
883 }
884 else
885 {
886 ntree_node<T>* parent = node->m_parent;
887 // impossible for parent to be null - should assert this
888 TYPENAME std::vector<ntree_node<T>*>::iterator found =
889 std::find(parent->m_children.begin(), parent->m_children.end(), node);
890 // impossible for find to fail - should assert this
891 result.m_root = *found;
892 parent->m_children.erase(found);
893 }
894 if (result.m_root)
895 {
896 result.m_root->m_parent = 0;
897 result.m_root->set_new_owner(&result);
898 }
899 }
900 return result;
901 }
902
903 template<typename T>
904 ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)
905 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
906 {
907 return cut(child(i, offset));
908 }
909
910 ////////////////////////////////////////////////////////////////////////////////
911
912 } // end namespace stlplus
913
This page took 0.07381 seconds and 3 git commands to generate.