00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
#ifndef tree_hh_
00046
#define tree_hh_
00047
00048
#include <cassert>
00049
#include <memory>
00050
#include <stdexcept>
00051
#include <iterator>
00052
#include <set>
00053
00054
00055
00056
00057
namespace kp {
00058
00059
template <
class T1,
class T2>
00060
inline void constructor(T1* p, T2& val)
00061 {
00062
new ((
void *) p) T1(val);
00063 }
00064
00065
template <
class T1>
00066
inline void constructor(T1* p)
00067 {
00068
new ((
void *) p) T1;
00069 }
00070
00071
template <
class T1>
00072
inline void kp::destructor(T1* p)
00073 {
00074 p->~T1();
00075 }
00076
00077 };
00078
00079
template<
class T>
00080
class tree_node_ {
00081
public:
00082 tree_node_<T> *parent;
00083 tree_node_<T> *first_child, *last_child;
00084 tree_node_<T> *prev_sibling, *next_sibling;
00085 T data;
00086 };
00087
00088
template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
00089
class tree {
00090
protected:
00091
typedef tree_node_<T> tree_node;
00092
public:
00093
typedef T value_type;
00094
00095
class iterator_base;
00096
class pre_order_iterator;
00097
class post_order_iterator;
00098
class sibling_iterator;
00099
00100 tree();
00101 tree(
const T&);
00102 tree(
const iterator_base&);
00103 tree(
const tree<T, tree_node_allocator>&);
00104 ~tree();
00105
void operator=(
const tree<T, tree_node_allocator>&);
00106
00107
#ifdef __SGI_STL_PORT
00108
class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t> {
00109
#else
00110
class iterator_base {
00111
#endif
00112
public:
00113
typedef T value_type;
00114
typedef T* pointer;
00115
typedef T& reference;
00116
typedef size_t size_type;
00117
typedef ptrdiff_t difference_type;
00118
typedef std::bidirectional_iterator_tag iterator_category;
00119
00120 iterator_base();
00121 iterator_base(tree_node *);
00122
00123 T& operator*() const;
00124 T* operator->() const;
00125
00126
void skip_children();
00127
unsigned int number_of_children() const;
00128
00129 sibling_iterator begin() const;
00130 sibling_iterator end() const;
00131
00132 tree_node *node;
00133 protected:
00134
bool skip_current_children_;
00135 };
00136
00137 class pre_order_iterator : public iterator_base {
00138
public:
00139 pre_order_iterator();
00140 pre_order_iterator(tree_node *);
00141 pre_order_iterator(
const iterator_base&);
00142 pre_order_iterator(
const sibling_iterator&);
00143
00144
bool operator==(
const pre_order_iterator&) const;
00145
bool operator!=(const pre_order_iterator&) const;
00146 pre_order_iterator& operator++();
00147 pre_order_iterator& operator--();
00148 pre_order_iterator operator++(
int);
00149 pre_order_iterator operator--(
int);
00150 pre_order_iterator& operator+=(
unsigned int);
00151 pre_order_iterator& operator-=(
unsigned int);
00152 };
00153
00154 class post_order_iterator : public iterator_base {
00155
public:
00156 post_order_iterator();
00157 post_order_iterator(tree_node *);
00158 post_order_iterator(
const iterator_base&);
00159 post_order_iterator(
const sibling_iterator&);
00160
00161
bool operator==(
const post_order_iterator&) const;
00162
bool operator!=(const post_order_iterator&) const;
00163 post_order_iterator& operator++();
00164 post_order_iterator& operator--();
00165 post_order_iterator operator++(
int);
00166 post_order_iterator operator--(
int);
00167 post_order_iterator& operator+=(
unsigned int);
00168 post_order_iterator& operator-=(
unsigned int);
00169
00170
void descend_all();
00171 };
00172
00173 typedef pre_order_iterator iterator;
00174
00175 class fixed_depth_iterator : public iterator_base {
00176
public:
00177 fixed_depth_iterator();
00178 fixed_depth_iterator(tree_node *);
00179 fixed_depth_iterator(
const iterator_base&);
00180 fixed_depth_iterator(
const sibling_iterator&);
00181 fixed_depth_iterator(
const fixed_depth_iterator&);
00182
00183
bool operator==(
const fixed_depth_iterator&) const;
00184
bool operator!=(const fixed_depth_iterator&) const;
00185 fixed_depth_iterator& operator++();
00186 fixed_depth_iterator& operator--();
00187 fixed_depth_iterator operator++(
int);
00188 fixed_depth_iterator operator--(
int);
00189 fixed_depth_iterator& operator+=(
unsigned int);
00190 fixed_depth_iterator& operator-=(
unsigned int);
00191
00192 tree_node *first_parent_;
00193 private:
00194
void set_first_parent_();
00195
void find_leftmost_parent_();
00196 };
00197
00198 class sibling_iterator : public iterator_base {
00199
public:
00200 sibling_iterator();
00201 sibling_iterator(tree_node *);
00202 sibling_iterator(
const sibling_iterator&);
00203 sibling_iterator(
const iterator_base&);
00204
00205
bool operator==(
const sibling_iterator&) const;
00206
bool operator!=(const sibling_iterator&) const;
00207 sibling_iterator& operator++();
00208 sibling_iterator& operator--();
00209 sibling_iterator operator++(
int);
00210 sibling_iterator operator--(
int);
00211 sibling_iterator& operator+=(
unsigned int);
00212 sibling_iterator& operator-=(
unsigned int);
00213
00214 tree_node *range_first() const;
00215 tree_node *range_last() const;
00216 tree_node *parent_;
00217 private:
00218
void set_parent_();
00219 };
00220
00221
00222 pre_order_iterator begin() const;
00223 pre_order_iterator end() const;
00224 post_order_iterator begin_post() const;
00225 post_order_iterator end_post() const;
00226 fixed_depth_iterator begin_fixed(const iterator_base&,
unsigned int) const;
00227 fixed_depth_iterator end_fixed(const iterator_base&,
unsigned int) const;
00228
00229 sibling_iterator begin(const iterator_base&) const;
00230 sibling_iterator end(const iterator_base&) const;
00231
00232 template<typename iter> iter parent(iter) const;
00233 sibling_iterator previous_sibling(const iterator_base&) const;
00234 sibling_iterator next_sibling(const iterator_base&) const;
00235
00236
void clear();
00237
00238 template<typename iter> iter erase(iter);
00239
00240
void erase_children(const iterator_base&);
00241
00242
00243 template<typename iter> iter append_child(iter position);
00244 template<typename iter> iter append_child(iter position, const T& x);
00245
00246 template<typename iter> iter append_child(iter position, iter other_position);
00247 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
00248
00249
00250 pre_order_iterator set_head(const T& x);
00251
00252 template<typename iter> iter insert(iter position, const T& x);
00253
00254
00255 sibling_iterator insert(sibling_iterator position, const T& x);
00256
00257 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
00258
00259 template<typename iter> iter insert_after(iter position, const T& x);
00260
00261
00262 template<typename iter> iter replace(iter position, const T& x);
00263
00264 template<typename iter> iter replace(iter position, const iterator_base& from);
00265
00266 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
00267 sibling_iterator new_begin, sibling_iterator new_end);
00268
00269
00270 template<typename iter> iter flatten(iter position);
00271
00272 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
00273
00274 template<typename iter> iter reparent(iter position, iter from);
00275
00276
00277 template<typename iter> iter move_after(iter target, iter source);
00278 template<typename iter> iter move_before(iter target, iter source);
00279 template<typename iter> iter move_below(iter target, iter source);
00280
00281
00282
void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
00283
bool duplicate_leaves=false);
00284
00285
void sort(sibling_iterator from, sibling_iterator to,
bool deep=false);
00286 template<class StrictWeakOrdering>
00287
void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp,
bool deep=false);
00288
00289 template<typename iter>
00290
bool equal(const iter& one, const iter& two, const iter& three) const;
00291 template<typename iter, class BinaryPredicate>
00292
bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
00293 template<typename iter>
00294
bool equal_subtree(const iter& one, const iter& two) const;
00295 template<typename iter, class BinaryPredicate>
00296
bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
00297
00298 tree subtree(sibling_iterator from, sibling_iterator to) const;
00299
void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
00300
00301
void swap(sibling_iterator it);
00302
00303
00304
00305
00306
00307
int size() const;
00308
00309
bool empty() const;
00310
00311
int depth(const iterator_base&) const;
00312
00313
unsigned int number_of_children(const iterator_base&) const;
00314
00315
unsigned int number_of_siblings(const iterator_base&) const;
00316
00317
bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
00318 const iterator_base& end) const;
00319
00320
00321
bool is_valid(const iterator_base&) const;
00322
00323
00324
unsigned int index(sibling_iterator it) const;
00325
00326 sibling_iterator child(const iterator_base& position,
unsigned int) const;
00327
00328 class iterator_base_less {
00329
public:
00330
bool operator()(
const typename tree<T, tree_node_allocator>::iterator_base& one,
00331
const typename tree<T, tree_node_allocator>::iterator_base& two)
const
00332
{
00333
return one.node < two.node;
00334 }
00335 };
00336 tree_node *head, *feet;
00337
private:
00338 tree_node_allocator alloc_;
00339
void head_initialise_();
00340
void copy_(
const tree<T, tree_node_allocator>& other);
00341
template<
class StrictWeakOrdering>
00342
class compare_nodes {
00343
public:
00344
bool operator()(
const tree_node*,
const tree_node *);
00345 };
00346 };
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
template <
class T,
class tree_node_allocator>
00369
bool operator>(
const typename tree<T, tree_node_allocator>::iterator_base& one,
00370
const typename tree<T, tree_node_allocator>::iterator_base& two)
00371 {
00372
if(one.node > two.node)
return true;
00373
return false;
00374 }
00375
00376
00377
00378
00379
00380
template <
class T,
class tree_node_allocator>
00381 tree<T, tree_node_allocator>::tree()
00382 {
00383 head_initialise_();
00384 }
00385
00386
template <
class T,
class tree_node_allocator>
00387 tree<T, tree_node_allocator>::tree(
const T& x)
00388 {
00389 head_initialise_();
00390 set_head(x);
00391 }
00392
00393
template <
class T,
class tree_node_allocator>
00394 tree<T, tree_node_allocator>::tree(
const iterator_base& other)
00395 {
00396 head_initialise_();
00397 set_head((*other));
00398 replace(begin(), other);
00399 }
00400
00401
template <
class T,
class tree_node_allocator>
00402 tree<T, tree_node_allocator>::~tree()
00403 {
00404 clear();
00405 alloc_.deallocate(head,1);
00406 alloc_.deallocate(feet,1);
00407 }
00408
00409
template <
class T,
class tree_node_allocator>
00410
void tree<T, tree_node_allocator>::head_initialise_()
00411 {
00412 head = alloc_.allocate(1,0);
00413 feet = alloc_.allocate(1,0);
00414
00415 head->parent=0;
00416 head->first_child=0;
00417 head->last_child=0;
00418 head->prev_sibling=0;
00419 head->next_sibling=feet;
00420
00421 feet->parent=0;
00422 feet->first_child=0;
00423 feet->last_child=0;
00424 feet->prev_sibling=head;
00425 feet->next_sibling=0;
00426 }
00427
00428
template <
class T,
class tree_node_allocator>
00429
void tree<T, tree_node_allocator>::operator=(
const tree<T, tree_node_allocator>& other)
00430 {
00431 copy_(other);
00432 }
00433
00434
template <
class T,
class tree_node_allocator>
00435 tree<T, tree_node_allocator>::tree(
const tree<T, tree_node_allocator>& other)
00436 {
00437 head_initialise_();
00438 copy_(other);
00439 }
00440
00441
template <
class T,
class tree_node_allocator>
00442
void tree<T, tree_node_allocator>::copy_(
const tree<T, tree_node_allocator>& other)
00443 {
00444 clear();
00445 pre_order_iterator it=other.begin(), to=begin();
00446
while(it!=other.end()) {
00447 to=insert(to, (*it));
00448 it.skip_children();
00449 ++it;
00450 }
00451 to=begin();
00452 it=other.begin();
00453
while(it!=other.end()) {
00454 to=replace(to, it);
00455 to.skip_children();
00456 it.skip_children();
00457 ++to;
00458 ++it;
00459 }
00460 }
00461
00462
template <
class T,
class tree_node_allocator>
00463
void tree<T, tree_node_allocator>::clear()
00464 {
00465
if(head)
00466
while(head->next_sibling!=feet)
00467 erase(pre_order_iterator(head->next_sibling));
00468 }
00469
00470
template<
class T,
class tree_node_allocator>
00471
void tree<T, tree_node_allocator>::erase_children(
const iterator_base& it)
00472 {
00473 tree_node *cur=it.node->first_child;
00474 tree_node *prev=0;
00475
00476
while(cur!=0) {
00477 prev=cur;
00478 cur=cur->next_sibling;
00479 erase_children(pre_order_iterator(prev));
00480 kp::destructor(&prev->data);
00481 alloc_.deallocate(prev,1);
00482 }
00483 it.node->first_child=0;
00484 it.node->last_child=0;
00485 }
00486
00487
template<
class T,
class tree_node_allocator>
00488
template<
class iter>
00489 iter tree<T, tree_node_allocator>::erase(iter it)
00490 {
00491 tree_node *cur=it.node;
00492 assert(cur!=head);
00493 iter ret=it;
00494 ret.skip_children();
00495 ++ret;
00496 erase_children(it);
00497
if(cur->prev_sibling==0) {
00498 cur->parent->first_child=cur->next_sibling;
00499 }
00500
else {
00501 cur->prev_sibling->next_sibling=cur->next_sibling;
00502 }
00503
if(cur->next_sibling==0) {
00504 cur->parent->last_child=cur->prev_sibling;
00505 }
00506
else {
00507 cur->next_sibling->prev_sibling=cur->prev_sibling;
00508 }
00509
00510 kp::destructor(&cur->data);
00511 alloc_.deallocate(cur,1);
00512
return ret;
00513 }
00514
00515
template <
class T,
class tree_node_allocator>
00516
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin()
const
00517
{
00518
return pre_order_iterator(head->next_sibling);
00519 }
00520
00521
template <
class T,
class tree_node_allocator>
00522
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end()
const
00523
{
00524
return pre_order_iterator(feet);
00525 }
00526
00527
template <
class T,
class tree_node_allocator>
00528
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post()
const
00529
{
00530 tree_node *tmp=head->next_sibling;
00531
if(tmp!=feet) {
00532
while(tmp->first_child)
00533 tmp=tmp->first_child;
00534 }
00535
return post_order_iterator(tmp);
00536 }
00537
00538
template <
class T,
class tree_node_allocator>
00539
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post()
const
00540
{
00541
return post_order_iterator(feet);
00542 }
00543
00544
template <
class T,
class tree_node_allocator>
00545
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(
const iterator_base& pos,
unsigned int dp)
const
00546
{
00547 tree_node *tmp=pos.node;
00548
unsigned int curdepth=0;
00549
while(curdepth<dp) {
00550
while(tmp->first_child==0) {
00551 tmp=tmp->next_sibling;
00552
if(tmp==0)
00553
throw std::range_error(
"tree: begin_fixed out of range");
00554 }
00555 tmp=tmp->first_child;
00556 ++curdepth;
00557 }
00558
return tmp;
00559 }
00560
00561
template <
class T,
class tree_node_allocator>
00562
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(
const iterator_base& pos,
unsigned int dp)
const
00563
{
00564 assert(1==0);
00565 tree_node *tmp=pos.node;
00566
unsigned int curdepth=1;
00567
while(curdepth<dp) {
00568
while(tmp->first_child==0) {
00569 tmp=tmp->next_sibling;
00570
if(tmp==0)
00571
throw std::range_error(
"tree: end_fixed out of range");
00572 }
00573 tmp=tmp->first_child;
00574 ++curdepth;
00575 }
00576
return tmp;
00577 }
00578
00579
template <
class T,
class tree_node_allocator>
00580
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(
const iterator_base& pos)
const
00581
{
00582
if(pos.node->first_child==0) {
00583
return end(pos);
00584 }
00585
return pos.node->first_child;
00586 }
00587
00588
template <
class T,
class tree_node_allocator>
00589
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(
const iterator_base& pos)
const
00590
{
00591 sibling_iterator ret(0);
00592 ret.parent_=pos.node;
00593
return ret;
00594 }
00595
00596
template <
class T,
class tree_node_allocator>
00597
template <
typename iter>
00598 iter tree<T, tree_node_allocator>::parent(iter position)
const
00599
{
00600 assert(
position.node!=0);
00601
return iter(
position.node->parent);
00602 }
00603
00604
template <
class T,
class tree_node_allocator>
00605
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::previous_sibling(
const iterator_base& position)
const
00606
{
00607 assert(
position.node!=0);
00608
return sibling_iterator(
position.node->prev_sibling);
00609 }
00610
00611
template <
class T,
class tree_node_allocator>
00612
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::next_sibling(
const iterator_base& position)
const
00613
{
00614 assert(
position.node!=0);
00615
if(
position.node->next_sibling==0)
00616
return end(pre_order_iterator(
position.node->parent));
00617
else
00618
return sibling_iterator(
position.node->next_sibling);
00619 }
00620
00621
template <
class T,
class tree_node_allocator>
00622
template <
typename iter>
00623 iter tree<T, tree_node_allocator>::append_child(iter position)
00624 {
00625 assert(
position.node!=head);
00626
00627 tree_node* tmp = alloc_.allocate(1,0);
00628 kp::constructor(&tmp->data);
00629 tmp->first_child=0;
00630 tmp->last_child=0;
00631
00632 tmp->parent=
position.node;
00633
if(
position.node->last_child!=0) {
00634
position.node->last_child->next_sibling=tmp;
00635 }
00636
else {
00637
position.node->first_child=tmp;
00638 }
00639 tmp->prev_sibling=
position.node->last_child;
00640
position.node->last_child=tmp;
00641 tmp->next_sibling=0;
00642
return tmp;
00643 }
00644
00645
template <
class T,
class tree_node_allocator>
00646
template <
class iter>
00647 iter tree<T, tree_node_allocator>::append_child(iter position,
const T& x)
00648 {
00649
00650
00651
00652
00653 assert(
position.node!=head);
00654
00655 tree_node* tmp = alloc_.allocate(1,0);
00656 kp::constructor(&tmp->data, x);
00657 tmp->first_child=0;
00658 tmp->last_child=0;
00659
00660 tmp->parent=
position.node;
00661
if(
position.node->last_child!=0) {
00662
position.node->last_child->next_sibling=tmp;
00663 }
00664
else {
00665
position.node->first_child=tmp;
00666 }
00667 tmp->prev_sibling=
position.node->last_child;
00668
position.node->last_child=tmp;
00669 tmp->next_sibling=0;
00670
return tmp;
00671 }
00672
00673
template <
class T,
class tree_node_allocator>
00674
template <
class iter>
00675 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
00676 {
00677 assert(
position.node!=head);
00678
00679 sibling_iterator aargh=append_child(position, value_type());
00680
return replace(aargh, other);
00681 }
00682
00683
template <
class T,
class tree_node_allocator>
00684
template <
class iter>
00685 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
00686 {
00687 iter ret=from;
00688
00689
while(from!=to) {
00690 insert_subtree(
position.end(), from);
00691 ++from;
00692 }
00693
return ret;
00694 }
00695
00696
template <
class T,
class tree_node_allocator>
00697
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(
const T& x)
00698 {
00699 assert(head->next_sibling==feet);
00700
return insert(iterator(feet), x);
00701 }
00702
00703
template <
class T,
class tree_node_allocator>
00704
template <
class iter>
00705 iter tree<T, tree_node_allocator>::insert(iter position,
const T& x)
00706 {
00707
if(
position.node==0) {
00708
position.node=feet;
00709
00710 }
00711 tree_node* tmp = alloc_.allocate(1,0);
00712 kp::constructor(&tmp->data, x);
00713 tmp->first_child=0;
00714 tmp->last_child=0;
00715
00716 tmp->parent=
position.node->parent;
00717 tmp->next_sibling=
position.node;
00718 tmp->prev_sibling=
position.node->prev_sibling;
00719
position.node->prev_sibling=tmp;
00720
00721
if(tmp->prev_sibling==0)
00722 tmp->parent->first_child=tmp;
00723
else
00724 tmp->prev_sibling->next_sibling=tmp;
00725
return tmp;
00726 }
00727
00728
template <
class T,
class tree_node_allocator>
00729
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position,
const T& x)
00730 {
00731 tree_node* tmp = alloc_.allocate(1,0);
00732 kp::constructor(&tmp->data, x);
00733 tmp->first_child=0;
00734 tmp->last_child=0;
00735
00736 tmp->next_sibling=
position.node;
00737
if(
position.node==0) {
00738 tmp->parent=
position.parent_;
00739 tmp->prev_sibling=
position.range_last();
00740 tmp->parent->last_child=tmp;
00741 }
00742
else {
00743 tmp->parent=
position.node->parent;
00744 tmp->prev_sibling=
position.node->prev_sibling;
00745
position.node->prev_sibling=tmp;
00746 }
00747
00748
if(tmp->prev_sibling==0)
00749 tmp->parent->first_child=tmp;
00750
else
00751 tmp->prev_sibling->next_sibling=tmp;
00752
return tmp;
00753 }
00754
00755
template <
class T,
class tree_node_allocator>
00756
template <
class iter>
00757 iter tree<T, tree_node_allocator>::insert_after(iter position,
const T& x)
00758 {
00759 tree_node* tmp = alloc_.allocate(1,0);
00760 kp::constructor(&tmp->data, x);
00761 tmp->first_child=0;
00762 tmp->last_child=0;
00763
00764 tmp->parent=
position.node->parent;
00765 tmp->prev_sibling=
position.node;
00766 tmp->next_sibling=
position.node->next_sibling;
00767
position.node->next_sibling=tmp;
00768
00769
if(tmp->next_sibling==0) {
00770
if(tmp->parent)
00771 tmp->parent->last_child=tmp;
00772 }
00773
else {
00774 tmp->next_sibling->prev_sibling=tmp;
00775 }
00776
return tmp;
00777 }
00778
00779
template <
class T,
class tree_node_allocator>
00780
template <
class iter>
00781 iter tree<T, tree_node_allocator>::insert_subtree(iter position,
const iterator_base& subtree)
00782 {
00783
00784 iter it=insert(position, value_type());
00785
00786
return replace(it, subtree);
00787 }
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
template <
class T,
class tree_node_allocator>
00800
template <
class iter>
00801 iter tree<T, tree_node_allocator>::replace(iter position,
const T& x)
00802 {
00803 kp::destructor(&
position.node->data);
00804 kp::constructor(&
position.node->data, x);
00805
return position;
00806 }
00807
00808
template <
class T,
class tree_node_allocator>
00809
template <
class iter>
00810 iter tree<T, tree_node_allocator>::replace(iter position,
const iterator_base& from)
00811 {
00812 assert(
position.node!=head);
00813 tree_node *current_from=from.node;
00814 tree_node *start_from=from.node;
00815 tree_node *current_to =
position.node;
00816
00817
00818 erase_children(position);
00819 tree_node* tmp = alloc_.allocate(1,0);
00820 kp::constructor(&tmp->data, (*from));
00821 tmp->first_child=0;
00822 tmp->last_child=0;
00823
if(current_to->prev_sibling==0) {
00824 current_to->parent->first_child=tmp;
00825 }
00826
else {
00827 current_to->prev_sibling->next_sibling=tmp;
00828 }
00829 tmp->prev_sibling=current_to->prev_sibling;
00830
if(current_to->next_sibling==0) {
00831 current_to->parent->last_child=tmp;
00832 }
00833
else {
00834 current_to->next_sibling->prev_sibling=tmp;
00835 }
00836 tmp->next_sibling=current_to->next_sibling;
00837 tmp->parent=current_to->parent;
00838 kp::destructor(¤t_to->data);
00839 alloc_.deallocate(current_to,1);
00840 current_to=tmp;
00841
00842
00843 tree_node *last=from.node->next_sibling;
00844
00845 pre_order_iterator toit=tmp;
00846
00847
do {
00848 assert(current_from!=0);
00849
if(current_from->first_child != 0) {
00850 current_from=current_from->first_child;
00851 toit=append_child(toit, current_from->data);
00852 }
00853
else {
00854
while(current_from->next_sibling==0 && current_from!=start_from) {
00855 current_from=current_from->parent;
00856 toit=parent(toit);
00857 assert(current_from!=0);
00858 }
00859 current_from=current_from->next_sibling;
00860
if(current_from!=last) {
00861 toit=append_child(parent(toit), current_from->data);
00862 }
00863 }
00864 }
while(current_from!=last);
00865
00866
return current_to;
00867 }
00868
00869
template <
class T,
class tree_node_allocator>
00870
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
00871 sibling_iterator orig_begin,
00872 sibling_iterator orig_end,
00873 sibling_iterator new_begin,
00874 sibling_iterator new_end)
00875 {
00876 tree_node *orig_first=orig_begin.node;
00877 tree_node *new_first=new_begin.node;
00878 tree_node *orig_last=orig_first;
00879
while((++orig_begin)!=orig_end)
00880 orig_last=orig_last->next_sibling;
00881 tree_node *new_last=new_first;
00882
while((++new_begin)!=new_end)
00883 new_last=new_last->next_sibling;
00884
00885
00886
bool first=
true;
00887 pre_order_iterator ret;
00888
while(1==1) {
00889 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
00890
if(first) {
00891 ret=tt;
00892 first=
false;
00893 }
00894
if(new_first==new_last)
00895
break;
00896 new_first=new_first->next_sibling;
00897 }
00898
00899
00900
bool last=
false;
00901 tree_node *next=orig_first;
00902
while(1==1) {
00903
if(next==orig_last)
00904 last=
true;
00905 next=next->next_sibling;
00906 erase((pre_order_iterator)orig_first);
00907
if(last)
00908
break;
00909 orig_first=next;
00910 }
00911
return ret;
00912 }
00913
00914
template <
class T,
class tree_node_allocator>
00915
template <
typename iter>
00916 iter tree<T, tree_node_allocator>::flatten(iter position)
00917 {
00918
if(
position.node->first_child==0)
00919
return position;
00920
00921 tree_node *tmp=
position.node->first_child;
00922
while(tmp) {
00923 tmp->parent=
position.node->parent;
00924 tmp=tmp->next_sibling;
00925 }
00926
if(
position.node->next_sibling) {
00927
position.node->last_child->next_sibling=
position.node->next_sibling;
00928
position.node->next_sibling->prev_sibling=
position.node->last_child;
00929 }
00930
else {
00931
position.node->parent->last_child=
position.node->last_child;
00932 }
00933
position.node->next_sibling=
position.node->first_child;
00934
position.node->next_sibling->prev_sibling=
position.node;
00935
position.node->first_child=0;
00936
position.node->last_child=0;
00937
00938
return position;
00939 }
00940
00941
00942
template <
class T,
class tree_node_allocator>
00943
template <
typename iter>
00944 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
00945 {
00946 tree_node *first=begin.node;
00947 tree_node *last=first;
00948
if(begin==end)
return begin;
00949
00950
while((++begin)!=end) {
00951 last=last->next_sibling;
00952 }
00953
00954
if(first->prev_sibling==0) {
00955 first->parent->first_child=last->next_sibling;
00956 }
00957
else {
00958 first->prev_sibling->next_sibling=last->next_sibling;
00959 }
00960
if(last->next_sibling==0) {
00961 last->parent->last_child=first->prev_sibling;
00962 }
00963
else {
00964 last->next_sibling->prev_sibling=first->prev_sibling;
00965 }
00966
if(
position.node->first_child==0) {
00967
position.node->first_child=first;
00968
position.node->last_child=last;
00969 first->prev_sibling=0;
00970 }
00971
else {
00972
position.node->last_child->next_sibling=first;
00973 first->prev_sibling=
position.node->last_child;
00974
position.node->last_child=last;
00975 }
00976 last->next_sibling=0;
00977
00978 tree_node *pos=first;
00979
while(1==1) {
00980 pos->parent=
position.node;
00981
if(pos==last)
break;
00982 pos=pos->next_sibling;
00983 }
00984
00985
return first;
00986 }
00987
00988
template <
class T,
class tree_node_allocator>
00989
template <
typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
00990 {
00991
if(from.node->first_child==0)
return position;
00992
return reparent(position, from.node->first_child, end(from));
00993 }
00994
00995
template <
class T,
class tree_node_allocator>
00996
template <
typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
00997 {
00998 tree_node *dst=target.node;
00999 tree_node *src=source.node;
01000 assert(dst);
01001 assert(src);
01002
01003
if(dst==src)
return source;
01004
01005
01006
if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01007
else src->parent->first_child=src->next_sibling;
01008
if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01009
else src->parent->last_child=src->prev_sibling;
01010
01011
01012
if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
01013
else dst->parent->first_child=src;
01014 src->prev_sibling=dst->prev_sibling;
01015 dst->prev_sibling=src;
01016 src->next_sibling=dst;
01017 src->parent=dst->parent;
01018
return src;
01019 }
01020
01021
template <
class T,
class tree_node_allocator>
01022
void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
01023 sibling_iterator from1, sibling_iterator from2,
01024
bool duplicate_leaves)
01025 {
01026 sibling_iterator fnd;
01027
while(from1!=from2) {
01028
if((fnd=std::find(to1, to2, (*from1))) != to2) {
01029
if(from1.begin()==from1.end()) {
01030
if(duplicate_leaves)
01031 append_child(parent(to1), (*from1));
01032 }
01033
else {
01034 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
01035 }
01036 }
01037
else {
01038 insert_subtree(to2, from1);
01039 }
01040 ++from1;
01041 }
01042 }
01043
01044
template <
class T,
class tree_node_allocator>
01045
template <
class StrictWeakOrdering>
01046
bool tree<T, tree_node_allocator>::compare_nodes<StrictWeakOrdering>::operator()(
const tree_node *a,
01047
const tree_node *b)
01048 {
01049
static StrictWeakOrdering comp;
01050
01051
return comp(a->data, b->data);
01052 }
01053
01054
template <
class T,
class tree_node_allocator>
01055
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
bool deep)
01056 {
01057 std::less<T> comp;
01058 sort(from, to, comp, deep);
01059 }
01060
01061
template <
class T,
class tree_node_allocator>
01062
template <
class StrictWeakOrdering>
01063
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
01064 StrictWeakOrdering comp,
bool deep)
01065 {
01066
if(from==to)
return;
01067
01068
01069
01070 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
01071 sibling_iterator it=from, it2=to;
01072
while(it != to) {
01073 nodes.insert(it.node);
01074 ++it;
01075 }
01076
01077 --it2;
01078
01079
01080 tree_node *prev=from.node->prev_sibling;
01081 tree_node *next=it2.node->next_sibling;
01082
typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
01083
if(prev==0) {
01084
if((*nit)->parent!=0)
01085 (*nit)->parent->first_child=(*nit);
01086 }
01087
else prev->next_sibling=(*nit);
01088
01089 --eit;
01090
while(nit!=eit) {
01091 (*nit)->prev_sibling=prev;
01092
if(prev)
01093 prev->next_sibling=(*nit);
01094 prev=(*nit);
01095 ++nit;
01096 }
01097
01098
if(prev)
01099 prev->next_sibling=(*eit);
01100
01101
01102 (*eit)->next_sibling=next;
01103 (*eit)->prev_sibling=prev;
01104
if(next==0) {
01105
if((*eit)->parent!=0)
01106 (*eit)->parent->last_child=(*eit);
01107 }
01108
else next->prev_sibling=(*eit);
01109
01110
if(deep) {
01111 sibling_iterator bcs(*nodes.begin());
01112 sibling_iterator ecs(*eit);
01113 ++ecs;
01114
while(bcs!=ecs) {
01115 sort(begin(bcs), end(bcs), comp, deep);
01116 ++bcs;
01117 }
01118 }
01119 }
01120
01121
template <
class T,
class tree_node_allocator>
01122
template <
typename iter>
01123
bool tree<T, tree_node_allocator>::equal(
const iter& one_,
const iter& two,
const iter& three_)
const
01124
{
01125 std::equal_to<T> comp;
01126
return equal(one_, two, three_, comp);
01127 }
01128
01129
template <
class T,
class tree_node_allocator>
01130
template <
typename iter>
01131
bool tree<T, tree_node_allocator>::equal_subtree(
const iter& one_,
const iter& two_)
const
01132
{
01133 std::equal_to<T> comp;
01134
return equal_subtree(one_, two_, comp);
01135 }
01136
01137
template <
class T,
class tree_node_allocator>
01138
template <
typename iter,
class BinaryPredicate>
01139
bool tree<T, tree_node_allocator>::equal(
const iter& one_,
const iter& two,
const iter& three_, BinaryPredicate fun)
const
01140
{
01141 pre_order_iterator one(one_), three(three_);
01142
01143
01144
01145
while(one!=two && is_valid(three)) {
01146
if(!fun(*one,*three))
01147
return false;
01148
if(one.number_of_children()!=three.number_of_children())
01149
return false;
01150 ++one;
01151 ++three;
01152 }
01153
return true;
01154 }
01155
01156
template <
class T,
class tree_node_allocator>
01157
template <
typename iter,
class BinaryPredicate>
01158
bool tree<T, tree_node_allocator>::equal_subtree(
const iter& one_,
const iter& two_, BinaryPredicate fun)
const
01159
{
01160 pre_order_iterator one(one_), two(two_);
01161
01162
if(!fun(*one,*two))
return false;
01163
if(number_of_children(one)!=number_of_children(two))
return false;
01164
return equal(begin(one),end(one),begin(two),fun);
01165 }
01166
01167
template <
class T,
class tree_node_allocator>
01168 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to)
const
01169
{
01170 tree tmp;
01171 tmp.set_head(value_type());
01172 tmp.replace(tmp.begin(), tmp.end(), from, to);
01173
return tmp;
01174 }
01175
01176
template <
class T,
class tree_node_allocator>
01177
void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to)
const
01178
{
01179 tmp.set_head(value_type());
01180 tmp.replace(tmp.begin(), tmp.end(), from, to);
01181 }
01182
01183
template <
class T,
class tree_node_allocator>
01184
int tree<T, tree_node_allocator>::size()
const
01185
{
01186
int i=0;
01187 pre_order_iterator it=begin(), eit=end();
01188
while(it!=eit) {
01189 ++i;
01190 ++it;
01191 }
01192
return i;
01193 }
01194
01195
template <
class T,
class tree_node_allocator>
01196
bool tree<T, tree_node_allocator>::empty()
const
01197
{
01198 pre_order_iterator it=begin(), eit=end();
01199
return (it==eit);
01200 }
01201
01202
template <
class T,
class tree_node_allocator>
01203
int tree<T, tree_node_allocator>::depth(
const iterator_base& it)
const
01204
{
01205 tree_node* pos=it.node;
01206 assert(pos!=0);
01207
int ret=0;
01208
while(pos->parent!=0) {
01209 pos=pos->parent;
01210 ++ret;
01211 }
01212
return ret;
01213 }
01214
01215
template <
class T,
class tree_node_allocator>
01216
unsigned int tree<T, tree_node_allocator>::number_of_children(
const iterator_base& it)
const
01217
{
01218 tree_node *pos=it.node->first_child;
01219
if(pos==0)
return 0;
01220
01221
unsigned int ret=1;
01222
01223
01224
01225
01226
while((pos=pos->next_sibling))
01227 ++ret;
01228
return ret;
01229 }
01230
01231
template <
class T,
class tree_node_allocator>
01232
unsigned int tree<T, tree_node_allocator>::number_of_siblings(
const iterator_base& it)
const
01233
{
01234 tree_node *pos=it.node;
01235
unsigned int ret=1;
01236
while(pos->next_sibling && pos->next_sibling!=head) {
01237 ++ret;
01238 pos=pos->next_sibling;
01239 }
01240
return ret;
01241 }
01242
01243
template <
class T,
class tree_node_allocator>
01244
void tree<T, tree_node_allocator>::swap(sibling_iterator it)
01245 {
01246 tree_node *nxt=it.node->next_sibling;
01247
if(nxt) {
01248
if(it.node->prev_sibling)
01249 it.node->prev_sibling->next_sibling=nxt;
01250
else
01251 it.node->parent->first_child=nxt;
01252 nxt->prev_sibling=it.node->prev_sibling;
01253 tree_node *nxtnxt=nxt->next_sibling;
01254
if(nxtnxt)
01255 nxtnxt->prev_sibling=it.node;
01256
else
01257 it.node->parent->last_child=it.node;
01258 nxt->next_sibling=it.node;
01259 it.node->prev_sibling=nxt;
01260 it.node->next_sibling=nxtnxt;
01261 }
01262 }
01263
01264
01265
01266
01267
01268
01269
01270
01271
01272
01273
01274
01275
01276
01277
01278
template <
class T,
class tree_node_allocator>
01279
bool tree<T, tree_node_allocator>::is_in_subtree(
const iterator_base& it,
const iterator_base& begin,
01280
const iterator_base& end)
const
01281
{
01282
01283 pre_order_iterator tmp=begin;
01284
while(tmp!=end) {
01285
if(tmp==it)
return true;
01286 ++tmp;
01287 }
01288
return false;
01289 }
01290
01291
template <
class T,
class tree_node_allocator>
01292
bool tree<T, tree_node_allocator>::is_valid(
const iterator_base& it)
const
01293
{
01294
if(it.node==0 || it.node==feet)
return false;
01295
else return true;
01296 }
01297
01298
template <
class T,
class tree_node_allocator>
01299
unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it)
const
01300
{
01301
unsigned int ind=0;
01302
if(it.node->parent==0) {
01303
while(it.node->prev_sibling!=head) {
01304 it.node=it.node->prev_sibling;
01305 ++ind;
01306 }
01307 }
01308
else {
01309
while(it.node->prev_sibling!=0) {
01310 it.node=it.node->prev_sibling;
01311 ++ind;
01312 }
01313 }
01314
return ind;
01315 }
01316
01317
01318
template <
class T,
class tree_node_allocator>
01319
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(
const iterator_base& it,
unsigned int num)
const
01320
{
01321 tree_node *tmp=it.node->first_child;
01322
while(num--) {
01323 assert(tmp!=0);
01324 tmp=tmp->next_sibling;
01325 }
01326
return tmp;
01327 }
01328
01329
01330
01331
01332
01333
01334
template <
class T,
class tree_node_allocator>
01335 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01336 : node(0), skip_current_children_(false)
01337 {
01338 }
01339
01340
template <
class T,
class tree_node_allocator>
01341 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01342 : node(tn), skip_current_children_(false)
01343 {
01344 }
01345
01346
template <
class T,
class tree_node_allocator>
01347 T& tree<T, tree_node_allocator>::iterator_base::operator*()
const
01348
{
01349
return node->data;
01350 }
01351
01352
template <
class T,
class tree_node_allocator>
01353 T* tree<T, tree_node_allocator>::iterator_base::operator->()
const
01354
{
01355
return &(node->data);
01356 }
01357
01358
template <
class T,
class tree_node_allocator>
01359
bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(
const post_order_iterator& other)
const
01360
{
01361
if(other.node!=this->node)
return true;
01362
else return false;
01363 }
01364
01365
template <
class T,
class tree_node_allocator>
01366
bool tree<T, tree_node_allocator>::post_order_iterator::operator==(
const post_order_iterator& other)
const
01367
{
01368
if(other.node==this->node)
return true;
01369
else return false;
01370 }
01371
01372
template <
class T,
class tree_node_allocator>
01373
bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(
const pre_order_iterator& other)
const
01374
{
01375
if(other.node!=this->node)
return true;
01376
else return false;
01377 }
01378
01379
template <
class T,
class tree_node_allocator>
01380
bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(
const pre_order_iterator& other)
const
01381
{
01382
if(other.node==this->node)
return true;
01383
else return false;
01384 }
01385
01386
template <
class T,
class tree_node_allocator>
01387
bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(
const sibling_iterator& other)
const
01388
{
01389
if(other.node!=this->node)
return true;
01390
else return false;
01391 }
01392
01393
template <
class T,
class tree_node_allocator>
01394
bool tree<T, tree_node_allocator>::sibling_iterator::operator==(
const sibling_iterator& other)
const
01395
{
01396
if(other.node==this->node)
return true;
01397
else return false;
01398 }
01399
01400
template <
class T,
class tree_node_allocator>
01401
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin()
const
01402
{
01403 sibling_iterator ret(node->first_child);
01404 ret.parent_=this->node;
01405
return ret;
01406 }
01407
01408
template <
class T,
class tree_node_allocator>
01409
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end()
const
01410
{
01411 sibling_iterator ret(0);
01412 ret.parent_=node;
01413
return ret;
01414 }
01415
01416
template <
class T,
class tree_node_allocator>
01417
void tree<T, tree_node_allocator>::iterator_base::skip_children()
01418 {
01419 skip_current_children_=
true;
01420 }
01421
01422
template <
class T,
class tree_node_allocator>
01423
unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children()
const
01424
{
01425 tree_node *pos=node->first_child;
01426
if(pos==0)
return 0;
01427
01428
unsigned int ret=1;
01429
while(pos!=node->last_child) {
01430 ++ret;
01431 pos=pos->next_sibling;
01432 }
01433
return ret;
01434 }
01435
01436
01437
01438
01439
01440
template <
class T,
class tree_node_allocator>
01441 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
01442 : iterator_base(0)
01443 {
01444 }
01445
01446
template <
class T,
class tree_node_allocator>
01447 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
01448 : iterator_base(tn)
01449 {
01450 }
01451
01452
template <
class T,
class tree_node_allocator>
01453 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(
const iterator_base &other)
01454 : iterator_base(other.node)
01455 {
01456 }
01457
01458
template <
class T,
class tree_node_allocator>
01459 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(
const sibling_iterator& other)
01460 : iterator_base(other.node)
01461 {
01462
if(this->node==0) {
01463
if(other.range_last()!=0)
01464 this->node=other.range_last();
01465
else
01466 this->node=other.parent_;
01467 this->skip_children();
01468 ++(*this);
01469 }
01470 }
01471
01472
template <
class T,
class tree_node_allocator>
01473
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
01474 {
01475 assert(this->node!=0);
01476
if(!this->skip_current_children_ && this->node->first_child != 0) {
01477 this->node=this->node->first_child;
01478 }
01479
else {
01480 this->skip_current_children_=
false;
01481
while(this->node->next_sibling==0) {
01482 this->node=this->node->parent;
01483
if(this->node==0)
01484
return *
this;
01485 }
01486 this->node=this->node->next_sibling;
01487 }
01488
return *
this;
01489 }
01490
01491
template <
class T,
class tree_node_allocator>
01492
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
01493 {
01494 assert(this->node!=0);
01495
if(this->node->prev_sibling) {
01496 this->node=this->node->prev_sibling;
01497
while(this->node->last_child)
01498 this->node=this->node->last_child;
01499 }
01500
else {
01501 this->node=this->node->parent;
01502
if(this->node==0)
01503
return *
this;
01504 }
01505
return *
this;
01506 }
01507
01508
template <
class T,
class tree_node_allocator>
01509
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(
int n)
01510 {
01511 pre_order_iterator copy = *
this;
01512 ++(*this);
01513
return copy;
01514 }
01515
01516
template <
class T,
class tree_node_allocator>
01517
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(
int n)
01518 {
01519 pre_order_iterator copy = *
this;
01520 --(*this);
01521
return copy;
01522 }
01523
01524
template <
class T,
class tree_node_allocator>
01525
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(
unsigned int num)
01526 {
01527
while(num>0) {
01528 ++(*this);
01529 --num;
01530 }
01531
return (*this);
01532 }
01533
01534
template <
class T,
class tree_node_allocator>
01535
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(
unsigned int num)
01536 {
01537
while(num>0) {
01538 --(*this);
01539 --num;
01540 }
01541
return (*this);
01542 }
01543
01544
01545
01546
01547
01548
template <
class T,
class tree_node_allocator>
01549 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
01550 : iterator_base(0)
01551 {
01552 }
01553
01554
template <
class T,
class tree_node_allocator>
01555 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
01556 : iterator_base(tn)
01557 {
01558 }
01559
01560
template <
class T,
class tree_node_allocator>
01561 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(
const iterator_base &other)
01562 : iterator_base(other.node)
01563 {
01564 }
01565
01566
template <
class T,
class tree_node_allocator>
01567 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(
const sibling_iterator& other)
01568 : iterator_base(other.node)
01569 {
01570
if(this->node==0) {
01571
if(other.range_last()!=0)
01572 this->node=other.range_last();
01573
else
01574 this->node=other.parent_;
01575 this->skip_children();
01576 ++(*this);
01577 }
01578 }
01579
01580
template <
class T,
class tree_node_allocator>
01581
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
01582 {
01583 assert(this->node!=0);
01584
if(this->node->next_sibling==0)
01585 this->node=this->node->parent;
01586
else {
01587 this->node=this->node->next_sibling;
01588
if(this->skip_current_children_) {
01589 this->skip_current_children_=
false;
01590 }
01591
else {
01592
while(this->node->first_child)
01593 this->node=this->node->first_child;
01594 }
01595 }
01596
return *
this;
01597 }
01598
01599
template <
class T,
class tree_node_allocator>
01600
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
01601 {
01602 assert(this->node!=0);
01603
if(this->skip_current_children_ || this->node->last_child==0) {
01604 this->skip_current_children_=
false;
01605
while(this->node->prev_sibling==0)
01606 this->node=this->node->parent;
01607 this->node=this->node->prev_sibling;
01608 }
01609
else {
01610 this->node=this->node->last_child;
01611 }
01612
return *
this;
01613 }
01614
01615
template <
class T,
class tree_node_allocator>
01616
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(
int)
01617 {
01618 post_order_iterator copy = *
this;
01619 ++(*this);
01620
return copy;
01621 }
01622
01623
template <
class T,
class tree_node_allocator>
01624
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(
int)
01625 {
01626 post_order_iterator copy = *
this;
01627 --(*this);
01628
return copy;
01629 }
01630
01631
01632
template <
class T,
class tree_node_allocator>
01633
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(
unsigned int num)
01634 {
01635
while(num>0) {
01636 ++(*this);
01637 --num;
01638 }
01639
return (*this);
01640 }
01641
01642
template <
class T,
class tree_node_allocator>
01643
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(
unsigned int num)
01644 {
01645
while(num>0) {
01646 --(*this);
01647 --num;
01648 }
01649
return (*this);
01650 }
01651
01652
template <
class T,
class tree_node_allocator>
01653
void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
01654 {
01655 assert(this->node!=0);
01656
while(this->node->first_child)
01657 this->node=this->node->first_child;
01658 }
01659
01660
01661
01662
01663
template <
class T,
class tree_node_allocator>
01664 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
01665 : iterator_base()
01666 {
01667 set_first_parent_();
01668 }
01669
01670
template <
class T,
class tree_node_allocator>
01671 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
01672 : iterator_base(tn)
01673 {
01674 set_first_parent_();
01675 }
01676
01677
template <
class T,
class tree_node_allocator>
01678 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const iterator_base& other)
01679 : iterator_base(other.node)
01680 {
01681 set_first_parent_();
01682 }
01683
01684
template <
class T,
class tree_node_allocator>
01685 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const sibling_iterator& other)
01686 : iterator_base(other.node), first_parent_(other.parent_)
01687 {
01688 find_leftmost_parent_();
01689 }
01690
01691
template <
class T,
class tree_node_allocator>
01692 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const fixed_depth_iterator& other)
01693 : iterator_base(other.node), first_parent_(other.first_parent_)
01694 {
01695 }
01696
01697
template <
class T,
class tree_node_allocator>
01698
void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
01699 {
01700
return;
01701
01702 first_parent_=0;
01703
if(this->node==0)
return;
01704
if(this->node->parent!=0)
01705 first_parent_=this->node->parent;
01706
if(first_parent_)
01707 find_leftmost_parent_();
01708 }
01709
01710
template <
class T,
class tree_node_allocator>
01711
void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
01712 {
01713
return;
01714 tree_node *tmppar=first_parent_;
01715
while(tmppar->prev_sibling) {
01716 tmppar=tmppar->prev_sibling;
01717
if(tmppar->first_child)
01718 first_parent_=tmppar;
01719 }
01720 }
01721
01722
template <
class T,
class tree_node_allocator>
01723
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
01724 {
01725 assert(this->node!=0);
01726
if(this->node->next_sibling!=0) {
01727 this->node=this->node->next_sibling;
01728 assert(this->node!=0);
01729
if(this->node->parent==0 && this->node->next_sibling==0)
01730 this->node=0;
01731 }
01732
else {
01733 tree_node *par=this->node->parent;
01734
do {
01735 par=par->next_sibling;
01736
if(par==0) {
01737 this->node=0;
01738
return *
this;
01739 }
01740 }
while(par->first_child==0);
01741 this->node=par->first_child;
01742 }
01743
return *
this;
01744 }
01745
01746
template <
class T,
class tree_node_allocator>
01747
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
01748 {
01749 assert(this->node!=0);
01750
if(this->node->prev_sibling!=0) {
01751 this->node=this->node->prev_sibling;
01752 assert(this->node!=0);
01753
if(this->node->parent==0 && this->node->prev_sibling==0)
01754 this->node=0;
01755 }
01756
else {
01757 tree_node *par=this->node->parent;
01758
do {
01759 par=par->prev_sibling;
01760
if(par==0) {
01761 this->node=0;
01762
return *
this;
01763 }
01764 }
while(par->last_child==0);
01765 this->node=par->last_child;
01766 }
01767
return *
this;
01768 }
01769
01770
template <
class T,
class tree_node_allocator>
01771
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(
int)
01772 {
01773 fixed_depth_iterator copy = *
this;
01774 ++(*this);
01775
return copy;
01776 }
01777
01778
template <
class T,
class tree_node_allocator>
01779
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(
int)
01780 {
01781 fixed_depth_iterator copy = *
this;
01782 --(*this);
01783
return copy;
01784 }
01785
01786
template <
class T,
class tree_node_allocator>
01787
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(
unsigned int num)
01788 {
01789
while(num>0) {
01790 --(*this);
01791 --(num);
01792 }
01793
return (*this);
01794 }
01795
01796
template <
class T,
class tree_node_allocator>
01797
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(
unsigned int num)
01798 {
01799
while(num>0) {
01800 ++(*this);
01801 --(num);
01802 }
01803
return *
this;
01804 }
01805
01806
01807
01808
01809
01810
01811
template <
class T,
class tree_node_allocator>
01812 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
01813 : iterator_base()
01814 {
01815 set_parent_();
01816 }
01817
01818
template <
class T,
class tree_node_allocator>
01819 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
01820 : iterator_base(tn)
01821 {
01822 set_parent_();
01823 }
01824
01825
template <
class T,
class tree_node_allocator>
01826 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(
const iterator_base& other)
01827 : iterator_base(other.node)
01828 {
01829 set_parent_();
01830 }
01831
01832
template <
class T,
class tree_node_allocator>
01833 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(
const sibling_iterator& other)
01834 : iterator_base(other), parent_(other.parent_)
01835 {
01836 }
01837
01838
template <
class T,
class tree_node_allocator>
01839
void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
01840 {
01841 parent_=0;
01842
if(this->node==0)
return;
01843
if(this->node->parent!=0)
01844 parent_=this->node->parent;
01845 }
01846
01847
template <
class T,
class tree_node_allocator>
01848
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
01849 {
01850
if(this->node)
01851 this->node=this->node->next_sibling;
01852
return *
this;
01853 }
01854
01855
template <
class T,
class tree_node_allocator>
01856
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
01857 {
01858
if(this->node) this->node=this->node->prev_sibling;
01859
else {
01860 assert(parent_);
01861 this->node=parent_->last_child;
01862 }
01863
return *
this;
01864 }
01865
01866
template <
class T,
class tree_node_allocator>
01867
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(
int)
01868 {
01869 sibling_iterator copy = *
this;
01870 ++(*this);
01871
return copy;
01872 }
01873
01874
template <
class T,
class tree_node_allocator>
01875
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(
int)
01876 {
01877 sibling_iterator copy = *
this;
01878 --(*this);
01879
return copy;
01880 }
01881
01882
template <
class T,
class tree_node_allocator>
01883
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(
unsigned int num)
01884 {
01885
while(num>0) {
01886 ++(*this);
01887 --num;
01888 }
01889
return (*this);
01890 }
01891
01892
template <
class T,
class tree_node_allocator>
01893
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(
unsigned int num)
01894 {
01895
while(num>0) {
01896 --(*this);
01897 --num;
01898 }
01899
return (*this);
01900 }
01901
01902
template <
class T,
class tree_node_allocator>
01903
typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first()
const
01904
{
01905 tree_node *tmp=parent_->first_child;
01906
return tmp;
01907 }
01908
01909
template <
class T,
class tree_node_allocator>
01910
typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last()
const
01911
{
01912
return parent_->last_child;
01913 }
01914
01915
01916
#endif
01917
01918
01919
01920