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_ALGO_H
00031 #define __VGTL_ALGO_H
00032
00033 #include <algorithm>
00034 #include <vgtl_helpers.h>
00035 #include <vgtl_gdata.h>
00036
00037 __VGTL_BEGIN_NAMESPACE
00038
00039 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
00040 #pragma set woff 1209
00041 #endif
00042
00044
00049 template <class _Iterator, class _Node>
00050 class __Child_data_iterator
00051 {
00052 private:
00053 typedef __Child_data_iterator<_Iterator, _Node> _Self;
00054
00055 public:
00056 typedef typename std::iterator_traits<_Iterator>::iterator_category iterator_category;
00057 typedef typename std::iterator_traits<_Iterator>::difference_type difference_type;
00058
00059 public:
00061
00062 typedef ctree_data_hook value_type;
00063 typedef value_type* pointer;
00064 typedef value_type& reference;
00066
00067 typedef _Iterator iterator_type;
00068 protected:
00070 _Iterator current;
00071
00072 public:
00074
00075 __Child_data_iterator() {}
00076 explicit __Child_data_iterator(iterator_type __x) : current(__x) {}
00078
00080 __Child_data_iterator(const _Self& __x) : current(__x.current) {}
00081
00083 iterator_type base() const { return current; }
00084
00086 reference operator*() const {
00087 return (*((_Node*)*current)).data_hook();
00088 }
00089 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00090 pointer operator->() const { return &(operator*()); }
00091 #endif
00092
00094
00095 bool operator== (const _Self& __x) const { return (*this).current == __x.current; }
00096 bool operator!= (const _Self& __x) const { return (*this).current != __x.current; }
00098
00100 _Self& operator= (const iterator_type& it)
00101 {
00102 current = it;
00103 return *this;
00104 }
00105
00107
00108 _Self& operator++() {
00109 ++current;
00110 return *this;
00111 }
00112 _Self& operator++(int) {
00113 _Self __tmp = *this;
00114 ++current;
00115 return __tmp;
00116 }
00117 _Self& operator--() {
00118 --current;
00119 return *this;
00120 }
00121 _Self& operator--(int) {
00122 _Self __tmp = *this;
00123 --current;
00124 return __tmp;
00125 }
00127
00129
00130
00131 return _Self(current + __n);
00132 }
00133 _Self& operator+=(difference_type __n) {
00134 current += __n;
00135 return *this;
00136 }
00137 _Self operator-(difference_type __n) const {
00138 return _Self(current - __n);
00139 }
00140 _Self& operator-=(difference_type __n) {
00141 current -= __n;
00142 return *this;
00143 }
00144 reference operator[](difference_type __n) const { return *(*this + __n); }
00146 };
00147
00149
00154 template <class _Tree>
00155 class child_data_iterator :
00156 public __Child_data_iterator<typename _Tree::children_iterator,
00157 typename _Tree::node_type>
00158 {
00159 private:
00160 typedef child_data_iterator<_Tree> _Self;
00161 typedef typename _Tree::children_iterator _Iterator;
00162 typedef typename _Tree::node_type _Node;
00163
00164 typedef typename child_data_iterator<_Tree>::iterator_type iterator_type;
00165
00166 public:
00168 child_data_iterator() {}
00170 explicit child_data_iterator(iterator_type __x) { current = __x; }
00171
00173 child_data_iterator(const _Self& __x) { current = __x.current; }
00174
00176 _Self& operator= (const iterator_type& it)
00177 {
00178 current = it;
00179 return *this;
00180 }
00181 };
00182
00189 template <class _IterativeWalker, class _Function>
00190 _Function walk(_IterativeWalker __first, _IterativeWalker __last, _Function __f)
00191 {
00192 typedef __Child_data_iterator<typename _IterativeWalker::children_iterator,
00193 typename _IterativeWalker::node_type> __cit;
00194 for ( ; __first != __last; ++__first)
00195 __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
00196 __cit(__first.child_end()));
00197 return __f;
00198 }
00199
00204 template <class _PrePostWalker, class _Function>
00205 _Function pre_post_walk(_PrePostWalker __first, _PrePostWalker __last,
00206 _Function __f)
00207 {
00208 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00209 typename _PrePostWalker::node_type> __cit;
00210 for ( ; __first != __last; ++__first)
00211 __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
00212 __cit(__first.child_end()),
00213 __first.in_preorder());
00214 return __f;
00215 }
00216
00222 template <class _PrePostWalker, class _Function1, class _Function2>
00223 _Function2 pre_post_walk(_PrePostWalker __first, _PrePostWalker __last,
00224 _Function1 __f1, _Function2 __f2)
00225 {
00226 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00227 typename _PrePostWalker::node_type> __cit;
00228 for ( ; __first != __last; ++__first)
00229 __first.in_preorder() ?
00230 __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
00231 __cit(__first.child_end())) :
00232 __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
00233 __cit(__first.child_end()));
00234 return __f2;
00235 }
00236
00246 template <class _PrePostWalker, class _Function>
00247 _Function var_walk(_PrePostWalker __first, _PrePostWalker __last,
00248 _Function __f)
00249 {
00250 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00251 typename _PrePostWalker::node_type> __cit;
00252 for ( ; __first != __last; ++__first)
00253 if(__f(*__first, __first.data_hook(), __cit(__first.child_begin()),
00254 __cit(__first.child_end()), __first.in_preorder()))
00255 ~__first;
00256 return __f;
00257 }
00258
00269 template <class _PrePostWalker, class _Function1, class _Function2>
00270 _Function2 var_walk(_PrePostWalker __first, _PrePostWalker __last,
00271 _Function1 __f1, _Function2 __f2)
00272 {
00273 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00274 typename _PrePostWalker::node_type> __cit;
00275 for ( ; __first != __last; ++__first)
00276 if(__first.in_preorder() ?
00277 __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
00278 __cit(__first.child_end())):
00279 __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
00280 __cit(__first.child_end())))
00281 ~__first;
00282 return __f2;
00283 }
00284
00294 template <class _PrePostWalker, class _Function, class _Predicate>
00295 _Function walk_if(_PrePostWalker __first, _PrePostWalker __last,
00296 _Function __f, _Predicate __pred)
00297 {
00298 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00299 typename _PrePostWalker::node_type> __cit;
00300 for ( ; __first != __last; ++__first)
00301 {
00302 __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
00303 __cit(__first.child_end()), __first.in_preorder());
00304 if(__pred(*__first))
00305 ~__first;
00306 }
00307 return __f;
00308 }
00309
00320 template <class _PrePostWalker, class _Function1, class _Function2,
00321 class _Predicate>
00322 _Function2 walk_if(_PrePostWalker __first, _PrePostWalker __last,
00323 _Function1 __f1, _Function2 __f2, _Predicate __pred)
00324 {
00325 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00326 typename _PrePostWalker::node_type> __cit;
00327 for ( ; __first != __last; ++__first)
00328 {
00329 __first.in_preorder() ? __f1(*__first, __first.data_hook(),
00330 __cit(__first.child_begin()),
00331 __cit(__first.child_end())) :
00332 __f2(*__first, __first.data_hook(),
00333 __cit(__first.child_begin()),
00334 __cit(__first.child_end()));
00335 if(__pred(*__first))
00336 ~__first;
00337 }
00338 return __f2;
00339 }
00340
00353 template <class _PrePostWalker, class _Function1, class _Function2,
00354 class _Predicate1, class _Predicate2>
00355 _Function2 walk_if(_PrePostWalker __first, _PrePostWalker __last,
00356 _Function1 __f1, _Function2 __f2, _Predicate1 __pred1,
00357 _Predicate2 __pred2)
00358 {
00359 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00360 typename _PrePostWalker::node_type> __cit;
00361 for ( ; __first != __last; ++__first)
00362 {
00363 if(__first.in_preorder())
00364 {
00365 __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
00366 __cit(__first.child_end()));
00367 if(__pred1(*__first))
00368 ~__first;
00369 }
00370 else
00371 {
00372 __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
00373 __cit(__first.child_end()));
00374 if(__pred2(*__first))
00375 ~__first;
00376 }
00377 }
00378 return __f2;
00379 }
00380
00391 template <class _PrePostWalker, class _Function1, class _Function2,
00392 class _Predicate>
00393 _Function2 cached_walk_if(_PrePostWalker __first, _PrePostWalker __last,
00394 _Function1 __f1, _Function2 __f2, _Predicate __pred)
00395 {
00396 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00397 typename _PrePostWalker::node_type> __cit;
00398 for ( ; __first != __last; ++__first)
00399 {
00400 if(__first.in_preorder())
00401 {
00402 __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
00403 __cit(__first.child_end()));
00404 if(__pred(*__first))
00405 ~__first;
00406 }
00407 else
00408 __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
00409 __cit(__first.child_end()));
00410 }
00411 return __f2;
00412 }
00413
00424 template <class _PrePostWalker, class _Function1, class _Function2,
00425 class _Predicate>
00426 _Function2 multi_walk_if(_PrePostWalker __first, _PrePostWalker __last,
00427 _Function1 __f1, _Function2 __f2, _Predicate __pred)
00428 {
00429 typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
00430 typename _PrePostWalker::node_type> __cit;
00431 for ( ; __first != __last; ++__first)
00432 {
00433 if(__first.in_preorder())
00434 __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
00435 __cit(__first.child_end()));
00436 else
00437 {
00438 __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
00439 __cit(__first.child_end()));
00440 if(__pred(*__first))
00441 ~__first;
00442 }
00443 }
00444 return __f2;
00445 }
00446
00454 template <class _Walker, class _Function>
00455 _Function walk_up(_Walker __w, _Function __f)
00456 {
00457 while(!__w.is_root())
00458 {
00459 __f(*__w, __w.data_hook(), __w.parent_data_hook());
00460 __w <<= false;
00461 }
00462 return __f;
00463 }
00464
00474 template <class _Walker, class _Function>
00475 _Function var_walk_up(_Walker __w, _Function __f)
00476 {
00477 while(!__w.is_root())
00478 {
00479 if(__f(*__w, __w.data_hook(), __w.parent_data_hook()))
00480 break;
00481 __w <<= false;
00482 }
00483 return __f;
00484 }
00485
00495 template <class _Walker, class _Function, class _Predicate>
00496 _Function walk_up_if(_Walker __w, _Function __f, _Predicate __p)
00497 {
00498 while(!__w.is_root())
00499 {
00500 __f(*__w, __w.data_hook(), __w.parent_data_hook());
00501 if(__p(*__w, __w.data_hook()))
00502 break;
00503 __w <<= false;
00504 }
00505 return __f;
00506 }
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00529 template <class _Walker, class _Visitor>
00530 typename _Visitor::return_value recursive_preorder_walk(_Walker __w,
00531 _Visitor __f)
00532 {
00533 typename _Walker::children_iterator __it, __e;
00534
00535 if(__w.is_ground())
00536 {
00537 __e = __w.child_end();
00538 __f.vinit();
00539 for(__it = __w.child_begin(); __it != __e; ++__it)
00540 __f.vcollect(_recursive_preorder_walk(__w>>__it, __f));
00541 return __f.vvalue();
00542 }
00543 else if(__w.is_sky())
00544 return __f.vvalue();
00545 else
00546 {
00547 __f.preorder(*__w);
00548 __e = __w.child_end();
00549 for(__it = __w.child_begin(); __it != __e; ++__it)
00550 __f.collect(*__w, _recursive_preorder_walk(__w>>__it, __f));
00551 return __f.value();
00552 }
00553 }
00554
00567 template <class _Walker, class _Visitor>
00568 typename _Visitor::return_value _recursive_preorder_walk(_Walker __w,
00569 _Visitor __f)
00570 {
00571 typename _Walker::children_iterator __it, __e;
00572
00573 if(__w.is_sky())
00574 return __f.vvalue();
00575 __f.preorder(*__w);
00576 __e = __w.child_end();
00577 for(__it = __w.child_begin(); __it != __e; ++__it)
00578 __f.collect(*__w, _recursive_preorder_walk(__w>>__it, __f));
00579 return __f.value();
00580 }
00581
00594 template <class _Walker, class _Visitor>
00595 typename _Visitor::return_value recursive_postorder_walk(_Walker __w,
00596 _Visitor __f)
00597 {
00598 typename _Walker::children_iterator __it, __e;
00599
00600 if(__w.is_ground())
00601 {
00602 __f.vinit();
00603 __e = __w.child_end();
00604 for(__it = __w.child_begin(); __it != __e; ++__it)
00605 __f.vcollect(_recursive_postorder_walk(__w>>__it, __f));
00606 return __f.vvalue();
00607 }
00608 else if(__w.is_sky())
00609 return __f.vvalue();
00610 else
00611 {
00612 __f.init();
00613 __e = __w.child_end();
00614 for(__it = __w.child_begin(); __it != __e; ++__it)
00615 __f.collect(*__w, _recursive_postorder_walk(__w>>__it, __f));
00616 __f.postorder(*__w);
00617 return __f.value();
00618 }
00619 }
00620
00634 template <class _Walker, class _Visitor>
00635 typename _Visitor::return_value _recursive_postorder_walk(_Walker __w,
00636 _Visitor __f)
00637 {
00638 typename _Walker::children_iterator __it, __e;
00639
00640 if(__w.is_sky())
00641 return __f.vvalue();
00642 __f.init();
00643 __e = __w.child_end();
00644 for(__it = __w.child_begin(); __it != __e; ++__it)
00645 __f.collect(*__w, _recursive_postorder_walk(__w>>__it, __f));
00646 __f.postorder(*__w);
00647 return __f.value();
00648 }
00649
00662 template <class _Walker, class _Visitor>
00663 typename _Visitor::return_value recursive_walk(_Walker __w, _Visitor __f)
00664 {
00665 typename _Walker::children_iterator __it, __e;
00666
00667 if(__w.is_ground())
00668 {
00669 __e = __w.child_end();
00670 __f.vinit();
00671 for(__it = __w.child_begin(); __it != __e; ++__it)
00672 __f.vcollect(_recursive_walk(__w>>__it, __f));
00673 return __f.vvalue();
00674 }
00675 else if(__w.is_sky())
00676 return __f.vvalue();
00677 else
00678 {
00679 __f.preorder(*__w);
00680 __e = __w.child_end();
00681 for(__it = __w.child_begin(); __it != __e; ++__it)
00682 __f.collect(*__w, _recursive_walk(__w>>__it, __f));
00683 __f.postorder(*__w);
00684 return __f.value();
00685 }
00686 }
00687
00701 template <class _Walker, class _Visitor>
00702 typename _Visitor::return_value _recursive_walk(_Walker __w, _Visitor __f)
00703 {
00704 typename _Walker::children_iterator __it, __e;
00705
00706 if(__w.is_sky())
00707 return __f.vvalue();
00708 __f.preorder(*__w);
00709 __e = __w.child_end();
00710 for(__it = __w.child_begin(); __it != __e; ++__it)
00711 __f.collect(*__w, _recursive_walk(__w>>__it, __f));
00712 __f.postorder(*__w);
00713 return __f.value();
00714 }
00715
00729 template <class _Walker, class _Visitor>
00730 typename _Visitor::return_value recursive_preorder_walk_if(_Walker __w,
00731 _Visitor __f)
00732 {
00733 typename _Walker::children_iterator __it, __e;
00734
00735 if(__w.is_ground())
00736 {
00737 __e = __w.child_end();
00738 __f.vinit();
00739 for(__it = __w.child_begin(); __it != __e; ++__it)
00740 __f.vcollect(_recursive_preorder_walk_if(__w>>__it, __f));
00741 return __f.vvalue();
00742 }
00743 else if(__w.is_sky())
00744 return __f.vvalue();
00745 else
00746 {
00747 if(__f.preorder(*__w))
00748 {
00749 __e = __w.child_end();
00750 for(__it = __w.child_begin(); __it != __e; ++__it)
00751 __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f));
00752 }
00753 return __f.value();
00754 }
00755 }
00756
00771 template <class _Walker, class _Visitor>
00772 typename _Visitor::return_value _recursive_preorder_walk_if(_Walker __w,
00773 _Visitor __f)
00774 {
00775 typename _Walker::children_iterator __it, __e;
00776
00777 if(__w.is_sky())
00778 return __f.vvalue();
00779 if(__f.preorder(*__w))
00780 {
00781 __e = __w.child_end();
00782 for(__it = __w.child_begin(); __it != __e; ++__it)
00783 __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f));
00784 }
00785 return __f.value();
00786 }
00787
00802 template <class _Walker, class _Visitor, class _Predicate>
00803 typename _Visitor::return_value recursive_preorder_walk_if(_Walker __w,
00804 _Visitor __f, _Predicate __p)
00805 {
00806 typename _Walker::children_iterator __it, __e;
00807
00808 if(__w.is_ground())
00809 {
00810 __e = __w.child_end();
00811 __f.vinit();
00812 for(__it = __w.child_begin(); __it != __e; ++__it)
00813 __f.vcollect(_recursive_preorder_walk_if(__w>>__it, __f, __p));
00814 return __f.vvalue();
00815 }
00816 else if(__w.is_sky())
00817 return __f.vvalue();
00818 else
00819 {
00820 __f.preorder(*__w);
00821 if(__p(*__w))
00822 {
00823 __e = __w.child_end();
00824 for(__it = __w.child_begin(); __it != __e; ++__it)
00825 __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f, __p));
00826 }
00827 return __f.value();
00828 }
00829 }
00830
00846 template <class _Walker, class _Visitor, class _Predicate>
00847 typename _Visitor::return_value _recursive_preorder_walk_if(_Walker __w,
00848 _Visitor __f, _Predicate __p)
00849 {
00850 typename _Walker::children_iterator __it, __e;
00851
00852 if(__w.is_sky())
00853 return __f.vvalue();
00854 __f.preorder(*__w);
00855 if(__p(*__w))
00856 {
00857 __e = __w.child_end();
00858 for(__it = __w.child_begin(); __it != __e; ++__it)
00859 __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f, __p));
00860 }
00861 return __f.value();
00862 }
00863
00879 template <class _Walker, class _Visitor, class _Predicate>
00880 typename _Visitor::return_value recursive_postorder_walk_if(_Walker __w,
00881 _Visitor __f, _Predicate __p)
00882 {
00883 typename _Walker::children_iterator __it, __e;
00884
00885 if(__w.is_ground())
00886 {
00887 __f.vinit();
00888 __e = __w.child_end();
00889 for(__it = __w.child_begin(); __it != __e; ++__it)
00890 __f.vcollect(_recursive_postorder_walk_if(__w>>__it, __f, __p));
00891 return __f.vvalue();
00892 }
00893 else if(__w.is_sky())
00894 return __f.vvalue();
00895 else
00896 {
00897 __f.init();
00898 if(__p(*__w))
00899 {
00900 __e = __w.child_end();
00901 for(__it = __w.child_begin(); __it != __e; ++__it)
00902 __f.collect(*__w, _recursive_postorder_walk_if(__w>>__it, __f, __p));
00903 }
00904 __f.postorder(*__w, __w.data_hook());
00905 return __f.value();
00906 }
00907 }
00908
00925 template <class _Walker, class _Visitor, class _Predicate>
00926 typename _Visitor::return_value _recursive_postorder_walk_if(_Walker __w,
00927 _Visitor __f, _Predicate __p)
00928 {
00929 typename _Walker::children_iterator __it, __e;
00930
00931 if(__w.is_sky())
00932 return __f.vvalue();
00933 __f.init();
00934 if(__p(*__w))
00935 {
00936 __e = __w.child_end();
00937 for(__it = __w.child_begin(); __it != __e; ++__it)
00938 __f.collect(*__w, _recursive_postorder_walk_if(__w>>__it, __f, __p));
00939 }
00940 __f.postorder(*__w, __w.data_hook());
00941 return __f.value();
00942 }
00943
00961 template <class _Walker, class _Visitor>
00962 typename _Visitor::return_value recursive_walk_if(_Walker __w, _Visitor __f)
00963 {
00964 typename _Walker::children_iterator __it, __e;
00965
00966 if(__w.is_ground())
00967 {
00968 __e = __w.child_end();
00969 __f.vinit();
00970 for(__it = __w.child_begin(); __it != __e; ++__it)
00971 __f.vcollect(_recursive_walk_if(__w>>__it, __f));
00972 return __f.vvalue();
00973 }
00974 else if(__w.is_sky())
00975 return __f.vvalue();
00976 else
00977 {
00978 while(1)
00979 {
00980 if(__f.preorder(*__w))
00981 {
00982 __e = __w.child_end();
00983 for(__it = __w.child_begin(); __it != __e; ++__it)
00984 __f.collect(*__w, _recursive_walk_if(__w>>__it, __f));
00985 }
00986 if(!__f.postorder(*__w))
00987 break;
00988 }
00989 return __f.value();
00990 }
00991 }
00992
01011 template <class _Walker, class _Visitor>
01012 typename _Visitor::return_value _recursive_walk_if(_Walker __w, _Visitor __f)
01013 {
01014 typename _Walker::children_iterator __it, __e;
01015
01016 if(__w.is_sky())
01017 return __f.vvalue();
01018 while(1)
01019 {
01020 if(__f.preorder(*__w))
01021 {
01022 __e = __w.child_end();
01023 for(__it = __w.child_begin(); __it != __e; ++__it)
01024 __f.collect(*__w, _recursive_walk_if(__w>>__it, __f));
01025 }
01026 if(!__f.postorder(*__w))
01027 break;
01028 }
01029 return __f.value();
01030 }
01031
01046 template <class _Walker, class _Visitor>
01047 typename _Visitor::return_value recursive_cached_walk(_Walker __w, _Visitor __f)
01048 {
01049 typename _Walker::children_iterator __it, __e;
01050
01051 if(__w.is_ground())
01052 {
01053 __e = __w.child_end();
01054 __f.vinit();
01055 for(__it = __w.child_begin(); __it != __e; ++__it)
01056 __f.vcollect(_recursive_cached_walk(__w>>__it, __f));
01057 return __f.vvalue();
01058 }
01059 else if(__w.is_sky())
01060 return __f.vvalue();
01061 else
01062 {
01063 if(__f.preorder(*__w))
01064 {
01065 __e = __w.child_end();
01066 for(__it = __w.child_begin(); __it != __e; ++__it)
01067 __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f));
01068 }
01069 __f.postorder(*__w);
01070 return __f.value();
01071 }
01072 }
01073
01089 template <class _Walker, class _Visitor>
01090 typename _Visitor::return_value _recursive_cached_walk(_Walker __w,
01091 _Visitor __f)
01092 {
01093 typename _Walker::children_iterator __it, __e;
01094
01095 if(__w.is_sky())
01096 return __f.vvalue();
01097 if(__f.preorder(*__w))
01098 {
01099 __e = __w.child_end();
01100 for(__it = __w.child_begin(); __it != __e; ++__it)
01101 __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f));
01102 }
01103 __f.postorder(*__w);
01104 return __f.value();
01105 }
01106
01122 template <class _Walker, class _Visitor>
01123 typename _Visitor::return_value recursive_multi_walk(_Walker __w, _Visitor __f)
01124 {
01125 typename _Walker::children_iterator __it, __e;
01126
01127 if(__w.is_ground())
01128 {
01129 __e = __w.child_end();
01130 __f.vinit();
01131 for(__it = __w.child_begin(); __it != __e; ++__it)
01132 __f.vcollect(_recursive_mulit_walk(__w>>__it, __f));
01133 return __f.vvalue();
01134 }
01135 else if(__w.is_sky())
01136 return __f.vvalue();
01137 else
01138 {
01139 while(1)
01140 {
01141 __f.preorder(*__w);
01142 __e = __w.child_end();
01143 for(__it = __w.child_begin(); __it != __e; ++__it)
01144 __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f));
01145 if(!__f.postorder(*__w))
01146 break;
01147 }
01148 return __f.value();
01149 }
01150 }
01151
01168 template <class _Walker, class _Visitor>
01169 typename _Visitor::return_value _recursive_multi_walk(_Walker __w, _Visitor __f)
01170 {
01171 typename _Walker::children_iterator __it, __e;
01172
01173 if(__w.is_sky())
01174 return __f.vvalue();
01175 while(1)
01176 {
01177 __f.preorder(*__w);
01178 __e = __w.child_end();
01179 for(__it = __w.child_begin(); __it != __e; ++__it)
01180 __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f));
01181 if(!__f.postorder(*__w))
01182 break;
01183 }
01184 return __f.value();
01185 }
01186
01204 template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
01205 typename _Visitor::return_value recursive_walk_if(_Walker __w, _Visitor __f,
01206 _Predicate1 __p1, _Predicate2 __p2)
01207 {
01208 typename _Walker::children_iterator __it, __e;
01209
01210 if(__w.is_ground())
01211 {
01212 __e = __w.child_end();
01213 __f.vinit();
01214 for(__it = __w.child_begin(); __it != __e; ++__it)
01215 __f.vcollect(_recursive_walk_if(__w>>__it, __f, __p1, __p2));
01216 return __f.vvalue();
01217 }
01218 else if(__w.is_sky())
01219 return __f.vvalue();
01220 else
01221 {
01222 while(1)
01223 {
01224 __f.preorder(*__w);
01225 if(__p1(*__w))
01226 {
01227 __e = __w.child_end();
01228 for(__it = __w.child_begin(); __it != __e; ++__it)
01229 __f.collect(*__w, _recursive_walk_if(__w>>__it, __f, __p1, __p2));
01230 }
01231 __f.postorder(*__w);
01232 if(!__p2(*__w))
01233 break;
01234 }
01235 return __f.value();
01236 }
01237 }
01238
01257 template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
01258 typename _Visitor::return_value _recursive_walk_if(_Walker __w, _Visitor __f,
01259 _Predicate1 __p1, _Predicate2 __p2)
01260 {
01261 typename _Walker::children_iterator __it, __e;
01262
01263 if(__w.is_sky())
01264 return __f.vvalue();
01265 while(1)
01266 {
01267 __f.preorder(*__w);
01268 if(__p1(*__w))
01269 {
01270 __e = __w.child_end();
01271 for(__it = __w.child_begin(); __it != __e; ++__it)
01272 __f.collect(*__w, _recursive_walk_if(__w>>__it, __f, __p1, __p2));
01273 }
01274 __f.postorder(*__w);
01275 if(!__p2(*__w))
01276 break;
01277 }
01278 return __f.value();
01279 }
01280
01295 template <class _Walker, class _Visitor, class _Predicate>
01296 typename _Visitor::return_value recursive_cached_walk(_Walker __w, _Visitor __f,
01297 _Predicate __p)
01298 {
01299 typename _Walker::children_iterator __it, __e;
01300
01301 if(__w.is_ground())
01302 {
01303 __e = __w.child_end();
01304 __f.vinit();
01305 for(__it = __w.child_begin(); __it != __e; ++__it)
01306 __f.vcollect(_recursive_cached_walk(__w>>__it, __f, __p));
01307 return __f.vvalue();
01308 }
01309 else if(__w.is_sky())
01310 return __f.vvalue();
01311 else
01312 {
01313 __f.preorder(*__w);
01314 if(__p(*__w))
01315 {
01316 __e = __w.child_end();
01317 for(__it = __w.child_begin(); __it != __e; ++__it)
01318 __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f, __p));
01319 }
01320 __f.postorder(*__w);
01321 return __f.value();
01322 }
01323 }
01324
01340 template <class _Walker, class _Visitor, class _Predicate>
01341 typename _Visitor::return_value _recursive_cached_walk(_Walker __w, _Visitor __f,
01342 _Predicate __p)
01343 {
01344 typename _Walker::children_iterator __it, __e;
01345
01346 if(__w.is_sky())
01347 return __f.vvalue();
01348 __f.preorder(*__w);
01349 if(__p(*__w))
01350 {
01351 __e = __w.child_end();
01352 for(__it = __w.child_begin(); __it != __e; ++__it)
01353 __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f, __p));
01354 }
01355 __f.postorder(*__w);
01356 return __f.value();
01357 }
01358
01374 template <class _Walker, class _Visitor, class _Predicate>
01375 typename _Visitor::return_value recursive_multi_walk(_Walker __w, _Visitor __f,
01376 _Predicate __p)
01377 {
01378 typename _Walker::children_iterator __it, __e;
01379
01380 if(__w.is_ground())
01381 {
01382 __e = __w.child_end();
01383 __f.vinit();
01384 for(__it = __w.child_begin(); __it != __e; ++__it)
01385 __f.vcollect(_recursive_multi_walk(__w>>__it, __f, __p));
01386 return __f.vvalue();
01387 }
01388 else if(__w.is_sky())
01389 return __f.vvalue();
01390 else
01391 {
01392 while(1)
01393 {
01394 __f.preorder(*__w);
01395 __e = __w.child_end();
01396 for(__it = __w.child_begin(); __it != __e; ++__it)
01397 __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f, __p));
01398 __f.postorder(*__w);
01399 if(!__p(*__w))
01400 break;
01401 }
01402 return __f.value();
01403 }
01404 }
01405
01422 template <class _Walker, class _Visitor, class _Predicate>
01423 typename _Visitor::return_value _recursive_multi_walk(_Walker __w, _Visitor __f,
01424 _Predicate __p)
01425 {
01426 typename _Walker::children_iterator __it, __e;
01427
01428 if(__w.is_sky())
01429 return __f.vvalue();
01430 while(1)
01431 {
01432 __f.preorder(*__w);
01433 __e = __w.child_end();
01434 for(__it = __w.child_begin(); __it != __e; ++__it)
01435 __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f, __p));
01436 __f.postorder(*__w);
01437 if(!__p(*__w))
01438 break;
01439 }
01440 return __f.value();
01441 }
01442
01454 template <class _Walker, class _Visitor>
01455 typename _Visitor::return_value recursive_preorder_walk_up(_Walker __w,
01456 _Visitor __f)
01457 {
01458 typename _Walker::parents_iterator __it, __e;
01459
01460 if(__w.is_sky())
01461 {
01462 __e = __w.parent_end();
01463 __f.vinit();
01464 for(__it = __w.parent_begin(); __it != __e; ++__it)
01465 __f.vcollect(_recursive_preorder_walk_up(__w<<__it, __f));
01466 return __f.vvalue();
01467 }
01468 else if(__w.is_ground())
01469 return __f.vvalue();
01470 else
01471 {
01472 __f.preorder(*__w);
01473 __e = __w.parent_end();
01474 for(__it = __w.parent_begin(); __it != __e; ++__it)
01475 __f.collect(*__w, _recursive_preorder_walk_up(__w<<__it, __f));
01476 return __f.value();
01477 }
01478 }
01479
01492 template <class _Walker, class _Visitor>
01493 typename _Visitor::return_value _recursive_preorder_walk_up(_Walker __w,
01494 _Visitor __f)
01495 {
01496 typename _Walker::parents_iterator __it, __e;
01497
01498 if(__w.is_ground())
01499 return __f.vvalue();
01500 __f.preorder(*__w);
01501 __e = __w.parent_end();
01502 for(__it = __w.parent_begin(); __it != __e; ++__it)
01503 __f.collect(*__w, _recursive_preorder_walk_up(__w<<__it, __f));
01504 return __f.value();
01505 }
01506
01520 template <class _Walker, class _Visitor>
01521 typename _Visitor::return_value recursive_preorder_walk_up_if(_Walker __w,
01522 _Visitor __f)
01523 {
01524 typename _Walker::parents_iterator __it, __e;
01525
01526 if(__w.is_sky())
01527 {
01528 __e = __w.parent_end();
01529 __f.vinit();
01530 for(__it = __w.parent_begin(); __it != __e; ++__it)
01531 __f.vcollect(_recursive_preorder_walk_up_if(__w<<__it, __f));
01532 return __f.vvalue();
01533 }
01534 else if(__w.is_ground())
01535 return __f.vvalue();
01536 else
01537 {
01538 if(__f.preorder(*__w))
01539 {
01540 __e = __w.parent_end();
01541 for(__it = __w.parent_begin(); __it != __e; ++__it)
01542 __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f));
01543 }
01544 return __f.value();
01545 }
01546 }
01547
01562 template <class _Walker, class _Visitor>
01563 typename _Visitor::return_value _recursive_preorder_walk_up_if(_Walker __w,
01564 _Visitor __f)
01565 {
01566 typename _Walker::parents_iterator __it, __e;
01567
01568 if(__w.is_ground())
01569 return __f.vvalue();
01570 if(__f.preorder(*__w))
01571 {
01572 __e = __w.parent_end();
01573 for(__it = __w.parent_begin(); __it != __e; ++__it)
01574 __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f));
01575 }
01576 return __f.value();
01577 }
01578
01593 template <class _Walker, class _Visitor, class _Predicate>
01594 typename _Visitor::return_value recursive_preorder_walk_up_if(_Walker __w,
01595 _Visitor __f, _Predicate __p)
01596 {
01597 typename _Walker::parents_iterator __it, __e;
01598
01599 if(__w.is_sky())
01600 {
01601 __e = __w.parent_end();
01602 __f.vinit();
01603 for(__it = __w.parent_begin(); __it != __e; ++__it)
01604 __f.vcollect(_recursive_preorder_walk_up_if(__w<<__it, __f, __p));
01605 return __f.vvalue();
01606 }
01607 else if(__w.is_ground())
01608 return __f.vvalue();
01609 else
01610 {
01611 __f.preorder(*__w);
01612 if(__p(*__w))
01613 {
01614 __e = __w.parent_end();
01615 for(__it = __w.parent_begin(); __it != __e; ++__it)
01616 __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f, __p));
01617 }
01618 return __f.value();
01619 }
01620 }
01621
01637 template <class _Walker, class _Visitor, class _Predicate>
01638 typename _Visitor::return_value _recursive_preorder_walk_up_if(_Walker __w,
01639 _Visitor __f, _Predicate __p)
01640 {
01641 typename _Walker::parents_iterator __it, __e;
01642
01643 if(__w.is_ground())
01644 return __f.vvalue();
01645 __f.preorder(*__w);
01646 if(__p(*__w))
01647 {
01648 __e = __w.parent_end();
01649 for(__it = __w.parent_begin(); __it != __e; ++__it)
01650 __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f, __p));
01651 }
01652 return __f.value();
01653 }
01654
01667 template <class _Walker, class _Visitor>
01668 typename _Visitor::return_value recursive_postorder_walk_up(_Walker __w,
01669 _Visitor __f)
01670 {
01671 typename _Walker::parents_iterator __it, __e;
01672
01673 if(__w.is_sky())
01674 {
01675 __f.vinit();
01676 __e = __w.parent_end();
01677 for(__it = __w.parent_begin(); __it != __e; ++__it)
01678 __f.vcollect(_recursive_postorder_walk_up(__w<<__it, __f));
01679 return __f.vvalue();
01680 }
01681 else if(__w.is_ground())
01682 return __f.vvalue();
01683 else
01684 {
01685 __f.init();
01686 __e = __w.parent_end();
01687 for(__it = __w.parent_begin(); __it != __e; ++__it)
01688 __f.collect(*__w, _recursive_postorder_walk_up(__w<<__it, __f));
01689 __f.postorder(*__w);
01690 return __f.value();
01691 }
01692 }
01693
01707 template <class _Walker, class _Visitor>
01708 typename _Visitor::return_value _recursive_postorder_walk_up(_Walker __w,
01709 _Visitor __f)
01710 {
01711 typename _Walker::parents_iterator __it, __e;
01712
01713 if(__w.is_ground())
01714 return __f.vvalue();
01715 __f.init();
01716 __e = __w.parent_end();
01717 for(__it = __w.parent_begin(); __it != __e; ++__it)
01718 __f.collect(*__w, _recursive_postorder_walk_up(__w<<__it, __f));
01719 __f.postorder(*__w);
01720 return __f.value();
01721 }
01722
01738 template <class _Walker, class _Visitor, class _Predicate>
01739 typename _Visitor::return_value recursive_postorder_walk_up_if(_Walker __w,
01740 _Visitor __f, _Predicate __p)
01741 {
01742 typename _Walker::parents_iterator __it, __e;
01743
01744 if(__w.is_sky())
01745 {
01746 __f.vinit();
01747 __e = __w.parent_end();
01748 for(__it = __w.parent_begin(); __it != __e; ++__it)
01749 __f.vcollect(_recursive_postorder_walk_up(__w<<__it, __f, __p));
01750 return __f.vvalue();
01751 }
01752 else if(__w.is_ground())
01753 return __f.vvalue();
01754 else
01755 {
01756 __f.init();
01757 if(__p(*__w))
01758 {
01759 __e = __w.parent_end();
01760 for(__it = __w.parent_begin(); __it != __e; ++__it)
01761 __f.collect(*__w, _recursive_postorder_walk_up_if(__w<<__it, __f, __p));
01762 }
01763 __f.postorder(*__w);
01764 return __f.value();
01765 }
01766 }
01767
01783 template <class _Walker, class _Visitor, class _Predicate>
01784 typename _Visitor::return_value _recursive_postorder_walk_up_if(_Walker __w,
01785 _Visitor __f, _Predicate __p)
01786 {
01787 typename _Walker::parents_iterator __it, __e;
01788
01789 if(__w.is_ground())
01790 return __f.vvalue();
01791 __f.init();
01792 if(__p(*__w))
01793 {
01794 __e = __w.parent_end();
01795 for(__it = __w.parent_begin(); __it != __e; ++__it)
01796 __f.collect(*__w, _recursive_postorder_walk_up_if(__w<<__it, __f, __p));
01797 }
01798 __f.postorder(*__w);
01799 return __f.value();
01800 }
01801
01814 template <class _Walker, class _Visitor>
01815 typename _Visitor::return_value recursive_walk_up(_Walker __w, _Visitor __f)
01816 {
01817 typename _Walker::parents_iterator __it, __e;
01818
01819 if(__w.is_sky())
01820 {
01821 __e = __w.parent_end();
01822 __f.vinit();
01823 for(__it = __w.parent_begin(); __it != __e; ++__it)
01824 __f.vcollect(_recursive_walk_up(__w<<__it, __f));
01825 return __f.vvalue();
01826 }
01827 else if(__w.is_ground())
01828 return __f.vvalue();
01829 else
01830 {
01831 __f.preorder(*__w);
01832 __e = __w.parent_end();
01833 for(__it = __w.parent_begin(); __it != __e; ++__it)
01834 __f.collect(*__w, _recursive_walk_up(__w<<__it, __f));
01835 __f.postorder(*__w);
01836 return __f.value();
01837 }
01838 }
01839
01853 template <class _Walker, class _Visitor>
01854 typename _Visitor::return_value _recursive_walk_up(_Walker __w, _Visitor __f)
01855 {
01856 typename _Walker::parents_iterator __it, __e;
01857
01858 if(__w.is_ground())
01859 return __f.vvalue();
01860 __f.preorder(*__w);
01861 __e = __w.parent_end();
01862 for(__it = __w.parent_begin(); __it != __e; ++__it)
01863 __f.collect(*__w, _recursive_walk_up(__w<<__it, __f));
01864 __f.postorder(*__w);
01865 return __f.value();
01866 }
01867
01885 template <class _Walker, class _Visitor>
01886 typename _Visitor::return_value recursive_walk_up_if(_Walker __w, _Visitor __f)
01887 {
01888 typename _Walker::parents_iterator __it, __e;
01889
01890 if(__w.is_sky())
01891 {
01892 __e = __w.parent_end();
01893 __f.vinit();
01894 for(__it = __w.parent_begin(); __it != __e; ++__it)
01895 __f.vcollect(_recursive_walk_up_if(__w<<__it, __f));
01896 return __f.vvalue();
01897 }
01898 else if(__w.is_ground())
01899 return __f.vvalue();
01900 else
01901 {
01902 while(1)
01903 {
01904 if(__f.preorder(*__w))
01905 {
01906 __e = __w.parent_end();
01907 for(__it = __w.parent_begin(); __it != __e; ++__it)
01908 __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f));
01909 }
01910 if(!__f.postorder(*__w))
01911 break;
01912 }
01913 return __f.value();
01914 }
01915 }
01916
01935 template <class _Walker, class _Visitor>
01936 typename _Visitor::return_value _recursive_walk_up_if(_Walker __w, _Visitor __f)
01937 {
01938 typename _Walker::parents_iterator __it, __e;
01939
01940 if(__w.is_ground())
01941 return __f.vvalue();
01942 while(1)
01943 {
01944 if(__f.preorder(*__w))
01945 {
01946 __e = __w.parent_end();
01947 for(__it = __w.parent_begin(); __it != __e; ++__it)
01948 __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f));
01949 }
01950 if(!__f.postorder(*__w))
01951 break;
01952 }
01953 return __f.value();
01954 }
01955
01973 template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
01974 typename _Visitor::return_value recursive_walk_up_if(_Walker __w, _Visitor __f,
01975 _Predicate1 __p1, _Predicate2 __p2)
01976 {
01977 typename _Walker::parents_iterator __it, __e;
01978
01979 if(__w.is_sky())
01980 {
01981 __e = __w.parent_end();
01982 __f.vinit();
01983 for(__it = __w.parent_begin(); __it != __e; ++__it)
01984 __f.vcollect(_recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
01985 return __f.vvalue();
01986 }
01987 else if(__w.is_ground())
01988 return __f.vvalue();
01989 else
01990 {
01991 while(1)
01992 {
01993 __f.preorder(*__w);
01994 if(__p1(*__w))
01995 {
01996 __e = __w.parent_end();
01997 for(__it = __w.parent_begin(); __it != __e; ++__it)
01998 __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
01999 }
02000 __f.postorder(*__w);
02001 if(!__p2(*__w))
02002 break;
02003 }
02004 return __f.value();
02005 }
02006 }
02007
02026 template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
02027 typename _Visitor::return_value _recursive_walk_up_if(_Walker __w, _Visitor __f,
02028 _Predicate1 __p1, _Predicate2 __p2)
02029 {
02030 typename _Walker::parents_iterator __it, __e;
02031
02032 if(__w.is_ground())
02033 return __f.vvalue();
02034 while(1)
02035 {
02036 __f.preorder(*__w);
02037 if(__p1(*__w))
02038 {
02039 __e = __w.parent_end();
02040 for(__it = __w.parent_begin(); __it != __e; ++__it)
02041 __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
02042 }
02043 __f.postorder(*__w);
02044 if(!__p2(*__w))
02045 break;
02046 }
02047 return __f.value();
02048 }
02049
02064 template <class _Walker, class _Visitor>
02065 typename _Visitor::return_value recursive_cached_walk_up(_Walker __w,
02066 _Visitor __f)
02067 {
02068 typename _Walker::parents_iterator __it, __e;
02069
02070 if(__w.is_sky())
02071 {
02072 __e = __w.parent_end();
02073 __f.vinit();
02074 for(__it = __w.parent_begin(); __it != __e; ++__it)
02075 __f.vcollect(_recursive_cached_walk_up(__w<<__it, __f));
02076 return __f.vvalue();
02077 }
02078 else if(__w.is_ground())
02079 return __f.vvalue();
02080 else
02081 {
02082 if(__f.preorder(*__w))
02083 {
02084 __e = __w.parent_end();
02085 for(__it = __w.parent_begin(); __it != __e; ++__it)
02086 __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f));
02087 }
02088 __f.postorder(*__w);
02089 return __f.value();
02090 }
02091 }
02092
02108 template <class _Walker, class _Visitor>
02109 typename _Visitor::return_value _recursive_cached_walk_up(_Walker __w,
02110 _Visitor __f)
02111 {
02112 typename _Walker::parents_iterator __it, __e;
02113
02114 if(__w.is_ground())
02115 return __f.vvalue();
02116 if(__f.preorder(*__w))
02117 {
02118 __e = __w.parent_end();
02119 for(__it = __w.parent_begin(); __it != __e; ++__it)
02120 __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f));
02121 }
02122 __f.postorder(*__w);
02123 return __f.value();
02124 }
02125
02141 template <class _Walker, class _Visitor>
02142 typename _Visitor::return_value recursive_multi_walk_up(_Walker __w,
02143 _Visitor __f)
02144 {
02145 typename _Walker::parents_iterator __it, __e;
02146
02147 if(__w.is_sky())
02148 {
02149 __e = __w.parent_end();
02150 __f.vinit();
02151 for(__it = __w.parent_begin(); __it != __e; ++__it)
02152 __f.vcollect(_recursive_multi_walk_up(__w<<__it, __f));
02153 return __f.vvalue();
02154 }
02155 else if(__w.is_ground())
02156 return __f.vvalue();
02157 else
02158 {
02159 while(1)
02160 {
02161 __f.preorder(*__w);
02162 __e = __w.parent_end();
02163 for(__it = __w.parent_begin(); __it != __e; ++__it)
02164 __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
02165 if(!__f.postorder(*__w))
02166 break;
02167 }
02168 return __f.value();
02169 }
02170 }
02171
02188 template <class _Walker, class _Visitor>
02189 typename _Visitor::return_value _recursive_multi_walk_up(_Walker __w,
02190 _Visitor __f)
02191 {
02192 typename _Walker::parents_iterator __it, __e;
02193
02194 if(__w.is_ground())
02195 return __f.vvalue();
02196 while(1)
02197 {
02198 __f.preorder(*__w);
02199 __e = __w.parent_end();
02200 for(__it = __w.parent_begin(); __it != __e; ++__it)
02201 __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
02202 if(!__f.postorder(*__w))
02203 break;
02204 }
02205 return __f.value();
02206 }
02207
02222 template <class _Walker, class _Visitor, class _Predicate>
02223 typename _Visitor::return_value recursive_cached_walk_up(_Walker __w,
02224 _Visitor __f, _Predicate __p)
02225 {
02226 typename _Walker::parents_iterator __it, __e;
02227
02228 if(__w.is_sky())
02229 {
02230 __e = __w.parent_end();
02231 __f.vinit();
02232 for(__it = __w.parent_begin(); __it != __e; ++__it)
02233 __f.vcollect(_recursive_cached_walk_up(__w<<__it, __f, __p));
02234 return __f.vvalue();
02235 }
02236 else if(__w.is_ground())
02237 return __f.vvalue();
02238 else
02239 {
02240 __f.preorder(*__w);
02241 if(__p(*__w))
02242 {
02243 __e = __w.parent_end();
02244 for(__it = __w.parent_begin(); __it != __e; ++__it)
02245 __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f, __p));
02246 }
02247 __f.postorder(*__w);
02248 return __f.value();
02249 }
02250 }
02251
02267 template <class _Walker, class _Visitor, class _Predicate>
02268 typename _Visitor::return_value _recursive_cached_walk_up(_Walker __w,
02269 _Visitor __f, _Predicate __p)
02270 {
02271 typename _Walker::parents_iterator __it, __e;
02272
02273 if(__w.is_ground())
02274 return __f.vvalue();
02275 __f.preorder(*__w);
02276 if(__p(*__w))
02277 {
02278 __e = __w.parent_end();
02279 for(__it = __w.parent_begin(); __it != __e; ++__it)
02280 __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f, __p));
02281 }
02282 __f.postorder(*__w);
02283 return __f.value();
02284 }
02285
02301 template <class _Walker, class _Visitor, class _Predicate>
02302 typename _Visitor::return_value recursive_multi_walk_up(_Walker __w,
02303 _Visitor __f, _Predicate __p)
02304 {
02305 typename _Walker::parents_iterator __it, __e;
02306
02307
02308 if(__w.is_sky())
02309 {
02310 __e = __w.parent_end();
02311 __f.vinit();
02312 for(__it = __w.parent_begin(); __it != __e; ++__it)
02313 __f.vcollect(_recursive_multi_walk_up(__w<<__it, __f, __p));
02314 return __f.vvalue();
02315 }
02316 else if(__w.is_ground())
02317 return __f.vvalue();
02318 else
02319 {
02320 while(1)
02321 {
02322 __f.preorder(*__w);
02323 __e = __w.parent_end();
02324 for(__it = __w.parent_begin(); __it != __e; ++__it)
02325 __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f, __p));
02326 __f.postorder(*__w);
02327 if(!__p(*__w))
02328 break;
02329 }
02330 return __f.value();
02331 }
02332 }
02333
02350 template <class _Walker, class _Visitor, class _Predicate>
02351 typename _Visitor::return_value _recursive_multi_walk_up(_Walker __w,
02352 _Visitor __f, _Predicate __p)
02353 {
02354 typename _Walker::parents_iterator __it, __e;
02355
02356
02357 if(__w.is_ground())
02358 return __f.vvalue();
02359 while(1)
02360 {
02361 __f.preorder(*__w);
02362 __e = __w.parent_end();
02363 for(__it = __w.parent_begin(); __it != __e; ++__it)
02364 __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
02365 __f.postorder(*__w);
02366 if(!__p(*__w))
02367 break;
02368 }
02369 return __f.value();
02370 }
02371
02388 template <class _Walker, class _Visitor>
02389 typename _Visitor::return_value general_directed_walk(_Walker __w, _Visitor __f)
02390 {
02391 _Walker __n;
02392
02393 while(__f.analyze(__w))
02394 {
02395 __f.preorder(*__w);
02396 if(__f.walk_up())
02397 __n = __w<<__f.up();
02398 else
02399 __n = __w<<__f.down();
02400 __f.postorder(*__w);
02401 __w = __n;
02402 }
02403 return __f.value();
02404 }
02405
02417 template <class _Walker, class _Visitor>
02418 typename _Visitor::return_value general_directed_walk_down(_Walker __w,
02419 _Visitor __f)
02420 {
02421 _Walker __n;
02422
02423 while(__f.analyze(__w))
02424 {
02425 __f.preorder(*__w);
02426 __n = __w<<__f.down();
02427 __f.postorder(*__w);
02428 __w = __n;
02429 }
02430 return __f.value();
02431 }
02432
02444 template <class _Walker, class _Visitor>
02445 typename _Visitor::return_value general_directed_walk_up(_Walker __w,
02446 _Visitor __f)
02447 {
02448 _Walker __n;
02449
02450 while(__f.analyze(__w))
02451 {
02452 __f.preorder(*__w);
02453 __n = __w<<__f.up();
02454 __f.postorder(*__w);
02455 __w = __n;
02456 }
02457 return __f.value();
02458 }
02459
02477 template <class _Walker, class _Visitor>
02478 typename _Visitor::return_value recursive_general_directed_walk(_Walker __w,
02479 _Visitor __f)
02480 {
02481 __f.preorder(*__w);
02482 while(__f.analyze(__w))
02483 {
02484 if(__f.walk_up())
02485 __f.collect(*__w, recursive_general_directed_walk(__w<<__f.up(), __f),
02486 true);
02487 else
02488 __f.collect(*__w, recursive_general_directed_walk(__w<<__f.down(), __f),
02489 false);
02490 }
02491 __f.postorder(*__w);
02492 return __f.value();
02493 }
02494
02507 template <class _Walker, class _Visitor>
02508 typename _Visitor::return_value recursive_general_directed_walk_down(
02509 _Walker __w, _Visitor __f)
02510 {
02511 __f.preorder(*__w);
02512 while(__f.analyze(__w))
02513 {
02514 __f.collect(*__w, recursive_general_directed_walk_down(__w<<__f.down(), __f));
02515 }
02516 __f.postorder(*__w);
02517 return __f.value();
02518 }
02519
02532 template <class _Walker, class _Visitor>
02533 typename _Visitor::return_value recursive_general_directed_walk_up(_Walker __w,
02534 _Visitor __f)
02535 {
02536 __f.preorder(*__w);
02537 while(__f.analyze(__w))
02538 {
02539 __f.collect(*__w, recursive_general_directed_walk_up(__w>>__f.up(), __f));
02540 }
02541 __f.postorder(*__w);
02542 return __f.value();
02543 }
02544
02556 template <class _Walker, class _Visitor>
02557 typename _Visitor::return_value general_walk(_Walker __w, _Visitor __f)
02558 {
02559 _Walker __n;
02560
02561 while(__f.analyze(__w))
02562 {
02563 __f.preorder(*__w);
02564 __n = __w>>__f.next();
02565 __f.postorder(*__w);
02566 __w = __n;
02567 }
02568 return __f.value();
02569 }
02570
02583 template <class _Walker, class _Visitor>
02584 typename _Visitor::return_value recursive_general_walk(_Walker __w,
02585 _Visitor __f)
02586 {
02587 __f.preorder(*__w);
02588 while(__f.analyze(__w))
02589 __f.collect(*__w, recursive_general_walk(__w>>__f.next(), __f));
02590 __f.postorder(*__w);
02591 return __f.value();
02592 }
02593
02594 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
02595 #pragma reset woff 1209
02596 #endif
02597
02598 __VGTL_END_NAMESPACE
02599
02600 #endif
02601
02602
02603
02604