epoc32/include/stdapis/boost/graph/visitors.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2
     3
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2
     4
//
williamr@2
     5
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     6
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     7
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     8
//=======================================================================
williamr@2
     9
//
williamr@2
    10
// Revision History:
williamr@2
    11
//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
williamr@2
    12
//
williamr@2
    13
#ifndef BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
williamr@2
    14
#define BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
williamr@2
    15
williamr@2
    16
#include <iosfwd>
williamr@2
    17
#include <boost/config.hpp>
williamr@2
    18
#include <boost/property_map.hpp>
williamr@2
    19
#include <boost/graph/graph_traits.hpp>
williamr@2
    20
#include <boost/limits.hpp>
williamr@2
    21
#include <boost/graph/detail/is_same.hpp>
williamr@2
    22
williamr@2
    23
namespace boost {
williamr@2
    24
williamr@2
    25
  // This is a bit more convenient than std::numeric_limits because
williamr@2
    26
  // you don't have to explicitly provide type T.
williamr@2
    27
  template <class T>
williamr@2
    28
  inline T numeric_limits_max(T) { return (std::numeric_limits<T>::max)(); }
williamr@2
    29
williamr@2
    30
  //========================================================================
williamr@2
    31
  // Event Tags
williamr@2
    32
williamr@2
    33
  namespace detail {
williamr@2
    34
    // For partial specialization workaround
williamr@2
    35
    enum event_visitor_enum
williamr@2
    36
    { on_no_event_num,
williamr@2
    37
      on_initialize_vertex_num, on_start_vertex_num,
williamr@2
    38
      on_discover_vertex_num, on_finish_vertex_num, on_examine_vertex_num,
williamr@2
    39
      on_examine_edge_num, on_tree_edge_num, on_non_tree_edge_num,
williamr@2
    40
      on_gray_target_num, on_black_target_num,
williamr@2
    41
      on_forward_or_cross_edge_num, on_back_edge_num,
williamr@2
    42
      on_edge_relaxed_num, on_edge_not_relaxed_num,
williamr@2
    43
      on_edge_minimized_num, on_edge_not_minimized_num
williamr@2
    44
    };
williamr@2
    45
williamr@2
    46
    template<typename Event, typename Visitor>
williamr@2
    47
    struct functor_to_visitor : Visitor
williamr@2
    48
    {
williamr@2
    49
      typedef Event event_filter;
williamr@2
    50
      functor_to_visitor(const Visitor& visitor) : Visitor(visitor) {}
williamr@2
    51
    };
williamr@2
    52
williamr@2
    53
  } // namespace detail
williamr@2
    54
williamr@2
    55
  struct on_no_event { enum { num = detail::on_no_event_num }; };
williamr@2
    56
williamr@2
    57
  struct on_initialize_vertex {
williamr@2
    58
    enum { num = detail::on_initialize_vertex_num }; };
williamr@2
    59
  struct on_start_vertex { enum { num = detail::on_start_vertex_num }; };
williamr@2
    60
  struct on_discover_vertex { enum { num = detail::on_discover_vertex_num }; };
williamr@2
    61
  struct on_examine_vertex { enum { num = detail::on_examine_vertex_num }; };
williamr@2
    62
  struct on_finish_vertex { enum { num = detail::on_finish_vertex_num }; };
williamr@2
    63
williamr@2
    64
  struct on_examine_edge { enum { num = detail::on_examine_edge_num }; };
williamr@2
    65
  struct on_tree_edge { enum { num = detail::on_tree_edge_num }; };
williamr@2
    66
  struct on_non_tree_edge { enum { num = detail::on_non_tree_edge_num }; };
williamr@2
    67
  struct on_gray_target { enum { num = detail::on_gray_target_num }; };
williamr@2
    68
  struct on_black_target { enum { num = detail::on_black_target_num }; };
williamr@2
    69
  struct on_forward_or_cross_edge {
williamr@2
    70
    enum { num = detail::on_forward_or_cross_edge_num }; };
williamr@2
    71
  struct on_back_edge { enum { num = detail::on_back_edge_num }; };
williamr@2
    72
williamr@2
    73
  struct on_edge_relaxed { enum { num = detail::on_edge_relaxed_num }; };
williamr@2
    74
  struct on_edge_not_relaxed {
williamr@2
    75
    enum { num = detail::on_edge_not_relaxed_num }; };
williamr@2
    76
  struct on_edge_minimized { enum { num = detail::on_edge_minimized_num }; };
williamr@2
    77
  struct on_edge_not_minimized {
williamr@2
    78
    enum { num = detail::on_edge_not_minimized_num }; };
williamr@2
    79
williamr@2
    80
  struct true_tag { enum { num = true }; };
williamr@2
    81
  struct false_tag { enum { num = false }; };
williamr@2
    82
williamr@2
    83
  //========================================================================
williamr@2
    84
  // base_visitor and null_visitor
williamr@2
    85
williamr@2
    86
  // needed for MSVC workaround
williamr@2
    87
  template <class Visitor>
williamr@2
    88
  struct base_visitor {
williamr@2
    89
    typedef on_no_event event_filter;
williamr@2
    90
    template <class T, class Graph>
williamr@2
    91
    void operator()(T, Graph&) { }
williamr@2
    92
  };
williamr@2
    93
williamr@2
    94
  struct null_visitor : public base_visitor<null_visitor> {
williamr@2
    95
    typedef on_no_event event_filter;
williamr@2
    96
    template <class T, class Graph>
williamr@2
    97
    void operator()(T, Graph&) { }
williamr@2
    98
  };
williamr@2
    99
williamr@2
   100
  //========================================================================
williamr@2
   101
  // The invoke_visitors() function
williamr@2
   102
williamr@2
   103
  namespace detail {
williamr@2
   104
    template <class Visitor, class T, class Graph>
williamr@2
   105
    inline void
williamr@2
   106
    invoke_dispatch(Visitor& v, T x, Graph& g, true_tag) {
williamr@2
   107
       v(x, g);
williamr@2
   108
    }
williamr@2
   109
    template <class Visitor, class T, class Graph>
williamr@2
   110
    inline void
williamr@2
   111
    invoke_dispatch(Visitor&, T, Graph&, false_tag) { }
williamr@2
   112
  } // namespace detail
williamr@2
   113
williamr@2
   114
  template <class Visitor, class Rest, class T, class Graph, class Tag>
williamr@2
   115
  inline void
williamr@2
   116
  invoke_visitors(std::pair<Visitor, Rest>& vlist, T x, Graph& g, Tag tag) {
williamr@2
   117
    typedef typename Visitor::event_filter Category;
williamr@2
   118
    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
williamr@2
   119
      IsSameTag;
williamr@2
   120
    detail::invoke_dispatch(vlist.first, x, g, IsSameTag());
williamr@2
   121
    invoke_visitors(vlist.second, x, g, tag);
williamr@2
   122
  }
williamr@2
   123
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
williamr@2
   124
  template <class Visitor, class T, class Graph, class Tag>
williamr@2
   125
  inline void
williamr@2
   126
  invoke_visitors(base_visitor<Visitor>& vis, T x, Graph& g, Tag) {
williamr@2
   127
    typedef typename Visitor::event_filter Category;
williamr@2
   128
    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
williamr@2
   129
      IsSameTag;
williamr@2
   130
    Visitor& v = static_cast<Visitor&>(vis);
williamr@2
   131
    detail::invoke_dispatch(v, x, g, IsSameTag());
williamr@2
   132
  }
williamr@2
   133
#else
williamr@2
   134
  template <class Visitor, class T, class Graph, class Tag>
williamr@2
   135
  inline void
williamr@2
   136
  invoke_visitors(Visitor& v, T x, Graph& g, Tag) {
williamr@2
   137
    typedef typename Visitor::event_filter Category;
williamr@2
   138
    typedef typename graph_detail::is_same<Category, Tag>::is_same_tag
williamr@2
   139
      IsSameTag;
williamr@2
   140
    detail::invoke_dispatch(v, x, g, IsSameTag());
williamr@2
   141
  }
williamr@2
   142
#endif
williamr@2
   143
williamr@2
   144
  //========================================================================
williamr@2
   145
  // predecessor_recorder
williamr@2
   146
williamr@2
   147
  template <class PredecessorMap, class Tag>
williamr@2
   148
  struct predecessor_recorder
williamr@2
   149
    : public base_visitor<predecessor_recorder<PredecessorMap, Tag> >
williamr@2
   150
  {
williamr@2
   151
    typedef Tag event_filter;
williamr@2
   152
    predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) { }
williamr@2
   153
    template <class Edge, class Graph>
williamr@2
   154
    void operator()(Edge e, const Graph& g) {
williamr@2
   155
      put(m_predecessor, target(e, g), source(e, g));
williamr@2
   156
    }
williamr@2
   157
    PredecessorMap m_predecessor;
williamr@2
   158
  };
