Vienna Graph Template Library: vgtl

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