« back to all changes in this revision
Viewing changes to src/tree.hh
- browse files at revision 9
- compare with another revision
- download diff
- download tarball
- view history from revision 9
- Committer: Package Import Robot
- Author(s): D Haley
- Date: 2013-05-17 00:52:39 UTC
- mfrom: (3.1.4 experimental)
- Revision ID: package-import@ubuntu.com-20130517005239-7bl4mnhkvrhc2ba6
Tags: 0.0.13-1
Upload to unstable
- files added:
- .pc/.quilt_patches
- data
- data/textures
- data/textures/tex-source
- docs/developers
- docs/samples
- docs/samples/externalProg
- packaging/deps
- packaging/deps/sources
- packaging/mingw-debian-cross
- packaging/mingw-debian-cross/patches
- src/backend
- src/backend/APT
- src/backend/filters
- src/common
- src/gl
- src/gui
- src/gui/dialogs
- src/gui/dialogs/animateSubDialogs
- src/gui/glade-skeleton
- src/gui/glade-skeleton/animateSubDialogs
- files removed:
- .pc/3depict-docdir.patch
- .pc/3depict-docdir.patch/src
- .pc/font-path-changed.patch
- .pc/font-path-changed.patch/src
- deps
- src/filters
- src/glade-skeleton
- src/tex-source
- src/textures
- files modified:
- .pc/FTGL-lowercase.patch/configure
added
removed
src/tree.hh
1
2
// STL-like templated tree class.
3
//
4
// Copyright (C) 2001-2009 Kasper Peeters <kasper.peeters@aei.mpg.de>
5
// Distributed under the GNU General Public License version 3,
6
// (eventually to be changed to the Boost Software License).
7
8
/** The tree.hh library for C++ provides an STL-like container class
9
for n-ary trees, templated over the data stored at the
10
nodes. Various types of iterators are provided (post-order,
11
pre-order, and others). Where possible the access methods are
12
compatible with the STL or alternative algorithms are
13
available.
14
*/
15
16
17
#ifndef tree_hh_
18
#define tree_hh_
19
20
#include <cassert>
21
#include <cstddef>
22
#include <memory>
23
#include <stdexcept>
24
#include <iterator>
25
#include <set>
26
#include <queue>
27
#include <algorithm>
28
29
// HP-style construct/destroy have gone from the standard,
30
// so here is a copy.
31
32
namespace kp {
33
34
template <class T1, class T2>
35
void constructor(T1* p, T2& val)
36
{
37
new ((void *) p) T1(val);
38
}
39
40
template <class T1>
41
void constructor(T1* p)
42
{
43
new ((void *) p) T1;
44
}
45
46
template <class T1>
47
void destructor(T1* p)
48
{
49
p->~T1();
50
}
51
52
}
53
54
/// A node in the tree, combining links to other nodes as well as the actual data.
55
template<class T>
56
class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
57
public:
58
tree_node_<T> *parent;
59
tree_node_<T> *first_child, *last_child;
60
tree_node_<T> *prev_sibling, *next_sibling;
61
T data;
62
}; // __attribute__((packed));
63
64
template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
65
class tree {
66
protected:
67
typedef tree_node_<T> tree_node;
68
public:
69
/// Value of the data stored at a node.
70
typedef T value_type;
71
72
class iterator_base;
73
class pre_order_iterator;
74
class post_order_iterator;
75
class sibling_iterator;
76
class leaf_iterator;
77
78
tree();
79
tree(const T&);
80
tree(const iterator_base&);
81
tree(const tree<T, tree_node_allocator>&);
82
~tree();
83
void operator=(const tree<T, tree_node_allocator>&);
84
85
/// Base class for iterators, only pointers stored, no traversal logic.
86
#ifdef __SGI_STL_PORT
87
class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
88
#else
89
class iterator_base {
90
#endif
91
public:
92
typedef T value_type;
93
typedef T* pointer;
94
typedef T& reference;
95
typedef size_t size_type;
96
typedef ptrdiff_t difference_type;
97
typedef std::bidirectional_iterator_tag iterator_category;
98
99
iterator_base();
100
iterator_base(tree_node *);
101
102
T& operator*() const;
103
T* operator->() const;
104
105
/// When called, the next increment/decrement skips children of this node.
106
void skip_children();
107
void skip_children(bool skip);
108
/// Number of children of the node pointed to by the iterator.
109
unsigned int number_of_children() const;
110
111
sibling_iterator begin() const;
112
sibling_iterator end() const;
113
114
tree_node *node;
115
protected:
116
bool skip_current_children_;
117
};
118
119
/// Depth-first iterator, first accessing the node, then its children.
120
class pre_order_iterator : public iterator_base {
121
public:
122
pre_order_iterator();
123
pre_order_iterator(tree_node *);
124
pre_order_iterator(const iterator_base&);
125
pre_order_iterator(const sibling_iterator&);
126
127
bool operator==(const pre_order_iterator&) const;
128
bool operator!=(const pre_order_iterator&) const;
129
pre_order_iterator& operator++();
130
pre_order_iterator& operator--();
131
pre_order_iterator operator++(int);
132
pre_order_iterator operator--(int);
133
pre_order_iterator& operator+=(unsigned int);
134
pre_order_iterator& operator-=(unsigned int);
135
};
136
137
/// Depth-first iterator, first accessing the children, then the node itself.
138
class post_order_iterator : public iterator_base {
139
public:
140
post_order_iterator();
141
post_order_iterator(tree_node *);
142
post_order_iterator(const iterator_base&);
143
post_order_iterator(const sibling_iterator&);
144
145
bool operator==(const post_order_iterator&) const;
146
bool operator!=(const post_order_iterator&) const;
147
post_order_iterator& operator++();
148
post_order_iterator& operator--();
149
post_order_iterator operator++(int);
150
post_order_iterator operator--(int);
151
post_order_iterator& operator+=(unsigned int);
152
post_order_iterator& operator-=(unsigned int);
153
154
/// Set iterator to the first child as deep as possible down the tree.
155
void descend_all();
156
};
157
158
/// Breadth-first iterator, using a queue
159
class breadth_first_queued_iterator : public iterator_base {
160
public:
161
breadth_first_queued_iterator();
162
breadth_first_queued_iterator(tree_node *);
163
breadth_first_queued_iterator(const iterator_base&);
164
165
bool operator==(const breadth_first_queued_iterator&) const;
166
bool operator!=(const breadth_first_queued_iterator&) const;
167
breadth_first_queued_iterator& operator++();
168
breadth_first_queued_iterator operator++(int);
169
breadth_first_queued_iterator& operator+=(unsigned int);
170
171
private:
172
std::queue<tree_node *> traversal_queue;
173
};
174
175
/// The default iterator types throughout the tree class.
176
typedef pre_order_iterator iterator;
177
typedef breadth_first_queued_iterator breadth_first_iterator;
178
179
/// Iterator which traverses only the nodes at a given depth from the root.
180
class fixed_depth_iterator : public iterator_base {
181
public:
182
fixed_depth_iterator();
183
fixed_depth_iterator(tree_node *);
184
fixed_depth_iterator(const iterator_base&);
185
fixed_depth_iterator(const sibling_iterator&);
186
fixed_depth_iterator(const fixed_depth_iterator&);
187
188
bool operator==(const fixed_depth_iterator&) const;
189
bool operator!=(const fixed_depth_iterator&) const;
190
fixed_depth_iterator& operator++();
191
fixed_depth_iterator& operator--();
192
fixed_depth_iterator operator++(int);
193
fixed_depth_iterator operator--(int);
194
fixed_depth_iterator& operator+=(unsigned int);
195
fixed_depth_iterator& operator-=(unsigned int);
196
197
tree_node *top_node;
198
};
199
200
/// Iterator which traverses only the nodes which are siblings of each other.
201
class sibling_iterator : public iterator_base {
202
public:
203
sibling_iterator();
204
sibling_iterator(tree_node *);
205
sibling_iterator(const sibling_iterator&);
206
sibling_iterator(const iterator_base&);
207
208
bool operator==(const sibling_iterator&) const;
209
bool operator!=(const sibling_iterator&) const;
210
sibling_iterator& operator++();
211
sibling_iterator& operator--();
212
sibling_iterator operator++(int);
213
sibling_iterator operator--(int);
214
sibling_iterator& operator+=(unsigned int);
215
sibling_iterator& operator-=(unsigned int);
216
217
tree_node *range_first() const;
218
tree_node *range_last() const;
219
tree_node *parent_;
220
private:
221
void set_parent_();
222
};
223
224
/// Iterator which traverses only the leaves.
225
class leaf_iterator : public iterator_base {
226
public:
227
leaf_iterator();
228
leaf_iterator(tree_node *, tree_node *top=0);
229
leaf_iterator(const sibling_iterator&);
230
leaf_iterator(const iterator_base&);
231
232
bool operator==(const leaf_iterator&) const;
233
bool operator!=(const leaf_iterator&) const;
234
leaf_iterator& operator++();
235
leaf_iterator& operator--();
236
leaf_iterator operator++(int);
237
leaf_iterator operator--(int);
238
leaf_iterator& operator+=(unsigned int);
239
leaf_iterator& operator-=(unsigned int);
240
private:
241
tree_node *top_node;
242
};
243
244
/// Return iterator to the beginning of the tree.
245
inline pre_order_iterator begin() const;
246
/// Return iterator to the end of the tree.
247
inline pre_order_iterator end() const;
248
/// Return post-order iterator to the beginning of the tree.
249
post_order_iterator begin_post() const;
250
/// Return post-order end iterator of the tree.
251
post_order_iterator end_post() const;
252
/// Return fixed-depth iterator to the first node at a given depth from the given iterator.
253
fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
254
/// Return fixed-depth end iterator.
255
fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
256
/// Return breadth-first iterator to the first node at a given depth.
257
breadth_first_queued_iterator begin_breadth_first() const;
258
/// Return breadth-first end iterator.
259
breadth_first_queued_iterator end_breadth_first() const;
260
/// Return sibling iterator to the first child of given node.
261
sibling_iterator begin(const iterator_base&) const;
262
/// Return sibling end iterator for children of given node.
263
sibling_iterator end(const iterator_base&) const;
264
/// Return leaf iterator to the first leaf of the tree.
265
leaf_iterator begin_leaf() const;
266
/// Return leaf end iterator for entire tree.
267
leaf_iterator end_leaf() const;
268
/// Return leaf iterator to the first leaf of the subtree at the given node.
269
leaf_iterator begin_leaf(const iterator_base& top) const;
270
/// Return leaf end iterator for the subtree at the given node.
271
leaf_iterator end_leaf(const iterator_base& top) const;
272
273
/// Return iterator to the parent of a node.
274
template<typename iter> static iter parent(iter);
275
/// Return iterator to the previous sibling of a node.
276
template<typename iter> iter previous_sibling(iter) const;
277
/// Return iterator to the next sibling of a node.
278
template<typename iter> iter next_sibling(iter) const;
279
/// Return iterator to the next node at a given depth.
280
template<typename iter> iter next_at_same_depth(iter) const;
281
282
/// Erase all nodes of the tree.
283
void clear();
284
/// Erase element at position pointed to by iterator, return incremented iterator.
285
template<typename iter> iter erase(iter);
286
/// Erase all children of the node pointed to by iterator.
287
void erase_children(const iterator_base&);
288
289
/// Insert empty node as last/first child of node pointed to by position.
290
template<typename iter> iter append_child(iter position);
291
template<typename iter> iter prepend_child(iter position);
292
/// Insert node as last/first child of node pointed to by position.
293
template<typename iter> iter append_child(iter position, const T& x);
294
template<typename iter> iter prepend_child(iter position, const T& x);
295
/// Append the node (plus its children) at other_position as last/first child of position.
296
template<typename iter> iter append_child(iter position, iter other_position);
297
template<typename iter> iter prepend_child(iter position, iter other_position);
298
/// Append the nodes in the from-to range (plus their children) as last/first children of position.
299
template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
300
template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
301
302
/// Short-hand to insert topmost node in otherwise empty tree.
303
pre_order_iterator set_head(const T& x);
304
/// Insert node as previous sibling of node pointed to by position.
305
template<typename iter> iter insert(iter position, const T& x);
306
/// Specialisation of previous member.
307
sibling_iterator insert(sibling_iterator position, const T& x);
308
/// Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
309
template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
310
/// Insert node as next sibling of node pointed to by position.
311
template<typename iter> iter insert_after(iter position, const T& x);
312
/// Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
313
template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
314
315
/// Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
316
template<typename iter> iter replace(iter position, const T& x);
317
/// Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
318
template<typename iter> iter replace(iter position, const iterator_base& from);
319
/// Replace string of siblings (plus their children) with copy of a new string (with children); see above
320
sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
321
sibling_iterator new_begin, sibling_iterator new_end);
322
323
/// Move all children of node at 'position' to be siblings, returns position.
324
template<typename iter> iter flatten(iter position);
325
/// Move nodes in range to be children of 'position'.
326
template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
327
/// Move all child nodes of 'from' to be children of 'position'.
328
template<typename iter> iter reparent(iter position, iter from);
329
330
/// Replace node with a new node, making the old node a child of the new node.
331
template<typename iter> iter wrap(iter position, const T& x);
332
333
/// Move 'source' node (plus its children) to become the next sibling of 'target'.
334
template<typename iter> iter move_after(iter target, iter source);
335
/// Move 'source' node (plus its children) to become the previous sibling of 'target'.
336
template<typename iter> iter move_before(iter target, iter source);
337
sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
338
/// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
339
template<typename iter> iter move_ontop(iter target, iter source);
340
341
/// Merge with other tree, creating new branches and leaves only if they are not already present.
342
void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
343
bool duplicate_leaves=false);
344
/// Sort (std::sort only moves values of nodes, this one moves children as well).
345
void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
346
template<class StrictWeakOrdering>
347
void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
348
/// Compare two ranges of nodes (compares nodes as well as tree structure).
349
template<typename iter>
350
bool equal(const iter& one, const iter& two, const iter& three) const;
351
template<typename iter, class BinaryPredicate>
352
bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
353
template<typename iter>
354
bool equal_subtree(const iter& one, const iter& two) const;
355
template<typename iter, class BinaryPredicate>
356
bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
357
/// Extract a new tree formed by the range of siblings plus all their children.
358
tree subtree(sibling_iterator from, sibling_iterator to) const;
359
void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
360
/// Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
361
void swap(sibling_iterator it);
362
/// Exchange two nodes (plus subtrees)
363
void swap(iterator, iterator);
364
365
/// Count the total number of nodes.
366
size_t size() const;
367
/// Count the total number of nodes below the indicated node (plus one).
368
size_t size(const iterator_base&) const;
369
/// Check if tree is empty.
370
bool empty() const;
371
/// Compute the depth to the root or to a fixed other iterator.
372
static int depth(const iterator_base&);
373
static int depth(const iterator_base&, const iterator_base&);
374
/// Determine the maximal depth of the tree. An empty tree has max_depth=-1.
375
int max_depth() const;
376
/// Determine the maximal depth of the tree with top node at the given position.
377
int max_depth(const iterator_base&) const;
378
/// Count the number of children of node at position.
379
static unsigned int number_of_children(const iterator_base&);
380
/// Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.
381
unsigned int number_of_siblings(const iterator_base&) const;
382
/// Determine whether node at position is in the subtrees with root in the range.
383
bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
384
const iterator_base& end) const;
385
/// Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
386
bool is_valid(const iterator_base&) const;
387
388
/// Determine the index of a node in the range of siblings to which it belongs.
389
unsigned int index(sibling_iterator it) const;
390
/// Inverse of 'index': return the n-th child of the node at position.
391
static sibling_iterator child(const iterator_base& position, unsigned int);
392
/// Return iterator to the sibling indicated by index
393
sibling_iterator sibling(const iterator_base& position, unsigned int);
394
395
/// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
396
class iterator_base_less {
397
public:
398
bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
399
const typename tree<T, tree_node_allocator>::iterator_base& two) const
400
{
401
return one.node < two.node;
402
}
403
};
404
tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
405
private:
406
tree_node_allocator alloc_;
407
void head_initialise_();
408
void copy_(const tree<T, tree_node_allocator>& other);
409
410
/// Comparator class for two nodes of a tree (used for sorting and searching).
411
template<class StrictWeakOrdering>
412
class compare_nodes {
413
public:
414
compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
415
416
bool operator()(const tree_node *a, const tree_node *b)
417
{
418
return comp_(a->data, b->data);
419
}
420
private:
421
StrictWeakOrdering comp_;
422
};
423
};
424
425
//template <class T, class tree_node_allocator>
426
//class iterator_base_less {
427
// public:
428
// bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
429
// const typename tree<T, tree_node_allocator>::iterator_base& two) const
430
// {
431
// txtout << "operatorclass<" << one.node < two.node << std::endl;
432
// return one.node < two.node;
433
// }
434
//};
435
436
// template <class T, class tree_node_allocator>
437
// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
438
// const typename tree<T, tree_node_allocator>::iterator& two)
439
// {
440
// txtout << "operator< " << one.node < two.node << std::endl;
441
// if(one.node < two.node) return true;
442
// return false;
443
// }
444
//
445
// template <class T, class tree_node_allocator>
446
// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
447
// const typename tree<T, tree_node_allocator>::iterator& two)
448
// {
449
// txtout << "operator== " << one.node == two.node << std::endl;
450
// if(one.node == two.node) return true;
451
// return false;
452
// }
453
//
454
// template <class T, class tree_node_allocator>
455
// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
456
// const typename tree<T, tree_node_allocator>::iterator_base& two)
457
// {
458
// txtout << "operator> " << one.node < two.node << std::endl;
459
// if(one.node > two.node) return true;
460
// return false;
461
// }
462
463
464
465
// Tree
466
467
template <class T, class tree_node_allocator>
468
tree<T, tree_node_allocator>::tree()
469
{
470
head_initialise_();
471
}
472
473
template <class T, class tree_node_allocator>
474
tree<T, tree_node_allocator>::tree(const T& x)
475
{
476
head_initialise_();
477
set_head(x);
478
}
479
480
template <class T, class tree_node_allocator>
481
tree<T, tree_node_allocator>::tree(const iterator_base& other)
482
{
483
head_initialise_();
484
set_head((*other));
485
replace(begin(), other);
486
}
487
488
template <class T, class tree_node_allocator>
489
tree<T, tree_node_allocator>::~tree()
490
{
491
clear();
492
alloc_.deallocate(head,1);
493
alloc_.deallocate(feet,1);
494
}
495
496
template <class T, class tree_node_allocator>
497
void tree<T, tree_node_allocator>::head_initialise_()
498
{
499
head = alloc_.allocate(1,0); // MSVC does not have default second argument
500
feet = alloc_.allocate(1,0);
501
502
head->parent=0;
503
head->first_child=0;
504
head->last_child=0;
505
head->prev_sibling=0; //head;
506
head->next_sibling=feet; //head;
507
508
feet->parent=0;
509
feet->first_child=0;
510
feet->last_child=0;
511
feet->prev_sibling=head;
512
feet->next_sibling=0;
513
}
514
515
template <class T, class tree_node_allocator>
516
void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
517
{
518
copy_(other);
519
}
520
521
template <class T, class tree_node_allocator>
522
tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
523
{
524
head_initialise_();
525
copy_(other);
526
}
527
528
template <class T, class tree_node_allocator>
529
void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
530
{
531
clear();
532
pre_order_iterator it=other.begin(), to=begin();
533
while(it!=other.end()) {
534
to=insert(to, (*it));
535
it.skip_children();
536
++it;
537
}
538
to=begin();
539
it=other.begin();
540
while(it!=other.end()) {
541
to=replace(to, it);
542
to.skip_children();
543
it.skip_children();
544
++to;
545
++it;
546
}
547
}
548
549
template <class T, class tree_node_allocator>
550
void tree<T, tree_node_allocator>::clear()
551
{
552
if(head)
553
while(head->next_sibling!=feet)
554
erase(pre_order_iterator(head->next_sibling));
555
}
556
557
template<class T, class tree_node_allocator>
558
void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
559
{
560
// std::cout << "erase_children " << it.node << std::endl;
561
if(it.node==0) return;
562
563
tree_node *cur=it.node->first_child;
564
tree_node *prev=0;
565
566
while(cur!=0) {
567
prev=cur;
568
cur=cur->next_sibling;
569
erase_children(pre_order_iterator(prev));
570
kp::destructor(&prev->data);
571
alloc_.deallocate(prev,1);
572
}
573
it.node->first_child=0;
574
it.node->last_child=0;
575
// std::cout << "exit" << std::endl;
576
}
577
578
template<class T, class tree_node_allocator>
579
template<class iter>
580
iter tree<T, tree_node_allocator>::erase(iter it)
581
{
582
tree_node *cur=it.node;
583
assert(cur!=head);
584
iter ret=it;
585
ret.skip_children();
586
++ret;
587
erase_children(it);
588
if(cur->prev_sibling==0) {
589
cur->parent->first_child=cur->next_sibling;
590
}
591
else {
592
cur->prev_sibling->next_sibling=cur->next_sibling;
593
}
594
if(cur->next_sibling==0) {
595
cur->parent->last_child=cur->prev_sibling;
596
}
597
else {
598
cur->next_sibling->prev_sibling=cur->prev_sibling;
599
}
600
601
kp::destructor(&cur->data);
602
alloc_.deallocate(cur,1);
603
return ret;
604
}
605
606
template <class T, class tree_node_allocator>
607
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
608
{
609
return pre_order_iterator(head->next_sibling);
610
}
611
612
template <class T, class tree_node_allocator>
613
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
614
{
615
return pre_order_iterator(feet);
616
}
617
618
template <class T, class tree_node_allocator>
619
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
620
{
621
return breadth_first_queued_iterator(head->next_sibling);
622
}
623
624
template <class T, class tree_node_allocator>
625
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
626
{
627
return breadth_first_queued_iterator();
628
}
629
630
template <class T, class tree_node_allocator>
631
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
632
{
633
tree_node *tmp=head->next_sibling;
634
if(tmp!=feet) {
635
while(tmp->first_child)
636
tmp=tmp->first_child;
637
}
638
return post_order_iterator(tmp);
639
}
640
641
template <class T, class tree_node_allocator>
642
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
643
{
644
return post_order_iterator(feet);
645
}
646
647
template <class T, class tree_node_allocator>
648
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
649
{
650
typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;
651
ret.top_node=pos.node;
652
653
tree_node *tmp=pos.node;
654
unsigned int curdepth=0;
655
while(curdepth<dp) { // go down one level
656
while(tmp->first_child==0) {
657
if(tmp->next_sibling==0) {
658
// try to walk up and then right again
659
do {
660
if(tmp==ret.top_node)
661
throw std::range_error("tree: begin_fixed out of range");
662
tmp=tmp->parent;
663
if(tmp==0)
664
throw std::range_error("tree: begin_fixed out of range");
665
--curdepth;
666
} while(tmp->next_sibling==0);
667
}
668
tmp=tmp->next_sibling;
669
}
670
tmp=tmp->first_child;
671
++curdepth;
672
}
673
674
ret.node=tmp;
675
return ret;
676
}
677
678
template <class T, class tree_node_allocator>
679
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
680
{
681
assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround
682
tree_node *tmp=pos.node;
683
unsigned int curdepth=1;
684
while(curdepth<dp) { // go down one level
685
while(tmp->first_child==0) {
686
tmp=tmp->next_sibling;
687
if(tmp==0)
688
throw std::range_error("tree: end_fixed out of range");
689
}
690
tmp=tmp->first_child;
691
++curdepth;
692
}
693
return tmp;
694
}
695
696
template <class T, class tree_node_allocator>
697
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
698
{
699
assert(pos.node!=0);
700
if(pos.node->first_child==0) {
701
return end(pos);
702
}
703
return pos.node->first_child;
704
}
705
706
template <class T, class tree_node_allocator>
707
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
708
{
709
sibling_iterator ret(0);
710
ret.parent_=pos.node;
711
return ret;
712
}
713
714
template <class T, class tree_node_allocator>
715
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const
716
{
717
tree_node *tmp=head->next_sibling;
718
if(tmp!=feet) {
719
while(tmp->first_child)
720
tmp=tmp->first_child;
721
}
722
return leaf_iterator(tmp);
723
}
724
725
template <class T, class tree_node_allocator>
726
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const
727
{
728
return leaf_iterator(feet);
729
}
730
731
template <class T, class tree_node_allocator>
732
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf(const iterator_base& top) const
733
{
734
tree_node *tmp=top.node;
735
while(tmp->first_child)
736
tmp=tmp->first_child;
737
return leaf_iterator(tmp, top.node);
738
}
739
740
template <class T, class tree_node_allocator>
741
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf(const iterator_base& top) const
742
{
743
return leaf_iterator(top.node, top.node);
744
}
745
746
template <class T, class tree_node_allocator>
747
template <typename iter>
748
iter tree<T, tree_node_allocator>::parent(iter position)
749
{
750
assert(position.node!=0);
751
return iter(position.node->parent);
752
}
753
754
template <class T, class tree_node_allocator>
755
template <typename iter>
756
iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
757
{
758
assert(position.node!=0);
759
iter ret(position);
760
ret.node=position.node->prev_sibling;
761
return ret;
762
}
763
764
template <class T, class tree_node_allocator>
765
template <typename iter>
766
iter tree<T, tree_node_allocator>::next_sibling(iter position) const
767
{
768
assert(position.node!=0);
769
iter ret(position);
770
ret.node=position.node->next_sibling;
771
return ret;
772
}
773
774
template <class T, class tree_node_allocator>
775
template <typename iter>
776
iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
777
{
778
// We make use of a temporary fixed_depth iterator to implement this.
779
780
typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp(position.node);
781
782
++tmp;
783
return iter(tmp);
784
785
// assert(position.node!=0);
786
// iter ret(position);
787
//
788
// if(position.node->next_sibling) {
789
// ret.node=position.node->next_sibling;
790
// }
791
// else {
792
// int relative_depth=0;
793
// upper:
794
// do {
795
// ret.node=ret.node->parent;
796
// if(ret.node==0) return ret;
797
// --relative_depth;
798
// } while(ret.node->next_sibling==0);
799
// lower:
800
// ret.node=ret.node->next_sibling;
801
// while(ret.node->first_child==0) {
802
// if(ret.node->next_sibling==0)
803
// goto upper;
804
// ret.node=ret.node->next_sibling;
805
// if(ret.node==0) return ret;
806
// }
807
// while(relative_depth<0 && ret.node->first_child!=0) {
808
// ret.node=ret.node->first_child;
809
// ++relative_depth;
810
// }
811
// if(relative_depth<0) {
812
// if(ret.node->next_sibling==0) goto upper;
813
// else goto lower;
814
// }
815
// }
816
// return ret;
817
}
818
819
template <class T, class tree_node_allocator>
820
template <typename iter>
821
iter tree<T, tree_node_allocator>::append_child(iter position)
822
{
823
assert(position.node!=head);
824
assert(position.node);
825
826
tree_node *tmp=alloc_.allocate(1,0);
827
kp::constructor(&tmp->data);
828
tmp->first_child=0;
829
tmp->last_child=0;
830
831
tmp->parent=position.node;
832
if(position.node->last_child!=0) {
833
position.node->last_child->next_sibling=tmp;
834
}
835
else {
836
position.node->first_child=tmp;
837
}
838
tmp->prev_sibling=position.node->last_child;
839
position.node->last_child=tmp;
840
tmp->next_sibling=0;
841
return tmp;
842
}
843
844
template <class T, class tree_node_allocator>
845
template <typename iter>
846
iter tree<T, tree_node_allocator>::prepend_child(iter position)
847
{
848
assert(position.node!=head);
849
assert(position.node);
850
851
tree_node *tmp=alloc_.allocate(1,0);
852
kp::constructor(&tmp->data);
853
tmp->first_child=0;
854
tmp->last_child=0;
855
856
tmp->parent=position.node;
857
if(position.node->first_child!=0) {
858
position.node->first_child->prev_sibling=tmp;
859
}
860
else {
861
position.node->last_child=tmp;
862
}
863
tmp->next_sibling=position.node->first_child;
864
position.node->prev_child=tmp;
865
tmp->prev_sibling=0;
866
return tmp;
867
}
868
869
template <class T, class tree_node_allocator>
870
template <class iter>
871
iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
872
{
873
// If your program fails here you probably used 'append_child' to add the top
874
// node to an empty tree. From version 1.45 the top element should be added
875
// using 'insert'. See the documentation for further information, and sorry about
876
// the API change.
877
assert(position.node!=head);
878
assert(position.node);
879
880
tree_node* tmp = alloc_.allocate(1,0);
881
kp::constructor(&tmp->data, x);
882
tmp->first_child=0;
883
tmp->last_child=0;
884
885
tmp->parent=position.node;
886
if(position.node->last_child!=0) {
887
position.node->last_child->next_sibling=tmp;
888
}
889
else {
890
position.node->first_child=tmp;
891
}
892
tmp->prev_sibling=position.node->last_child;
893
position.node->last_child=tmp;
894
tmp->next_sibling=0;
895
return tmp;
896
}
897
898
template <class T, class tree_node_allocator>
899
template <class iter>
900
iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
901
{
902
assert(position.node!=head);
903
assert(position.node);
904
905
tree_node* tmp = alloc_.allocate(1,0);
906
kp::constructor(&tmp->data, x);
907
tmp->first_child=0;
908
tmp->last_child=0;
909
910
tmp->parent=position.node;
911
if(position.node->first_child!=0) {
912
position.node->first_child->prev_sibling=tmp;
913
}
914
else {
915
position.node->last_child=tmp;
916
}
917
tmp->next_sibling=position.node->first_child;
918
position.node->first_child=tmp;
919
tmp->prev_sibling=0;
920
return tmp;
921
}
922
923
template <class T, class tree_node_allocator>
924
template <class iter>
925
iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
926
{
927
assert(position.node!=head);
928
assert(position.node);
929
930
sibling_iterator aargh=append_child(position, value_type());
931
return replace(aargh, other);
932
}
933
934
template <class T, class tree_node_allocator>
935
template <class iter>
936
iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
937
{
938
assert(position.node!=head);
939
assert(position.node);
940
941
sibling_iterator aargh=prepend_child(position, value_type());
942
return replace(aargh, other);
943
}
944
945
template <class T, class tree_node_allocator>
946
template <class iter>
947
iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
948
{
949
assert(position.node!=head);
950
assert(position.node);
951
952
iter ret=from;
953
954
while(from!=to) {
955
insert_subtree(position.end(), from);
956
++from;
957
}
958
return ret;
959
}
960
961
template <class T, class tree_node_allocator>
962
template <class iter>
963
iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)
964
{
965
assert(position.node!=head);
966
assert(position.node);
967
968
iter ret=from;
969
970
while(from!=to) {
971
insert_subtree(position.begin(), from);
972
++from;
973
}
974
return ret;
975
}
976
977
template <class T, class tree_node_allocator>
978
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
979
{
980
assert(head->next_sibling==feet);
981
return insert(iterator(feet), x);
982
}
983
984
template <class T, class tree_node_allocator>
985
template <class iter>
986
iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
987
{
988
if(position.node==0) {
989
position.node=feet; // Backward compatibility: when calling insert on a null node,
990
// insert before the feet.
991
}
992
tree_node* tmp = alloc_.allocate(1,0);
993
kp::constructor(&tmp->data, x);
994
tmp->first_child=0;
995
tmp->last_child=0;
996
997
tmp->parent=position.node->parent;
998
tmp->next_sibling=position.node;
999
tmp->prev_sibling=position.node->prev_sibling;
1000
position.node->prev_sibling=tmp;
1001
1002
if(tmp->prev_sibling==0) {
1003
if(tmp->parent) // when inserting nodes at the head, there is no parent
1004
tmp->parent->first_child=tmp;
1005
}
1006
else
1007
tmp->prev_sibling->next_sibling=tmp;
1008
return tmp;
1009
}
1010
1011
template <class T, class tree_node_allocator>
1012
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
1013
{
1014
tree_node* tmp = alloc_.allocate(1,0);
1015
kp::constructor(&tmp->data, x);
1016
tmp->first_child=0;
1017
tmp->last_child=0;
1018
1019
tmp->next_sibling=position.node;
1020
if(position.node==0) { // iterator points to end of a subtree
1021
tmp->parent=position.parent_;
1022
tmp->prev_sibling=position.range_last();
1023
tmp->parent->last_child=tmp;
1024
}
1025
else {
1026
tmp->parent=position.node->parent;
1027
tmp->prev_sibling=position.node->prev_sibling;
1028
position.node->prev_sibling=tmp;
1029
}
1030
1031
if(tmp->prev_sibling==0) {
1032
if(tmp->parent) // when inserting nodes at the head, there is no parent
1033
tmp->parent->first_child=tmp;
1034
}
1035
else
1036
tmp->prev_sibling->next_sibling=tmp;
1037
return tmp;
1038
}
1039
1040
template <class T, class tree_node_allocator>
1041
template <class iter>
1042
iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
1043
{
1044
tree_node* tmp = alloc_.allocate(1,0);
1045
kp::constructor(&tmp->data, x);
1046
tmp->first_child=0;
1047
tmp->last_child=0;
1048
1049
tmp->parent=position.node->parent;
1050
tmp->prev_sibling=position.node;
1051
tmp->next_sibling=position.node->next_sibling;
1052
position.node->next_sibling=tmp;
1053
1054
if(tmp->next_sibling==0) {
1055
if(tmp->parent) // when inserting nodes at the head, there is no parent
1056
tmp->parent->last_child=tmp;
1057
}
1058
else {
1059
tmp->next_sibling->prev_sibling=tmp;
1060
}
1061
return tmp;
1062
}
1063
1064
template <class T, class tree_node_allocator>
1065
template <class iter>
1066
iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
1067
{
1068
// insert dummy
1069
iter it=insert(position, value_type());
1070
// replace dummy with subtree
1071
return replace(it, subtree);
1072
}
1073
1074
template <class T, class tree_node_allocator>
1075
template <class iter>
1076
iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)
1077
{
1078
// insert dummy
1079
iter it=insert_after(position, value_type());
1080
// replace dummy with subtree
1081
return replace(it, subtree);
1082
}
1083
1084
// template <class T, class tree_node_allocator>
1085
// template <class iter>
1086
// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
1087
// {
1088
// // insert dummy
1089
// iter it(insert(position, value_type()));
1090
// // replace dummy with subtree
1091
// return replace(it, subtree);
1092
// }
1093
1094
template <class T, class tree_node_allocator>
1095
template <class iter>
1096
iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
1097
{
1098
kp::destructor(&position.node->data);
1099
kp::constructor(&position.node->data, x);
1100
return position;
1101
}
1102
1103
template <class T, class tree_node_allocator>
1104
template <class iter>
1105
iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
1106
{
1107
assert(position.node!=head);
1108
tree_node *current_from=from.node;
1109
tree_node *start_from=from.node;
1110
tree_node *current_to =position.node;
1111
1112
// replace the node at position with head of the replacement tree at from
1113
// std::cout << "warning!" << position.node << std::endl;
1114
erase_children(position);
1115
// std::cout << "no warning!" << std::endl;
1116
tree_node* tmp = alloc_.allocate(1,0);
1117
kp::constructor(&tmp->data, (*from));
1118
tmp->first_child=0;
1119
tmp->last_child=0;
1120
if(current_to->prev_sibling==0) {
1121
if(current_to->parent!=0)
1122
current_to->parent->first_child=tmp;
1123
}
1124
else {
1125
current_to->prev_sibling->next_sibling=tmp;
1126
}
1127
tmp->prev_sibling=current_to->prev_sibling;
1128
if(current_to->next_sibling==0) {
1129
if(current_to->parent!=0)
1130
current_to->parent->last_child=tmp;
1131
}
1132
else {
1133
current_to->next_sibling->prev_sibling=tmp;
1134
}
1135
tmp->next_sibling=current_to->next_sibling;
1136
tmp->parent=current_to->parent;
1137
kp::destructor(¤t_to->data);
1138
alloc_.deallocate(current_to,1);
1139
current_to=tmp;
1140
1141
// only at this stage can we fix 'last'
1142
tree_node *last=from.node->next_sibling;
1143
1144
pre_order_iterator toit=tmp;
1145
// copy all children
1146
do {
1147
assert(current_from!=0);
1148
if(current_from->first_child != 0) {
1149
current_from=current_from->first_child;
1150
toit=append_child(toit, current_from->data);
1151
}
1152
else {
1153
while(current_from->next_sibling==0 && current_from!=start_from) {
1154
current_from=current_from->parent;
1155
toit=parent(toit);
1156
assert(current_from!=0);
1157
}
1158
current_from=current_from->next_sibling;
1159
if(current_from!=last) {
1160
toit=append_child(parent(toit), current_from->data);
1161
}
1162
}
1163
} while(current_from!=last);
1164
1165
return current_to;
1166
}
1167
1168
template <class T, class tree_node_allocator>
1169
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
1170
sibling_iterator orig_begin,
1171
sibling_iterator orig_end,
1172
sibling_iterator new_begin,
1173
sibling_iterator new_end)
1174
{
1175
tree_node *orig_first=orig_begin.node;
1176
tree_node *new_first=new_begin.node;
1177
tree_node *orig_last=orig_first;
1178
while((++orig_begin)!=orig_end)
1179
orig_last=orig_last->next_sibling;
1180
tree_node *new_last=new_first;
1181
while((++new_begin)!=new_end)
1182
new_last=new_last->next_sibling;
1183
1184
// insert all siblings in new_first..new_last before orig_first
1185
bool first=true;
1186
pre_order_iterator ret;
1187
while(1==1) {
1188
pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1189
if(first) {
1190
ret=tt;
1191
first=false;
1192
}
1193
if(new_first==new_last)
1194
break;
1195
new_first=new_first->next_sibling;
1196
}
1197
1198
// erase old range of siblings
1199
bool last=false;
1200
tree_node *next=orig_first;
1201
while(1==1) {
1202
if(next==orig_last)
1203
last=true;
1204
next=next->next_sibling;
1205
erase((pre_order_iterator)orig_first);
1206
if(last)
1207
break;
1208
orig_first=next;
1209
}
1210
return ret;
1211
}
1212
1213
template <class T, class tree_node_allocator>
1214
template <typename iter>
1215
iter tree<T, tree_node_allocator>::flatten(iter position)
1216
{
1217
if(position.node->first_child==0)
1218
return position;
1219
1220
tree_node *tmp=position.node->first_child;
1221
while(tmp) {
1222
tmp->parent=position.node->parent;
1223
tmp=tmp->next_sibling;
1224
}
1225
if(position.node->next_sibling) {
1226
position.node->last_child->next_sibling=position.node->next_sibling;
1227
position.node->next_sibling->prev_sibling=position.node->last_child;
1228
}
1229
else {
1230
position.node->parent->last_child=position.node->last_child;
1231
}
1232
position.node->next_sibling=position.node->first_child;
1233
position.node->next_sibling->prev_sibling=position.node;
1234
position.node->first_child=0;
1235
position.node->last_child=0;
1236
1237
return position;
1238
}
1239
1240
1241
template <class T, class tree_node_allocator>
1242
template <typename iter>
1243
iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
1244
{
1245
tree_node *first=begin.node;
1246
tree_node *last=first;
1247
1248
assert(first!=position.node);
1249
1250
if(begin==end) return begin;
1251
// determine last node
1252
while((++begin)!=end) {
1253
last=last->next_sibling;
1254
}
1255
// move subtree
1256
if(first->prev_sibling==0) {
1257
first->parent->first_child=last->next_sibling;
1258
}
1259
else {
1260
first->prev_sibling->next_sibling=last->next_sibling;
1261
}
1262
if(last->next_sibling==0) {
1263
last->parent->last_child=first->prev_sibling;
1264
}
1265
else {
1266
last->next_sibling->prev_sibling=first->prev_sibling;
1267
}
1268
if(position.node->first_child==0) {
1269
position.node->first_child=first;
1270
position.node->last_child=last;
1271
first->prev_sibling=0;
1272
}
1273
else {
1274
position.node->last_child->next_sibling=first;
1275
first->prev_sibling=position.node->last_child;
1276
position.node->last_child=last;
1277
}
1278
last->next_sibling=0;
1279
1280
tree_node *pos=first;
1281
for(;;) {
1282
pos->parent=position.node;
1283
if(pos==last) break;
1284
pos=pos->next_sibling;
1285
}
1286
1287
return first;
1288
}
1289
1290
template <class T, class tree_node_allocator>
1291
template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1292
{
1293
if(from.node->first_child==0) return position;
1294
return reparent(position, from.node->first_child, end(from));
1295
}
1296
1297
template <class T, class tree_node_allocator>
1298
template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
1299
{
1300
assert(position.node!=0);
1301
sibling_iterator fr=position, to=position;
1302
++to;
1303
iter ret = insert(position, x);
1304
reparent(ret, fr, to);
1305
return ret;
1306
}
1307
1308
template <class T, class tree_node_allocator>
1309
template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
1310
{
1311
tree_node *dst=target.node;
1312
tree_node *src=source.node;
1313
assert(dst);
1314
assert(src);
1315
1316
if(dst==src) return source;
1317
if(dst->next_sibling)
1318
if(dst->next_sibling==src) // already in the right spot
1319
return source;
1320
1321
// take src out of the tree
1322
if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1323
else src->parent->first_child=src->next_sibling;
1324
if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1325
else src->parent->last_child=src->prev_sibling;
1326
1327
// connect it to the new point
1328
if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1329
else dst->parent->last_child=src;
1330
src->next_sibling=dst->next_sibling;
1331
dst->next_sibling=src;
1332
src->prev_sibling=dst;
1333
src->parent=dst->parent;
1334
return src;
1335
}
1336
1337
template <class T, class tree_node_allocator>
1338
template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1339
{
1340
tree_node *dst=target.node;
1341
tree_node *src=source.node;
1342
assert(dst);
1343
assert(src);
1344
1345
if(dst==src) return source;
1346
if(dst->prev_sibling)
1347
if(dst->prev_sibling==src) // already in the right spot
1348
return source;
1349
1350
// take src out of the tree
1351
if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1352
else src->parent->first_child=src->next_sibling;
1353
if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1354
else src->parent->last_child=src->prev_sibling;
1355
1356
// connect it to the new point
1357
if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1358
else dst->parent->first_child=src;
1359
src->prev_sibling=dst->prev_sibling;
1360
dst->prev_sibling=src;
1361
src->next_sibling=dst;
1362
src->parent=dst->parent;
1363
return src;
1364
}
1365
1366
// specialisation for sibling_iterators
1367
template <class T, class tree_node_allocator>
1368
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target,
1369
sibling_iterator source)
1370
{
1371
tree_node *dst=target.node;
1372
tree_node *src=source.node;
1373
tree_node *dst_prev_sibling;
1374
if(dst==0) { // must then be an end iterator
1375
dst_prev_sibling=target.parent_->last_child;
1376
assert(dst_prev_sibling);
1377
}
1378
else dst_prev_sibling=dst->prev_sibling;
1379
assert(src);
1380
1381
if(dst==src) return source;
1382
if(dst_prev_sibling)
1383
if(dst_prev_sibling==src) // already in the right spot
1384
return source;
1385
1386
// take src out of the tree
1387
if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1388
else src->parent->first_child=src->next_sibling;
1389
if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1390
else src->parent->last_child=src->prev_sibling;
1391
1392
// connect it to the new point
1393
if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1394
else target.parent_->first_child=src;
1395
src->prev_sibling=dst_prev_sibling;
1396
if(dst) {
1397
dst->prev_sibling=src;
1398
src->parent=dst->parent;
1399
}
1400
src->next_sibling=dst;
1401
return src;
1402
}
1403
1404
template <class T, class tree_node_allocator>
1405
template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
1406
{
1407
tree_node *dst=target.node;
1408
tree_node *src=source.node;
1409
assert(dst);
1410
assert(src);
1411
1412
if(dst==src) return source;
1413
1414
// remember connection points
1415
tree_node *b_prev_sibling=dst->prev_sibling;
1416
tree_node *b_next_sibling=dst->next_sibling;
1417
tree_node *b_parent=dst->parent;
1418
1419
// remove target
1420
erase(target);
1421
1422
// take src out of the tree
1423
if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1424
else src->parent->first_child=src->next_sibling;
1425
if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1426
else src->parent->last_child=src->prev_sibling;
1427
1428
// connect it to the new point
1429
if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1430
else b_parent->first_child=src;
1431
if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1432
else b_parent->last_child=src;
1433
src->prev_sibling=b_prev_sibling;
1434
src->next_sibling=b_next_sibling;
1435
src->parent=b_parent;
1436
return src;
1437
}
1438
1439
template <class T, class tree_node_allocator>
1440
void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
1441
sibling_iterator from1, sibling_iterator from2,
1442
bool duplicate_leaves)
1443
{
1444
sibling_iterator fnd;
1445
while(from1!=from2) {
1446
if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1447
if(from1.begin()==from1.end()) { // full depth reached
1448
if(duplicate_leaves)
1449
append_child(parent(to1), (*from1));
1450
}
1451
else { // descend further
1452
merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1453
}
1454
}
1455
else { // element missing
1456
insert_subtree(to2, from1);
1457
}
1458
++from1;
1459
}
1460
}
1461
1462
1463
template <class T, class tree_node_allocator>
1464
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
1465
{
1466
std::less<T> comp;
1467
sort(from, to, comp, deep);
1468
}
1469
1470
template <class T, class tree_node_allocator>
1471
template <class StrictWeakOrdering>
1472
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
1473
StrictWeakOrdering comp, bool deep)
1474
{
1475
if(from==to) return;
1476
// make list of sorted nodes
1477
// CHECK: if multiset stores equivalent nodes in the order in which they
1478
// are inserted, then this routine should be called 'stable_sort'.
1479
std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1480
sibling_iterator it=from, it2=to;
1481
while(it != to) {
1482
nodes.insert(it.node);
1483
++it;
1484
}
1485
// reassemble
1486
--it2;
1487
1488
// prev and next are the nodes before and after the sorted range
1489
tree_node *prev=from.node->prev_sibling;
1490
tree_node *next=it2.node->next_sibling;
1491
typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
1492
if(prev==0) {
1493
if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1494
(*nit)->parent->first_child=(*nit);
1495
}
1496
else prev->next_sibling=(*nit);
1497
1498
--eit;
1499
while(nit!=eit) {
1500
(*nit)->prev_sibling=prev;
1501
if(prev)
1502
prev->next_sibling=(*nit);
1503
prev=(*nit);
1504
++nit;
1505
}
1506
// prev now points to the last-but-one node in the sorted range
1507
if(prev)
1508
prev->next_sibling=(*eit);
1509
1510
// eit points to the last node in the sorted range.
1511
(*eit)->next_sibling=next;
1512
(*eit)->prev_sibling=prev; // missed in the loop above
1513
if(next==0) {
1514
if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1515
(*eit)->parent->last_child=(*eit);
1516
}
1517
else next->prev_sibling=(*eit);
1518
1519
if(deep) { // sort the children of each node too
1520
sibling_iterator bcs(*nodes.begin());
1521
sibling_iterator ecs(*eit);
1522
++ecs;
1523
while(bcs!=ecs) {
1524
sort(begin(bcs), end(bcs), comp, deep);
1525
++bcs;
1526
}
1527
}
1528
}
1529
1530
template <class T, class tree_node_allocator>
1531
template <typename iter>
1532
bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1533
{
1534
std::equal_to<T> comp;
1535
return equal(one_, two, three_, comp);
1536
}
1537
1538
template <class T, class tree_node_allocator>
1539
template <typename iter>
1540
bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1541
{
1542
std::equal_to<T> comp;
1543
return equal_subtree(one_, two_, comp);
1544
}
1545
1546
template <class T, class tree_node_allocator>
1547
template <typename iter, class BinaryPredicate>
1548
bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1549
{
1550
pre_order_iterator one(one_), three(three_);
1551
1552
// if(one==two && is_valid(three) && three.number_of_children()!=0)
1553
// return false;
1554
while(one!=two && is_valid(three)) {
1555
if(!fun(*one,*three))
1556
return false;
1557
if(one.number_of_children()!=three.number_of_children())
1558
return false;
1559
++one;
1560
++three;
1561
}
1562
return true;
1563
}
1564
1565
template <class T, class tree_node_allocator>
1566
template <typename iter, class BinaryPredicate>
1567
bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1568
{
1569
pre_order_iterator one(one_), two(two_);
1570
1571
if(!fun(*one,*two)) return false;
1572
if(number_of_children(one)!=number_of_children(two)) return false;
1573
return equal(begin(one),end(one),begin(two),fun);
1574
}
1575
1576
template <class T, class tree_node_allocator>
1577
tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
1578
{
1579
tree tmp;
1580
tmp.set_head(value_type());
1581
tmp.replace(tmp.begin(), tmp.end(), from, to);
1582
return tmp;
1583
}
1584
1585
template <class T, class tree_node_allocator>
1586
void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
1587
{
1588
tmp.set_head(value_type());
1589
tmp.replace(tmp.begin(), tmp.end(), from, to);
1590
}
1591
1592
template <class T, class tree_node_allocator>
1593
size_t tree<T, tree_node_allocator>::size() const
1594
{
1595
size_t i=0;
1596
pre_order_iterator it=begin(), eit=end();
1597
while(it!=eit) {
1598
++i;
1599
++it;
1600
}
1601
return i;
1602
}
1603
1604
template <class T, class tree_node_allocator>
1605
size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const
1606
{
1607
size_t i=0;
1608
pre_order_iterator it=top, eit=top;
1609
eit.skip_children();
1610
++eit;
1611
while(it!=eit) {
1612
++i;
1613
++it;
1614
}
1615
return i;
1616
}
1617
1618
template <class T, class tree_node_allocator>
1619
bool tree<T, tree_node_allocator>::empty() const
1620
{
1621
pre_order_iterator it=begin(), eit=end();
1622
return (it==eit);
1623
}
1624
1625
template <class T, class tree_node_allocator>
1626
int tree<T, tree_node_allocator>::depth(const iterator_base& it)
1627
{
1628
tree_node* pos=it.node;
1629
assert(pos!=0);
1630
int ret=0;
1631
while(pos->parent!=0) {
1632
pos=pos->parent;
1633
++ret;
1634
}
1635
return ret;
1636
}
1637
1638
template <class T, class tree_node_allocator>
1639
int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root)
1640
{
1641
tree_node* pos=it.node;
1642
assert(pos!=0);
1643
int ret=0;
1644
while(pos->parent!=0 && pos!=root.node) {
1645
pos=pos->parent;
1646
++ret;
1647
}
1648
return ret;
1649
}
1650
1651
template <class T, class tree_node_allocator>
1652
int tree<T, tree_node_allocator>::max_depth() const
1653
{
1654
int maxd=-1;
1655
for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
1656
maxd=std::max(maxd, max_depth(it));
1657
1658
return maxd;
1659
}
1660
1661
1662
template <class T, class tree_node_allocator>
1663
int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
1664
{
1665
tree_node *tmp=pos.node;
1666
1667
if(tmp==0 || tmp==head || tmp==feet) return -1;
1668
1669
int curdepth=0, maxdepth=0;
1670
while(true) { // try to walk the bottom of the tree
1671
while(tmp->first_child==0) {
1672
if(tmp==pos.node) return maxdepth;
1673
if(tmp->next_sibling==0) {
1674
// try to walk up and then right again
1675
do {
1676
tmp=tmp->parent;
1677
if(tmp==0) return maxdepth;
1678
--curdepth;
1679
} while(tmp->next_sibling==0);
1680
}
1681
if(tmp==pos.node) return maxdepth;
1682
tmp=tmp->next_sibling;
1683
}
1684
tmp=tmp->first_child;
1685
++curdepth;
1686
maxdepth=std::max(curdepth, maxdepth);
1687
}
1688
}
1689
1690
template <class T, class tree_node_allocator>
1691
unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)
1692
{
1693
tree_node *pos=it.node->first_child;
1694
if(pos==0) return 0;
1695
1696
unsigned int ret=1;
1697
// while(pos!=it.node->last_child) {
1698
// ++ret;
1699
// pos=pos->next_sibling;
1700
// }
1701
while((pos=pos->next_sibling))
1702
++ret;
1703
return ret;
1704
}
1705
1706
template <class T, class tree_node_allocator>
1707
unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
1708
{
1709
tree_node *pos=it.node;
1710
unsigned int ret=0;
1711
// count forward
1712
while(pos->next_sibling &&
1713
pos->next_sibling!=head &&
1714
pos->next_sibling!=feet) {
1715
++ret;
1716
pos=pos->next_sibling;
1717
}
1718
// count backward
1719
pos=it.node;
1720
while(pos->prev_sibling &&
1721
pos->prev_sibling!=head &&
1722
pos->prev_sibling!=feet) {
1723
++ret;
1724
pos=pos->prev_sibling;
1725
}
1726
1727
return ret;
1728
}
1729
1730
template <class T, class tree_node_allocator>
1731
void tree<T, tree_node_allocator>::swap(sibling_iterator it)
1732
{
1733
tree_node *nxt=it.node->next_sibling;
1734
if(nxt) {
1735
if(it.node->prev_sibling)
1736
it.node->prev_sibling->next_sibling=nxt;
1737
else
1738
it.node->parent->first_child=nxt;
1739
nxt->prev_sibling=it.node->prev_sibling;
1740
tree_node *nxtnxt=nxt->next_sibling;
1741
if(nxtnxt)
1742
nxtnxt->prev_sibling=it.node;
1743
else
1744
it.node->parent->last_child=it.node;
1745
nxt->next_sibling=it.node;
1746
it.node->prev_sibling=nxt;
1747
it.node->next_sibling=nxtnxt;
1748
}
1749
}
1750
1751
template <class T, class tree_node_allocator>
1752
void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
1753
{
1754
// if one and two are adjacent siblings, use the sibling swap
1755
if(one.node->next_sibling==two.node) swap(one);
1756
else if(two.node->next_sibling==one.node) swap(two);
1757
else {
1758
tree_node *nxt1=one.node->next_sibling;
1759
tree_node *nxt2=two.node->next_sibling;
1760
tree_node *pre1=one.node->prev_sibling;
1761
tree_node *pre2=two.node->prev_sibling;
1762
tree_node *par1=one.node->parent;
1763
tree_node *par2=two.node->parent;
1764
1765
// reconnect
1766
one.node->parent=par2;
1767
one.node->next_sibling=nxt2;
1768
if(nxt2) nxt2->prev_sibling=one.node;
1769
else par2->last_child=one.node;
1770
one.node->prev_sibling=pre2;
1771
if(pre2) pre2->next_sibling=one.node;
1772
else par2->first_child=one.node;
1773
1774
two.node->parent=par1;
1775
two.node->next_sibling=nxt1;
1776
if(nxt1) nxt1->prev_sibling=two.node;
1777
else par1->last_child=two.node;
1778
two.node->prev_sibling=pre1;
1779
if(pre1) pre1->next_sibling=two.node;
1780
else par1->first_child=two.node;
1781
}
1782
}
1783
1784
// template <class BinaryPredicate>
1785
// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1786
// sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1787
// BinaryPredicate fun) const
1788
// {
1789
// assert(1==0); // this routine is not finished yet.
1790
// while(from!=to) {
1791
// if(fun(*subfrom, *from)) {
1792
//
1793
// }
1794
// }
1795
// return to;
1796
// }
1797
1798
template <class T, class tree_node_allocator>
1799
bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
1800
const iterator_base& end) const
1801
{
1802
// FIXME: this should be optimised.
1803
pre_order_iterator tmp=begin;
1804
while(tmp!=end) {
1805
if(tmp==it) return true;
1806
++tmp;
1807
}
1808
return false;
1809
}
1810
1811
template <class T, class tree_node_allocator>
1812
bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
1813
{
1814
if(it.node==0 || it.node==feet || it.node==head) return false;
1815
else return true;
1816
}
1817
1818
template <class T, class tree_node_allocator>
1819
unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
1820
{
1821
unsigned int ind=0;
1822
if(it.node->parent==0) {
1823
while(it.node->prev_sibling!=head) {
1824
it.node=it.node->prev_sibling;
1825
++ind;
1826
}
1827
}
1828
else {
1829
while(it.node->prev_sibling!=0) {
1830
it.node=it.node->prev_sibling;
1831
++ind;
1832
}
1833
}
1834
return ind;
1835
}
1836
1837
template <class T, class tree_node_allocator>
1838
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling(const iterator_base& it, unsigned int num)
1839
{
1840
tree_node *tmp;
1841
if(it.node->parent==0) {
1842
tmp=head->next_sibling;
1843
while(num) {
1844
tmp = tmp->next_sibling;
1845
--num;
1846
}
1847
}
1848
else {
1849
tmp=it.node->parent->first_child;
1850
while(num) {
1851
assert(tmp!=0);
1852
tmp = tmp->next_sibling;
1853
--num;
1854
}
1855
}
1856
return tmp;
1857
}
1858
1859
1860
template <class T, class tree_node_allocator>
1861
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num)
1862
{
1863
tree_node *tmp=it.node->first_child;
1864
while(num--) {
1865
assert(tmp!=0);
1866
tmp=tmp->next_sibling;
1867
}
1868
return tmp;
1869
}
1870
1871
1872
1873
1874
// Iterator base
1875
1876
template <class T, class tree_node_allocator>
1877
tree<T, tree_node_allocator>::iterator_base::iterator_base()
1878
: node(0), skip_current_children_(false)
1879
{
1880
}
1881
1882
template <class T, class tree_node_allocator>
1883
tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
1884
: node(tn), skip_current_children_(false)
1885
{
1886
}
1887
1888
template <class T, class tree_node_allocator>
1889
T& tree<T, tree_node_allocator>::iterator_base::operator*() const
1890
{
1891
return node->data;
1892
}
1893
1894
template <class T, class tree_node_allocator>
1895
T* tree<T, tree_node_allocator>::iterator_base::operator->() const
1896
{
1897
return &(node->data);
1898
}
1899
1900
template <class T, class tree_node_allocator>
1901
bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
1902
{
1903
if(other.node!=this->node) return true;
1904
else return false;
1905
}
1906
1907
template <class T, class tree_node_allocator>
1908
bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
1909
{
1910
if(other.node==this->node) return true;
1911
else return false;
1912
}
1913
1914
template <class T, class tree_node_allocator>
1915
bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
1916
{
1917
if(other.node!=this->node) return true;
1918
else return false;
1919
}
1920
1921
template <class T, class tree_node_allocator>
1922
bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
1923
{
1924
if(other.node==this->node) return true;
1925
else return false;
1926
}
1927
1928
template <class T, class tree_node_allocator>
1929
bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
1930
{
1931
if(other.node!=this->node) return true;
1932
else return false;
1933
}
1934
1935
template <class T, class tree_node_allocator>
1936
bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
1937
{
1938
if(other.node==this->node) return true;
1939
else return false;
1940
}
1941
1942
template <class T, class tree_node_allocator>
1943
bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
1944
{
1945
if(other.node!=this->node) return true;
1946
else return false;
1947
}
1948
1949
template <class T, class tree_node_allocator>
1950
bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
1951
{
1952
if(other.node==this->node && other.top_node==this->top_node) return true;
1953
else return false;
1954
}
1955
1956
template <class T, class tree_node_allocator>
1957
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
1958
{
1959
if(node->first_child==0)
1960
return end();
1961
1962
sibling_iterator ret(node->first_child);
1963
ret.parent_=this->node;
1964
return ret;
1965
}
1966
1967
template <class T, class tree_node_allocator>
1968
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
1969
{
1970
sibling_iterator ret(0);
1971
ret.parent_=node;
1972
return ret;
1973
}
1974
1975
template <class T, class tree_node_allocator>
1976
void tree<T, tree_node_allocator>::iterator_base::skip_children()
1977
{
1978
skip_current_children_=true;
1979
}
1980
1981
template <class T, class tree_node_allocator>
1982
void tree<T, tree_node_allocator>::iterator_base::skip_children(bool skip)
1983
{
1984
skip_current_children_=skip;
1985
}
1986
1987
template <class T, class tree_node_allocator>
1988
unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
1989
{
1990
tree_node *pos=node->first_child;
1991
if(pos==0) return 0;
1992
1993
unsigned int ret=1;
1994
while(pos!=node->last_child) {
1995
++ret;
1996
pos=pos->next_sibling;
1997
}
1998
return ret;
1999
}
2000
2001
2002
2003
// Pre-order iterator
2004
2005
template <class T, class tree_node_allocator>
2006
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
2007
: iterator_base(0)
2008
{
2009
}
2010
2011
template <class T, class tree_node_allocator>
2012
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
2013
: iterator_base(tn)
2014
{
2015
}
2016
2017
template <class T, class tree_node_allocator>
2018
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
2019
: iterator_base(other.node)
2020
{
2021
}
2022
2023
template <class T, class tree_node_allocator>
2024
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
2025
: iterator_base(other.node)
2026
{
2027
if(this->node==0) {
2028
if(other.range_last()!=0)
2029
this->node=other.range_last();
2030
else
2031
this->node=other.parent_;
2032
this->skip_children();
2033
++(*this);
2034
}
2035
}
2036
2037
template <class T, class tree_node_allocator>
2038
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
2039
{
2040
assert(this->node!=0);
2041
if(!this->skip_current_children_ && this->node->first_child != 0) {
2042
this->node=this->node->first_child;
2043
}
2044
else {
2045
this->skip_current_children_=false;
2046
while(this->node->next_sibling==0) {
2047
this->node=this->node->parent;
2048
if(this->node==0)
2049
return *this;
2050
}
2051
this->node=this->node->next_sibling;
2052
}
2053
return *this;
2054
}
2055
2056
template <class T, class tree_node_allocator>
2057
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
2058
{
2059
assert(this->node!=0);
2060
if(this->node->prev_sibling) {
2061
this->node=this->node->prev_sibling;
2062
while(this->node->last_child)
2063
this->node=this->node->last_child;
2064
}
2065
else {
2066
this->node=this->node->parent;
2067
if(this->node==0)
2068
return *this;
2069
}
2070
return *this;
2071
}
2072
2073
template <class T, class tree_node_allocator>
2074
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)
2075
{
2076
pre_order_iterator copy = *this;
2077
++(*this);
2078
return copy;
2079
}
2080
2081
template <class T, class tree_node_allocator>
2082
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)
2083
{
2084
pre_order_iterator copy = *this;
2085
--(*this);
2086
return copy;
2087
}
2088
2089
template <class T, class tree_node_allocator>
2090
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
2091
{
2092
while(num>0) {
2093
++(*this);
2094
--num;
2095
}
2096
return (*this);
2097
}
2098
2099
template <class T, class tree_node_allocator>
2100
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
2101
{
2102
while(num>0) {
2103
--(*this);
2104
--num;
2105
}
2106
return (*this);
2107
}
2108
2109
2110
2111
// Post-order iterator
2112
2113
template <class T, class tree_node_allocator>
2114
tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
2115
: iterator_base(0)
2116
{
2117
}
2118
2119
template <class T, class tree_node_allocator>
2120
tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
2121
: iterator_base(tn)
2122
{
2123
}
2124
2125
template <class T, class tree_node_allocator>
2126
tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
2127
: iterator_base(other.node)
2128
{
2129
}
2130
2131
template <class T, class tree_node_allocator>
2132
tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
2133
: iterator_base(other.node)
2134
{
2135
if(this->node==0) {
2136
if(other.range_last()!=0)
2137
this->node=other.range_last();
2138
else
2139
this->node=other.parent_;
2140
this->skip_children();
2141
++(*this);
2142
}
2143
}
2144
2145
template <class T, class tree_node_allocator>
2146
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
2147
{
2148
assert(this->node!=0);
2149
if(this->node->next_sibling==0) {
2150
this->node=this->node->parent;
2151
this->skip_current_children_=false;
2152
}
2153
else {
2154
this->node=this->node->next_sibling;
2155
if(this->skip_current_children_) {
2156
this->skip_current_children_=false;
2157
}
2158
else {
2159
while(this->node->first_child)
2160
this->node=this->node->first_child;
2161
}
2162
}
2163
return *this;
2164
}
2165
2166
template <class T, class tree_node_allocator>
2167
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
2168
{
2169
assert(this->node!=0);
2170
if(this->skip_current_children_ || this->node->last_child==0) {
2171
this->skip_current_children_=false;
2172
while(this->node->prev_sibling==0)
2173
this->node=this->node->parent;
2174
this->node=this->node->prev_sibling;
2175
}
2176
else {
2177
this->node=this->node->last_child;
2178
}
2179
return *this;
2180
}
2181
2182
template <class T, class tree_node_allocator>
2183
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
2184
{
2185
post_order_iterator copy = *this;
2186
++(*this);
2187
return copy;
2188
}
2189
2190
template <class T, class tree_node_allocator>
2191
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
2192
{
2193
post_order_iterator copy = *this;
2194
--(*this);
2195
return copy;
2196
}
2197
2198
2199
template <class T, class tree_node_allocator>
2200
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
2201
{
2202
while(num>0) {
2203
++(*this);
2204
--num;
2205
}
2206
return (*this);
2207
}
2208
2209
template <class T, class tree_node_allocator>
2210
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
2211
{
2212
while(num>0) {
2213
--(*this);
2214
--num;
2215
}
2216
return (*this);
2217
}
2218
2219
template <class T, class tree_node_allocator>
2220
void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
2221
{
2222
assert(this->node!=0);
2223
while(this->node->first_child)
2224
this->node=this->node->first_child;
2225
}
2226
2227
2228
// Breadth-first iterator
2229
2230
template <class T, class tree_node_allocator>
2231
tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
2232
: iterator_base()
2233
{
2234
}
2235
2236
template <class T, class tree_node_allocator>
2237
tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
2238
: iterator_base(tn)
2239
{
2240
traversal_queue.push(tn);
2241
}
2242
2243
template <class T, class tree_node_allocator>
2244
tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
2245
: iterator_base(other.node)
2246
{
2247
traversal_queue.push(other.node);
2248
}
2249
2250
template <class T, class tree_node_allocator>
2251
bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
2252
{
2253
if(other.node!=this->node) return true;
2254
else return false;
2255
}
2256
2257
template <class T, class tree_node_allocator>
2258
bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
2259
{
2260
if(other.node==this->node) return true;
2261
else return false;
2262
}
2263
2264
template <class T, class tree_node_allocator>
2265
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
2266
{
2267
assert(this->node!=0);
2268
2269
// Add child nodes and pop current node
2270
sibling_iterator sib=this->begin();
2271
while(sib!=this->end()) {
2272
traversal_queue.push(sib.node);
2273
++sib;
2274
}
2275
traversal_queue.pop();
2276
if(traversal_queue.size()>0)
2277
this->node=traversal_queue.front();
2278
else
2279
this->node=0;
2280
return (*this);
2281
}
2282
2283
template <class T, class tree_node_allocator>
2284
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)
2285
{
2286
breadth_first_queued_iterator copy = *this;
2287
++(*this);
2288
return copy;
2289
}
2290
2291
template <class T, class tree_node_allocator>
2292
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
2293
{
2294
while(num>0) {
2295
++(*this);
2296
--num;
2297
}
2298
return (*this);
2299
}
2300
2301
2302
2303
// Fixed depth iterator
2304
2305
template <class T, class tree_node_allocator>
2306
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
2307
: iterator_base()
2308
{
2309
}
2310
2311
template <class T, class tree_node_allocator>
2312
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
2313
: iterator_base(tn), top_node(0)
2314
{
2315
}
2316
2317
template <class T, class tree_node_allocator>
2318
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
2319
: iterator_base(other.node), top_node(0)
2320
{
2321
}
2322
2323
template <class T, class tree_node_allocator>
2324
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
2325
: iterator_base(other.node), top_node(0)
2326
{
2327
}
2328
2329
template <class T, class tree_node_allocator>
2330
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
2331
: iterator_base(other.node), top_node(other.top_node)
2332
{
2333
}
2334
2335
template <class T, class tree_node_allocator>
2336
bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const
2337
{
2338
if(other.node==this->node && other.top_node==top_node) return true;
2339
else return false;
2340
}
2341
2342
template <class T, class tree_node_allocator>
2343
bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const
2344
{
2345
if(other.node!=this->node || other.top_node!=top_node) return true;
2346
else return false;
2347
}
2348
2349
template <class T, class tree_node_allocator>
2350
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
2351
{
2352
assert(this->node!=0);
2353
2354
if(this->node->next_sibling) {
2355
this->node=this->node->next_sibling;
2356
}
2357
else {
2358
int relative_depth=0;
2359
upper:
2360
do {
2361
if(this->node==this->top_node) {
2362
this->node=0; // FIXME: return a proper fixed_depth end iterator once implemented
2363
return *this;
2364
}
2365
this->node=this->node->parent;
2366
if(this->node==0) return *this;
2367
--relative_depth;
2368
} while(this->node->next_sibling==0);
2369
lower:
2370
this->node=this->node->next_sibling;
2371
while(this->node->first_child==0) {
2372
if(this->node->next_sibling==0)
2373
goto upper;
2374
this->node=this->node->next_sibling;
2375
if(this->node==0) return *this;
2376
}
2377
while(relative_depth<0 && this->node->first_child!=0) {
2378
this->node=this->node->first_child;
2379
++relative_depth;
2380
}
2381
if(relative_depth<0) {
2382
if(this->node->next_sibling==0) goto upper;
2383
else goto lower;
2384
}
2385
}
2386
return *this;
2387
}
2388
2389
template <class T, class tree_node_allocator>
2390
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
2391
{
2392
assert(this->node!=0);
2393
2394
if(this->node->prev_sibling) {
2395
this->node=this->node->prev_sibling;
2396
}
2397
else {
2398
int relative_depth=0;
2399
upper:
2400
do {
2401
if(this->node==this->top_node) {
2402
this->node=0;
2403
return *this;
2404
}
2405
this->node=this->node->parent;
2406
if(this->node==0) return *this;
2407
--relative_depth;
2408
} while(this->node->prev_sibling==0);
2409
lower:
2410
this->node=this->node->prev_sibling;
2411
while(this->node->last_child==0) {
2412
if(this->node->prev_sibling==0)
2413
goto upper;
2414
this->node=this->node->prev_sibling;
2415
if(this->node==0) return *this;
2416
}
2417
while(relative_depth<0 && this->node->last_child!=0) {
2418
this->node=this->node->last_child;
2419
++relative_depth;
2420
}
2421
if(relative_depth<0) {
2422
if(this->node->prev_sibling==0) goto upper;
2423
else goto lower;
2424
}
2425
}
2426
return *this;
2427
2428
//
2429
//
2430
// assert(this->node!=0);
2431
// if(this->node->prev_sibling!=0) {
2432
// this->node=this->node->prev_sibling;
2433
// assert(this->node!=0);
2434
// if(this->node->parent==0 && this->node->prev_sibling==0) // head element
2435
// this->node=0;
2436
// }
2437
// else {
2438
// tree_node *par=this->node->parent;
2439
// do {
2440
// par=par->prev_sibling;
2441
// if(par==0) { // FIXME: need to keep track of this!
2442
// this->node=0;
2443
// return *this;
2444
// }
2445
// } while(par->last_child==0);
2446
// this->node=par->last_child;
2447
// }
2448
// return *this;
2449
}
2450
2451
template <class T, class tree_node_allocator>
2452
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
2453
{
2454
fixed_depth_iterator copy = *this;
2455
++(*this);
2456
return copy;
2457
}
2458
2459
template <class T, class tree_node_allocator>
2460
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
2461
{
2462
fixed_depth_iterator copy = *this;
2463
--(*this);
2464
return copy;
2465
}
2466
2467
template <class T, class tree_node_allocator>
2468
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
2469
{
2470
while(num>0) {
2471
--(*this);
2472
--(num);
2473
}
2474
return (*this);
2475
}
2476
2477
template <class T, class tree_node_allocator>
2478
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
2479
{
2480
while(num>0) {
2481
++(*this);
2482
--(num);
2483
}
2484
return *this;
2485
}
2486
2487
2488
// Sibling iterator
2489
2490
template <class T, class tree_node_allocator>
2491
tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
2492
: iterator_base()
2493
{
2494
set_parent_();
2495
}
2496
2497
template <class T, class tree_node_allocator>
2498
tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
2499
: iterator_base(tn)
2500
{
2501
set_parent_();
2502
}
2503
2504
template <class T, class tree_node_allocator>
2505
tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
2506
: iterator_base(other.node)
2507
{
2508
set_parent_();
2509
}
2510
2511
template <class T, class tree_node_allocator>
2512
tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
2513
: iterator_base(other), parent_(other.parent_)
2514
{
2515
}
2516
2517
template <class T, class tree_node_allocator>
2518
void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
2519
{
2520
parent_=0;
2521
if(this->node==0) return;
2522
if(this->node->parent!=0)
2523
parent_=this->node->parent;
2524
}
2525
2526
template <class T, class tree_node_allocator>
2527
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
2528
{
2529
if(this->node)
2530
this->node=this->node->next_sibling;
2531
return *this;
2532
}
2533
2534
template <class T, class tree_node_allocator>
2535
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
2536
{
2537
if(this->node) this->node=this->node->prev_sibling;
2538
else {
2539
assert(parent_);
2540
this->node=parent_->last_child;
2541
}
2542
return *this;
2543
}
2544
2545
template <class T, class tree_node_allocator>
2546
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
2547
{
2548
sibling_iterator copy = *this;
2549
++(*this);
2550
return copy;
2551
}
2552
2553
template <class T, class tree_node_allocator>
2554
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
2555
{
2556
sibling_iterator copy = *this;
2557
--(*this);
2558
return copy;
2559
}
2560
2561
template <class T, class tree_node_allocator>
2562
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
2563
{
2564
while(num>0) {
2565
++(*this);
2566
--num;
2567
}
2568
return (*this);
2569
}
2570
2571
template <class T, class tree_node_allocator>
2572
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
2573
{
2574
while(num>0) {
2575
--(*this);
2576
--num;
2577
}
2578
return (*this);
2579
}
2580
2581
template <class T, class tree_node_allocator>
2582
typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
2583
{
2584
tree_node *tmp=parent_->first_child;
2585
return tmp;
2586
}
2587
2588
template <class T, class tree_node_allocator>
2589
typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
2590
{
2591
return parent_->last_child;
2592
}
2593
2594
// Leaf iterator
2595
2596
template <class T, class tree_node_allocator>
2597
tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
2598
: iterator_base(0), top_node(0)
2599
{
2600
}
2601
2602
template <class T, class tree_node_allocator>
2603
tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)
2604
: iterator_base(tn), top_node(top)
2605
{
2606
}
2607
2608
template <class T, class tree_node_allocator>
2609
tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)
2610
: iterator_base(other.node), top_node(0)
2611
{
2612
}
2613
2614
template <class T, class tree_node_allocator>
2615
tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)
2616
: iterator_base(other.node), top_node(0)
2617
{
2618
if(this->node==0) {
2619
if(other.range_last()!=0)
2620
this->node=other.range_last();
2621
else
2622
this->node=other.parent_;
2623
++(*this);
2624
}
2625
}
2626
2627
template <class T, class tree_node_allocator>
2628
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
2629
{
2630
assert(this->node!=0);
2631
if(this->node->first_child!=0) { // current node is no longer leaf (children got added)
2632
while(this->node->first_child)
2633
this->node=this->node->first_child;
2634
}
2635
else {
2636
while(this->node->next_sibling==0) {
2637
if (this->node->parent==0) return *this;
2638
this->node=this->node->parent;
2639
if (top_node != 0 && this->node==top_node) return *this;
2640
}
2641
this->node=this->node->next_sibling;
2642
while(this->node->first_child)
2643
this->node=this->node->first_child;
2644
}
2645
return *this;
2646
}
2647
2648
template <class T, class tree_node_allocator>
2649
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
2650
{
2651
assert(this->node!=0);
2652
while (this->node->prev_sibling==0) {
2653
if (this->node->parent==0) return *this;
2654
this->node=this->node->parent;
2655
if (top_node !=0 && this->node==top_node) return *this;
2656
}
2657
this->node=this->node->prev_sibling;
2658
while(this->node->last_child)
2659
this->node=this->node->last_child;
2660
return *this;
2661
}
2662
2663
template <class T, class tree_node_allocator>
2664
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
2665
{
2666
leaf_iterator copy = *this;
2667
++(*this);
2668
return copy;
2669
}
2670
2671
template <class T, class tree_node_allocator>
2672
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
2673
{
2674
leaf_iterator copy = *this;
2675
--(*this);
2676
return copy;
2677
}
2678
2679
2680
template <class T, class tree_node_allocator>
2681
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
2682
{
2683
while(num>0) {
2684
++(*this);
2685
--num;
2686
}
2687
return (*this);
2688
}
2689
2690
template <class T, class tree_node_allocator>
2691
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
2692
{
2693
while(num>0) {
2694
--(*this);
2695
--num;
2696
}
2697
return (*this);
2698
}
2699
2700
#endif
2701
2702
// Local variables:
2703
// default-tab-width: 3
2704
// End:
Loggerhead is a web-based interface for Breezy
Version: 2.0.1