williamr@2
   159
  template <class PredecessorMap, class Tag>
williamr@2
   160
  predecessor_recorder<PredecessorMap, Tag>
williamr@2
   161
  record_predecessors(PredecessorMap pa, Tag) {
williamr@2
   162
    return predecessor_recorder<PredecessorMap, Tag> (pa);
williamr@2
   163
  }
williamr@2
   164
williamr@2
   165
  //========================================================================
williamr@2
   166
  // edge_predecessor_recorder
williamr@2
   167
williamr@2
   168
  template <class PredEdgeMap, class Tag>
williamr@2
   169
  struct edge_predecessor_recorder
williamr@2
   170
    : public base_visitor<edge_predecessor_recorder<PredEdgeMap, Tag> >
williamr@2
   171
  {
williamr@2
   172
    typedef Tag event_filter;
williamr@2
   173
    edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) { }
williamr@2
   174
    template <class Edge, class Graph>
williamr@2
   175
    void operator()(Edge e, const Graph& g) {
williamr@2
   176
      put(m_predecessor, target(e, g), e);
williamr@2
   177
    }
williamr@2
   178
    PredEdgeMap m_predecessor;
williamr@2
   179
  };
williamr@2
   180
  template <class PredEdgeMap, class Tag>
williamr@2
   181
  edge_predecessor_recorder<PredEdgeMap, Tag>
