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
29namespace boost
30{
31
32namespace detail
33{
34
35 template < class VertexIterator, class OutEdgeIterator, class Graph >
36 class adj_list_edge_iterator
37 {
38 typedef adj_list_edge_iterator self;
39
40 public:
41 typedef std::forward_iterator_tag iterator_category;
42 typedef typename OutEdgeIterator::value_type value_type;
43 typedef typename OutEdgeIterator::reference reference;
44 typedef typename OutEdgeIterator::pointer pointer;
45 typedef typename OutEdgeIterator::difference_type difference_type;
46 typedef difference_type distance_type;
47
48 inline adj_list_edge_iterator() {}
49
50 inline adj_list_edge_iterator(const self& x)
51 : vBegin(x.vBegin)
52 , vCurr(x.vCurr)
53 , vEnd(x.vEnd)
54 , edges(x.edges)
55 , m_g(x.m_g)
56 {
57 }
58
59 template < class G >
60 inline adj_list_edge_iterator(
61 VertexIterator b, VertexIterator c, VertexIterator e, const G& g)
62 : vBegin(b), vCurr(c), vEnd(e), m_g(&g)
63 {
64 if (vCurr != vEnd)
65 {
66 while (vCurr != vEnd && out_degree(*vCurr, *m_g) == 0)
67 ++vCurr;
68 if (vCurr != vEnd)
69 edges = out_edges(*vCurr, *m_g);
70 }
71 }
72
73 /*Note:
74 In the directed graph cases, it is fine.
75 For undirected graphs, one edge go through twice.
76 */
77 inline self& operator++()
78 {
79 ++edges BOOST_GRAPH_MEMBER first;
80 if (edges BOOST_GRAPH_MEMBER first
81 == edges BOOST_GRAPH_MEMBER second)
82 {
83 ++vCurr;
84 while (vCurr != vEnd && out_degree(*vCurr, *m_g) == 0)
85 ++vCurr;
86 if (vCurr != vEnd)
87 edges = out_edges(*vCurr, *m_g);
88 }
89 return *this;
90 }
91 inline self operator++(int)
92 {
93 self tmp = *this;
94 ++(*this);
95 return tmp;
96 }
97 inline value_type operator*() const
98 {
99 return *edges BOOST_GRAPH_MEMBER first;
100 }
101 inline bool operator==(const self& x) const
102 {
103 return vCurr == x.vCurr
104 && (vCurr == vEnd
105 || edges BOOST_GRAPH_MEMBER first
106 == x.edges BOOST_GRAPH_MEMBER first);
107 }
108 inline bool operator!=(const self& x) const
109 {
110 return vCurr != x.vCurr
111 || (vCurr != vEnd
112 && edges BOOST_GRAPH_MEMBER first
113 != x.edges BOOST_GRAPH_MEMBER first);
114 }
115
116 protected:
117 VertexIterator vBegin;
118 VertexIterator vCurr;
119 VertexIterator vEnd;
120
121#ifdef BOOST_GRAPH_NO_OPTIONAL
122 std::pair< OutEdgeIterator, OutEdgeIterator > edges;
123#else
124 boost::optional< std::pair< OutEdgeIterator, OutEdgeIterator > > edges;
125#endif // ndef BOOST_GRAPH_NO_OPTIONAL
126 const Graph* m_g;
127 };
128
129} // namespace detail
130
131}
132
133#undef BOOST_GRAPH_MEMBER
134
135#endif // BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP
136