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
|
---|