boost/graph/tree_traits.hpp

   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 namespace boost {
  10
  11   template <class T>
  12   struct tree_traits {
  13     typedef typename T::node_descriptor node_descriptor;
  14     typedef typename T::children_iterator children_iterator;
  15   };
  16
  17
  18   template <class Tree, class TreeVisitor>
  19   void traverse_tree(typename tree_traits<Tree>::node_descriptor v,
  20                      Tree& t, TreeVisitor visitor)
  21   {
  22     visitor.preorder(v, t);
  23     typename tree_traits<Tree>::children_iterator i, end;
  24     tie(i, end) = children(v, t);
  25     if (i != end) {
  26       traverse_tree(*i++, t, visitor);
  27       visitor.inorder(v, t);
  28       while (i != end)
  29         traverse_tree(*i++, t, visitor);
  30     } else
  31       visitor.inorder(v, t);
  32     visitor.postorder(v, t);
  33   }
  34
  35   struct null_tree_visitor {
  36     template <typename Node, typename Tree> void preorder(Node, Tree&) { }
  37     template <typename Node, typename Tree> void inorder(Node, Tree&) { }
  38     template <typename Node, typename Tree> void postorder(Node, Tree&) { }
  39   };
  40
  41 } /* namespace boost */
  42
  43 #endif /* BOOST_TREE_STRUCTURE_HPP */