williamr@2
   182
  record_edge_predecessors(PredEdgeMap pa, Tag) {
williamr@2
   183
    return edge_predecessor_recorder<PredEdgeMap, Tag> (pa);
williamr@2
   184
  }
williamr@2
   185
williamr@2
   186
  //========================================================================
williamr@2
   187
  // distance_recorder
williamr@2
   188
williamr@2
   189
  template <class DistanceMap, class Tag>
williamr@2
   190
  struct distance_recorder
williamr@2
   191
    : public base_visitor<distance_recorder<DistanceMap, Tag> >
williamr@2
   192
  {
williamr@2
   193
    typedef Tag event_filter;
williamr@2
   194
    distance_recorder(DistanceMap pa) : m_distance(pa) { }
williamr@2
   195
    template <class Edge, class Graph>
williamr@2
   196
    void operator()(Edge e, const Graph& g) {
williamr@2
   197
      typename graph_traits<Graph>::vertex_descriptor
williamr@2
   198
        u = source(e, g), v = target(e, g);
williamr@2
   199
      put(m_distance, v, get(m_distance, u) + 1);
williamr@2
   200
    }
williamr@2
   201
    DistanceMap m_distance;
williamr@2
   202
  };
williamr@2
   203
  template <class DistanceMap, class Tag>
williamr@2
   204
  distance_recorder<DistanceMap, Tag>
williamr@2
   205
  record_distances(DistanceMap pa, Tag) {
williamr@2
   206
    return distance_recorder<DistanceMap, Tag> (pa);
williamr@2
   207
  }
williamr@2
   208
williamr@2
   209
  //========================================================================
williamr@2
   210
  // time_stamper
williamr@2
   211
williamr@2
   212
williamr@2
   213
  template <class TimeMap, class TimeT, class Tag>
williamr@2
   214
  struct time_stamper
williamr@2
   215
    : public base_visitor<time_stamper<TimeMap, TimeT, Tag> >
williamr@2
   216
  {
williamr@2
   217
    typedef Tag event_filter;
williamr@2
   218
    time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) { }
williamr@2
   219
    template <class Vertex, class Graph>
williamr@2
   220
    void operator()(Vertex u, const Graph&) {
williamr@2
   221
      put(m_time_pa, u, ++m_time);
williamr@2
   222
    }
williamr@2
   223
    TimeMap m_time_pa;
williamr@2
   224
    TimeT& m_time;
williamr@2
   225
  };
williamr@2
   226
  template <class TimeMap, class TimeT, class Tag>
williamr@2
   227
  time_stamper<TimeMap, TimeT, Tag>
williamr@2
   228
  stamp_times(TimeMap pa, TimeT& time_counter, Tag) {
williamr@2
   229
    return time_stamper<TimeMap, TimeT, Tag>(pa, time_counter);
williamr@2
   230
  }
williamr@2
   231
williamr@2
   232
  //========================================================================
williamr@2
   233
  // property_writer
williamr@2
   234
williamr@2
   235
  template <class PA, class OutputIterator, class Tag>
williamr@2
   236
  struct property_writer
williamr@2
   237
    : public base_visitor<property_writer<PA, OutputIterator, Tag> >
williamr@2
   238
  {
williamr@2
   239
    typedef Tag event_filter;
williamr@2
   240
williamr@2
   241
    property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) { }
williamr@2
   242
williamr@2
   243
    template <class T, class Graph>
williamr@2
   244
    void operator()(T x, Graph&) { *m_out++ = get(m_pa, x); }
williamr@2
   245
    PA m_pa;
williamr@2
   246
    OutputIterator m_out;
williamr@2
   247
  };
williamr@2
   248
  template <class PA, class OutputIterator, class Tag>
williamr@2
   249
  property_writer<PA, OutputIterator, Tag>
williamr@2
   250
  write_property(PA pa, OutputIterator out, Tag) {
williamr@2
   251
    return property_writer<PA, OutputIterator, Tag>(pa, out);
williamr@2
   252
  }
williamr@2
   253
williamr@2
   254
#define BOOST_GRAPH_EVENT_STUB(Event,Kind)                                 \
williamr@2
   255
    typedef ::boost::Event Event##_type;                                   \
williamr@2
   256
    template<typename Visitor>                                             \
williamr@2
   257
    Kind##_visitor<std::pair<detail::functor_to_visitor<Event##_type,      \
williamr@2
   258
                                                     Visitor>, Visitors> > \
williamr@2
   259
    do_##Event(Visitor visitor)                                            \
williamr@2
   260
    {                                                                      \
williamr@2
   261
      typedef std::pair<detail::functor_to_visitor<Event##_type, Visitor>, \
williamr@2
   262
                        Visitors> visitor_list;                            \
williamr@2
   263
      typedef Kind##_visitor<visitor_list> result_type;                    \
williamr@2
   264
      return result_type(visitor_list(visitor, m_vis));                    \
williamr@2
   265
    }
williamr@2
   266
williamr@2
   267
} /* namespace boost */
williamr@2
   268
williamr@2
   269
#endif