[857] | 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
|
---|