Generic algorithms for external use


Functions

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_safe_walk_if (_Walker __w, _Visitor __f)
template<class _IterativeWalker , class _Function >
_Function walk (_IterativeWalker __first, _IterativeWalker __last, _Function __f)
template<class _PrePostWalker , class _Function >
_Function pre_post_walk (_PrePostWalker __first, _PrePostWalker __last, _Function __f)
template<class _PrePostWalker , class _Function1 , class _Function2 >
_Function2 pre_post_walk (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2)
template<class _PrePostWalker , class _Function >
_Function var_walk (_PrePostWalker __first, _PrePostWalker __last, _Function __f)
template<class _PrePostWalker , class _Function1 , class _Function2 >
_Function2 var_walk (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2)
template<class _PrePostWalker , class _Function , class _Predicate >
_Function walk_if (_PrePostWalker __first, _PrePostWalker __last, _Function __f, _Predicate __pred)
template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 walk_if (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2, _Predicate __pred)
template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate1 , class _Predicate2 >
_Function2 walk_if (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2, _Predicate1 __pred1, _Predicate2 __pred2)
template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 cached_walk_if (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2, _Predicate __pred)
template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 multi_walk_if (_PrePostWalker __first, _PrePostWalker __last, _Function1 __f1, _Function2 __f2, _Predicate __pred)
template<class _Walker , class _Function >
_Function walk_up (_Walker __w, _Function __f)
template<class _Walker , class _Function >
_Function var_walk_up (_Walker __w, _Function __f)
template<class _Walker , class _Function , class _Predicate >
_Function walk_up_if (_Walker __w, _Function __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_postorder_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_if (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_preorder_walk_if (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_postorder_walk_if (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_if (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_cached_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_multi_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate1 , class _Predicate2 >
_Visitor::return_value recursive_walk_if (_Walker __w, _Visitor __f, _Predicate1 __p1, _Predicate2 __p2)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_cached_walk (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_multi_walk (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_up_if (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_preorder_walk_up_if (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_postorder_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_postorder_walk_up_if (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_up_if (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate1 , class _Predicate2 >
_Visitor::return_value recursive_walk_up_if (_Walker __w, _Visitor __f, _Predicate1 __p1, _Predicate2 __p2)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_cached_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_multi_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_cached_walk_up (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_multi_walk_up (_Walker __w, _Visitor __f, _Predicate __p)
template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk_down (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk_down (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk_up (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value general_walk (_Walker __w, _Visitor __f)
template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_walk (_Walker __w, _Visitor __f)
template<class _BidirIter , class _Tp >
_BidirIter rfind (_BidirIter __first, _BidirIter __last, const _Tp &__val)
template<class _BidirIter , class _Predicate >
_BidirIter rfind_if (_BidirIter __first, _BidirIter __last, _Predicate __pred)
template<class _Walker , class _Test >
void recursive_consistency_test (_Walker __w, const _Test &__t)

Detailed Description

The generic functions in this section are for external use.

Function Documentation

template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 cached_walk_if ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2,
_Predicate  __pred 
) [inline]

this tree walk is a pre+post walk, calling two functions at every node, one in the preorder and the other in the postorder visit. If the function returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 394 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • analyze is called before walking for every virtual node. While this function returns true, the walk goes on.
  • preorder is called before a walk direction is being decided.
  • postorder is called after the walk dircetion has been found.
  • walk_up shall return whether the next step of the walk is upwards or downwards.
  • up is called for an upwards step and decides which in-edge to take.
  • down is called for a downwards step and decides which out-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2390 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk_down ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • analyze is called before walking for every virtual node. While this function returns true, the walk goes on.
  • preorder is called before a walk direction is being decided.
  • postorder is called after the walk dircetion has been found.
  • down is called to decide which out-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2419 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value general_directed_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • analyze is called before walking for every virtual node. While this function returns true, the walk goes on.
  • preorder is called before a walk direction is being decided.
  • postorder is called after the walk dircetion has been found.
  • up is called to decide which in-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2446 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value general_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a general walk starting at __w. At every node various methods of the visitor __f are called:

  • analyze is called before walking for every virtual node. While this function returns true, the walk goes on.
  • preorder is called before a walk direction is being decided.
  • postorder is called after the walk dircetion has been found.
  • next is called to decide which edge to follow.
  • value is called to compute the return value for this node.

Definition at line 2558 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 multi_walk_if ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2,
_Predicate  __pred 
) [inline]

this tree walk is a pre+post walk, calling two functions at every node, one in the preorder and the other in the postorder visit. If the function returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 427 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function1 , class _Function2 >
_Function2 pre_post_walk ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2 
) [inline]

make a pre and post order tree walk, calling two different functions, one in the preorder step, the other in the postorder step.

Definition at line 224 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function >
_Function pre_post_walk ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function  __f 
) [inline]

make a pre and post order tree walk, calling a function for every node.

Definition at line 206 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_cached_walk ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If then predicate __p returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited.
  • value is called to compute the return value for this node

Definition at line 1297 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_cached_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If it returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited.
  • value is called to compute the return value for this node

Definition at line 1048 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_cached_walk_up ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If then predicate __p returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited.
  • value is called to compute the return value for this node

Definition at line 2224 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_cached_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If it returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited.
  • value is called to compute the return value for this node

Definition at line 2066 of file vgtl_algo.h.

template<class _Walker , class _Test >
void recursive_consistency_test ( _Walker  __w,
const _Test &  __t 
) [inline]

perform a consistency test of the tree or DAG.

Definition at line 49 of file vgtl_test.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • preorder is called before any child is visited
  • analyze is called everytime before a child node might be vistied. While this function returns true, the walk goes on at this node.
  • collect is called everytime a child has finished.
  • postorder is called after the walk dircetion has been found.
  • walk_up shall return whether the next step of the walk is upwards or downwards.
  • up is called for an upwards step and decides which in-edge to take.
  • down is called for a downwards step and decides which out-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2479 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk_down ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • preorder is called before any child is visited
  • analyze is called everytime before a child node might be vistied. While this function returns true, the walk goes on at this node.
  • collect is called everytime a child has finished.
  • postorder is called after the walk dircetion has been found.
  • down is called to decide which out-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2509 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_directed_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive general directed walk starting at __w. At every node various methods of the visitor __f are called:

  • preorder is called before any child is visited
  • analyze is called everytime before a child node might be vistied. While this function returns true, the walk goes on at this node.
  • collect is called everytime a child has finished.
  • postorder is called after the walk dircetion has been found.
  • up is called to decide which in-edge to take.
  • value is called to compute the return value for this node.

Definition at line 2534 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_general_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive general walk starting at __w. At every node various methods of the visitor __f are called:

  • preorder is called before any child is visited
  • analyze is called everytime before a child node might be vistied. While this function returns true, the walk goes on at this node.
  • collect is called everytime a child has finished.
  • postorder is called after the walk dircetion has been found.
  • next is called to decide which edge to follow.
  • value is called to compute the return value for this node.

Definition at line 2585 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_multi_walk ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If the predicate __p returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 1376 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_multi_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If it returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 1124 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_multi_walk_up ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If the predicate __p returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 2303 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_multi_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If it returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 2143 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_postorder_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive postorder walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • init is called before the children are visited
  • collect is called everytime a child has finished
  • postorder is called after all children have finished
  • value is called to compute the return value for this node

Definition at line 596 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_postorder_walk_if ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive postorder walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • init is called before the children are visited. Then the predicate is called. If this predicate returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • postorder is called after all children have been visited.
  • collect is called everytime a child has finished.
  • value is called to compute the return value for this node.

Definition at line 881 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_postorder_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive postorder walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • init is called before the children are visited
  • collect is called everytime a child has finished
  • postorder is called after all children have finished
  • value is called to compute the return value for this node

Definition at line 1669 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_postorder_walk_up_if ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive postorder walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • init is called before the children are visited. Then the predicate is called. If this predicate returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • postorder is called after all children have been visited.
  • collect is called everytime a child has finished.
  • value is called to compute the return value for this node.

Definition at line 1740 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive preorder walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 531 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_preorder_walk_if ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive preorder walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. Then the predicate is called. If this predicate returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 804 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_if ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive preorder walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If this function returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 731 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive preorder walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 1456 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate >
_Visitor::return_value recursive_preorder_walk_up_if ( _Walker  __w,
_Visitor  __f,
_Predicate  __p 
) [inline]

perform a recursive preorder walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. Then the predicate is called. If this predicate returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 1595 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_preorder_walk_up_if ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive preorder walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If this function returns true, the children are visited. Otherwise, the node is treated as if it was a terminal node.
  • collect is called everytime a child has finished
  • value is called to compute the return value for this node

Definition at line 1522 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_safe_walk_if ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited. If it returns true, the children are visited. If it returns false, the children are ignored.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If it returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 59 of file vgtl_addalgo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited
  • collect is called everytime a child has finished
  • postorder is called after all children have been visited
  • value is called to compute the return value for this node

Definition at line 664 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate1 , class _Predicate2 >
_Visitor::return_value recursive_walk_if ( _Walker  __w,
_Visitor  __f,
_Predicate1  __p1,
_Predicate2  __p2 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If then predicate p1 returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited. If then predicate p2 returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node

Definition at line 1206 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_if ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited. If it returns true, the children are visited. If it returns false, the children are ignored.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If it returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 963 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_up ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited
  • collect is called everytime a child has finished
  • postorder is called after all children have been visited
  • value is called to compute the return value for this node

Definition at line 1816 of file vgtl_algo.h.

template<class _Walker , class _Visitor , class _Predicate1 , class _Predicate2 >
_Visitor::return_value recursive_walk_up_if ( _Walker  __w,
_Visitor  __f,
_Predicate1  __p1,
_Predicate2  __p2 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node
  • vcollect is called after a child of a virtual node has finished
  • vvalue is called to compute the return value of a virtual node
  • preorder is called before the children are visited. If then predicate p1 returns true, the children are visited. If it returns false, the children are ignored
  • collect is called everytime a child has finished
  • postorder is called after the children have been visited. If then predicate p2 returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node

Definition at line 1975 of file vgtl_algo.h.

template<class _Walker , class _Visitor >
_Visitor::return_value recursive_walk_up_if ( _Walker  __w,
_Visitor  __f 
) [inline]

perform a recursive pre+post order walk towards the root starting at __w. At every node various methods of the visitor __f are called:

  • vinit is called before walking for every virtual node.
  • vcollect is called after a child of a virtual node has finished.
  • vvalue is called to compute the return value of a virtual node.
  • preorder is called before the children are visited. If it returns true, the children are visited. If it returns false, the children are ignored.
  • collect is called everytime a child has finished.
  • postorder is called after the children have been visited. If it returns true, the walk is continued by switching back to preorder mode for this node. If it returns false, the walk is over for this node.
  • value is called to compute the return value for this node.

Definition at line 1887 of file vgtl_algo.h.

template<class _BidirIter , class _Tp >
_BidirIter rfind ( _BidirIter  __first,
_BidirIter  __last,
const _Tp &  __val 
) [inline]

Find the last occurrence of a value in a sequence.

Parameters:
__first An input iterator.
__last An input iterator.
__val The value to find.
Returns:
The last iterator i in the range [__first,__last) such that *i == val, or __last if no such iterator exists.

Definition at line 192 of file vgtl_helpers.h.

template<class _BidirIter , class _Predicate >
_BidirIter rfind_if ( _BidirIter  __first,
_BidirIter  __last,
_Predicate  __pred 
) [inline]

Find the last element in a sequence for which a predicate is true.

Parameters:
__first An input iterator.
__last An input iterator.
__pred A predicate.
Returns:
The last iterator i in the range [__first,__last) such that __pred(*i) is true, or __last if no such iterator exists.

Definition at line 208 of file vgtl_helpers.h.

template<class _PrePostWalker , class _Function1 , class _Function2 >
_Function2 var_walk ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2 
) [inline]

this tree walk is a pre+post walk, calling two functions at every node, one in the preorder and the other in the postorder step. If the function returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 271 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function >
_Function var_walk ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function  __f 
) [inline]

this tree walk is a pre+post walk, calling a function at every node. If the function returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 248 of file vgtl_algo.h.

template<class _Walker , class _Function >
_Function var_walk_up ( _Walker  __w,
_Function  __f 
) [inline]

this tree walk is a pre+post walk towards the root, calling a function at every node. If the function returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 476 of file vgtl_algo.h.

template<class _IterativeWalker , class _Function >
_Function walk ( _IterativeWalker  __first,
_IterativeWalker  __last,
_Function  __f 
) [inline]

make a pre or post order tree walk, calling a function for every node it is also possible to perform a pre+post order walk. In that case the function _f must distinguish between the two calls by itself.

Definition at line 191 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate1 , class _Predicate2 >
_Function2 walk_if ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2,
_Predicate1  __pred1,
_Predicate2  __pred2 
) [inline]

this tree walk is a pre+post walk, calling two functions at every node, one in the preorder and the other in the postorder visit. If the predicates return true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks. Predicate pred1 is called in the preorder phase, predicate pred2 in the postorder phase.

Definition at line 356 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function1 , class _Function2 , class _Predicate >
_Function2 walk_if ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function1  __f1,
_Function2  __f2,
_Predicate  __pred 
) [inline]

this tree walk is a pre+post walk, calling two functions at every node, one in the preorder and the other in the postorder visit. If the predicate returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 323 of file vgtl_algo.h.

template<class _PrePostWalker , class _Function , class _Predicate >
_Function walk_if ( _PrePostWalker  __first,
_PrePostWalker  __last,
_Function  __f,
_Predicate  __pred 
) [inline]

this tree walk is a pre+post walk, calling a function at every node. If the predicate returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 296 of file vgtl_algo.h.

template<class _Walker , class _Function >
_Function walk_up ( _Walker  __w,
_Function  __f 
) [inline]

make a pre or post order tree walk towards the root node, calling a function for every node it is also possible to perform a pre+post order walk. In that case the function _f must distinguish between the two calls by itself.

Definition at line 456 of file vgtl_algo.h.

template<class _Walker , class _Function , class _Predicate >
_Function walk_up_if ( _Walker  __w,
_Function  __f,
_Predicate  __p 
) [inline]

this tree walk is a pre+post walk towards the root, calling a function at every node. If the predicate returns true, the status of the walker is flipped from pre to post (or vice versa). If the status is changed from pre to post, the subtree originating from the current position is not visited, if the status change is the other way round, it is revisited. This allows for cached or partially multi pass walks.

Definition at line 497 of file vgtl_algo.h.

Generated on Tue Feb 9 14:42:14 2010 for Vienna Graph Template Library by  doxygen 1.5.8