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