00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __VGTL_TREE_H_
00031 #define __VGTL_TREE_H_
00032
00033 #include <vector>
00034 #include <list>
00035 #include <multimap>
00036 #include <multiset>
00037 #include <algorithm>
00038 #include <iterator>
00039 #include <string>
00040 #include <utility>
00041 #include <g_data.h>
00042
00044 #define _C_W_preorder 1
00045
00046 #define _C_W_postorder 2
00047
00049 typedef enum {cw_pre = _C_W_preorder, cw_post = _C_W_postorder,
00050 cw_pre_post = _C_W_preorder|_C_W_postorder} walker_type;
00051
00052 #include <vgtl_helpers.h>
00053 #include <vgtl_intadapt.h>
00054
00055 __VGTL_BEGIN_NAMESPACE
00056
00058
00062 template <class _Tp, class _Ctr, class _Iterator>
00063 class _Tree_node
00064 {
00065 private:
00066 typedef void* _Void_pointer;
00067 typedef _Iterator _Ctr_iterator;
00068 typedef _Tree_node<_Tp,_Ctr,_Iterator> _Self;
00069
00070 public:
00072 _Tp _C_data;
00074 _Void_pointer _C_parent;
00076 _Ctr _C_children;
00077
00079 _Tree_node() { _C_data();
00080 __VGTL_TRY {
00081 initialize();
00082 }
00083 __VGTL_UNWIND( );
00084 }
00085
00087 void initialize() {
00088 std::_Construct(&_C_children);
00089 _C_parent = NULL;
00090 }
00091
00093 void get_rid_of() {
00094 std::_Destroy(&_C_children);
00095 }
00096
00098 void clear_tree();
00100 void clear_children()
00101 { _C_children.erase(_C_children.begin(), _C_children.end()); }
00102
00104 _Ctr_iterator get_childentry_iterator(_Void_pointer __p)
00105 { _Ctr_iterator __tmp;
00106 for(__tmp = _C_children.begin(); __tmp != _C_children.end(); ++__tmp)
00107 if(*__tmp == __p) break;
00108 return __tmp;
00109 }
00110
00111 #ifdef __VGTL_MEMBER_TEMPLATES
00112
00116 template <class _Output_Iterator>
00117 void add_all_children(_Output_Iterator fi, _Self* _parent);
00118
00120 template <class Compare>
00121 void sort_children(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
00122 {
00123 sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
00124 }
00125
00127 template <class Compare>
00128 void sort_parents(_Ctr_iterator first, _Ctr_iterator last, Compare comp) {}
00129 #endif
00130 };
00131
00133
00137 template <class _Tp, class _Ctr, class _Iterator>
00138 class _ITree_node : public _Tree_node<_Tp,_Ctr,_Iterator>
00139 {
00140 private:
00141 typedef void* _Void_pointer;
00142 typedef _Iterator _Ctr_iterator;
00143 typedef _ITree_node<_Tp,_Ctr,_Iterator> _Self;
00144
00145 public:
00147 ctree_data_hook _C_data_hook;
00148
00150 _ITree_node() { _C_data();
00151 __VGTL_TRY {
00152 initialize();
00153 }
00154 __VGTL_UNWIND( );
00155 }
00156
00158 void initialize() {
00159 std::_Construct(&_C_children);
00160 _C_parent = NULL;
00161 _C_data_hook.f = 0;
00162 }
00163
00165 void get_rid_of() {
00166 std::_Destroy(&_C_children);
00167 std::_Destroy(&_C_data_hook);
00168 }
00169
00171 ctree_data_hook& data_hook() { return _C_data_hook; }
00172
00173 };
00174
00175 #ifdef __VGTL_MEMBER_TEMPLATES
00176 template <class _Tp, class _Ctr, class _Iterator>
00177 template <class _Output_Iterator>
00178 void
00179 _Tree_node<_Tp,_Ctr,_Iterator>::
00180 add_all_children(_Output_Iterator fi, _Self* _parent)
00181 { _Ctr_iterator it;
00182 for(it = _C_children.begin();
00183 it != _C_children.end();
00184 ++it)
00185 {
00186 *fi++ = *it;
00187 (*((_Self*)*it))._C_parent = _parent;
00188 }
00189 };
00190 #endif
00191
00192
00193 template <class _Tp, class _Ctr, class _Iterator>
00194 void
00195 _Tree_node<_Tp,_Ctr,_Iterator>::clear_tree()
00196 {
00197 _Ctr* chld = &this->_C_children;
00198 _Iterator it;
00199
00200 for(it = chld->begin(); it != chld->end(); ++it)
00201 ((_Tree_node<_Tp,_Ctr,_Iterator>*)(*it))->clear_tree();
00202 this->_C_children.erase(this->_C_children.begin(), this->_C_children.end());
00203 this->_C_parent = NULL;
00204
00205 std::_Destroy(&this->_C_data);
00206 get_rid_of();
00207 }
00208
00209
00210 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00211 class _Node>
00212 class _Tree_iterator;
00213
00215
00219 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00220 class _Node>
00221 class _Tree_walker_base
00222 {
00223 public:
00224 typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node> walker;
00225 typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_walker;
00226 typedef _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Self;
00227 typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Itr;
00228
00230
00231 typedef _Tp value_type;
00232 typedef _Ptr pointer;
00233 typedef _Ref reference;
00235 private:
00236 typedef _Iterator _Ctr_iterator;
00237
00238 public:
00240
00241 typedef __one_iterator<void *> parents_iterator;
00242 typedef _Ctr_iterator children_iterator;
00243 typedef _Node node_type;
00244
00245 typedef size_t size_type;
00246 typedef ptrdiff_t difference_type;
00248
00249 public:
00251 _Node* _C_w_cur;
00252
00253 public:
00255 _Tree_walker_base() {}
00256
00258 _Tree_walker_base(_Node* __x) : _C_w_cur(__x) { }
00259
00261 _Tree_walker_base(const walker& __x) : _C_w_cur(__x._C_w_cur) {}
00262
00264 reference operator*() const { return (*_C_w_cur)._C_data; }
00265
00266 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00267
00268 pointer operator->() const { return &(operator*()); }
00269 #endif
00270
00271 public:
00273 _Self& operator=(const _Itr& __x) {
00274 _C_w_cur = __x._C_i_cur;
00275 return *this;
00276 }
00277
00279 ctree_data_hook& data_hook() { return (*_C_w_cur)._C_data_hook; }
00281 ctree_data_hook& parent_data_hook()
00282 { return ((_Node*)(*_C_w_cur)._C_parent)->_C_data_hook; }
00283
00285 const _Node* parent() { return (_Node*)(*_C_w_cur)._C_parent; }
00287 const _Node* node() { return _C_w_cur; }
00288
00290 size_type n_children() { return _C_w_cur->_C_children.size(); }
00292 size_type n_parents() { return _C_w_cur->_C_parent ? 1 : 0; }
00293
00295 bool is_leaf() { return _C_w_cur->_C_children.empty(); }
00297 bool is_root()
00298 { return parent() != NULL && (*parent())._C_parent == NULL; }
00299
00301 bool is_ground() { return parent() == NULL; }
00303 bool is_sky() { return false; }
00304
00306 children_iterator child_begin() { return _C_w_cur->_C_children.begin(); }
00308 children_iterator child_end() { return _C_w_cur->_C_children.end(); }
00309
00311 parents_iterator parent_begin()
00312 { return parents_iterator(&_C_w_cur->_C_parent); }
00314 parents_iterator parent_end()
00315 { return parents_iterator(&_C_w_cur->_C_parent, false); }
00316
00318 template <class _Function>
00319 _Function for_each_child(_Function __f)
00320 {
00321 return for_each(child_begin(), child_end(), __f);
00322 }
00324 template <class _Function>
00325 _Function for_each_parent(_Function __f)
00326 {
00327 return for_each(parent_begin(), parent_end(), __f);
00328 }
00329
00331 template <class Compare>
00332 void sort_children(children_iterator first, children_iterator last,
00333 Compare comp)
00334 { (*_C_w_cur).sort_children(first, last, comp); }
00335
00337 template <class Compare>
00338 void sort_parents(parents_iterator first, parents_iterator last,
00339 Compare comp) {}
00340
00342 template <class Compare>
00343 void sort_children(Compare comp)
00344 { (*_C_w_cur).sort_children(child_begin(), child_end(), comp); }
00345
00347 template <class Compare>
00348 void sort_parents(Compare comp) {}
00349 };
00350
00352
00357 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00358 class _Node>
00359 class _Tree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
00360 {
00361 public:
00362 typedef _Tree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node> walker;
00363 typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_walker;
00364 typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Self;
00365
00366 public:
00368 struct {
00369 unsigned int order:2;
00370 unsigned int front_to_back:1;
00371 unsigned int depth_first:1;
00372 } _C_w_t;
00374 bool _C_w_in_preorder;
00376 std::vector<_Iterator> _C_w_cur_it;
00377
00378 public:
00380 _Tree_walker() : _C_w_cur_it() {_C_w_cur_it.reserve(32); }
00381
00382 private:
00384 void _find_start_node();
00386 void _find_end_node();
00388 void _find_next_preorder();
00390 void _find_next_postorder();
00392 void _find_next_any();
00394 void _find_prev_preorder();
00396 void _find_prev_postorder();
00398 void _find_prev_any();
00399
00400 public:
00405 _Tree_walker(_Node* __x, int order = (_C_W_preorder|_C_W_postorder),
00406 bool front_to_back = true, bool depth_first = true,
00407 bool find_start = true)
00408 : _C_w_cur_it() {
00409 _C_w_cur = __x;
00410 _C_w_cur_it.reserve(32);
00411 _C_w_t.order = order;
00412 _C_w_t.front_to_back = front_to_back;
00413 _C_w_t.depth_first = depth_first;
00414 if(__x->_C_parent == NULL)
00415 _C_w_in_preorder = find_start;
00416 else if(find_start)
00417 _find_start_node();
00418 else
00419 _find_end_node(); }
00420
00422 _Tree_walker(const walker& __x) : _C_w_in_preorder(__x._C_w_in_preorder),
00423 _C_w_cur_it(__x._C_w_cur_it) {
00424 _C_w_cur = __x._C_w_cur;
00425 _C_w_t = __x._C_w_t;
00426 }
00427
00429
00430 bool operator==(const _Self& __x) const
00431 { return (_C_w_t.order == 0 && __x._C_w_t.order == 0) ||
00432 (_C_w_cur == __x._C_w_cur &&
00433 _C_w_in_preorder == __x._C_w_in_preorder &&
00434 _C_w_t.order == __x._C_w_t.order &&
00435 _C_w_t.front_to_back == __x._C_w_t.front_to_back &&
00436 _C_w_t.depth_first == __x._C_w_t.depth_first &&
00437 _C_w_cur_it == __x._C_w_cur_it); }
00438 bool operator!=(const _Self& __x) const
00439 { return (_C_w_t.order != 0 || __x._C_w_t.order != 0) &&
00440 (_C_w_cur != __x._C_w_cur ||
00441 _C_w_in_preorder != __x._C_w_in_preorder ||
00442 _C_w_t.order != __x._C_w_t.order ||
00443 _C_w_t.front_to_back != __x._C_w_t.front_to_back ||
00444 _C_w_t.depth_first != __x._C_w_t.depth_first ||
00445 _C_w_cur_it != __x._C_w_cur_it); }
00447
00448 public:
00450
00451 _Self& operator++() {
00452 if(_C_w_t.depth_first)
00453 {
00454 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00455 {
00456 _find_next_any();
00457 }
00458 else if(_C_w_t.order & _C_W_preorder)
00459 {
00460 _find_next_preorder();
00461 }
00462 else
00463 {
00464 _find_next_postorder();
00465 }
00466 }
00467 else
00468 {
00469 ;
00470 }
00471 return *this;
00472 }
00473 _Self operator++(int) {
00474 _Self __tmp = *this;
00475 ++*this;
00476 return __tmp;
00477 }
00478
00479 _Self& operator--() {
00480 if(_C_w_t.depth_first)
00481 {
00482 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00483 {
00484 _find_prev_any();
00485 }
00486 else if(_C_w_t.order & _C_W_preorder)
00487 {
00488 _find_prev_preorder();
00489 }
00490 else
00491 {
00492 _find_prev_postorder();
00493 }
00494 }
00495 else
00496 {
00497 ;
00498 }
00499 return *this;
00500 }
00501 _Self operator--(int) {
00502 _Self __tmp = *this;
00503 --*this;
00504 return __tmp;
00505 }
00507
00509
00510 _Self operator<<(const parents_iterator& __dummy) {
00511 _Self __tmp = *this;
00512 _Node *help = __tmp._C_w_cur._C_parent;
00513 if(help == NULL)
00514 {
00515 __tmp._C_w_t.order = 0;
00516 }
00517 else
00518 {
00519 __tmp._C_w_cur = help;
00520 if(__tmp._C_w_t.order & _C_W_postorder)
00521 __tmp._C_w_in_preorder = false;
00522 if(!__tmp._C_w_cur_it.empty())
00523 pop_back(__tmp._C_w_cur_it);
00524 }
00525 return __tmp;
00526 }
00527
00529
00530 _Self operator>>(const children_iterator& __i) {
00531 _Self __tmp = *this;
00532 _Node *help = (_Node*) *__i;
00533 if(__tmp._C_w_t.order & _C_W_preorder)
00534 __tmp._C_w_in_preorder = true;
00535 __tmp._C_w_cur_it.push_back(__i);
00536 __tmp._C_w_cur = help;
00537 return __tmp;
00538 }
00539
00541 _Self& operator<<=(const parents_iterator& __dummy) {
00542 _Node *help = _C_w_cur._C_parent;
00543 if(help == NULL)
00544 {
00545 _C_w_t.order = 0;
00546 }
00547 else
00548 {
00549 _C_w_cur = help;
00550 if(_C_w_t.order & _C_W_postorder)
00551 _C_w_in_preorder = false;
00552 if(!_C_w_cur_it.empty())
00553 pop_back(_C_w_cur_it);
00554 }
00555 return *this;
00556 }
00557
00559 _Self& operator>>=(const children_iterator& __i) {
00560 _Node *help = (_Node*) *__i;
00561 if(_C_w_t.order & _C_W_preorder)
00562 _C_w_in_preorder = true;
00563 push_back(_C_w_cur_it, __i);
00564 _C_w_cur = help;
00565 return *this;
00566 }
00567
00569 _Self& operator~() {
00570 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00571 _C_w_in_preorder = !_C_w_in_preorder;
00572 return *this;
00573 }
00574
00576 _Self& operator=(const _Itr& __x) {
00577 _C_w_cur = __x._C_i_cur;
00578 _C_w_cur_it = __x._C_i_cur_it;
00579 _C_w_t.order = _C_W_postorder;
00580 _C_w_t.depth_first = 1;
00581 _C_w_t.front_to_back = 1;
00582 return *this;
00583 }
00584
00586 bool in_preorder() { return _C_w_in_preorder; }
00587 };
00588
00589 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00590 class _Node>
00591 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_start_node()
00592 {
00593 if(_C_w_t.depth_first)
00594 {
00595 if(_C_w_t.order & _C_W_preorder)
00596 {
00597 _C_w_in_preorder = true;
00598 }
00599 else if(_C_w_t.order & _C_W_postorder)
00600 {
00601 _C_w_in_preorder = false;
00602 if(_C_w_t.front_to_back)
00603 {
00604 while(!_C_w_cur->_C_children.empty())
00605 {
00606 _Ctr_iterator help;
00607
00608 help = _C_w_cur->_C_children.begin();
00609 _C_w_cur = (_Node*)*help;
00610 _C_w_cur_it.push_back(help);
00611 }
00612 }
00613 else
00614 {
00615 while(!_C_w_cur->_C_children.empty())
00616 {
00617 _Ctr_iterator help;
00618
00619 help = _C_w_cur->_C_children.end();
00620 --help;
00621 _C_w_cur = (_Node*)*help;
00622 _C_w_cur_it.push_back(help);
00623 }
00624 }
00625 }
00626 }
00627 else
00628 {
00629 ;
00630 }
00631 }
00632
00633 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00634 class _Node>
00635 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_end_node()
00636 {
00637 if(_C_w_t.depth_first)
00638 {
00639 if(_C_w_t.order & _C_W_postorder)
00640 {
00641 _C_w_in_preorder = false;
00642 (&_C_w_cur_it)->~std::vector();
00643 _C_w_cur_it.reserve(32);
00644 }
00645 else if(_C_w_t.order & _C_W_postorder)
00646 {
00647 _C_w_in_preorder = true;
00648 if(_C_w_t.front_to_back)
00649 {
00650 while(!_C_w_cur->_C_children.empty())
00651 {
00652 _Ctr_iterator help;
00653
00654 help = _C_w_cur->_C_children.begin();
00655 _C_w_cur = (_Node*)*help;
00656 _C_w_cur_it.push_back(help);
00657 }
00658 }
00659 else
00660 {
00661 while(!_C_w_cur->_C_children.empty())
00662 {
00663 _Ctr_iterator help;
00664
00665 help = _C_w_cur->_C_children.end();
00666 --help;
00667 _C_w_cur = (_Node*)*help;
00668 _C_w_cur_it.push_back(help);
00669 }
00670 }
00671 }
00672 }
00673 else
00674 {
00675 ;
00676 }
00677 }
00678
00679 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00680 class _Node>
00681 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_preorder()
00682 {
00683 _Ctr_iterator help;
00684
00685 if(_C_w_cur->_C_children.empty())
00686 {
00687 while(1)
00688 {
00689 if(_C_w_cur_it.empty())
00690 {
00691 if(_C_w_cur->_C_parent == NULL && _C_w_in_preorder)
00692 _C_w_in_preorder = false;
00693 else
00694 _C_w_t.order = 0;
00695 break;
00696 }
00697 help = _C_w_cur_it.back();
00698 _C_w_cur_it.pop_back();
00699 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00700 if(_C_w_t.front_to_back)
00701 {
00702 ++help;
00703 if(help != _C_w_cur->_C_children.end())
00704
00705 {
00706 _C_w_cur_it.push_back(help);
00707 _C_w_cur = (_Node*)*help;
00708 break;
00709 }
00710 }
00711 else
00712 {
00713 if(help != _C_w_cur->_C_children.begin())
00714
00715 {
00716 --help;
00717 _C_w_cur_it.push_back(help);
00718 _C_w_cur = (_Node*)*help;
00719 break;
00720 }
00721 }
00722 }
00723 }
00724 else if(!_C_w_in_preorder)
00725 _C_w_t.order = 0;
00726 else
00727 {
00728 if(_C_w_t.front_to_back)
00729 help = _C_w_cur->_C_children.begin();
00730 else
00731 {
00732 help = _C_w_cur->_C_children.end();
00733 help--;
00734 }
00735 _C_w_cur_it.push_back(help);
00736 _C_w_cur = (_Node*)*help;
00737 }
00738 }
00739
00740 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00741 class _Node>
00742 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_postorder()
00743 {
00744 if(_C_w_in_preorder)
00745 {
00746 _C_w_in_preorder = false;
00747 _find_start_node();
00748 }
00749 else if(_C_w_cur_it.empty())
00750 {
00751 _C_w_t.order = 0;
00752 }
00753 else
00754 {
00755 _Ctr_iterator help = _C_w_cur_it.back();
00756 _C_w_cur_it.pop_back();
00757 if(_C_w_t.front_to_back)
00758 {
00759 ++help;
00760 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00761
00762 {
00763 do
00764 {
00765 _C_w_cur_it.push_back(help);
00766 _C_w_cur = (_Node*)*help;
00767 help = _C_w_cur->_C_children.begin();
00768 } while(!_C_w_cur->_C_children.empty());
00769 }
00770 else
00771 {
00772 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00773 }
00774 }
00775 else
00776 {
00777 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00778
00779 {
00780 do
00781 {
00782 --help;
00783 _C_w_cur_it.push_back(help);
00784 _C_w_cur = (_Node*)*help;
00785 help = _C_w_cur->_C_children.end();
00786 } while(!_C_w_cur->_C_children.empty());
00787 }
00788 else
00789 {
00790 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00791 }
00792 }
00793 }
00794 }
00795
00796 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00797 class _Node>
00798 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_any() {
00799 if(_C_w_in_preorder)
00800 {
00801 if(_C_w_cur->_C_children.empty())
00802 _C_w_in_preorder = false;
00803 else
00804 {
00805 _Ctr_iterator help;
00806 if(_C_w_t.front_to_back)
00807 help = _C_w_cur->_C_children.begin();
00808 else
00809 {
00810 help = _C_w_cur->_C_children.end();
00811 --help;
00812 }
00813 _C_w_cur_it.push_back(help);
00814 _C_w_cur = (_Node*)*help;
00815 }
00816 }
00817 else
00818 {
00819 _Ctr_iterator help;
00820
00821 if(!_C_w_cur_it.empty())
00822 {
00823 help = _C_w_cur_it.back();
00824 _C_w_cur_it.pop_back();
00825 if(_C_w_t.front_to_back)
00826 {
00827 ++help;
00828 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00829
00830 {
00831 _C_w_cur_it.push_back(help);
00832 _C_w_cur = (_Node*)*help;
00833 _C_w_in_preorder = true;
00834 }
00835 else
00836 {
00837 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00838 }
00839 }
00840 else
00841 {
00842 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00843
00844 {
00845 --help;
00846 _C_w_cur_it.push_back(help);
00847 _C_w_cur = (_Node*)*help;
00848 _C_w_in_preorder = true;
00849 }
00850 else
00851 {
00852 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00853 }
00854 }
00855 }
00856 else
00857 {
00858 _C_w_t.order = 0;
00859 }
00860 }
00861 }
00862
00863 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00864 class _Node>
00865 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_preorder()
00866 {
00867 if(!_C_w_in_preorder)
00868 {
00869 _C_w_t.order = _C_W_postorder;
00870 _C_w_t.front_to_back = !_C_w_t.front_to_back;
00871 _find_start_node();
00872 _C_w_in_preorder = true;
00873 _C_w_t.order = _C_W_preorder;
00874 _C_w_t.front_to_back = !_C_w_t.front_to_back;
00875 }
00876 else if(_C_w_cur_it.empty())
00877 {
00878 _C_w_t.order = 0;
00879 }
00880 else
00881 {
00882 _Ctr_iterator help = _C_w_cur_it.back();
00883 _C_w_cur_it.pop_back();
00884 if(!_C_w_t.front_to_back)
00885 {
00886 ++help;
00887 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00888
00889 {
00890 do
00891 {
00892 _C_w_cur_it.push_back(help);
00893 _C_w_cur = (_Node*)*help;
00894 help = _C_w_cur->_C_children.begin();
00895 } while(!_C_w_cur->_C_children.empty());
00896 }
00897 else
00898 {
00899 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00900 }
00901 }
00902 else
00903 {
00904 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00905
00906 {
00907 do
00908 {
00909 --help;
00910 _C_w_cur_it.push_back(help);
00911 _C_w_cur = (_Node*)*help;
00912 help = _C_w_cur->_C_children.end();
00913 } while(!_C_w_cur->_C_children.empty());
00914 }
00915 else
00916 {
00917 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00918 }
00919 }
00920 }
00921 }
00922
00923 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00924 class _Node>
00925 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_postorder()
00926 {
00927 _Ctr_iterator help;
00928
00929 if(_C_w_cur->_C_children.empty())
00930 {
00931 while(1)
00932 {
00933 if(_C_w_cur_it.empty())
00934 {
00935 if(_C_w_cur->_C_parent == NULL && !_C_w_in_preorder)
00936 _C_w_in_preorder = true;
00937 else
00938 _C_w_t.order = 0;
00939 break;
00940 }
00941 help = _C_w_cur_it.back();
00942 _C_w_cur_it.pop_back();
00943 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00944 if(!_C_w_t.front_to_back)
00945 {
00946 ++help;
00947 if(help != _C_w_cur->_C_children.end())
00948
00949 {
00950 _C_w_cur_it.push_back(help);
00951 _C_w_cur = (_Node*)*help;
00952 break;
00953 }
00954 }
00955 else
00956 {
00957 if(help != _C_w_cur->_C_children.begin())
00958
00959 {
00960 --help;
00961 _C_w_cur_it.push_back(help);
00962 _C_w_cur = (_Node*)*help;
00963 break;
00964 }
00965 }
00966 }
00967 }
00968 else if(_C_w_in_preorder)
00969 _C_w_t.order = 0;
00970 else
00971 {
00972 if(!_C_w_t.front_to_back)
00973 help = _C_w_cur->_C_children.begin();
00974 else
00975 {
00976 help = _C_w_cur->_C_children.end();
00977 help--;
00978 }
00979 _C_w_cur_it.push_back(help);
00980 _C_w_cur = (_Node*)*help;
00981 }
00982 }
00983
00984 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00985 class _Node>
00986 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_any()
00987 {
00988 if(!_C_w_in_preorder)
00989 {
00990 if(_C_w_cur->_C_children.empty())
00991 _C_w_in_preorder = true;
00992 else
00993 {
00994 _Ctr_iterator help;
00995 if(!_C_w_t.front_to_back)
00996 help = _C_w_cur->_C_children.begin();
00997 else
00998 {
00999 help = _C_w_cur->_C_children.end();
01000 --help;
01001 }
01002 _C_w_cur_it.push_back(help);
01003 _C_w_cur = (_Node*)*help;
01004 }
01005 }
01006 else
01007 {
01008 _Ctr_iterator help;
01009
01010 if(!_C_w_cur_it.empty())
01011 {
01012 help = _C_w_cur_it.back();
01013 _C_w_cur_it.pop_back();
01014 if(!_C_w_t.front_to_back)
01015 {
01016 ++help;
01017 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
01018
01019 {
01020 _C_w_cur_it.push_back(help);
01021 _C_w_cur = (_Node*)*help;
01022 _C_w_in_preorder = false;
01023 }
01024 else
01025 {
01026 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
01027 }
01028 }
01029 else
01030 {
01031 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
01032
01033 {
01034 --help;
01035 _C_w_cur_it.push_back(help);
01036 _C_w_cur = (_Node*)*help;
01037 _C_w_in_preorder = false;
01038 }
01039 else
01040 {
01041 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
01042 }
01043 }
01044 }
01045 else
01046 {
01047 _C_w_t.order = 0;
01048 }
01049 }
01050 }
01051
01053
01058 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01059 class _Node>
01060 class _RTree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
01061 {
01062 public:
01063 typedef _RTree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node> walker;
01064 typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_walker;
01065 typedef _RTree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Self;
01066
01067 public:
01069 _RTree_walker() {}
01070
01072 _RTree_walker(_Node* __x) { _C_w_cur = __x; }
01073
01075 _RTree_walker(const walker& __x) { _C_w_cur = __x._C_w_cur; }
01076
01077 public:
01079
01080 bool operator==(const _Self& __x) const
01081 { return _C_w_cur == __x._C_w_cur; }
01082 bool operator!=(const _Self& __x) const
01083 { return _C_w_cur != __x._C_w_cur; }
01085
01087
01088 _Self operator<<(const parents_iterator& __dummy) {
01089 _Self __tmp = *this;
01090 _Node *help = __tmp._C_w_cur._C_parent;
01091 if(help != NULL)
01092 __tmp._C_w_cur = help;
01093 return __tmp;
01094 }
01095
01097
01098 _Self operator>>(const children_iterator& __i) {
01099 _Self __tmp = *this;
01100 __tmp._C_w_cur = (_Node*) *__i;
01101 return __tmp;
01102 }
01103
01105 _Self& operator<<=(const parents_iterator& __dummy) {
01106 _Node *help = _C_w_cur._C_parent;
01107 if(help != NULL)
01108 _C_w_cur = help;
01109 return *this;
01110 }
01111
01113 _Self& operator>>=(const children_iterator& __i) {
01114 _C_w_cur = (_Node*) *__i;
01115 return *this;
01116 }
01117
01119 _Self& operator=(const _Itr& __x) {
01120 _C_w_cur = __x._C_i_cur;
01121 return *this;
01122 }
01123
01125 _Self& operator=(const _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>& __x)
01126 {
01127 _C_w_cur = __x._C_w_cur;
01128 return *this;
01129 }
01130 };
01131
01133
01138 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01139 class _Node>
01140 class _Tree_iterator
01141 {
01142 public:
01143 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node> iterator;
01144 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_iterator;
01145 typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Self;
01146 typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node> _Walk;
01147
01149
01150 typedef std::bidirectional_iterator_tag iterator_category;
01151 typedef _Tp value_type;
01152 typedef _Ptr pointer;
01153 typedef _Ref reference;
01154 typedef size_t size_type;
01155 typedef ptrdiff_t difference_type;
01157 typedef _Iterator _Ctr_iterator;
01158
01159 protected:
01161 _Node* _C_i_cur;
01163 std::vector<_Ctr_iterator> _C_i_cur_it;
01164
01165 public:
01167 _Tree_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
01169 _Tree_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
01170 _C_i_cur_it(__x._C_i_cur_it) {}
01172 _Tree_iterator(const _Node* __n, bool st = false) : _C_i_cur_it()
01173 { _C_i_cur = __n; if(st) find_start_node(); }
01174
01176
01177 bool operator==(const _Self& __x) const
01178 { return (_C_i_cur->_C_parent == NULL &&
01179 __x._C_i_cur->_C_parent == NULL) ||
01180 ( _C_i_cur == __x._C_i_cur &&
01181 _C_i_cur_it == __x._C_i_cur_it);
01182 }
01183 bool operator!=(const _Self& __x) const
01184 { return (_C_i_cur->_C_parent != NULL ||
01185 __x._C_i_cur->_C_parent != NULL) &&
01186 ( _C_i_cur != __x._C_i_cur ||
01187 _C_i_cur_it != __x._C_i_cur_it);
01188 }
01190
01191 reference operator*() const { return (*_C_i_cur)._C_data; }
01192
01193 #ifndef __SGI_STL_NO_ARROW_OPERATOR
01194
01195 pointer operator->() const { return &(operator*()); }
01196 #endif
01197
01198 ctree_data_hook& data_hook() { return (*_C_i_cur)._C_data_hook; }
01199
01200 private:
01202 void find_start_node();
01204 void find_next_node();
01206 void find_prev_node();
01207
01208 public:
01210 _Self& operator=(const _Walk& __x) {
01211 _C_i_cur = __x._C_w_cur;
01212 _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
01213
01214
01215 find_start_node();
01216 return *this;
01217 }
01218
01220
01221 _Self& operator++() {
01222 find_next_node();
01223 return *this;
01224 }
01225 _Self operator++(int) {
01226 _Self __tmp = *this;
01227 ++*this;
01228 return __tmp;
01229 }
01230
01231 _Self& operator--() {
01232 find_prev_node();
01233 return *this;
01234 }
01235 _Self operator--(int) {
01236 _Self __tmp = *this;
01237 --*this;
01238 return __tmp;
01239 }
01241 };
01242
01243 #ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01244 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01245 inline std::bidirectional_iterator_tag
01246 iterator_category(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01247 {
01248 return std::bidirectional_iterator_tag();
01249 }
01250
01251 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01252 inline _Tp*
01253 value_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01254 {
01255 return 0;
01256 }
01257
01258 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01259 inline ptrdiff_t*
01260 distance_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01261 {
01262 return 0;
01263 }
01264
01265 #endif
01266
01267 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01268 class _Node>
01269 void
01270 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_start_node()
01271 {
01272 _Node* __s = _C_i_cur;
01273 _Ctr_iterator __help;
01274
01275 while(__s->_C_parent != NULL)
01276 {
01277 __help = ((_Node*)__s->_C_parent)->get_childentry_iterator((void*)__s);
01278 _C_i_cur_it.insert(_C_i_cur_it.begin(), __help);
01279 __s = (_Node*)__s->_C_parent;
01280 }
01281 while(!_C_i_cur->_C_children.empty())
01282 {
01283 __help = _C_i_cur->_C_children.begin();
01284 _C_i_cur = (_Node*)*__help;
01285 _C_i_cur_it.push_back(__help);
01286 }
01287 }
01288
01289 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01290 class _Node>
01291 void
01292 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_next_node()
01293 {
01294 if(_C_i_cur->_C_parent != NULL)
01295 {
01296 _Ctr_iterator __help = _C_i_cur_it.back();
01297 _C_i_cur_it.pop_back();
01298 ++__help;
01299 if(__help != ((_Node*)_C_i_cur->_C_parent)->_C_children.end())
01300 {
01301 do
01302 {
01303 _C_i_cur_it.push_back(__help);
01304 _C_i_cur = (_Node*)*__help;
01305 __help = _C_i_cur->_C_children.begin();
01306 } while(!_C_i_cur->_C_children.empty());
01307 }
01308 else
01309 {
01310 _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01311 }
01312 }
01313 }
01314
01315 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01316 class _Node>
01317 void
01318 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_prev_node()
01319 {
01320 _Ctr_iterator help;
01321
01322 if(_C_i_cur->_C_children.empty())
01323 {
01324 while(1)
01325 {
01326 if(_C_i_cur->_C_parent == NULL)
01327 break;
01328 help = _C_i_cur_it.back();
01329 _C_i_cur_it.pop_back();
01330 _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01331 if(help != _C_i_cur->_C_children.begin())
01332 {
01333 --help;
01334 _C_i_cur_it.push_back(help);
01335 _C_i_cur = (_Node*)*help;
01336 break;
01337 }
01338 }
01339 }
01340 else
01341 {
01342 help = _C_i_cur->_C_children.end();
01343 --help;
01344 _C_i_cur_it.push_back(help);
01345 _C_i_cur = (_Node*)*help;
01346 }
01347 }
01348
01349 #ifdef __VGTL_USE_STD_ALLOCATORS
01350
01352
01362 template <class _Tp, class _Ctr, class _I, class _Node, class _Allocator,
01363 bool _IsStatic>
01364 class _Tree_alloc_base {
01365 public:
01366 typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
01367 allocator_type;
01368 allocator_type get_allocator() const { return _Node_allocator; }
01369
01370 _Tree_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
01371
01372 protected:
01374 _Node* _C_get_node()
01375 { return _Node_allocator.allocate(1); }
01377 void _C_put_node(_Node* __p)
01378 { _Node_allocator.deallocate(__p, 1); }
01379
01380 protected:
01381 typename std::_Alloc_traits<_Node, _Allocator>::allocator_type
01382 _Node_allocator;
01383
01384 protected:
01386 _Node* _C_node;
01387 };
01388
01390
01400 template <class _Tp, class _Ctr, class _I, class _Node, class _Allocator>
01401 class _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Allocator, true> {
01402 public:
01403 typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
01404 allocator_type;
01405 allocator_type get_allocator() const { return allocator_type(); }
01406
01407 _Tree_alloc_base(const allocator_type&) {}
01408
01409 protected:
01410 typedef typename std::_Alloc_traits<_Node, _Allocator>::_Alloc_type
01411 _Alloc_type;
01413 _Node* _C_get_node()
01414 { return _Alloc_type::allocate(1); }
01416 void _C_put_node(_Node* __p)
01417 { _Alloc_type::deallocate(__p, 1); }
01418
01419 protected:
01421 _Node* _C_node;
01422 };
01423
01425
01429 template <class _Tp, class _Ctr, class _I, class _Node, class _Alloc>
01430 class _Tree_base
01431 : public _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Alloc,
01432 std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01433 {
01434 public:
01435 typedef _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Alloc,
01436 std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01437 _Base;
01439 typedef typename _Base::allocator_type allocator_type;
01440
01442 typedef _Ctr container_type;
01444 typedef _I children_iterator;
01446 typedef __one_iterator<void *> parents_iterator;
01447
01449 _Tree_base(const allocator_type& __a) : _Base(__a) {
01450 _C_node = _C_get_node();
01451 __VGTL_TRY {
01452 _C_node->initialize();
01453 }
01454 __VGTL_UNWIND(_C_put_node(_C_node));
01455 }
01457 virtual ~_Tree_base() {
01458 clear();
01459 _C_put_node(_C_node);
01460 }
01461
01463 void clear();
01465 void clear_children()
01466 { _C_node->clear_children(); }
01467
01470 template <class _Output_Iterator>
01471 void add_all_children(_Output_Iterator fi, _Node* _parent);
01472 };
01473 #else
01474
01476
01480 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01481 class _Tree_base
01482 {
01483 public:
01485 typedef _Alloc allocator_type;
01487 allocator_type get_allocator() const { return allocator_type(); }
01488
01490 typedef _Ctr container_type;
01492 typedef _Iterator children_iterator;
01494 typedef __one_iterator<void *> parents_iterator;
01495
01497 _Tree_base(const allocator_type&) {
01498 _C_node = _C_get_node();
01499 _C_node->initialize();
01500 }
01502 virtual ~_Tree_base() {
01503 clear();
01504 _C_put_node(_C_node);
01505 }
01506
01508 void clear();
01509
01510 protected:
01511 typedef simple_alloc<Node, _Alloc> _Alloc_type;
01513 _Node* _C_get_node()
01514 { return _Alloc_type::allocate(1); }
01516 void _C_put_node(_Node* __p)
01517 { _Alloc_type::deallocate(__p, 1); }
01518
01519 protected:
01521 _Node* _C_node;
01522
01524 void clear_children()
01525 { _C_node->clear_children(); }
01526
01529 template <class _Output_Iterator>
01530 void add_all_children(_Output_Iterator fi, _Node* _parent);
01531 };
01532
01533 #endif
01534
01535 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01536 template <class _Output_Iterator>
01537 inline void
01538 _Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::add_all_children(
01539 _Output_Iterator fi, _Node* _parent)
01540 { _C_node->add_all_children(fi, _parent); };
01541
01542 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01543 void
01544 _Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::clear()
01545 {
01546 this->_C_node->clear_tree();
01547 this->_C_node->clear_children();
01548 }
01549
01551
01556 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Node,
01557 class _Alloc>
01558 class __Tree_t : public _Tree_base<_Tp, _Ctr, _Iterator, _Node, _Alloc>
01559 {
01560 public:
01561 typedef _Ctr container_type;
01562 typedef _Iterator children_iterator;
01563 typedef __one_iterator<void *> parents_iterator;
01564 typedef _Inserter container_insert_arg;
01565
01566 protected:
01567 typedef void* _Void_pointer;
01568 typedef _Tree_base<_Tp, container_type, children_iterator, _Node, _Alloc> _Base;
01569 typedef __Tree_t<_Tp,_Ctr,_Iterator,_Inserter,_Node,_Alloc> _Self;
01570
01571 public:
01573
01574 typedef _Tp value_type;
01575 typedef _Node node_type;
01576 typedef value_type* pointer;
01577 typedef const value_type* const_pointer;
01578 typedef value_type& reference;
01579 typedef const value_type& const_reference;
01580 typedef size_t size_type;
01581 typedef ptrdiff_t difference_type;
01583
01584 typedef typename _Base::allocator_type allocator_type;
01586 allocator_type get_allocator() const { return _Base::get_allocator(); }
01587
01588 public:
01590 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
01592 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
01593
01594 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01595
01596 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01598 typedef std::reverse_iterator<iterator> reverse_iterator;
01599 #else
01600
01601 typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
01602 const_reference,difference_type>
01603 const_reverse_iterator;
01605 typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
01606 difference_type>
01607 reverse_iterator;
01608 #endif
01609
01611 typedef _RTree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> walker;
01613 typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_walker;
01614
01615 protected:
01616 typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
01617 typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;
01618
01619 protected:
01620 #ifdef __VGTL_HAS_NAMESPACES
01621 using _Base::_C_node;
01622 using _Base::_C_put_node;
01623 using _Base::_C_get_node;
01624 #endif
01625
01626 protected:
01628 _Node* _C_create_node(const _Tp& __x)
01629 {
01630 _Node* __p = _C_get_node();
01631 __VGTL_TRY {
01632 __p->initialize();
01633 std::_Construct(&__p->_C_data, __x);
01634 }
01635 __VGTL_UNWIND(_C_put_node(__p));
01636 return __p;
01637 }
01638
01640 _Node* _C_create_node()
01641 {
01642 _Node* __p = _C_get_node();
01643 __VGTL_TRY {
01644 __p->initialize();
01645 std::_Construct(&__p->_C_data);
01646 }
01647 __VGTL_UNWIND(_C_put_node(__p));
01648 return __p;
01649 }
01650
01651 public:
01653 explicit __Tree_t(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01654
01656 bool empty() const { return _C_node->_C_children.empty(); }
01657
01659 size_type max_size() const { return size_type(-1); }
01660
01662 void swap(_Self& __x)
01663 { __STD::swap(_C_node, __x._C_node); }
01664
01667 void insert_child(const __walker_base& __position, const _Tp& __x,
01668 const container_insert_arg& __It)
01669 { _Node* __tmp = _C_create_node(__x);
01670 __position._C_w_cur->_C_children.insert(__It,__tmp);
01671 __tmp->_C_parent = __position._C_w_cur;
01672 }
01675 void insert_child(const __walker_base& __position,
01676 const container_insert_arg& __It)
01677 { insert_child(__position, _Tp(), __It); }
01678
01681 void insert_children(const __walker_base& __position, size_type __n,
01682 const _Tp& __x, const children_iterator& __It)
01683 { _Node* __tmp;
01684 std::vector<_Node *> __Ctr;
01685 __Ctr.reserve(__n);
01686
01687 for(int i=n; i>0; i--)
01688 {
01689 __tmp = _C_create_node(__x);
01690 __Ctr.insert(__Ctr.end(), __tmp);
01691 __tmp->_C_parent = __position._C_w_cur;
01692 }
01693 __position._C_w_cur->_C_children.insert(__It,
01694 __Ctr.begin(), __Ctr.end());
01695 }
01696
01701 void insert_subtree(const __walker_base& __position,
01702 _Self& __subtree, const children_iterator& __It)
01703 {
01704 __subtree.add_all_children(inserter(__position._C_w_cur->_C_children,
01705 __It), __position._C_w_cur);
01706 __subtree.clear_children();
01707 }
01708
01712 void erase(const __walker_base& __position)
01713 { _Node* __tmp = __position._C_w_cur;
01714 _Node* __parent = (_Node*)__tmp->_C_parent;
01715
01716 if(__parent != NULL)
01717 {
01718 children_iterator __ip = __parent->get_childentry_iterator(__tmp);
01719
01720 if(!__tmp->_C_children.empty())
01721 {
01722 children_iterator __it = __tmp->_C_children.end();
01723
01724 *__ip = *--__it;
01725 ((_Node*)*__it)->_C_parent = __parent;
01726 __tmp->_C_children.erase(__it);
01727 if(!__tmp->_C_children.empty())
01728 {
01729 __tmp->add_all_children(inserter(__parent->_C_children, __ip),
01730 __parent);
01731 __tmp->clear_children();
01732 }
01733 }
01734 _C_put_node(__tmp);
01735 }
01736 }
01737
01742 _Node* erase_tree(const __walker_base& __position)
01743 { _Node* __tmp = __position._C_w_cur;
01744 _Node* __parent = (_Node*)__tmp->_C_parent;
01745
01746 if(__parent == NULL)
01747 {
01748 this->_C_node = _C_create_node();
01749 return __tmp;
01750 }
01751 else
01752 {
01753 children_iterator __ip = __parent->get_childentry_iterator(__tmp);
01754
01755 __parent->_C_children.erase(__ip);
01756 __parent = _C_create_node();
01757 __parent->_C_data = 0;
01758 __parent->_C_children.insert(__parent->_C_children.end(), __tmp);
01759 __tmp->_C_parent = __parent;
01760 return __parent;
01761 }
01762 }
01763
01764
01769 bool erase_child(const __walker_base& __position,
01770 const children_iterator& __It)
01771 {
01772 _Node* __chld = (_Node*)*__It;
01773
01774 if(!__chld->_C_children.empty())
01775 { return false; }
01776 else
01777 {
01778 __position->_C_w_cur->_C_children.erase(__It);
01779 _C_put_node(__chld);
01780 return true;
01781 }
01782 }
01783
01789 _Node* erase_subtree(const __walker_base& __position,
01790 const children_iterator& __It)
01791 { _Node* __chld = (_Node*)*__It;
01792 _Node* __tmp = _C_create_node();
01793
01794 __position->_C_w_cur->_C_children.erase(__It);
01795 __chld->_C_parent = __tmp;
01796 __tmp->_C_data = 0;
01797 __tmp->_C_children.insert(__tmp->_C_children.end(), __chld);
01798 return __tmp;
01799 }
01800
01804 size_type depth(const walker& __position)
01805 { size_type __d=0;
01806 _Node* __x = __position._C_w_cur;
01807 while(__x != NULL)
01808 {
01809 __x = (_Node*)__x._C_parent;
01810 __d++;
01811 }
01812 return __d;
01813 }
01814
01816 void clear() { _Base::clear(); }
01817
01822 __Tree_t(size_type __n, const _Tp& __value,
01823 const allocator_type& __a = allocator_type()) : _Base(__a)
01824 { insert(root(), __n, __value); }
01829 explicit __Tree_t(size_type __n) : _Base(allocator_type())
01830 { insert(root(), __n, _Tp()); }
01831
01832 private:
01834 _Node* copy_subtree(_Node* __x, _Node* __parent)
01835 { children_iterator cit;
01836
01837 _Node* __h = _C_create_node();
01838 std::_Construct(&__h->_C_data, __x->_C_data);
01839 __h->_C_parent = (void*)__parent;
01840 for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
01841 __h->_C_children.insert(__h->_C_children.end(),
01842 copy_subtree((_Node*)*cit, __h));
01843 return __h;
01844 }
01845
01846 public:
01848 __Tree_t(const _Self& __x) : _Base(__x.get_allocator())
01849 { children_iterator cit;
01850 for(cit = __x._C_node->_C_children.begin();
01851 cit != __x._C_node->_C_children.end(); ++cit)
01852 this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
01853 copy_subtree((_Node*)*cit, this->_C_node));
01854 }
01855
01857 virtual ~__Tree_t() {}
01858
01860 _Self& operator=(const _Self& __x);
01861
01866 _Self& operator=(_Node* __x)
01867 {
01868 this->_C_node = __x;
01869 return *this;
01870 }
01871
01872 #if 0
01873 friend bool operator== __VGTL_NULL_TMPL_ARGS (
01874 const __Tree_t& __x, const __Tree_t& __y);
01875 #endif
01876 };
01877
01879
01883 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01884 class __Tree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
01885 _Tree_node<_Tp,_Ctr,_Iterator>, _Alloc>
01886 {
01887 protected:
01888 typedef void* _Void_pointer;
01889 typedef _Tree_node<_Tp, container_type, children_iterator> _Node;
01890 typedef __Tree_t<_Tp, container_type, children_iterator, _Inserter, _Node, _Alloc> _Base;
01891 typedef __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
01892
01893 public:
01894 typedef _Node node_type;
01895
01896 public:
01898 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
01900 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
01901
01902 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01903
01904 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01906 typedef std::reverse_iterator<iterator> reverse_iterator;
01907 #else
01908
01909 typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
01910 const_reference,difference_type>
01911 const_reverse_iterator;
01913 typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
01914 difference_type>
01915 reverse_iterator;
01916 #endif
01917
01918 protected:
01919 typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
01920 typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;
01921
01922 protected:
01923 #ifdef __VGTL_HAS_NAMESPACES
01924 using _Base::_C_node;
01925 using _Base::_C_put_node;
01926 using _Base::_C_get_node;
01927 #endif
01928
01929 public:
01931 explicit __Tree(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01932
01933
01934
01935
01936
01938 walker ground()
01939 { walker __help(_C_node); return __help; }
01940
01942 const_walker ground() const
01943 { const_walker __help(_C_node); return __help; }
01944
01946 walker root(children_iterator __it)
01947 { walker __help = root();
01948 __help >>= __it;
01949 return __help; }
01951 const_walker root(children_iterator __it) const
01952 { const_walker __help = root();
01953 __help >>= __it;
01954 return __help; }
01956 walker root()
01957 { return root(_C_node->child_begin()); }
01959 const_walker root() const
01960 { return root(_C_node->child_begin()); }
01961
01963 iterator begin()
01964 { iterator __help(_C_node, true);
01965 return __help; }
01967 iterator end()
01968 { iterator __help(_C_node);
01969 return __help; }
01970
01972 const_iterator begin() const
01973 { const_iterator __help(_C_node, true);
01974 return __help; }
01976 const_iterator end() const
01977 { const_iterator __help(_C_node);
01978 return __help; }
01979
01981 reverse_iterator rbegin()
01982 { return reverse_iterator(end()); }
01984 reverse_iterator rend()
01985 { return reverse_iterator(begin()); }
01986
01988 const_reverse_iterator rbegin() const
01989 { return const_reverse_iterator(end()); }
01991 const_reverse_iterator rend() const
01992 { return const_reverse_iterator(begin()); }
01993
01995 reference getroot() { return *ground(); }
01997 const_reference getroot() const { return *ground(); }
01998
02003 __Tree(size_type __n, const _Tp& __value,
02004 const allocator_type& __a = allocator_type()) : _Base(__a)
02005 { insert(ground(), __n, __value); }
02010 explicit __Tree(size_type __n) : _Base(allocator_type())
02011 { insert(ground(), __n, _Tp()); }
02012
02013 public:
02015 __Tree(const _Self& __x) : _Base(__x) {}
02016
02018 virtual ~__Tree() {}
02019
02021 _Self& operator=(const _Self& __x);
02022
02027 _Self& operator=(_Node* __x)
02028 {
02029 this->_C_node = __x;
02030 return *this;
02031 }
02032
02034 friend bool operator== __VGTL_NULL_TMPL_ARGS (
02035 const __Tree& __x, const __Tree& __y);
02036 };
02037
02039
02043 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02044 class __ITree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
02045 _ITree_node<_Tp,_Ctr,_Iterator>, _Alloc>
02046 {
02047 protected:
02048 typedef void* _Void_pointer;
02049 typedef _ITree_node<_Tp, container_type, children_iterator> _Node;
02050 typedef __Tree_t<_Tp,container_type,children_iterator,_Inserter,_Node,_Alloc> _Base;
02051 typedef __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
02052
02053 public:
02054 typedef _Node node_type;
02055
02057 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
02059 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
02060
02062 typedef _Tree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,_Node> iterative_walker;
02064 typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,_Node> const_iterative_walker;
02065
02066 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
02067
02068 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
02070 typedef std::reverse_iterator<iterator> reverse_iterator;
02071 #else
02072
02073 typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
02074 const_reference,difference_type>
02075 const_reverse_iterator;
02077 typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
02078 difference_type>
02079 reverse_iterator;
02080 #endif
02081
02082 protected:
02083 #ifdef __VGTL_HAS_NAMESPACES
02084 using _Base::_C_node;
02085 using _Base::_C_put_node;
02086 using _Base::_C_get_node;
02087 #endif
02088
02089 public:
02091 explicit __ITree(const allocator_type& __a = allocator_type()) : _Base(__a) {}
02092
02093
02094
02095
02096
02098 iterative_walker root(walker_type wt = cw_pre_post,
02099 bool front_to_back = true,
02100 bool depth_first = true)
02101 { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
02102 return __help; }
02103
02105 const_iterative_walker root(walker_type wt = cw_pre_post,
02106 bool front_to_back = true,
02107 bool depth_first = true) const
02108 { const_iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
02109 return __help; }
02110
02112 iterative_walker through()
02113 { iterative_walker __help(_C_node, 0, 0, 0);
02114 return __help; }
02116 const_iterative_walker through() const
02117 { const_iterative_walker __help(_C_node, 0, 0, 0);
02118 return __help; }
02119
02121 iterative_walker begin(walker_type wt = cw_pre_post,
02122 bool front_to_back = true,
02123 bool depth_first = true)
02124 { iterative_walker __help = root(wt, front_to_back, depth_first);
02125 ++__help;
02126 return __help; }
02128 const_iterative_walker begin(walker_type wt = cw_pre_post,
02129 bool front_to_back = true,
02130 bool depth_first = true) const
02131 { const_iterative_walker __help = root(wt, front_to_back, depth_first);
02132 ++__help;
02133 return __help; }
02134
02136 iterative_walker end(walker_type wt = cw_pre_post,
02137 bool front_to_back = true,
02138 bool depth_first = true)
02139 { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first, false);
02140 return __help; }
02142 const_iterative_walker end(walker_type wt = cw_pre_post,
02143 bool front_to_back = true,
02144 bool depth_first = true) const
02145 { const_iterative_walker __help(_C_node, (int)wt, front_to_back,
02146 depth_first, false);
02147 return __help; }
02148
02150 reverse_iterator rbegin()
02151 { return reverse_iterator(end()); }
02153 reverse_iterator rend()
02154 { return reverse_iterator(begin()); }
02155
02157 const_reverse_iterator rbegin() const
02158 { return const_reverse_iterator(end()); }
02160 const_reverse_iterator rend() const
02161 { return const_reverse_iterator(begin()); }
02162
02164 size_type size() const {
02165 size_type __result = 0;
02166 distance(begin(cw_pre), end(cw_pre), __result);
02167 return __result;
02168 }
02169
02171 reference getroot() { return *root(cw_pre,true,true); }
02173 const_reference getroot() const { return *root(cw_pre,true,true); }
02174
02176 size_type depth(const iterative_walker& __position)
02177 { return __position._C_w_cur_it.size(); }
02178
02183 __ITree(size_type __n, const _Tp& __value,
02184 const allocator_type& __a = allocator_type()) : _Base(__a)
02185 { insert(root(), __n, __value); }
02190 explicit __ITree(size_type __n) : _Base(allocator_type())
02191 { insert(root(), __n, _Tp()); }
02192
02193 public:
02195 __ITree(const _Self& __x) : _Base(__x) {}
02196
02198 virtual ~__ITree() {}
02199
02201 _Self& operator=(const _Self& __x);
02202
02207 _Self& operator=(_Node* __x)
02208 {
02209 this->_C_node = __x;
02210 return *this;
02211 }
02212
02214 friend bool operator== __VGTL_NULL_TMPL_ARGS (
02215 const __ITree& __x, const __ITree& __y);
02216 };
02217
02218
02219 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02220 inline bool operator==(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02221 const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02222 {
02223 typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_walker const_walker;
02224 typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::children_iterator children_iterator;
02225 const_walker __w1 = __x.ground();
02226 const_walker __w2 = __y.ground();
02227 children_iterator __it1, __it2;
02228
02229 if(__w1->n_children() != __w2->n_children())
02230 return false;
02231 for(__it1 = __w1->child_begin(), __it2 = __w2->child_begin();
02232 __it1 != __w1->child_end(); ++__it1, ++__it2)
02233 {
02234 if(!compare_trees(__w1 >> __it1, __w2 >> __it2))
02235 return false;
02236 }
02237 return true;
02238 }
02239
02240 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02241 inline bool operator==(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02242 const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02243 {
02244 typedef typename __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_iterative_walker const_walker;
02245 const_walker __w1 = __x.begin(cw_pre);
02246 const_walker __w2 = __y.begin(cw_pre);
02247 const_walker __e1 = __x.end(cw_pre);
02248 const_walker __e2 = __y.end(cw_pre);
02249
02250
02251 for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
02252 if(__w1.in_preorder() != __w2.in_preorder() ||
02253 (__w1.in_preorder() && *__w1 != *__w2))
02254 return false;
02255 return __w1 == __e1 && __w2 == __e2;
02256 }
02257
02258 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02259 inline bool operator<(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02260 const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02261 {
02262 return lexicographical_compare(__x.begin(), __x.end(),
02263 __y.begin(), __y.end());
02264 }
02265
02266 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02267 inline bool operator<(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02268 const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02269 {
02270 return lexicographical_compare(__x.begin(cw_pre), __x.end(cw_pre),
02271 __y.begin(cw_pre), __y.end(cw_pre));
02272 }
02273
02274 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02275 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
02276 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
02277 {
02278 children_iterator cit;
02279
02280 if (this != &__x) {
02281 this->_C_node->clear_tree();
02282 this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
02283 this->_C_node->_C_children.end());
02284 for(cit = __x._C_node->_C_children.begin();
02285 cit != __x._C_node->_C_children.end(); ++cit)
02286 this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
02287 copy_subtree((_Node*)*cit, this->_C_node));
02288 }
02289 return *this;
02290 }
02291
02292 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02293 __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
02294 __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
02295 {
02296 children_iterator cit;
02297
02298 if (this != &__x) {
02299 this->_C_node->clear_tree();
02300 this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
02301 this->_C_node->_C_children.end());
02302 for(cit = __x._C_node->_C_children.begin();
02303 cit != __x._C_node->_C_children.end(); ++cit)
02304 this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
02305 copy_subtree((_Node*)*cit, this->_C_node));
02306 }
02307 return *this;
02308 }
02309
02311
02317 template <class _Tp,
02318 template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
02319 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02320 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02321 class ntree : public __ITree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
02322 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02323 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02324 _Alloc>
02325 {
02326 private:
02327 typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
02328 protected:
02329 typedef ntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
02330
02331 public:
02335 void insert(const __walker_base& __position, const _Tp& __x)
02336 { _Node* __tmp = _C_create_node(__x);
02337 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02338 children_iterator __it;
02339
02340 if(__parent == NULL)
02341 {
02342 __position._C_w_cur->add_all_children(
02343 back_inserter(__tmp->_C_children), __tmp);
02344 __tmp->_C_parent = __position._C_w_cur;
02345 __position._C_w_cur->clear_children();
02346 __position._C_w_cur->_C_children.insert(
02347 __position._C_w_cur->_C_children.end(), __tmp);
02348 }
02349 else
02350 {
02351 __it = __parent->get_childentry_iterator(__position._C_w_cur);
02352 *__it = __tmp;
02353 __tmp->clear_children();
02354 __tmp->_C_children.insert(__tmp->_C_children.end(),
02355 __position._C_w_cur);
02356 __position._C_w_cur->_C_parent = __tmp;
02357 __tmp->_C_parent = __parent;
02358 }
02359 }
02363 void insert(const __walker_base& __position)
02364 { insert(__position, _Tp()); }
02365
02368 void push_child(const __walker_base& __position, const _Tp& __x)
02369 { insert_child(__position, __x,
02370 __position._C_w_cur->_C_children.end()); }
02373 void push_child(const __walker_base& __position)
02374 { push_child(__position, _Tp()); }
02375
02378 void push_children(const __walker_base& __position, size_type __n,
02379 const _Tp& __x)
02380 { insert_children(__position, __n, __x,
02381 __position._C_w_cur->_C_children.end()); }
02384 void push_children(const __walker_base& __position, size_type __n)
02385 { push_children(__position, n, _Tp()); }
02386
02389 void unshift_child(const __walker_base& __position, const _Tp& __x)
02390 { insert_child(__position, __x,
02391 __position._C_w_cur->_C_children.begin()); }
02394 void unshift_child(const __walker_base& __position)
02395 { unshift_child(__position, _Tp()); }
02396
02399 void unshift_children(const __walker_base& __position, size_type __n,
02400 const _Tp& __x)
02401 { insert_children(__position, __n, __x,
02402 __position._C_w_cur->_C_children.begin()); }
02405 void unshift_children(const __walker_base& __position, size_type __n)
02406 { unshift_children(__position, n, _Tp()); }
02407
02412 void push_subtree(const __walker_base& __position, _Self& __subtree)
02413 {
02414 __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02415 __subtree.clear_children();
02416 }
02417
02422 void unshift_subtree(const __walker_base& __position, _Self& __subtree)
02423 {
02424 __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02425 __subtree.clear_children();
02426 }
02427
02432 bool pop_child(const __walker_base& __position)
02433 { if(__position._C_w_cur->_C_children.empty())
02434 { return false; }
02435 else
02436 {
02437 children_iterator __it = __position._C_w_cur->_C_children.end();
02438 return erase_child(__position, --__it);
02439 }
02440 }
02441
02446 bool shift_child(const __walker_base& __position)
02447 { if(__position._C_w_cur->_C_children.empty())
02448 { return false; }
02449 else
02450 {
02451 children_iterator __it = __position._C_w_cur->_C_children.begin();
02452 return erase_child(__position, __it);
02453 }
02454 }
02455
02460 _Node* pop_subtree(const __walker_base& __position)
02461 {
02462 if(__position._C_w_cur->_C_children.empty())
02463 { return NULL; }
02464 else
02465 {
02466 children_iterator __it = __position._C_w_cur->_C_children.end();
02467 return erase_subtree(__position, --__it);
02468 }
02469 }
02470
02475 _Node* shift_subtree(const __walker_base& __position)
02476 {
02477 if(__position._C_w_cur->_C_children.empty())
02478 { return NULL; }
02479 else
02480 {
02481 children_iterator __it = __position._C_w_cur->_C_children.begin();
02482 return erase_subtree(__position, __it);
02483 }
02484 }
02485
02490 _Self& operator=(_Node* __x)
02491 {
02492 this->_C_node = __x;
02493 return *this;
02494 }
02495 };
02496
02498
02504 template <class _Tp,
02505 template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
02506 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02507 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02508 class rntree : public __Tree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
02509 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02510 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02511 _Alloc>
02512 {
02513 private:
02514 typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
02515 protected:
02516 typedef rntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
02517
02518 public:
02522 void insert(const __walker_base& __position, const _Tp& __x)
02523 { _Node* __tmp = _C_create_node(__x);
02524 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02525 children_iterator __it;
02526
02527 if(__parent == NULL)
02528 {
02529 __position._C_w_cur->add_all_children(
02530 back_inserter(__tmp->_C_children), __tmp);
02531 __tmp->_C_parent = __position._C_w_cur;
02532 __position._C_w_cur->clear_children();
02533 __position._C_w_cur->_C_children.insert(
02534 __position._C_w_cur->_C_children.end(), __tmp);
02535 }
02536 else
02537 {
02538 __it = __parent->get_childentry_iterator(__position._C_w_cur);
02539 *__it = __tmp;
02540 __tmp->clear_children();
02541 __tmp->_C_children.insert(__tmp->_C_children.end(),
02542 __position._C_w_cur);
02543 __position._C_w_cur->_C_parent = __tmp;
02544 __tmp->_C_parent = __parent;
02545 }
02546 }
02550 void insert(const __walker_base& __position)
02551 { insert(__position, _Tp()); }
02552
02555 void push_child(const __walker_base& __position, const _Tp& __x)
02556 { insert_child(__position, __x,
02557 __position._C_w_cur->_C_children.end()); }
02560 void push_child(const __walker_base& __position)
02561 { push_child(__position, _Tp()); }
02562
02565 void push_children(const __walker_base& __position, size_type __n,
02566 const _Tp& __x)
02567 { insert_children(__position, __n, __x,
02568 __position._C_w_cur->_C_children.end()); }
02571 void push_children(const __walker_base& __position, size_type __n)
02572 { push_children(__position, n, _Tp()); }
02573
02576 void unshift_child(const __walker_base& __position, const _Tp& __x)
02577 { insert_child(__position, __x,
02578 __position._C_w_cur->_C_children.begin()); }
02581 void unshift_child(const __walker_base& __position)
02582 { unshift_child(__position, _Tp()); }
02583
02586 void unshift_children(const __walker_base& __position, size_type __n,
02587 const _Tp& __x)
02588 { insert_children(__position, __n, __x,
02589 __position._C_w_cur->_C_children.begin()); }
02592 void unshift_children(const __walker_base& __position, size_type __n)
02593 { unshift_children(__position, n, _Tp()); }
02594
02599 void push_subtree(const __walker_base& __position, _Self& __subtree)
02600 {
02601 __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02602 __subtree.clear_children();
02603 }
02604
02609 void unshift_subtree(const __walker_base& __position, _Self& __subtree)
02610 {
02611 __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02612 __subtree.clear_children();
02613 }
02614
02619 bool pop_child(const __walker_base& __position)
02620 { if(__position._C_w_cur->_C_children.empty())
02621 { return false; }
02622 else
02623 {
02624 children_iterator __it = __position._C_w_cur->_C_children.end();
02625 return erase_child(__position, --__it);
02626 }
02627 }
02628
02633 bool shift_child(const __walker_base& __position)
02634 { if(__position._C_w_cur->_C_children.empty())
02635 { return false; }
02636 else
02637 {
02638 children_iterator __it = __position._C_w_cur->_C_children.begin();
02639 return erase_child(__position, __it);
02640 }
02641 }
02642
02647 _Node* pop_subtree(const __walker_base& __position)
02648 {
02649 if(__position._C_w_cur->_C_children.empty())
02650 { return NULL; }
02651 else
02652 {
02653 children_iterator __it = __position._C_w_cur->_C_children.end();
02654 return erase_subtree(__position, --__it);
02655 }
02656 }
02657
02662 _Node* shift_subtree(const __walker_base& __position)
02663 {
02664 if(__position._C_w_cur->_C_children.empty())
02665 { return NULL; }
02666 else
02667 {
02668 children_iterator __it = __position._C_w_cur->_C_children.begin();
02669 return erase_subtree(__position, __it);
02670 }
02671 }
02672
02677 _Self& operator=(_Node* __x)
02678 {
02679 this->_C_node = __x;
02680 return *this;
02681 }
02682 };
02683
02684
02686
02693 template <class _Tp,
02694 template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02695 class _Key = string,
02696 class _Compare = less<_Key>,
02697 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02698 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02699 class atree : public __ITree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
02700 pair_adaptor<typename _AssocCtr<_Key, void*,
02701 _Compare, _PtrAlloc>::iterator>,
02702 _Key, _Alloc>
02703 {
02704 protected:
02705 typedef atree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02706
02707 public:
02712 _Self& operator=(_Node* __x)
02713 {
02714 this->_C_node = __x;
02715 return *this;
02716 }
02717
02721 void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
02722 { _Node* __tmp = _C_create_node(__x);
02723 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02724 children_iterator __it;
02725
02726 if(__parent == NULL)
02727 {
02728 __position._C_w_cur->add_all_children(
02729 inserter(__tmp->_C_children.end()), __tmp);
02730 __tmp->_C_parent = __position._C_w_cur;
02731 __position._C_w_cur->clear_children();
02732 __position._C_w_cur->_C_children.insert(__k, __tmp);
02733 }
02734 else
02735 {
02736 __it = __parent->get_childentry_iterator(__position._C_w_cur);
02737 *__it = __tmp;
02738 __tmp->clear_children();
02739 __tmp->_C_children.insert(__k, __position._C_w_cur);
02740 __position._C_w_cur->_C_parent = __tmp;
02741 __tmp->_C_parent = __parent;
02742 }
02743 }
02747 void insert(const __walker_base& __position, const _Key& __k)
02748 { insert(__position, _Tp(), __k); }
02749
02750
02751 };
02752
02754
02761 template <class _Key, class _Compare = less<_Key>,
02762 template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
02763 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02764 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
02765 class stree : public __ITree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02766 _PtrAlloc>,
02767 typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02768 _PtrAlloc>::iterator,
02769 _Key&, _Alloc>
02770 {
02771 protected:
02772 typedef stree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
02773
02774 public:
02779 _Self& operator=(_Node* __x)
02780 {
02781 this->_C_node = __x;
02782 return *this;
02783 }
02784 };
02785
02787
02794 template <class _Tp,
02795 template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02796 class _Key = string,
02797 class _Compare = less<_Key>,
02798 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02799 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02800 class ratree : public __Tree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
02801 pair_adaptor<typename _AssocCtr<_Key, void*,
02802 _Compare, _PtrAlloc>::iterator>,
02803 _Key, _Alloc>
02804 {
02805 protected:
02806 typedef ratree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02807
02808 public:
02813 _Self& operator=(_Node* __x)
02814 {
02815 this->_C_node = __x;
02816 return *this;
02817 }
02818
02822 void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
02823 { _Node* __tmp = _C_create_node(__x);
02824 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02825 children_iterator __it;
02826
02827 if(__parent == NULL)
02828 {
02829 __position._C_w_cur->add_all_children(
02830 inserter(__tmp->_C_children.end()), __tmp);
02831 __tmp->_C_parent = __position._C_w_cur;
02832 __position._C_w_cur->clear_children();
02833 __position._C_w_cur->_C_children.insert(__k, __tmp);
02834 }
02835 else
02836 {
02837 __it = __parent->get_childentry_iterator(__position._C_w_cur);
02838 *__it = __tmp;
02839 __tmp->clear_children();
02840 __tmp->_C_children.insert(__k, __position._C_w_cur);
02841 __position._C_w_cur->_C_parent = __tmp;
02842 __tmp->_C_parent = __parent;
02843 }
02844 }
02848 void insert(const __walker_base& __position, const _Key& __k)
02849 { insert(__position, _Tp(), __k); }
02850
02851
02852 };
02853
02855
02862 template <class _Key, class _Compare = less<_Key>,
02863 template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
02864 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02865 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
02866 class rstree : public __Tree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02867 _PtrAlloc>,
02868 typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02869 _PtrAlloc>::iterator,
02870 _Key&, _Alloc>
02871 {
02872 protected:
02873 typedef rstree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
02874
02875 public:
02880 _Self& operator=(_Node* __x)
02881 {
02882 this->_C_node = __x;
02883 return *this;
02884 }
02885 };
02886
02887 __VGTL_END_NAMESPACE
02888
02889 #endif