Line data    Source code

       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           0 :     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           0 :       inline adj_list_edge_iterator() {}
      45             : 
      46           0 :       inline adj_list_edge_iterator(const self& x) 
      47             :       : vBegin(x.vBegin), vCurr(x.vCurr), vEnd(x.vEnd),
      48           0 :         edges(x.edges), m_g(x.m_g) { }
      49             : 
      50             :       template <class G>
      51           0 :       inline adj_list_edge_iterator(VertexIterator b, 
      52             :                                     VertexIterator c,
      53             :                                     VertexIterator e,
      54             :                                     const G& g) 
      55           0 :         : vBegin(b), vCurr(c), vEnd(e), m_g(&g) {
      56           0 :         if ( vCurr != vEnd ) {
      57           0 :           while ( vCurr != vEnd && out_degree(*vCurr, *m_g) == 0 )
      58           0 :             ++vCurr;
      59           0 :           if ( vCurr != vEnd )
      60           0 :             edges = out_edges(*vCurr, *m_g);
      61             :         }
      62           0 :       }
      63             : 
      64             :       /*Note:
      65             :         In the directed graph cases, it is fine. 
      66             :         For undirected graphs, one edge go through twice.
      67             :       */
      68           0 :       inline self& operator++() {
      69           0 :         ++edges BOOST_GRAPH_MEMBER first;
      70           0 :         if (edges BOOST_GRAPH_MEMBER first == edges BOOST_GRAPH_MEMBER second) 
      71             :         {
      72           0 :           ++vCurr;
      73           0 :           while ( vCurr != vEnd && out_degree(*vCurr, *m_g) == 0 )
      74           0 :             ++vCurr;
      75           0 :           if ( vCurr != vEnd )
      76           0 :             edges = out_edges(*vCurr, *m_g);
      77             :         }
      78           0 :         return *this;
      79             :       }
      80             :       inline self operator++(int) {
      81             :         self tmp = *this;
      82             :         ++(*this);
      83             :         return tmp;
      84             :       }
      85           0 :       inline value_type operator*() const 
      86           0 :       { 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           0 :       inline bool operator!=(const self& x) const {
      93           0 :         return vCurr != x.vCurr 
      94           0 :           || (vCurr != vEnd 
      95           0 :               && 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