graph/detail/incremental_components.hpp

0001 //=======================================================================
0002 // Copyright 2002 Indiana University.
0003 // Copyright 2009 Trustees of Indiana University.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
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_INCREMENTAL_COMPONENTS_HPP
0012 #define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
0013
0014 #include <boost/operators.hpp>
0015
0016 namespace boost
0017 {
0018
0019 namespace detail
0020 {
0021
0022     // Iterator for a component index linked list.  The contents of
0023     // each array element represent the next index in the list.  A
0024     // special value (the maximum index + 1) is used to terminate a
0025     // list.
0026     template < typename IndexRandomAccessIterator >
0027     class component_index_iterator
0028     : boost::forward_iterator_helper<
0029           component_index_iterator< IndexRandomAccessIterator >,
0030           typename std::iterator_traits<
0031               IndexRandomAccessIterator >::value_type,
0032           typename std::iterator_traits<
0033               IndexRandomAccessIterator >::difference_type,
0034           typename std::iterator_traits< IndexRandomAccessIterator >::pointer,
0035           typename std::iterator_traits<
0036               IndexRandomAccessIterator >::reference >
0037     {
0038
0039     private:
0040         typedef component_index_iterator< IndexRandomAccessIterator > self;
0041
0042     public:
0043         typedef std::forward_iterator_tag iterator_category;
0044         typedef typename std::iterator_traits<
0045             IndexRandomAccessIterator >::value_type value_type;
0046         typedef typename std::iterator_traits<
0047             IndexRandomAccessIterator >::difference_type reference;
0048         typedef
0049             typename std::iterator_traits< IndexRandomAccessIterator >::pointer
0050                 pointer;
0051         typedef typename std::iterator_traits<
0052             IndexRandomAccessIterator >::reference difference_type;
0053
0054         // Constructor for "begin" iterator
0055         component_index_iterator(
0056             IndexRandomAccessIterator index_iterator, value_type begin_index)
0057         : m_index_iterator(index_iterator), m_current_index(begin_index)
0058         {
0059         }
0060
0061         // Constructor for "end" iterator (end_index should be the linked
0062         // list terminator).
0063         component_index_iterator(value_type end_index)
0064         : m_current_index(end_index)
0065         {
0066         }
0067
0068         inline value_type operator*() const { return (m_current_index); }
0069
0070         self& operator++()
0071         {
0072             // Move to the next element in the linked list
0073             m_current_index = m_index_iterator[m_current_index];
0074             return (*this);
0075         }
0076
0077         bool operator==(const self& other_iterator) const
0078         {
0079             return (m_current_index == *other_iterator);
0080         }
0081
0082     protected:
0083         IndexRandomAccessIterator m_index_iterator;
0084         value_type m_current_index;
0085
0086     }; // class component_index_iterator
0087
0088 } // namespace detail
0089
0090 } // namespace detail
0091
0092 #endif // BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP