1 // (C) Copyright Jeremy Siek 1999. 2 // Distributed under the Boost Software License, Version 1.0. (See 3 // accompanying file LICENSE_1_0.txt or copy at 4 // http://www.boost.org/LICENSE_1_0.txt) 5 6 #ifndef BOOST_TREE_STRUCTURE_HPP 7 #define BOOST_TREE_STRUCTURE_HPP 8 9 #include <boost/tuple/tuple.hpp> //For boost::tie() 10 11 namespace boost { 12 13 template <class T> 14 struct tree_traits { 15 typedef typename T::node_descriptor node_descriptor; 16 typedef typename T::children_iterator children_iterator; 17 }; 18 19 20 template <class Tree, class TreeVisitor> traverse_tree(typename tree_traits<Tree>::node_descriptor v,Tree & t,TreeVisitor visitor)21 void traverse_tree(typename tree_traits<Tree>::node_descriptor v, 22 Tree& t, TreeVisitor visitor) 23 { 24 visitor.preorder(v, t); 25 typename tree_traits<Tree>::children_iterator i, end; 26 boost::tie(i, end) = children(v, t); 27 if (i != end) { 28 traverse_tree(*i++, t, visitor); 29 visitor.inorder(v, t); 30 while (i != end) 31 traverse_tree(*i++, t, visitor); 32 } else 33 visitor.inorder(v, t); 34 visitor.postorder(v, t); 35 } 36 37 struct null_tree_visitor { preorderboost::null_tree_visitor38 template <typename Node, typename Tree> void preorder(Node, Tree&) { } inorderboost::null_tree_visitor39 template <typename Node, typename Tree> void inorder(Node, Tree&) { } postorderboost::null_tree_visitor40 template <typename Node, typename Tree> void postorder(Node, Tree&) { } 41 }; 42 43 } /* namespace boost */ 44 45 #endif /* BOOST_TREE_STRUCTURE_HPP */ 46