Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

_Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node > Class Template Reference
[Classes and types for internal use]

automatic tree walkers More...

#include <vgtl_tree.h>

Inheritance diagram for _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >:

Inheritance graph
[legend]
Collaboration diagram for _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef _Tp value_type
typedef _Ptr pointer
typedef _Ref reference
typedef __one_iterator< void * > parents_iterator
typedef _Ctr_iterator children_iterator
typedef _Node node_type
typedef size_t size_type
typedef ptrdiff_t difference_type

Public Methods

 _Tree_walker ()
 _Tree_walker (_Node *__x, int order=(_C_W_preorder|_C_W_postorder), bool front_to_back=true, bool depth_first=true, bool find_start=true)
 _Tree_walker (const walker &__x)
_Self operator<< (const parents_iterator &__dummy)
 go to parent operator

_Self operator>> (const children_iterator &__i)
 go to child operator

_Self & operator<<= (const parents_iterator &__dummy)
_Self & operator>>= (const children_iterator &__i)
_Self & operator~ ()
_Self & operator= (const _Itr &__x)
bool in_preorder ()
reference operator * () const
pointer operator-> () const
ctree_data_hook & data_hook ()
ctree_data_hook & parent_data_hook ()
const _Node * parent ()
const _Node * node ()
size_type n_children ()
size_type n_parents ()
bool is_leaf ()
bool is_root ()
bool is_ground ()
bool is_sky ()
children_iterator child_begin ()
children_iterator child_end ()
parents_iterator parent_begin ()
parents_iterator parent_end ()
template<class _Function> _Function for_each_child (_Function __f)
template<class _Function> _Function for_each_parent (_Function __f)
template<class Compare> void sort_children (children_iterator first, children_iterator last, Compare comp)
template<class Compare> void sort_children (Compare comp)
template<class Compare> void sort_parents (parents_iterator first, parents_iterator last, Compare comp)
template<class Compare> void sort_parents (Compare comp)
bool operator== (const _Self &__x) const
bool operator!= (const _Self &__x) const
_Self & operator++ ()
_Self operator++ (int)
_Self & operator-- ()
_Self operator-- (int)

Public Attributes

struct {
} _C_w_t
bool _C_w_in_preorder
std::vector< _Iterator > _C_w_cur_it
_Node * _C_w_cur

Detailed Description

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
class _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >

This is the class defining automatic (iterative) tree walkers, which walk trees without guidance.

Definition at line 359 of file vgtl_tree.h.

Member Typedef Documentation

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef _Ctr_iterator _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::children_iterator [inherited]
 

standard walker definition

Definition at line 242 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef ptrdiff_t _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::difference_type [inherited]
 

standard walker definition

Definition at line 246 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef _Node _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::node_type [inherited]
 

standard walker definition

Definition at line 243 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef __one_iterator<void *> _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::parents_iterator [inherited]
 

standard walker definition

Definition at line 241 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef _Ptr _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::pointer [inherited]
 

standard walker definition

Definition at line 232 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef _Ref _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::reference [inherited]
 

standard walker definition

Definition at line 233 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef size_t _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::size_type [inherited]
 

standard walker definition

Definition at line 245 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
typedef _Tp _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::value_type [inherited]
 

standard walker definition

Definition at line 231 of file vgtl_tree.h.

Constructor & Destructor Documentation

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_Tree_walker (    )  [inline]
 

standard constructor

Definition at line 380 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_Tree_walker (  _Node *    __x,
int    order = (_C_W_preorder|_C_W_postorder),
bool    front_to_back = true,
bool    depth_first = true,
bool    find_start = true
)  [inline]
 

This is the main constructor for an automatic walker. It sets the starting position and, optionally, the walker type.

Definition at line 405 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_Tree_walker (  const walker &    __x )  [inline]
 

copy constructor

Definition at line 422 of file vgtl_tree.h.

Member Function Documentation

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
children_iterator _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::child_begin (    )  [inline, inherited]
 

return children_iterator to first child

Definition at line 306 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
children_iterator _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::child_end (    )  [inline, inherited]
 

return children_iterator beyond last child

Definition at line 308 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
ctree_data_hook& _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::data_hook (    )  [inline, inherited]
 

retrieve the data hook

Definition at line 279 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class _Function>
_Function _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::for_each_child (  _Function    __f )  [inline, inherited]
 

apply the function __f to all children

Definition at line 319 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class _Function>
_Function _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::for_each_parent (  _Function    __f )  [inline, inherited]
 

apply the function __f to all parents

Definition at line 325 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::in_preorder (    )  [inline]
 

are we in the preorder phase of a pre+post walk?

Definition at line 586 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::is_ground (    )  [inline, inherited]
 

is this node a virtual node - the ground (below all roots)?

Definition at line 301 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::is_leaf (    )  [inline, inherited]
 

is this node a leaf?

Definition at line 295 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::is_root (    )  [inline, inherited]
 

is this node a root?

Definition at line 297 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::is_sky (    )  [inline, inherited]
 

is this node a virtual node - the sky (above all leafs)?

Definition at line 303 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
size_type _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::n_children (    )  [inline, inherited]
 

return the number of children

Definition at line 290 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
size_type _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::n_parents (    )  [inline, inherited]
 

return the number of parents (0 or 1)

Definition at line 292 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
const _Node* _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::node (    )  [inline, inherited]
 

retrieve the full node

Definition at line 287 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
reference _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator * (    )  const [inline, inherited]
 

dereference operator

Definition at line 264 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator!= (  const _Self &    __x )  const [inline]
 

comparison operator

Definition at line 438 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator++ (  int    )  [inline]
 

in(de)crement operator

Definition at line 473 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator++ (    )  [inline]
 

in(de)crement operator

Definition at line 451 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator-- (  int    )  [inline]
 

in(de)crement operator

Definition at line 501 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator-- (    )  [inline]
 

in(de)crement operator

Definition at line 479 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
pointer _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator-> (    )  const [inline, inherited]
 

pointer operator

Definition at line 268 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator<< (  const parents_iterator &    __dummy )  [inline]
 

This operator moves the walker to the parent

Definition at line 510 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator<<= (  const parents_iterator &    __dummy )  [inline]
 

go to parent assignment operator

Definition at line 541 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator= (  const _Itr &    __x )  [inline]
 

assignment from iterator

Reimplemented from _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >.

Definition at line 576 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator== (  const _Self &    __x )  const [inline]
 

comparison operator

Definition at line 430 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator>> (  const children_iterator &    __i )  [inline]
 

This operator moves the walker to the child pointed to by __i

Definition at line 530 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator>>= (  const children_iterator &    __i )  [inline]
 

go to child assignment operator

Definition at line 559 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Self& _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::operator~ (    )  [inline]
 

switch from preorder to postorder phase

Definition at line 569 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
const _Node* _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::parent (    )  [inline, inherited]
 

retrieve the parent node

Definition at line 285 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
parents_iterator _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::parent_begin (    )  [inline, inherited]
 

return parents_iterator to first parent (the parent)

Definition at line 311 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
ctree_data_hook& _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::parent_data_hook (    )  [inline, inherited]
 

retrieve the parent's data hook

Definition at line 281 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
parents_iterator _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::parent_end (    )  [inline, inherited]
 

return parents_iterator beyond last parent

Definition at line 314 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class Compare>
void _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::sort_children (  Compare    comp )  [inline, inherited]
 

sort all children according to comp

Definition at line 343 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class Compare>
void _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::sort_children (  children_iterator    first,
children_iterator    last,
Compare    comp
)  [inline, inherited]
 

sort the children in the range [first,last) according to comp

Definition at line 332 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class Compare>
void _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::sort_parents (  Compare    comp )  [inline, inherited]
 

sort all parents according to comp (NOP = do nothing)

Definition at line 348 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
template<class Compare>
void _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::sort_parents (  parents_iterator    first,
parents_iterator    last,
Compare    comp
)  [inline, inherited]
 

sort the parents in the range [first,last) according to comp (NOP)

Definition at line 338 of file vgtl_tree.h.

Member Data Documentation

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
_Node* _Tree_walker_base< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_C_w_cur [inherited]
 

pointer to the current node

Definition at line 251 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
std::vector<_Iterator> _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_C_w_cur_it
 

internal stack

Definition at line 376 of file vgtl_tree.h.

template<class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator, class _Node>
bool _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_C_w_in_preorder
 

walker is in preorder mode?

Definition at line 374 of file vgtl_tree.h.

struct { ... } _Tree_walker< _Tp, _Ref, _Ptr, _Ctr, _Iterator, _Node >::_C_w_t
 

walker type (order, front to back/back to front, depth/breath first

The documentation for this class was generated from the following files:
Generated on Tue Nov 4 01:41:42 2003 for Vienna Graph Template Library by doxygen1.2.18