graph/detail/adj_list_edge_iterator.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP
0012 #define BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP
0013
0014 #include <iterator>
0015 #include <utility>
0016 #include <boost/detail/workaround.hpp>
0017
0018 #if BOOST_WORKAROUND(__IBMCPP__, <= 600)
0019 #define BOOST_GRAPH_NO_OPTIONAL
0020 #endif
0021
0022 #ifdef BOOST_GRAPH_NO_OPTIONAL
0023 #define BOOST_GRAPH_MEMBER .
0024 #else
0025 #define BOOST_GRAPH_MEMBER ->
0026 #include <boost/optional.hpp>
0027 #endif // ndef BOOST_GRAPH_NO_OPTIONAL
0028
0029 namespace boost
0030 {
0031
0032 namespace detail
0033 {
0034
0035     template < class VertexIterator, class OutEdgeIterator, class Graph >
0036     class adj_list_edge_iterator
0037     {
0038         typedef adj_list_edge_iterator self;
0039
0040     public:
0041         typedef std::forward_iterator_tag iterator_category;
0042         typedef typename OutEdgeIterator::value_type value_type;
0043         typedef typename OutEdgeIterator::reference reference;
0044         typedef typename OutEdgeIterator::pointer pointer;
0045         typedef typename OutEdgeIterator::difference_type difference_type;
0046         typedef difference_type distance_type;
0047
0048         inline adj_list_edge_iterator() {}
0049
0050         inline adj_list_edge_iterator(const self& x)
0051         : vBegin(x.vBegin)
0052         , vCurr(x.vCurr)
0053         , vEnd(x.vEnd)
0054         , edges(x.edges)
0055         , m_g(x.m_g)
0056         {
0057         }
0058
0059         template < class G >
0060         inline adj_list_edge_iterator(
0061             VertexIterator b, VertexIterator c, VertexIterator e, const G& g)
0062         : vBegin(b), vCurr(c), vEnd(e), m_g(&g)
0063         {
0064             if (vCurr != vEnd)
0065             {
0066                 while (vCurr != vEnd && out_degree(*vCurr, *m_g) == 0)
0067                     ++vCurr;
0068                 if (vCurr != vEnd)
0069                     edges = out_edges(*vCurr, *m_g);
0070             }
0071         }
0072
0073         /*Note:
0074           In the directed graph cases, it is fine.
0075           For undirected graphs, one edge go through twice.
0076         */
0077         inline self& operator++()
0078         {
0079             ++edges BOOST_GRAPH_MEMBER first;
0080             if (edges BOOST_GRAPH_MEMBER first
0081                 == edges BOOST_GRAPH_MEMBER second)
0082             {
0083                 ++vCurr;
0084                 while (vCurr != vEnd && out_degree(*vCurr, *m_g) == 0)
0085                     ++vCurr;
0086                 if (vCurr != vEnd)
0087                     edges = out_edges(*vCurr, *m_g);
0088             }
0089             return *this;
0090         }
0091         inline self operator++(int)
0092         {
0093             self tmp = *this;
0094             ++(*this);
0095             return tmp;
0096         }
0097         inline value_type operator*() const
0098         {
0099             return *edges BOOST_GRAPH_MEMBER first;
0100         }
0101         inline bool operator==(const self& x) const
0102         {
0103             return vCurr == x.vCurr
0104                 && (vCurr == vEnd
0105                     || edges BOOST_GRAPH_MEMBER first
0106                         == x.edges BOOST_GRAPH_MEMBER first);
0107         }
0108         inline bool operator!=(const self& x) const
0109         {
0110             return vCurr != x.vCurr
0111                 || (vCurr != vEnd
0112                     && edges BOOST_GRAPH_MEMBER first
0113                         != x.edges BOOST_GRAPH_MEMBER first);
0114         }
0115
0116     protected:
0117         VertexIterator vBegin;
0118         VertexIterator vCurr;
0119         VertexIterator vEnd;
0120
0121 #ifdef BOOST_GRAPH_NO_OPTIONAL
0122         std::pair< OutEdgeIterator, OutEdgeIterator > edges;
0123 #else
0124         boost::optional< std::pair< OutEdgeIterator, OutEdgeIterator > > edges;
0125 #endif // ndef BOOST_GRAPH_NO_OPTIONAL
0126         const Graph* m_g;
0127     };
0128
0129 } // namespace detail
0130
0131 }
0132
0133 #undef BOOST_GRAPH_MEMBER
0134
0135 #endif // BOOST_GRAPH_DETAIL_ADJ_LIST_EDGE_ITERATOR_HPP