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_GRAPH_H_
00031 #define __VGTL_GRAPH_H_
00032
00033 #include <vector.h>
00034 #include <list.h>
00035 #include <multimap.h>
00036 #include <multiset.h>
00037 #include <algo.h>
00038 #include <iterator.h>
00039 #include <string>
00040 #include <g_data.h>
00041
00042 #include <vgtl_helpers.h>
00043
00044 __VGTL_BEGIN_NAMESPACE
00045
00046 #define _C_W_preorder 1
00047 #define _C_W_postorder 2
00048
00049 WARNING: DO NOT USE THIS FILE -> NOT YET FINISHED!!!!!
00050
00051
00052 template <class _Tp, class _Ctr, class _Iterator>
00053 class _Graph_node
00054 {
00055 private:
00056 typedef void* _Void_pointer;
00057 typedef _Iterator _Ctr_iterator;
00058 typedef _Graph_node<_Tp,_Ctr,_Iterator> _Self;
00059
00060 public:
00061 _Tp _C_data;
00062 _Ctr _C_neighbors;
00063
00064 _Graph_node() { _C_data();
00065 __VGTL_TRY {
00066 construct(&_C_neighbors);
00067 }
00068 __VGTL_UNWIND( );
00069 }
00070 void clear_graph();
00071 void clear_neighbors()
00072 { _C_neighbors.erase(_C_neighbors.begin(), _C_neighbors.end()); }
00073
00074 _Ctr_iterator get_entry_iterator(_Void_pointer __p)
00075 { _Ctr_iterator __tmp;
00076 for(__tmp = _C_neighbors.begin(); __tmp != _C_neighbors.end();
00077 ++__tmp)
00078 if(*__tmp == __p) break;
00079 return __tmp;
00080 }
00081
00082 #ifdef __VGTL_MEMBER_TEMPLATES
00083 template <class _Output_Iterator>
00084 void add_all_neighbors(_Output_Iterator fi, _Self* _nb);
00085 #endif
00086 };
00087
00088 #ifdef __VGTL_MEMBER_TEMPLATES
00089 template <class _Tp, class _Ctr, class _Iterator>
00090 template <class _Output_Iterator>
00091 void
00092 _Graph_node<_Tp,_Ctr,_Iterator>::
00093 add_all_neighbors(_Output_Iterator fi, _Self* _nb)
00094 { _Ctr_iterator it;
00095 for(it = _C_neighbors.begin();
00096 it != _C_neighbors.end();
00097 ++it)
00098 {
00099 *fi++ = *it;
00100 ((_Self*)*it)->_C_neighbors.insert(((_Self*)*it)->_C_neighbors.end(),_nb);
00101 }
00102 };
00103 #endif
00104
00105
00106 template <class _Tp, class _Ctr, class _Iterator>
00107 void
00108 _Graph_node<_Tp,_Ctr,_Iterator>::clear_graph()
00109 {
00110
00111 destroy(&this->_C_data);
00112 }
00113
00114
00115 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00116 class _Graph_iterator;
00117
00118 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00119 class _Graph_walker_base
00120 {
00121 public:
00122 typedef _Graph_walker_base<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> walker;
00123 typedef _Graph_walker_base<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
00124 typedef _Graph_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00125 typedef _Graph_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Itr;
00126
00127 typedef _Tp value_type;
00128 typedef _Ptr pointer;
00129 typedef _Ref reference;
00130 private:
00131 typedef _Graph_node<_Tp,_Ctr,_Iterator> _Node;
00132 typedef _Iterator _Ctr_iterator;
00133
00134 public:
00135 typedef _Ctr_iterator container_iterator;
00136 typedef _Node node_type;
00137
00138 typedef size_t size_type;
00139 typedef ptrdiff_t difference_type;
00140
00141 public:
00142 _Node* _C_w_cur;
00143
00144 public:
00145 _Graph_walker_base() {}
00146
00147 public:
00148 _Graph_walker_base(_Node* __x) : _C_w_cur(__x) { }
00149
00150 _Graph_walker_base(const walker& __x) : _C_w_cur(__x._C_w_cur) {}
00151
00152 reference operator*() const { return (*_C_w_cur)._C_data; }
00153
00154 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00155 pointer operator->() const { return &(operator*()); }
00156 #endif
00157
00158 public:
00159 _Self& operator=(_Itr __x) {
00160 _C_w_cur = __x._C_i_cur;
00161 return *this;
00162 }
00163
00164 const _Node* node() { return _C_w_cur; }
00165 size_type n_neighbors() { return _C_w_cur->_C_neighbors.size(); }
00166
00167 _Ctr_iterator neighbor_begin() { return _C_w_cur->_C_neighbors.begin(); }
00168 _Ctr_iterator neighbor_end() { return _C_w_cur->_C_neighbors.end(); }
00169
00170 template <class _Function>
00171 _Function for_each_neighbor(_Function __f)
00172 {
00173 return for_each(neighbor_begin(), neighbor_end(), __f);
00174 }
00175 };
00176
00177
00178 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00179 class _Graph_walker : public _Graph_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator>
00180 {
00181 public:
00182 typedef _Graph_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> walker;
00183 typedef _Graph_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
00184 typedef _Graph_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00185
00186 public:
00187 struct {
00188 unsigned int order:2;
00189 unsigned int front_to_back:1;
00190 unsigned int depth_first:1;
00191 } _C_w_t;
00192 bool _C_w_in_preorder;
00193 vector<_Iterator> _C_w_cur_it;
00194
00195 public:
00196 _Tree_walker() : _C_w_cur_it() {_C_w_cur_it.reserve(32); }
00197
00198 private:
00199 void _find_start_node();
00200 void _find_end_node();
00201 void _find_next_preorder();
00202 void _find_next_postorder();
00203 void _find_next_any();
00204 void _find_prev_preorder();
00205 void _find_prev_postorder();
00206 void _find_prev_any();
00207
00208 public:
00209 _Tree_walker(_Node* __x, int order = (_C_W_preorder|_C_W_postorder),
00210 bool front_to_back = true, bool depth_first = true,
00211 bool find_start = true)
00212 : _C_w_cur_it() {
00213 _C_w_cur = __x;
00214 _C_w_cur_it.reserve(32);
00215 _C_w_t.order = order;
00216 _C_w_t.front_to_back = front_to_back;
00217 _C_w_t.depth_first = depth_first;
00218 if(__x->_C_parent == NULL)
00219 _C_w_in_preorder = find_start;
00220 else if(find_start)
00221 _find_start_node();
00222 else
00223 _find_end_node(); }
00224
00225 _Tree_walker(const walker& __x) : _C_w_in_preorder(__x._C_w_in_preorder),
00226 _C_w_cur_it(__x._C_w_cur_it) {
00227 _C_w_cur = __x._C_w_cur;
00228 _C_w_t = __x._C_w_t;
00229 }
00230
00231 bool operator==(const _Self& __x) const
00232 { return (_C_w_t.order == 0 && __x._C_w_t.order == 0) ||
00233 (_C_w_cur == __x._C_w_cur &&
00234 _C_w_in_preorder == __x._C_w_in_preorder &&
00235 _C_w_t.order == __x._C_w_t.order &&
00236 _C_w_t.front_to_back == __x._C_w_t.front_to_back &&
00237 _C_w_t.depth_first == __x._C_w_t.depth_first &&
00238 _C_w_cur_it == __x._C_w_cur_it); }
00239 bool operator!=(const _Self& __x) const
00240 { return (_C_w_t.order != 0 || __x._C_w_t.order != 0) &&
00241 (_C_w_cur != __x._C_w_cur ||
00242 _C_w_in_preorder != __x._C_w_in_preorder ||
00243 _C_w_t.order != __x._C_w_t.order ||
00244 _C_w_t.front_to_back != __x._C_w_t.front_to_back ||
00245 _C_w_t.depth_first != __x._C_w_t.depth_first ||
00246 _C_w_cur_it != __x._C_w_cur_it); }
00247
00248 public:
00249 _Self& operator++() {
00250 if(_C_w_t.depth_first)
00251 {
00252 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00253 {
00254 _find_next_any();
00255 }
00256 else if(_C_w_t.order & _C_W_preorder)
00257 {
00258 _find_next_preorder();
00259 }
00260 else
00261 {
00262 _find_next_postorder();
00263 }
00264 }
00265 else
00266 {
00267 ;
00268 }
00269 return *this;
00270 }
00271 _Self operator++(int) {
00272 _Self __tmp = *this;
00273 ++*this;
00274 return __tmp;
00275 }
00276
00277 _Self& operator--() {
00278 if(_C_w_t.depth_first)
00279 {
00280 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00281 {
00282 _find_prev_any();
00283 }
00284 else if(_C_w_t.order & _C_W_preorder)
00285 {
00286 _find_prev_preorder();
00287 }
00288 else
00289 {
00290 _find_prev_postorder();
00291 }
00292 }
00293 else
00294 {
00295 ;
00296 }
00297 return *this;
00298 }
00299 _Self operator--(int) {
00300 _Self __tmp = *this;
00301 --*this;
00302 return __tmp;
00303 }
00304
00305 _Self operator<<(bool search_start) {
00306 _Self __tmp = *this;
00307 _Node *help = __tmp._C_w_cur._C_parent;
00308 if(help == NULL)
00309 {
00310 __tmp._C_w_t.order = 0;
00311 }
00312 else
00313 {
00314 __tmp._C_w_cur = help;
00315 if(__tmp._C_w_t.order & _C_W_postorder)
00316 __tmp._C_w_in_preorder = false;
00317 if(!__tmp._C_w_cur_it.empty())
00318 pop_back(__tmp._C_w_cur_it);
00319 if(search_start)
00320 __tmp._find_start_node();
00321 }
00322 return __tmp;
00323 }
00324
00325 _Self operator>>(_Ctr_iterator i) {
00326 _Self __tmp = *this;
00327 _Node *help = (_Node*) *i;
00328 if(__tmp._C_w_t.order & _C_W_preorder)
00329 __tmp._C_w_in_preorder = true;
00330 __tmp._C_w_cur_it.push_back(i);
00331 __tmp._C_w_cur = help;
00332 return __tmp;
00333 }
00334
00335 _Self& operator<<=(bool search_start) {
00336 _Node *help = _C_w_cur._C_parent;
00337 if(help == NULL)
00338 {
00339 _C_w_t.order = 0;
00340 }
00341 else
00342 {
00343 _C_w_cur = help;
00344 if(_C_w_t.order & _C_W_postorder)
00345 _C_w_in_preorder = false;
00346 if(!_C_w_cur_it.empty())
00347 pop_back(_C_w_cur_it);
00348 if(search_start)
00349 _find_start_node();
00350 }
00351 return *this;
00352 }
00353
00354 _Self& operator>>=(_Ctr_iterator i) {
00355 _Node *help = (_Node*) *i;
00356 if(_C_w_t.order & _C_W_preorder)
00357 _C_w_in_preorder = true;
00358 push_back(_C_w_cur_it, i);
00359 _C_w_cur = help;
00360 return *this;
00361 }
00362
00363 _Self& operator~() {
00364 if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00365 _C_w_in_preorder = !_C_w_in_preorder;
00366 return *this;
00367 }
00368
00369 _Self& operator=(_Itr __x) {
00370 _C_w_cur = __x._C_i_cur;
00371 _C_w_cur_it = __x._C_i_cur_it;
00372 _C_w_t.order = _C_W_postorder;
00373 _C_w_t.depth_first = 1;
00374 _C_w_t.front_to_back = 1;
00375 return *this;
00376 }
00377
00378 bool in_preorder() { return _C_w_in_preorder; }
00379 };
00380
00381 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00382 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_start_node()
00383 {
00384 if(_C_w_t.depth_first)
00385 {
00386 if(_C_w_t.order & _C_W_preorder)
00387 {
00388 _C_w_in_preorder = true;
00389 }
00390 else if(_C_w_t.order & _C_W_postorder)
00391 {
00392 _C_w_in_preorder = false;
00393 if(_C_w_t.front_to_back)
00394 {
00395 while(!_C_w_cur->_C_children.empty())
00396 {
00397 _Ctr_iterator help;
00398
00399 help = _C_w_cur->_C_children.begin();
00400 _C_w_cur = (_Node*)*help;
00401 _C_w_cur_it.push_back(help);
00402 }
00403 }
00404 else
00405 {
00406 while(!_C_w_cur->_C_children.empty())
00407 {
00408 _Ctr_iterator help;
00409
00410 help = _C_w_cur->_C_children.end();
00411 --help;
00412 _C_w_cur = (_Node*)*help;
00413 _C_w_cur_it.push_back(help);
00414 }
00415 }
00416 }
00417 }
00418 else
00419 {
00420 ;
00421 }
00422 }
00423
00424 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00425 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_end_node()
00426 {
00427 if(_C_w_t.depth_first)
00428 {
00429 if(_C_w_t.order & _C_W_postorder)
00430 {
00431 _C_w_in_preorder = false;
00432 (&_C_w_cur_it)->~vector();
00433 _C_w_cur_it.reserve(32);
00434 }
00435 else if(_C_w_t.order & _C_W_postorder)
00436 {
00437 _C_w_in_preorder = true;
00438 if(_C_w_t.front_to_back)
00439 {
00440 while(!_C_w_cur->_C_children.empty())
00441 {
00442 _Ctr_iterator help;
00443
00444 help = _C_w_cur->_C_children.begin();
00445 _C_w_cur = (_Node*)*help;
00446 _C_w_cur_it.push_back(help);
00447 }
00448 }
00449 else
00450 {
00451 while(!_C_w_cur->_C_children.empty())
00452 {
00453 _Ctr_iterator help;
00454
00455 help = _C_w_cur->_C_children.end();
00456 --help;
00457 _C_w_cur = (_Node*)*help;
00458 _C_w_cur_it.push_back(help);
00459 }
00460 }
00461 }
00462 }
00463 else
00464 {
00465 ;
00466 }
00467 }
00468
00469 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00470 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_next_preorder()
00471 {
00472 _Ctr_iterator help;
00473
00474 if(_C_w_cur->_C_children.empty())
00475 {
00476 while(1)
00477 {
00478 if(_C_w_cur_it.empty())
00479 {
00480 if(_C_w_cur->_C_parent == NULL && _C_w_in_preorder)
00481 _C_w_in_preorder = false;
00482 else
00483 _C_w_t.order = 0;
00484 break;
00485 }
00486 help = _C_w_cur_it.back();
00487 _C_w_cur_it.pop_back();
00488 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00489 if(_C_w_t.front_to_back)
00490 {
00491 ++help;
00492 if(help != _C_w_cur->_C_children.end())
00493
00494 {
00495 _C_w_cur_it.push_back(help);
00496 _C_w_cur = (_Node*)*help;
00497 break;
00498 }
00499 }
00500 else
00501 {
00502 if(help != _C_w_cur->_C_children.begin())
00503
00504 {
00505 --help;
00506 _C_w_cur_it.push_back(help);
00507 _C_w_cur = (_Node*)*help;
00508 break;
00509 }
00510 }
00511 }
00512 }
00513 else if(!_C_w_in_preorder)
00514 _C_w_t.order = 0;
00515 else
00516 {
00517 if(_C_w_t.front_to_back)
00518 help = _C_w_cur->_C_children.begin();
00519 else
00520 {
00521 help = _C_w_cur->_C_children.end();
00522 help--;
00523 }
00524 _C_w_cur_it.push_back(help);
00525 _C_w_cur = (_Node*)*help;
00526 }
00527 }
00528
00529 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00530 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_next_postorder()
00531 {
00532 if(_C_w_in_preorder)
00533 {
00534 _C_w_in_preorder = false;
00535 _find_start_node();
00536 }
00537 else if(_C_w_cur_it.empty())
00538 {
00539 _C_w_t.order = 0;
00540 }
00541 else
00542 {
00543 _Ctr_iterator help = _C_w_cur_it.back();
00544 _C_w_cur_it.pop_back();
00545 if(_C_w_t.front_to_back)
00546 {
00547 ++help;
00548 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00549
00550 {
00551 do
00552 {
00553 _C_w_cur_it.push_back(help);
00554 _C_w_cur = (_Node*)*help;
00555 help = _C_w_cur->_C_children.begin();
00556 } while(!_C_w_cur->_C_children.empty());
00557 }
00558 else
00559 {
00560 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00561 }
00562 }
00563 else
00564 {
00565 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00566
00567 {
00568 do
00569 {
00570 --help;
00571 _C_w_cur_it.push_back(help);
00572 _C_w_cur = (_Node*)*help;
00573 help = _C_w_cur->_C_children.end();
00574 } while(!_C_w_cur->_C_children.empty());
00575 }
00576 else
00577 {
00578 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00579 }
00580 }
00581 }
00582 }
00583
00584 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00585 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_next_any() {
00586 if(_C_w_in_preorder)
00587 {
00588 if(_C_w_cur->_C_children.empty())
00589 _C_w_in_preorder = false;
00590 else
00591 {
00592 _Ctr_iterator help;
00593 if(_C_w_t.front_to_back)
00594 help = _C_w_cur->_C_children.begin();
00595 else
00596 {
00597 help = _C_w_cur->_C_children.end();
00598 --help;
00599 }
00600 _C_w_cur_it.push_back(help);
00601 _C_w_cur = (_Node*)*help;
00602 }
00603 }
00604 else
00605 {
00606 _Ctr_iterator help;
00607
00608 if(!_C_w_cur_it.empty())
00609 {
00610 help = _C_w_cur_it.back();
00611 _C_w_cur_it.pop_back();
00612 if(_C_w_t.front_to_back)
00613 {
00614 ++help;
00615 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00616
00617 {
00618 _C_w_cur_it.push_back(help);
00619 _C_w_cur = (_Node*)*help;
00620 _C_w_in_preorder = true;
00621 }
00622 else
00623 {
00624 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00625 }
00626 }
00627 else
00628 {
00629 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00630
00631 {
00632 --help;
00633 _C_w_cur_it.push_back(help);
00634 _C_w_cur = (_Node*)*help;
00635 _C_w_in_preorder = true;
00636 }
00637 else
00638 {
00639 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00640 }
00641 }
00642 }
00643 else
00644 {
00645 _C_w_t.order = 0;
00646 }
00647 }
00648 }
00649
00650 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00651 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_prev_preorder()
00652 {
00653 if(!_C_w_in_preorder)
00654 {
00655 _C_w_t.order = _C_W_postorder;
00656 _C_w_t.front_to_back = !_C_w_t.front_to_back;
00657 _find_start_node();
00658 _C_w_in_preorder = true;
00659 _C_w_t.order = _C_W_preorder;
00660 _C_w_t.front_to_back = !_C_w_t.front_to_back;
00661 }
00662 else if(_C_w_cur_it.empty())
00663 {
00664 _C_w_t.order = 0;
00665 }
00666 else
00667 {
00668 _Ctr_iterator help = _C_w_cur_it.back();
00669 _C_w_cur_it.pop_back();
00670 if(!_C_w_t.front_to_back)
00671 {
00672 ++help;
00673 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00674
00675 {
00676 do
00677 {
00678 _C_w_cur_it.push_back(help);
00679 _C_w_cur = (_Node*)*help;
00680 help = _C_w_cur->_C_children.begin();
00681 } while(!_C_w_cur->_C_children.empty());
00682 }
00683 else
00684 {
00685 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00686 }
00687 }
00688 else
00689 {
00690 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00691
00692 {
00693 do
00694 {
00695 --help;
00696 _C_w_cur_it.push_back(help);
00697 _C_w_cur = (_Node*)*help;
00698 help = _C_w_cur->_C_children.end();
00699 } while(!_C_w_cur->_C_children.empty());
00700 }
00701 else
00702 {
00703 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00704 }
00705 }
00706 }
00707 }
00708
00709 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00710 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_prev_postorder()
00711 {
00712 _Ctr_iterator help;
00713
00714 if(_C_w_cur->_C_children.empty())
00715 {
00716 while(1)
00717 {
00718 if(_C_w_cur_it.empty())
00719 {
00720 if(_C_w_cur->_C_parent == NULL && !_C_w_in_preorder)
00721 _C_w_in_preorder = true;
00722 else
00723 _C_w_t.order = 0;
00724 break;
00725 }
00726 help = _C_w_cur_it.back();
00727 _C_w_cur_it.pop_back();
00728 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00729 if(!_C_w_t.front_to_back)
00730 {
00731 ++help;
00732 if(help != _C_w_cur->_C_children.end())
00733
00734 {
00735 _C_w_cur_it.push_back(help);
00736 _C_w_cur = (_Node*)*help;
00737 break;
00738 }
00739 }
00740 else
00741 {
00742 if(help != _C_w_cur->_C_children.begin())
00743
00744 {
00745 --help;
00746 _C_w_cur_it.push_back(help);
00747 _C_w_cur = (_Node*)*help;
00748 break;
00749 }
00750 }
00751 }
00752 }
00753 else if(_C_w_in_preorder)
00754 _C_w_t.order = 0;
00755 else
00756 {
00757 if(!_C_w_t.front_to_back)
00758 help = _C_w_cur->_C_children.begin();
00759 else
00760 {
00761 help = _C_w_cur->_C_children.end();
00762 help--;
00763 }
00764 _C_w_cur_it.push_back(help);
00765 _C_w_cur = (_Node*)*help;
00766 }
00767 }
00768
00769 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00770 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_find_prev_any()
00771 {
00772 if(!_C_w_in_preorder)
00773 {
00774 if(_C_w_cur->_C_children.empty())
00775 _C_w_in_preorder = true;
00776 else
00777 {
00778 _Ctr_iterator help;
00779 if(!_C_w_t.front_to_back)
00780 help = _C_w_cur->_C_children.begin();
00781 else
00782 {
00783 help = _C_w_cur->_C_children.end();
00784 --help;
00785 }
00786 _C_w_cur_it.push_back(help);
00787 _C_w_cur = (_Node*)*help;
00788 }
00789 }
00790 else
00791 {
00792 _Ctr_iterator help;
00793
00794 if(!_C_w_cur_it.empty())
00795 {
00796 help = _C_w_cur_it.back();
00797 _C_w_cur_it.pop_back();
00798 if(!_C_w_t.front_to_back)
00799 {
00800 ++help;
00801 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00802
00803 {
00804 _C_w_cur_it.push_back(help);
00805 _C_w_cur = (_Node*)*help;
00806 _C_w_in_preorder = false;
00807 }
00808 else
00809 {
00810 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00811 }
00812 }
00813 else
00814 {
00815 if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00816
00817 {
00818 --help;
00819 _C_w_cur_it.push_back(help);
00820 _C_w_cur = (_Node*)*help;
00821 _C_w_in_preorder = false;
00822 }
00823 else
00824 {
00825 _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00826 }
00827 }
00828 }
00829 else
00830 {
00831 _C_w_t.order = 0;
00832 }
00833 }
00834 }
00835
00836 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00837 class _RTree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator>
00838 {
00839 public:
00840 typedef _RTree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> walker;
00841 typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
00842 typedef _RTree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00843
00844 public:
00845 _RTree_walker() {}
00846
00847 public:
00848 _RTree_walker(_Node* __x) { _C_w_cur = __x; }
00849
00850 _RTree_walker(const walker& __x) { _C_w_cur = __x._C_w_cur; }
00851
00852 public:
00853 bool operator==(const _Self& __x) const
00854 { return _C_w_cur == __x._C_w_cur; }
00855 bool operator!=(const _Self& __x) const
00856 { return _C_w_cur != __x._C_w_cur; }
00857
00858 _Self operator<<(bool search_start) {
00859 _Self __tmp = *this;
00860 _Node *help = __tmp._C_w_cur._C_parent;
00861 if(help != NULL)
00862 __tmp._C_w_cur = help;
00863 return __tmp;
00864 }
00865
00866 _Self operator>>(_Ctr_iterator i) {
00867 _Self __tmp = *this;
00868 __tmp._C_w_cur = (_Node*) *i;
00869 return __tmp;
00870 }
00871
00872 _Self& operator<<=(bool search_start) {
00873 _Node *help = _C_w_cur._C_parent;
00874 if(help != NULL)
00875 _C_w_cur = help;
00876 return *this;
00877 }
00878
00879 _Self& operator>>=(_Ctr_iterator i) {
00880 _C_w_cur = (_Node*) *i;
00881 return *this;
00882 }
00883
00884 _Self& operator=(_Itr __x) {
00885 _C_w_cur = __x._C_i_cur;
00886 return *this;
00887 }
00888
00889 _Self& operator=(_Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> __x) {
00890 _C_w_cur = __x._C_w_cur;
00891 return *this;
00892 }
00893 };
00894
00895 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00896 class _Tree_iterator
00897 {
00898 public:
00899 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> iterator;
00900 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_iterator;
00901 typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00902 typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Walk;
00903
00904 typedef bidirectional_iterator_tag iterator_category;
00905 typedef _Tp value_type;
00906 typedef _Ptr pointer;
00907 typedef _Ref reference;
00908 typedef _Tree_node<_Tp,_Ctr,_Iterator> _Node;
00909 typedef size_t size_type;
00910 typedef ptrdiff_t difference_type;
00911 typedef _Iterator _Ctr_iterator;
00912
00913 protected:
00914 _Node* _C_i_cur;
00915 vector<_Ctr_iterator> _C_i_cur_it;
00916
00917 public:
00918 _Tree_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
00919 _Tree_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
00920 _C_i_cur_it(__x._C_i_cur_it) {}
00921
00922 bool operator==(const _Self& __x) const
00923 { return (_C_i_cur->_C_parent == NULL &&
00924 __x._C_i_cur->_C_parent == NULL) ||
00925 ( _C_i_cur == __x._C_i_cur &&
00926 _C_i_cur_it == __x._C_i_cur_it);
00927 }
00928 bool operator!=(const _Self& __x) const
00929 { return (_C_i_cur->_C_parent != NULL ||
00930 __x._C_i_cur->_C_parent != NULL) &&
00931 ( _C_i_cur != __x._C_i_cur ||
00932 _C_i_cur_it != __x._C_i_cur_it);
00933 }
00934 reference operator*() const { return (*_C_i_cur)._C_data; }
00935
00936 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00937 pointer operator->() const { return &(operator*()); }
00938 #endif
00939 ctree_data_hook& data_hook() { return (*_C_i_cur)._C_data_hook; }
00940
00941 private:
00942 void find_start_node();
00943 void find_next_node();
00944 void find_prev_node();
00945
00946 public:
00947 _Self& operator=(_Walk __x) {
00948 _C_i_cur = __x._C_w_cur;
00949 _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
00950
00951
00952 find_start_node();
00953 return *this;
00954 }
00955
00956 _Self& operator++() {
00957 find_next_node();
00958 return *this;
00959 }
00960 _Self operator++(int) {
00961 _Self __tmp = *this;
00962 ++*this;
00963 return __tmp;
00964 }
00965
00966 _Self& operator--() {
00967 find_prev_node();
00968 return *this;
00969 }
00970 _Self operator--(int) {
00971 _Self __tmp = *this;
00972 --*this;
00973 return __tmp;
00974 }
00975 };
00976
00977 #ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION
00978 template <class _Tp, class _Ref, class _Ptr, class _Ctr>
00979 inline bidirectional_iterator_tag
00980 iterator_category(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr>&)
00981 {
00982 return bidirectional_iterator_tag();
00983 }
00984
00985 template <class _Tp, class _Ref, class _Ptr, class _Ctr>
00986 inline _Tp*
00987 value_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr>&)
00988 {
00989 return 0;
00990 }
00991
00992 template <class _Tp, class _Ref, class _Ptr, class _Ctr>
00993 inline ptrdiff_t*
00994 distance_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr>&)
00995 {
00996 return 0;
00997 }
00998
00999 #endif
01000
01001 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
01002 void
01003 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_start_node()
01004 {
01005 _Node* __s = _C_i_cur;
01006 _Ctr_iterator __help;
01007
01008 while(__s->_C_parent != NULL)
01009 {
01010 __help = ((_Node*)__s->_C_parent)->get_entry_iterator((void*)__s);
01011 _C_i_cur_it.push_front(__help);
01012 __s = (_Node*)__s->_C_parent;
01013 }
01014 while(!_C_i_cur->_C_children.empty())
01015 {
01016 __help = _C_i_cur->_C_children.begin();
01017 _C_i_cur = (_Node*)*__help;
01018 _C_i_cur_it.push_back(__help);
01019 }
01020 }
01021
01022 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
01023 void
01024 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_next_node()
01025 {
01026 if(_C_i_cur->_C_parent != NULL)
01027 {
01028 _Ctr_iterator help = _C_i_cur_it.back();
01029 _C_i_cur_it.pop_back();
01030 ++help;
01031 if(help != ((_Node*)_C_i_cur->_C_parent)->_C_children.end())
01032 {
01033 do
01034 {
01035 _C_i_cur_it.push_back(help);
01036 _C_i_cur = (_Node*)*help;
01037 help = _C_i_cur->_C_children.begin();
01038 } while(!_C_i_cur->_C_children.empty());
01039 }
01040 else
01041 {
01042 _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01043 }
01044 }
01045 }
01046
01047 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
01048 void
01049 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_prev_node()
01050 {
01051 _Ctr_iterator help;
01052
01053 if(_C_i_cur->_C_children.empty())
01054 {
01055 while(1)
01056 {
01057 if(_C_i_cur->_C_parent == NULL)
01058 break;
01059 help = _C_i_cur_it.back();
01060 _C_i_cur_it.pop_back();
01061 _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01062 if(help != _C_i_cur->_C_children.begin())
01063 {
01064 --help;
01065 _C_i_cur_it.push_back(help);
01066 _C_i_cur = (_Node*)*help;
01067 break;
01068 }
01069 }
01070 }
01071 else
01072 {
01073 help = _C_i_cur->_C_children.end();
01074 --help;
01075 _C_i_cur_it.push_back(help);
01076 _C_i_cur = (_Node*)*help;
01077 }
01078 }
01079
01080
01081
01082
01083
01084
01085
01086
01087 #ifdef __VGTL_USE_STD_ALLOCATORS
01088
01089
01090
01091 template <class _Tp, class _Ctr, class _I, class _Allocator, bool _IsStatic>
01092 class _Tree_alloc_base {
01093 public:
01094 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
01095 allocator_type;
01096 allocator_type get_allocator() const { return _Node_allocator; }
01097
01098 _Tree_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
01099
01100 protected:
01101 _Tree_node<_Tp,_Ctr,_I>* _C_get_node()
01102 { return _Node_allocator.allocate(1); }
01103 void _C_put_node(_Tree_node<_Tp,_Ctr,_I>* __p)
01104 { _Node_allocator.deallocate(__p, 1); }
01105
01106 protected:
01107 typename _Alloc_traits<_Tree_node<_Tp,_Ctr,_I>, _Allocator>::allocator_type
01108 _Node_allocator;
01109
01110 protected:
01111 _Tree_node<_Tp,_Ctr,_I>* _C_node;
01112 };
01113
01114
01115
01116 template <class _Tp, class _Ctr, class _I, class _Allocator>
01117 class _Tree_alloc_base<_Tp, _Ctr, _I, _Allocator, true> {
01118 public:
01119 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
01120 allocator_type;
01121 allocator_type get_allocator() const { return allocator_type(); }
01122
01123 _Tree_alloc_base(const allocator_type&) {}
01124
01125 protected:
01126 typedef typename _Alloc_traits<_Tree_node<_Tp,_Ctr,_I>, _Allocator>::_Alloc_type
01127 _Alloc_type;
01128 _Tree_node<_Tp,_Ctr,_I>* _C_get_node()
01129 { return _Alloc_type::allocate(1); }
01130 void _C_put_node(_Tree_node<_Tp,_Ctr,_I>* __p)
01131 { _Alloc_type::deallocate(__p, 1); }
01132
01133 protected:
01134 _Tree_node<_Tp,_Ctr,_I>* _C_node;
01135 };
01136
01137 template <class _Tp, class _Ctr, class _I, class _Alloc>
01138 class _Tree_base
01139 : public _Tree_alloc_base<_Tp, _Ctr, _I, _Alloc,
01140 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01141 {
01142 public:
01143 typedef _Tree_alloc_base<_Tp, _Ctr, _I, _Alloc,
01144 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01145 _Base;
01146 typedef typename _Base::allocator_type allocator_type;
01147
01148 typedef _Ctr container_type;
01149 typedef _I container_iterator;
01150
01151 _Tree_base(const allocator_type& __a) : _Base(__a) {
01152 _C_node = _C_get_node();
01153 __VGTL_TRY {
01154 construct(&_C_node->_C_children);
01155 }
01156 __VGTL_UNWIND(_C_put_node(_C_node));
01157 _C_node->_C_parent = NULL;
01158 _C_node->_C_data_hook.f = 0;
01159 }
01160 ~_Tree_base() {
01161 clear();
01162 _C_put_node(_C_node);
01163 }
01164
01165 void clear();
01166 void clear_children()
01167 { _C_node->clear_children(); }
01168
01169 template <class _Output_Iterator>
01170 void add_all_children(_Output_Iterator fi,
01171 _Tree_node<_Tp,_Ctr,_I>* _parent);
01172 };
01173 #else
01174
01175 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
01176 class _Tree_base
01177 {
01178 public:
01179 typedef _Alloc allocator_type;
01180 allocator_type get_allocator() const { return allocator_type(); }
01181
01182 typedef _Ctr container_type;
01183 typedef _Iterator container_iterator;
01184
01185 _Tree_base(const allocator_type&) {
01186 _C_node = _C_get_node();
01187 _C_node->_C_children();
01188 _C_node->_C_parent = NULL;
01189 }
01190 ~_Tree_base() {
01191 clear();
01192 _C_put_node(_C_node);
01193 }
01194
01195 void clear();
01196
01197 protected:
01198 typedef simple_alloc<_Tree_node<_Tp,_Ctr,_Iterator>, _Alloc> _Alloc_type;
01199 _Tree_node<_Tp,_Ctr,_Iterator>* _C_get_node()
01200 { return _Alloc_type::allocate(1); }
01201 void _C_put_node(_Tree_node<_Tp,_Ctr,_Iterator>* __p)
01202 { _Alloc_type::deallocate(__p, 1); }
01203
01204 protected:
01205 _Tree_node<_Tp,_Ctr,_Iterator>* _C_node;
01206
01207 void clear_children()
01208 { _C_node->clear_children(); }
01209
01210 template <class _Output_Iterator>
01211 void add_all_children(_Output_Iterator fi,
01212 _Tree_node<_Tp,_Ctr,_Iterator>* _parent);
01213 };
01214
01215 #endif
01216
01217 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
01218 template <class _Output_Iterator>
01219 inline void
01220 _Tree_base<_Tp,_Ctr,_Iterator,_Alloc>::add_all_children(_Output_Iterator fi,
01221 _Tree_node<_Tp,_Ctr,_Iterator>* _parent)
01222 { _C_node->add_all_children(fi, _parent); };
01223
01224 template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
01225 void
01226 _Tree_base<_Tp,_Ctr,_Iterator,_Alloc>::clear()
01227 {
01228 this->_C_node->clear_tree();
01229 this->_C_node->clear_children();
01230 }
01231
01232 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01233 class __Tree : public _Tree_base<_Tp, _Ctr, _Iterator, _Alloc>
01234 {
01235 public:
01236 typedef _Ctr container_type;
01237 typedef _Iterator container_iterator;
01238 typedef _Inserter container_insert_arg;
01239
01240 protected:
01241 typedef void* _Void_pointer;
01242 typedef _Tree_base<_Tp, container_type, container_iterator, _Alloc> _Base;
01243 typedef _Tree_node<_Tp, container_type, container_iterator> _Node;
01244 typedef __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
01245
01246 public:
01247 typedef _Tp value_type;
01248 typedef _Node node_type;
01249 typedef value_type* pointer;
01250 typedef const value_type* const_pointer;
01251 typedef value_type& reference;
01252 typedef const value_type& const_reference;
01253 typedef size_t size_type;
01254 typedef ptrdiff_t difference_type;
01255
01256
01257 typedef typename _Base::allocator_type allocator_type;
01258 allocator_type get_allocator() const { return _Base::get_allocator(); }
01259
01260 public:
01261 typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,container_iterator> iterator;
01262 typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_iterator;
01263
01264 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01265 typedef reverse_iterator<const_iterator> const_reverse_iterator;
01266 typedef reverse_iterator<iterator> reverse_iterator;
01267 #else
01268 typedef reverse_bidirectional_iterator<const_iterator,value_type,
01269 const_reference,difference_type>
01270 const_reverse_iterator;
01271 typedef reverse_bidirectional_iterator<iterator,value_type,reference,
01272 difference_type>
01273 reverse_iterator;
01274 #endif
01275
01276 typedef _Tree_walker<_Tp,_Tp&,_Tp*,container_type,container_iterator> walker;
01277 typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_walker;
01278
01279 typedef _RTree_walker<_Tp,_Tp&,_Tp*,container_type,container_iterator> recursive_walker;
01280 typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_recursive_walker;
01281
01282 protected:
01283 typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,container_iterator> __walker_base;
01284 typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> __const_walker_base;
01285
01286 protected:
01287 #ifdef __VGTL_HAS_NAMESPACES
01288 using _Base::_C_node;
01289 using _Base::_C_put_node;
01290 using _Base::_C_get_node;
01291 #endif
01292
01293 protected:
01294 _Node* _C_create_node(const _Tp& __x)
01295 {
01296 _Node* __p = _C_get_node();
01297 __VGTL_TRY {
01298 construct(&__p->_C_data, __x);
01299 construct(&__p->_C_children);
01300 }
01301 __VGTL_UNWIND(_C_put_node(__p));
01302 __p->_C_data_hook.f = 0;
01303 __p->_C_parent = NULL;
01304 return __p;
01305 }
01306
01307 _Node* _C_create_node()
01308 {
01309 _Node* __p = _C_get_node();
01310 __VGTL_TRY {
01311 construct(&__p->_C_data);
01312 construct(&__p->_C_children);
01313 }
01314 __VGTL_UNWIND(_C_put_node(__p));
01315 __p->_C_data_hook.f = 0;
01316 __p->_C_parent = NULL;
01317 return __p;
01318 }
01319
01320 public:
01321 explicit __Tree(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01322
01323
01324
01325
01326
01327 walker root(walker_type wt = cw_pre_post,
01328 bool front_to_back = true,
01329 bool depth_first = true)
01330 { walker __help(_C_node, (int)wt, front_to_back, depth_first);
01331 return __help; }
01332
01333 const_walker root(walker_type wt = cw_pre_post,
01334 bool front_to_back = true,
01335 bool depth_first = true) const
01336 { const_walker __help(_C_node, (int)wt, front_to_back, depth_first);
01337 return __help; }
01338
01339 walker through()
01340 { walker __help(_C_node, 0, 0, 0);
01341 return __help; }
01342 const_walker through() const
01343 { const_walker __help(_C_node, 0, 0, 0);
01344 return __help; }
01345
01346 walker begin(walker_type wt = cw_pre_post,
01347 bool front_to_back = true,
01348 bool depth_first = true)
01349 { walker __help = root(wt, front_to_back, depth_first);
01350 ++__help;
01351 return __help; }
01352 const_walker begin(walker_type wt = cw_pre_post,
01353 bool front_to_back = true,
01354 bool depth_first = true) const
01355 { const_walker __help = root(wt, front_to_back, depth_first);
01356 ++__help;
01357 return __help; }
01358
01359 walker end(walker_type wt = cw_pre_post,
01360 bool front_to_back = true,
01361 bool depth_first = true)
01362 { walker __help(_C_node, (int)wt, front_to_back, depth_first, false);
01363 return __help; }
01364 const_walker end(walker_type wt = cw_pre_post,
01365 bool front_to_back = true,
01366 bool depth_first = true) const
01367 { const_walker __help(_C_node, (int)wt, front_to_back,
01368 depth_first, false);
01369 return __help; }
01370
01371
01372
01373
01374
01375
01376
01377
01378
01379
01380
01381 reverse_iterator rbegin()
01382 { return reverse_iterator(end()); }
01383 reverse_iterator rend()
01384 { return reverse_iterator(begin()); }
01385
01386 const_reverse_iterator rbegin() const
01387 { return const_reverse_iterator(end()); }
01388 const_reverse_iterator rend() const
01389 { return const_reverse_iterator(begin()); }
01390
01391 bool empty() const { return _C_node->_C_children.empty(); }
01392
01393 size_type size() const {
01394 size_type __result = 0;
01395 distance(begin(cw_pre), end(cw_pre), __result);
01396 return __result;
01397 }
01398
01399 size_type max_size() const { return size_type(-1); }
01400
01401 reference getroot() { return *root(cw_pre,true,true); }
01402 const_reference getroot() const { return *root(cw_pre,true,true); }
01403
01404 void swap(_Self& __x)
01405 { __STD::swap(_C_node, __x._C_node); }
01406
01407
01408 void insert_child(const __walker_base& __position, const _Tp& __x,
01409 const container_insert_arg& __It)
01410 { _Node* __tmp = _C_create_node(__x);
01411 __position._C_w_cur->_C_children.insert(__It,__tmp);
01412 __tmp->_C_parent = __position._C_w_cur;
01413 }
01414 void insert_child(const __walker_base& __position,
01415 const container_insert_arg& __It)
01416 { insert_child(__position, _Tp(), __It); }
01417
01418 void insert_children(const __walker_base& __position, size_type __n,
01419 const _Tp& __x, const container_iterator& __It)
01420 { _Node* __tmp;
01421 vector<_Node *> __Ctr;
01422 __Ctr.reserve(__n);
01423
01424 for(int i=n; i>0; i--)
01425 {
01426 __tmp = _C_create_node(__x);
01427 __Ctr.insert(__Ctr.end(), __tmp);
01428 __tmp->_C_parent = __position._C_w_cur;
01429 }
01430 __position._C_w_cur->_C_children.insert(__It,
01431 __Ctr.begin(), __Ctr.end());
01432 }
01433
01434
01435 void insert_subtree(const __walker_base& __position,
01436 _Self& __subtree, const container_iterator& __It)
01437 {
01438 __subtree.add_all_children(inserter(__position._C_w_cur->_C_children, __It), __position._C_w_cur);
01439 __subtree.clear_children();
01440 }
01441
01442
01443 void erase(const __walker_base& __position)
01444 { _Node* __tmp = __position._C_w_cur;
01445 _Node* __parent = (_Node*)__tmp->_C_parent;
01446
01447 if(__parent != NULL)
01448 {
01449 container_iterator __ip = __parent->get_entry_iterator(__tmp);
01450
01451 if(!__tmp->_C_children.empty())
01452 {
01453 container_iterator __it = __tmp->_C_children.end();
01454
01455 *__ip = *--__it;
01456 ((_Node*)*__it)->_C_parent = __parent;
01457 __tmp->_C_children.erase(__it);
01458 if(!__tmp->_C_children.empty())
01459 {
01460 __tmp->add_all_children(inserter(__parent->_C_children, __ip),
01461 __parent);
01462 __tmp->clear_children();
01463 }
01464 }
01465 _C_put_node(__tmp);
01466 }
01467 }
01468
01469
01470 _Node* erase_tree(const __walker_base& __position)
01471 { _Node* __tmp = __position._C_w_cur;
01472 _Node* __parent = (_Node*)__tmp->_C_parent;
01473
01474 if(__parent == NULL)
01475 {
01476 this->_C_node = _C_create_node();
01477 return __tmp;
01478 }
01479 else
01480 {
01481 container_iterator __ip = __parent->get_entry_iterator(__tmp);
01482
01483 __parent->_C_children.erase(__ip);
01484 __parent = _C_create_node();
01485 __parent->_C_data = 0;
01486 __parent->_C_children.insert(__parent->_C_children.end(), __tmp);
01487 __tmp->_C_parent = __parent;
01488 return __parent;
01489 }
01490 }
01491
01492
01493
01494 bool erase_child(const __walker_base& __position,
01495 const container_iterator& __It)
01496 {
01497 _Node* __chld = (_Node*)*__It;
01498
01499 if(!__chld->_C_children.empty())
01500 { return false; }
01501 else
01502 {
01503 __position->_C_w_cur->_C_children.erase(__It);
01504 _C_put_node(__chld);
01505 return true;
01506 }
01507 }
01508
01509
01510 _Node* erase_subtree(const __walker_base& __position,
01511 const container_iterator& __It)
01512 { _Node* __chld = (_Node*)*__It;
01513 _Node* __tmp = _C_create_node();
01514
01515 __position->_C_w_cur->_C_children.erase(__It);
01516 __chld->_C_parent = __tmp;
01517 __tmp->_C_data = 0;
01518 __tmp->_C_children.insert(__tmp->_C_children.end(), __chld);
01519 return __tmp;
01520 }
01521
01522
01523 bool is_root() { return _C_node->_C_parent == NULL; }
01524
01525 size_type depth(const walker& __position)
01526 { return __position._C_w_cur_it.size(); }
01527
01528 size_type depth(const recursive_walker& __position)
01529 { size_type __d=0;
01530 _Node* __x = __position._C_w_cur;
01531 while(__x != NULL)
01532 {
01533 __x = (_Node*)__x._C_parent;
01534 __d++;
01535 }
01536 return __d;
01537 }
01538
01539 void clear() { _Base::clear(); }
01540
01541 __Tree(size_type __n, const _Tp& __value,
01542 const allocator_type& __a = allocator_type()) : _Base(__a)
01543 { insert(root(), __n, __value); }
01544 explicit __Tree(size_type __n) : _Base(allocator_type())
01545 { insert(root(), __n, _Tp()); }
01546
01547 private:
01548 _Node* copy_subtree(_Node* __x, _Node* __parent)
01549 { container_iterator cit;
01550
01551 _Node* __h = _C_create_node();
01552 construct(&__h->_C_data, __x->_C_data);
01553 __h->_C_parent = (void*)__parent;
01554 for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
01555 __h->_C_children.insert(__h->_C_children.end(),
01556 copy_subtree((_Node*)*cit, __h));
01557 return __h;
01558 }
01559
01560 public:
01561 __Tree(const _Self& __x) :
01562 _Base(__x.get_allocator())
01563 { container_iterator cit;
01564 for(cit = __x._C_node->_C_children.begin();
01565 cit != __x._C_node->_C_children.end(); ++cit)
01566 this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
01567 copy_subtree((_Node*)*cit, this->_C_node));
01568 }
01569
01570 ~__Tree() {}
01571
01572 _Self& operator=(const _Self& __x);
01573
01574 _Self& operator=(_Node* __x)
01575 {
01576 this->_C_node = __x;
01577 return *this;
01578 }
01579
01580 friend bool operator== __VGTL_NULL_TMPL_ARGS (
01581 const __Tree& __x, const __Tree& __y);
01582 };
01583
01584 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01585 inline bool operator==(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
01586 const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
01587 {
01588 typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_walker const_walker;
01589 const_walker __w1 = __x.begin(cw_pre);
01590 const_walker __w2 = __y.begin(cw_pre);
01591 const_walker __e1 = __x.end(cw_pre);
01592 const_walker __e2 = __y.end(cw_pre);
01593
01594
01595 for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
01596 if(__w1.in_preorder() != __w2.in_preorder() ||
01597 (__w1.in_preorder() && *__w1 != *__w2))
01598 return false;
01599 return __w1 == __e1 && __w2 == __e2;
01600 }
01601
01602 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01603 inline bool operator<(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
01604 const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
01605 {
01606 return lexicographical_compare(__x.begin(cw_pre), __x.end(cw_pre),
01607 __y.begin(cw_pre), __y.end(cw_pre));
01608 }
01609
01610 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01611 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
01612 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
01613 {
01614 container_iterator cit;
01615
01616 if (this != &__x) {
01617 this->_C_node->clear_tree();
01618 this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
01619 this->_C_node->_C_children.end());
01620 for(cit = __x._C_node->_C_children.begin();
01621 cit != __x._C_node->_C_children.end(); ++cit)
01622 this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
01623 copy_subtree((_Node*)*cit, this->_C_node));
01624 }
01625 return *this;
01626 }
01627
01628 template <class _Tp,
01629 template <class __Ty, class __AllocT> class _SequenceCtr = vector,
01630 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
01631 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
01632 class ntree : public __Tree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
01633 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01634 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01635 _Alloc>
01636 {
01637 private:
01638 typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
01639 protected:
01640 typedef ntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
01641
01642 public:
01643 void insert(const __walker_base& __position, const _Tp& __x)
01644 { _Node* __tmp = _C_create_node(__x);
01645 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
01646 container_iterator __it;
01647
01648 if(__parent == NULL)
01649 {
01650 __position._C_w_cur->add_all_children(
01651 back_inserter(__tmp->_C_children), __tmp);
01652 __tmp->_C_parent = __position._C_w_cur;
01653 __position._C_w_cur->clear_children();
01654 __position._C_w_cur->_C_children.insert(
01655 __position._C_w_cur->_C_children.end(), __tmp);
01656 }
01657 else
01658 {
01659 __it = __parent->get_entry_iterator(__position._C_w_cur);
01660 *__it = __tmp;
01661 __tmp->clear_children();
01662 __tmp->_C_children.insert(__tmp->_C_children.end(),
01663 __position._C_w_cur);
01664 __position._C_w_cur->_C_parent = __tmp;
01665 __tmp->_C_parent = __parent;
01666 }
01667 }
01668 void insert(const __walker_base& __position)
01669 { insert(__position, _Tp()); }
01670
01671
01672 void push_child(const __walker_base& __position, const _Tp& __x)
01673 { insert_child(__position, __x,
01674 __position._C_w_cur->_C_children.end()); }
01675 void push_child(const __walker_base& __position)
01676 { push_child(__position, _Tp()); }
01677
01678 void push_children(const __walker_base& __position, size_type __n,
01679 const _Tp& __x)
01680 { insert_children(__position, __n, __x,
01681 __position._C_w_cur->_C_children.end()); }
01682 void push_children(const __walker_base& __position, size_type __n)
01683 { push_children(__position, n, _Tp()); }
01684
01685
01686 void unshift_child(const __walker_base& __position, const _Tp& __x)
01687 { insert_child(__position, __x,
01688 __position._C_w_cur->_C_children.begin()); }
01689 void unshift_child(const __walker_base& __position)
01690 { unshift_child(__position, _Tp()); }
01691
01692 void unshift_children(const __walker_base& __position, size_type __n,
01693 const _Tp& __x)
01694 { insert_children(__position, __n, __x,
01695 __position._C_w_cur->_C_children.begin()); }
01696 void unshift_children(const __walker_base& __position, size_type __n)
01697 { unshift_children(__position, n, _Tp()); }
01698
01699
01700 void push_subtree(const __walker_base& __position, _Self& __subtree)
01701 {
01702 __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
01703 __subtree.clear_children();
01704 }
01705
01706 void unshift_subtree(const __walker_base& __position, _Self& __subtree)
01707 {
01708 __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
01709 __subtree.clear_children();
01710 }
01711
01712
01713 bool pop_child(const __walker_base& __position)
01714 { if(__position._C_w_cur->_C_children.empty())
01715 { return false; }
01716 else
01717 {
01718 container_iterator __it = __position._C_w_cur->_C_children.end();
01719 return erase_child(__position, --__it);
01720 }
01721 }
01722
01723 bool shift_child(const __walker_base& __position)
01724 { if(__position._C_w_cur->_C_children.empty())
01725 { return false; }
01726 else
01727 {
01728 container_iterator __it = __position._C_w_cur->_C_children.begin();
01729 return erase_child(__position, __it);
01730 }
01731 }
01732
01733
01734 _Node* pop_subtree(const __walker_base& __position)
01735 {
01736 if(__position._C_w_cur->_C_children.empty())
01737 { return NULL; }
01738 else
01739 {
01740 container_iterator __it = __position._C_w_cur->_C_children.end();
01741 return erase_subtree(__position, --__it);
01742 }
01743 }
01744
01745 _Node* shift_subtree(const __walker_base& __position)
01746 {
01747 if(__position._C_w_cur->_C_children.empty())
01748 { return NULL; }
01749 else
01750 {
01751 container_iterator __it = __position._C_w_cur->_C_children.begin();
01752 return erase_subtree(__position, __it);
01753 }
01754 }
01755
01756 _Self& operator=(_Node* __x)
01757 {
01758 this->_C_node = __x;
01759 return *this;
01760 }
01761 };
01762
01763 template <class _Tp,
01764 template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = multimap,
01765 class _Key = string,
01766 class _Compare = less<_Key>,
01767 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
01768 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
01769 class atree : public __Tree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
01770 pair_adaptor<typename _AssocCtr<_Key, void*,
01771 _Compare, _PtrAlloc>::iterator>,
01772 _Key, _Alloc>
01773 {
01774 protected:
01775 typedef atree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
01776
01777 public:
01778 _Self& operator=(_Node* __x)
01779 {
01780 this->_C_node = __x;
01781 return *this;
01782 }
01783
01784 void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
01785 { _Node* __tmp = _C_create_node(__x);
01786 _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
01787 container_iterator __it;
01788
01789 if(__parent == NULL)
01790 {
01791 __position._C_w_cur->add_all_children(
01792 inserter(__tmp->_C_children.end()), __tmp);
01793 __tmp->_C_parent = __position._C_w_cur;
01794 __position._C_w_cur->clear_children();
01795 __position._C_w_cur->_C_children.insert(__k, __tmp);
01796 }
01797 else
01798 {
01799 __it = __parent->get_entry_iterator(__position._C_w_cur);
01800 *__it = __tmp;
01801 __tmp->clear_children();
01802 __tmp->_C_children.insert(__k, __position._C_w_cur);
01803 __position._C_w_cur->_C_parent = __tmp;
01804 __tmp->_C_parent = __parent;
01805 }
01806 }
01807 void insert(const __walker_base& __position, const _Key& __k)
01808 { insert(__position, _Tp(), __k); }
01809
01810
01811 };
01812
01813 template <class _Key, class _Compare = less<_Key>,
01814 template <class __Key, class __Compare, class __AllocT> class _AssocCtr = multiset,
01815 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
01816 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
01817 class stree : public __Tree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
01818 _PtrAlloc>,
01819 typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
01820 _PtrAlloc>::iterator,
01821 _Key&, _Alloc>
01822 {
01823 protected:
01824 typedef stree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
01825
01826 public:
01827 _Self& operator=(_Node* __x)
01828 {
01829 this->_C_node = __x;
01830 return *this;
01831 }
01832 };
01833
01834 __VGTL_END_NAMESPACE
01835
01836 #endif // __VGTL_GRAPH_H_