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 
adj_list_edge_iterator()44       inline adj_list_edge_iterator() {}
45 
adj_list_edge_iterator(const self & x)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>
adj_list_edge_iterator(VertexIterator b,VertexIterator c,VertexIterator e,const G & 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       */
operator ++()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       }
operator ++(int)80       inline self operator++(int) {
81         self tmp = *this;
82         ++(*this);
83         return tmp;
84       }
operator *() const85       inline value_type operator*() const
86       { return *edges BOOST_GRAPH_MEMBER first; }
operator ==(const self & x) const87       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       }
operator !=(const self & x) const92       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
118