ceph/src/boost/boost/msm/mpl_graph/breadth_first_search.hpp

   1 // Copyright 2008-2010 Gordon Woodhull
   2 // Distributed under the Boost Software License, Version 1.0.
   3 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   4
   5 #ifndef BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
   6 #define BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
   7
   8 #include <boost/msm/mpl_graph/mpl_graph.hpp>
   9
  10 #include <boost/mpl/has_key.hpp>
  11 #include <boost/mpl/insert.hpp>
  12 #include <boost/mpl/pair.hpp>
  13 #include <boost/mpl/map.hpp>
  14 #include <boost/mpl/has_key.hpp>
  15 #include <boost/mpl/pop_front.hpp>
  16 #include <boost/mpl/empty.hpp>
  17 #include <boost/mpl/remove.hpp>
  18
  19 #include "search_colors.hpp"
  20
  21 namespace boost {
  22 namespace msm {
  23 namespace mpl_graph {
  24
  25 // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an
  26 // "operations" member class, and also a state.  the operations are expected to return a new state
  27 struct bfs_default_visitor_operations {
  28     template<typename Vertex, typename Graph, typename State>
  29     struct initialize_vertex {
  30         typedef State type;
  31     };
  32
  33     template<typename Vertex, typename Graph, typename State>
  34     struct discover_vertex {
  35         typedef State type;
  36     };
  37
  38     template<typename Vertex, typename Graph, typename State>
  39     struct examine_vertex {
  40         typedef State type;
  41     };
  42
  43     template<typename Vertex, typename Graph, typename State>
  44     struct examine_edge {
  45         typedef State type;
  46     };
  47
  48     template<typename Edge, typename Graph, typename State>
  49     struct tree_edge {
  50         typedef State type;
  51     };
  52
  53     template<typename Edge, typename Graph, typename State>
  54     struct non_tree_edge {
  55         typedef State type;
  56     };
  57
  58     template<typename Edge, typename Graph, typename State>
  59     struct gray_target {
  60         typedef State type;
  61     };
  62
  63     template<typename Edge, typename Graph, typename State>
  64     struct black_target {
  65         typedef State type;
  66     };
  67
  68     template<typename Vertex, typename Graph, typename State>
  69     struct finish_vertex {
  70         typedef State type;
  71     };
  72 };
  73
  74 namespace detail {
  75
  76 template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
  77 struct bfs_run_queue_examine_edge {
  78     typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
  79     typedef typename mpl::at_c<VCQState, 1>::type color_state;
  80     typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
  81
  82     typedef typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<typename mpl_graph::target<Edge, Graph>::type, color_state>::type, search_colors::White>::type,
  83          // unseen target: tree edge, discover target, paint it gray, and enqueue
  84          mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph,
  85                                                                             typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type,
  86                      typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type,
  87                      typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >,
  88          // seen
  89          mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>,
  90                                              search_colors::Gray>::type,
  91                               typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type,
  92                               typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type,
  93                      color_state,
  94                      vertex_queue>
  95          >::type type;
  96 };
  97
  98 // runs bfs on a queue, passing the new queue forward on recursion
  99 // returns pair<visitor_state, color_state>
 100 template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
 101 struct bfs_run_queue {
 102     // enter vertex
 103     typedef typename mpl::front<VertexQueue>::type Vertex;
 104     typedef typename mpl::pop_front<VertexQueue>::type Tail;
 105     typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
 106
 107     // loop over out edges
 108     typedef typename mpl::template
 109         fold<typename mpl_graph::out_edges<Vertex, Graph>::type,
 110              mpl::vector<examined_state, ColorMap, Tail>,
 111              bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
 112             >::type did_edges;
 113
 114     typedef typename VisitorOps::template
 115         finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type
 116             finished_vertex;
 117     // does map insert always overwrite?  i seem to remember this not working on msvc once
 118     typedef typename search_color_map_ops::template
 119         set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type
 120             colored_vertex;
 121     typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
 122
 123     typedef typename
 124         mpl::if_<typename mpl::empty<queued_targets>::type,
 125                  mpl::pair<finished_vertex, colored_vertex>,
 126                  bfs_run_queue<Graph, queued_targets,
 127                                VisitorOps, finished_vertex,
 128                                colored_vertex> >::type::type type;
 129 };
 130
 131 } // namespace detail
 132
 133 template<typename Graph, typename VisitorOps, typename VisitorState,
 134          typename Vertex,
 135          typename ColorMap = create_search_color_map::type >
 136 struct breadth_first_search {
 137     typedef typename VisitorOps::template
 138         discover_vertex<Vertex, Graph, VisitorState>::type
 139             discovered_state;
 140     typedef typename search_color_map_ops::template
 141         set_color<Vertex, search_colors::Gray, ColorMap>::type
 142             discovered_colors;
 143     typedef typename detail::
 144         bfs_run_queue<Graph, mpl::vector<Vertex>,
 145                       VisitorOps, discovered_state,
 146                       discovered_colors>::type type;
 147 };
 148
 149 template<typename Graph, typename VisitorOps, typename VisitorState,
 150          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
 151          typename ColorMap = create_search_color_map::type>
 152 struct breadth_first_search_all : // visit "first" first, then visit any still white
 153     mpl::fold<typename mpl_graph::vertices<Graph>::type,
 154               typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
 155               mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
 156                                       search_colors::White>,
 157                        breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
 158                                             mpl::_2, mpl::second<mpl::_1> >,
 159                        mpl::_1> >
 160 {};
 161
 162 } // namespace mpl_graph
 163 } // namespace msm
 164 } // namespace boost
 165
 166
 167 #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED