boost/boost/graph/detail/adj_list_edge_iterator.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP
  12 #define BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP
  13
  14 #include <iterator>
  15 #include <utility>
  16 #include <boost/detail/workaround.hpp>
  17
  18 #if BOOST_WORKAROUND( __IBMCPP__, <= 600 )
  19 #  define BOOST_GRAPH_NO_OPTIONAL
  20 #endif
  21
  22 #ifdef BOOST_GRAPH_NO_OPTIONAL
  23 #  define BOOST_GRAPH_MEMBER .
  24 #else
  25 #  define BOOST_GRAPH_MEMBER ->
  26 #  include <boost/optional.hpp>
  27 #endif // ndef BOOST_GRAPH_NO_OPTIONAL
  28
  29 namespace boost {
  30
  31   namespace detail {
  32
  33     template <class VertexIterator, class OutEdgeIterator, class Graph>
  34     class adj_list_edge_iterator {
  35       typedef adj_list_edge_iterator self;
  36     public:
  37       typedef std::forward_iterator_tag iterator_category;
  38       typedef typename OutEdgeIterator::value_type value_type;
  39       typedef typename OutEdgeIterator::reference  reference;
  40       typedef typename OutEdgeIterator::pointer    pointer;
  41       typedef typename OutEdgeIterator::difference_type difference_type;
  42       typedef difference_type distance_type;
  43
  44       inline adj_list_edge_iterator() {}
  45
  46       inline adj_list_edge_iterator(const self& x)
  47       : vBegin(x.vBegin), vCurr(x.vCurr), vEnd(x.vEnd),
  48         edges(x.edges), m_g(x.m_g) { }
  49
  50       template <class G>
  51       inline adj_list_edge_iterator(VertexIterator b,
  52                                     VertexIterator c,
  53                                     VertexIterator e,
  54                                     const G& g)
  55         : vBegin(b), vCurr(c), vEnd(e), m_g(&g) {
  56         if ( vCurr != vEnd ) {
  57           while ( vCurr != vEnd && out_degree(*vCurr, *m_g) == 0 )
  58             ++vCurr;
  59           if ( vCurr != vEnd )
  60             edges = out_edges(*vCurr, *m_g);
  61         }
  62       }
  63
  64       /*Note:
  65         In the directed graph cases, it is fine.
  66         For undirected graphs, one edge go through twice.
  67       */
  68       inline self& operator++() {
  69         ++edges BOOST_GRAPH_MEMBER first;
  70         if (edges BOOST_GRAPH_MEMBER first == edges BOOST_GRAPH_MEMBER second)
  71         {
  72           ++vCurr;
  73           while ( vCurr != vEnd && out_degree(*vCurr, *m_g) == 0 )
  74             ++vCurr;
  75           if ( vCurr != vEnd )
  76             edges = out_edges(*vCurr, *m_g);
  77         }
  78         return *this;
  79       }
  80       inline self operator++(int) {
  81         self tmp = *this;
  82         ++(*this);
  83         return tmp;
  84       }
  85       inline value_type operator*() const
  86       { return *edges BOOST_GRAPH_MEMBER first; }
  87       inline bool operator==(const self& x) const {
  88         return vCurr == x.vCurr
  89           && (vCurr == vEnd
  90               || edges BOOST_GRAPH_MEMBER first == x.edges BOOST_GRAPH_MEMBER first);
  91       }
  92       inline bool operator!=(const self& x) const {
  93         return vCurr != x.vCurr
  94           || (vCurr != vEnd
  95               && edges BOOST_GRAPH_MEMBER first != x.edges BOOST_GRAPH_MEMBER first);
  96       }
  97     protected:
  98       VertexIterator vBegin;
  99       VertexIterator vCurr;
 100       VertexIterator vEnd;
 101
 102 #ifdef BOOST_GRAPH_NO_OPTIONAL
 103       std::pair<OutEdgeIterator, OutEdgeIterator> edges;
 104 #else
 105       boost::optional<std::pair<OutEdgeIterator, OutEdgeIterator> >
 106         edges;
 107 #endif // ndef BOOST_GRAPH_NO_OPTIONAL
 108       const Graph* m_g;
 109     };
 110
 111   } // namespace detail
 112
 113 }
 114
 115 #undef BOOST_GRAPH_MEMBER
 116
 117 #endif // BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP