epoc32/include/stdapis/boost/graph/visitors.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/visitors.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,269 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +//
    1.13 +// Revision History:
    1.14 +//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
    1.15 +//
    1.16 +#ifndef BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
    1.17 +#define BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
    1.18 +
    1.19 +#include <iosfwd>
    1.20 +#include <boost/config.hpp>
    1.21 +#include <boost/property_map.hpp>
    1.22 +#include <boost/graph/graph_traits.hpp>
    1.23 +#include <boost/limits.hpp>
    1.24 +#include <boost/graph/detail/is_same.hpp>
    1.25 +
    1.26 +namespace boost {
    1.27 +
    1.28 +  // This is a bit more convenient than std::numeric_limits because
    1.29 +  // you don't have to explicitly provide type T.
    1.30 +  template <class T>
    1.31 +  inline T numeric_limits_max(T) { return (std::numeric_limits<T>::max)(); }
    1.32 +
    1.33 +  //========================================================================
    1.34 +  // Event Tags
    1.35 +
    1.36 +  namespace detail {
    1.37 +    // For partial specialization workaround
    1.38 +    enum event_visitor_enum
    1.39 +    { on_no_event_num,
    1.40 +      on_initialize_vertex_num, on_start_vertex_num,
    1.41 +      on_discover_vertex_num, on_finish_vertex_num, on_examine_vertex_num,
    1.42 +      on_examine_edge_num, on_tree_edge_num, on_non_tree_edge_num,
    1.43 +      on_gray_target_num, on_black_target_num,
    1.44 +      on_forward_or_cross_edge_num, on_back_edge_num,
    1.45 +      on_edge_relaxed_num, on_edge_not_relaxed_num,
    1.46 +      on_edge_minimized_num, on_edge_not_minimized_num
    1.47 +    };
    1.48 +
    1.49 +    template<typename Event, typename Visitor>
    1.50 +    struct functor_to_visitor : Visitor
    1.51 +    {
    1.52 +      typedef Event event_filter;
    1.53 +      functor_to_visitor(const Visitor& visitor) : Visitor(visitor) {}
    1.54 +    };
    1.55 +
    1.56 +  } // namespace detail
    1.57 +
    1.58 +  struct on_no_event { enum { num = detail::on_no_event_num }; };
    1.59 +
    1.60 +  struct on_initialize_vertex {
    1.61 +    enum { num = detail::on_initialize_vertex_num }; };
    1.62 +  struct on_start_vertex { enum { num = detail::on_start_vertex_num }; };
    1.63 +  struct on_discover_vertex { enum { num = detail::on_discover_vertex_num }; };
    1.64 +  struct on_examine_vertex { enum { num = detail::on_examine_vertex_num }; };
    1.65 +  struct on_finish_vertex { enum { num = detail::on_finish_vertex_num }; };
    1.66 +
    1.67 +  struct on_examine_edge { enum { num = detail::on_examine_edge_num }; };
    1.68 +  struct on_tree_edge { enum { num = detail::on_tree_edge_num }; };
    1.69 +  struct on_non_tree_edge { enum { num = detail::on_non_tree_edge_num }; };
    1.70 +  struct on_gray_target { enum { num = detail::on_gray_target_num }; };
    1.71 +  struct on_black_target { enum { num = detail::on_black_target_num }; };
    1.72 +  struct on_forward_or_cross_edge {
    1.73 +    enum { num = detail::on_forward_or_cross_edge_num }; };
    1.74 +  struct on_back_edge { enum { num = detail::on_back_edge_num }; };
    1.75 +
    1.76 +  struct on_edge_relaxed { enum { num = detail::on_edge_relaxed_num }; };
    1.77 +  struct on_edge_not_relaxed {
    1.78 +    enum { num = detail::on_edge_not_relaxed_num }; };
    1.79 +  struct on_edge_minimized { enum { num = detail::on_edge_minimized_num }; };
    1.80 +  struct on_edge_not_minimized {
    1.81 +    enum { num = detail::on_edge_not_minimized_num }; };
    1.82 +
    1.83 +  struct true_tag { enum { num = true }; };
    1.84 +  struct false_tag { enum { num = false }; };
    1.85 +
    1.86 +  //========================================================================
    1.87 +  // base_visitor and null_visitor
    1.88 +
    1.89 +  // needed for MSVC workaround
    1.90 +  template <class Visitor>
    1.91 +  struct base_visitor {
    1.92 +    typedef on_no_event event_filter;
    1.93 +    template <class T, class Graph>
    1.94 +    void operator()(T, Graph&) { }
    1.95 +  };
    1.96 +
    1.97 +  struct null_visitor : public base_visitor<null_visitor> {
    1.98 +    typedef on_no_event event_filter;
    1.99 +    template <class T, class Graph>
   1.100 +    void operator()(T, Graph&) { }
   1.101 +  };
   1.102 +
   1.103 +  //========================================================================
   1.104 +  // The invoke_visitors() function
   1.105 +
   1.106 +  namespace detail {
   1.107 +    template <class Visitor, class T, class Graph>
   1.108 +    inline void
   1.109 +    invoke_dispatch(Visitor& v, T x, Graph& g, true_tag) {
   1.110 +       v(x, g);
   1.111 +    }
   1.112 +    template <class Visitor, class T, class Graph>
   1.113 +    inline void
   1.114 +    invoke_dispatch(Visitor&, T, Graph&, false_tag) { }
   1.115 +  } // namespace detail
   1.116 +
   1.117 +  template <class Visitor, class Rest, class T, class Graph, class Tag>
   1.118 +  inline void
   1.119 +  invoke_visitors(std::pair<Visitor, Rest>& vlist, T x, Graph& g, Tag tag) {
   1.120 +    typedef typename Visitor::event_filter Category;
   1.121 +    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
   1.122 +      IsSameTag;
   1.123 +    detail::invoke_dispatch(vlist.first, x, g, IsSameTag());
   1.124 +    invoke_visitors(vlist.second, x, g, tag);
   1.125 +  }
   1.126 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
   1.127 +  template <class Visitor, class T, class Graph, class Tag>
   1.128 +  inline void
   1.129 +  invoke_visitors(base_visitor<Visitor>& vis, T x, Graph& g, Tag) {
   1.130 +    typedef typename Visitor::event_filter Category;
   1.131 +    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
   1.132 +      IsSameTag;
   1.133 +    Visitor& v = static_cast<Visitor&>(vis);
   1.134 +    detail::invoke_dispatch(v, x, g, IsSameTag());
   1.135 +  }
   1.136 +#else
   1.137 +  template <class Visitor, class T, class Graph, class Tag>
   1.138 +  inline void
   1.139 +  invoke_visitors(Visitor& v, T x, Graph& g, Tag) {
   1.140 +    typedef typename Visitor::event_filter Category;
   1.141 +    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
   1.142 +      IsSameTag;
   1.143 +    detail::invoke_dispatch(v, x, g, IsSameTag());
   1.144 +  }
   1.145 +#endif
   1.146 +
   1.147 +  //========================================================================
   1.148 +  // predecessor_recorder
   1.149 +
   1.150 +  template <class PredecessorMap, class Tag>
   1.151 +  struct predecessor_recorder
   1.152 +    : public base_visitor<predecessor_recorder<PredecessorMap, Tag> >
   1.153 +  {
   1.154 +    typedef Tag event_filter;
   1.155 +    predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) { }
   1.156 +    template <class Edge, class Graph>
   1.157 +    void operator()(Edge e, const Graph& g) {
   1.158 +      put(m_predecessor, target(e, g), source(e, g));
   1.159 +    }
   1.160 +    PredecessorMap m_predecessor;
   1.161 +  };
   1.162 +  template <class PredecessorMap, class Tag>
   1.163 +  predecessor_recorder<PredecessorMap, Tag>
   1.164 +  record_predecessors(PredecessorMap pa, Tag) {
   1.165 +    return predecessor_recorder<PredecessorMap, Tag> (pa);
   1.166 +  }
   1.167 +
   1.168 +  //========================================================================
   1.169 +  // edge_predecessor_recorder
   1.170 +
   1.171 +  template <class PredEdgeMap, class Tag>
   1.172 +  struct edge_predecessor_recorder
   1.173 +    : public base_visitor<edge_predecessor_recorder<PredEdgeMap, Tag> >
   1.174 +  {
   1.175 +    typedef Tag event_filter;
   1.176 +    edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) { }
   1.177 +    template <class Edge, class Graph>
   1.178 +    void operator()(Edge e, const Graph& g) {
   1.179 +      put(m_predecessor, target(e, g), e);
   1.180 +    }
   1.181 +    PredEdgeMap m_predecessor;
   1.182 +  };
   1.183 +  template <class PredEdgeMap, class Tag>
   1.184 +  edge_predecessor_recorder<PredEdgeMap, Tag>
   1.185 +  record_edge_predecessors(PredEdgeMap pa, Tag) {
   1.186 +    return edge_predecessor_recorder<PredEdgeMap, Tag> (pa);
   1.187 +  }
   1.188 +
   1.189 +  //========================================================================
   1.190 +  // distance_recorder
   1.191 +
   1.192 +  template <class DistanceMap, class Tag>
   1.193 +  struct distance_recorder
   1.194 +    : public base_visitor<distance_recorder<DistanceMap, Tag> >
   1.195 +  {
   1.196 +    typedef Tag event_filter;
   1.197 +    distance_recorder(DistanceMap pa) : m_distance(pa) { }
   1.198 +    template <class Edge, class Graph>
   1.199 +    void operator()(Edge e, const Graph& g) {
   1.200 +      typename graph_traits<Graph>::vertex_descriptor
   1.201 +        u = source(e, g), v = target(e, g);
   1.202 +      put(m_distance, v, get(m_distance, u) + 1);
   1.203 +    }
   1.204 +    DistanceMap m_distance;
   1.205 +  };
   1.206 +  template <class DistanceMap, class Tag>
   1.207 +  distance_recorder<DistanceMap, Tag>
   1.208 +  record_distances(DistanceMap pa, Tag) {
   1.209 +    return distance_recorder<DistanceMap, Tag> (pa);
   1.210 +  }
   1.211 +
   1.212 +  //========================================================================
   1.213 +  // time_stamper
   1.214 +
   1.215 +
   1.216 +  template <class TimeMap, class TimeT, class Tag>
   1.217 +  struct time_stamper
   1.218 +    : public base_visitor<time_stamper<TimeMap, TimeT, Tag> >
   1.219 +  {
   1.220 +    typedef Tag event_filter;
   1.221 +    time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) { }
   1.222 +    template <class Vertex, class Graph>
   1.223 +    void operator()(Vertex u, const Graph&) {
   1.224 +      put(m_time_pa, u, ++m_time);
   1.225 +    }
   1.226 +    TimeMap m_time_pa;
   1.227 +    TimeT& m_time;
   1.228 +  };
   1.229 +  template <class TimeMap, class TimeT, class Tag>
   1.230 +  time_stamper<TimeMap, TimeT, Tag>
   1.231 +  stamp_times(TimeMap pa, TimeT& time_counter, Tag) {
   1.232 +    return time_stamper<TimeMap, TimeT, Tag>(pa, time_counter);
   1.233 +  }
   1.234 +
   1.235 +  //========================================================================
   1.236 +  // property_writer
   1.237 +
   1.238 +  template <class PA, class OutputIterator, class Tag>
   1.239 +  struct property_writer
   1.240 +    : public base_visitor<property_writer<PA, OutputIterator, Tag> >
   1.241 +  {
   1.242 +    typedef Tag event_filter;
   1.243 +
   1.244 +    property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) { }
   1.245 +
   1.246 +    template <class T, class Graph>
   1.247 +    void operator()(T x, Graph&) { *m_out++ = get(m_pa, x); }
   1.248 +    PA m_pa;
   1.249 +    OutputIterator m_out;
   1.250 +  };
   1.251 +  template <class PA, class OutputIterator, class Tag>
   1.252 +  property_writer<PA, OutputIterator, Tag>
   1.253 +  write_property(PA pa, OutputIterator out, Tag) {
   1.254 +    return property_writer<PA, OutputIterator, Tag>(pa, out);
   1.255 +  }
   1.256 +
   1.257 +#define BOOST_GRAPH_EVENT_STUB(Event,Kind)                                 \
   1.258 +    typedef ::boost::Event Event##_type;                                   \
   1.259 +    template<typename Visitor>                                             \
   1.260 +    Kind##_visitor<std::pair<detail::functor_to_visitor<Event##_type,      \
   1.261 +                                                     Visitor>, Visitors> > \
   1.262 +    do_##Event(Visitor visitor)                                            \
   1.263 +    {                                                                      \
   1.264 +      typedef std::pair<detail::functor_to_visitor<Event##_type, Visitor>, \
   1.265 +                        Visitors> visitor_list;                            \
   1.266 +      typedef Kind##_visitor<visitor_list> result_type;                    \
   1.267 +      return result_type(visitor_list(visitor, m_vis));                    \
   1.268 +    }
   1.269 +
   1.270 +} /* namespace boost */
   1.271 +
   1.272 +#endif