boost/graph/tree_traits.hpp

0001 //  (C) Copyright Jeremy Siek 1999.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_TREE_STRUCTURE_HPP
0007 #define BOOST_TREE_STRUCTURE_HPP
0008
0009 #include <boost/tuple/tuple.hpp> //For boost::tie()
0010
0011 namespace boost
0012 {
0013
0014 template < class T > struct tree_traits
0015 {
0016     typedef typename T::node_descriptor node_descriptor;
0017     typedef typename T::children_iterator children_iterator;
0018 };
0019
0020 template < class Tree, class TreeVisitor >
0021 void traverse_tree(typename tree_traits< Tree >::node_descriptor v, Tree& t,
0022     TreeVisitor visitor)
0023 {
0024     visitor.preorder(v, t);
0025     typename tree_traits< Tree >::children_iterator i, end;
0026     boost::tie(i, end) = children(v, t);
0027     if (i != end)
0028     {
0029         traverse_tree(*i++, t, visitor);
0030         visitor.inorder(v, t);
0031         while (i != end)
0032             traverse_tree(*i++, t, visitor);
0033     }
0034     else
0035         visitor.inorder(v, t);
0036     visitor.postorder(v, t);
0037 }
0038
0039 struct null_tree_visitor
0040 {
0041     template < typename Node, typename Tree > void preorder(Node, Tree&) {}
0042     template < typename Node, typename Tree > void inorder(Node, Tree&) {}
0043     template < typename Node, typename Tree > void postorder(Node, Tree&) {}
0044 };
0045
0046 } /* namespace boost */
0047
0048 #endif /* BOOST_TREE_STRUCTURE_HPP */