williamr@2: // Boost.Range library williamr@2: // williamr@2: // Copyright Thorsten Ottosen & Pavol Droba 2003-2004. Use, modification and williamr@2: // distribution is subject to the Boost Software License, Version williamr@2: // 1.0. (See accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: // williamr@2: // For more information, see http://www.boost.org/libs/range/ williamr@2: // williamr@2: williamr@2: #ifndef BOOST_RANGE_ITERATOR_RANGE_HPP williamr@2: #define BOOST_RANGE_ITERATOR_RANGE_HPP williamr@2: williamr@2: // From boost/dynamic_bitset.hpp; thanks to Matthias Troyer for Cray X1 patch. williamr@2: #include // Define __STL_CONFIG_H, if appropriate. williamr@2: #ifndef BOOST_OLD_IOSTREAMS williamr@2: # if defined(__STL_CONFIG_H) && \ williamr@2: !defined (__STL_USE_NEW_IOSTREAMS) && !defined(__crayx1) \ williamr@2: /**/ williamr@2: # define BOOST_OLD_IOSTREAMS williamr@2: # endif williamr@2: #endif // #ifndef BOOST_OLD_IOSTREAMS williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #ifndef BOOST_OLD_IOSTREAMS williamr@2: # include williamr@2: #else williamr@2: # include williamr@2: #endif williamr@2: #include williamr@2: williamr@2: williamr@2: /*! \file williamr@2: Defines the \c iterator_class and related functions. williamr@2: \c iterator_range is a simple wrapper of iterator pair idiom. It provides williamr@2: a rich subset of Container interface. williamr@2: */ williamr@2: williamr@2: williamr@2: namespace boost williamr@2: { williamr@2: namespace iterator_range_detail williamr@2: { williamr@2: // williamr@2: // The functions adl_begin and adl_end are implemented in a separate williamr@2: // class for gcc-2.9x williamr@2: // williamr@2: template williamr@2: struct iterator_range_impl { williamr@2: template< class ForwardRange > williamr@2: static IteratorT adl_begin( ForwardRange& r ) williamr@2: { williamr@2: return IteratorT( boost::begin( r ) ); williamr@2: } williamr@2: williamr@2: template< class ForwardRange > williamr@2: static IteratorT adl_end( ForwardRange& r ) williamr@2: { williamr@2: return IteratorT( boost::end( r ) ); williamr@2: } williamr@2: }; williamr@2: williamr@2: template< class Left, class Right > williamr@2: inline bool equal( const Left& l, const Right& r ) williamr@2: { williamr@2: typedef BOOST_DEDUCED_TYPENAME boost::range_size::type sz_type; williamr@2: williamr@2: sz_type l_size = boost::size( l ), williamr@2: r_size = boost::size( r ); williamr@2: williamr@2: if( l_size != r_size ) williamr@2: return false; williamr@2: williamr@2: return std::equal( boost::begin(l), boost::end(l), williamr@2: boost::begin(r) ); williamr@2: } williamr@2: williamr@2: template< class Left, class Right > williamr@2: inline bool less_than( const Left& l, const Right& r ) williamr@2: { williamr@2: return std::lexicographical_compare( boost::begin(l), williamr@2: boost::end(l), williamr@2: boost::begin(r), williamr@2: boost::end(r) ); williamr@2: } williamr@2: williamr@2: struct range_tag { }; williamr@2: struct const_range_tag { }; williamr@2: williamr@2: } williamr@2: williamr@2: // iterator range template class -----------------------------------------// williamr@2: williamr@2: //! iterator_range class williamr@2: /*! williamr@2: An \c iterator_range delimits a range in a sequence by beginning and ending iterators. williamr@2: An iterator_range can be passed to an algorithm which requires a sequence as an input. williamr@2: For example, the \c toupper() function may be used most frequently on strings, williamr@2: but can also be used on iterator_ranges: williamr@2: williamr@2: \code williamr@2: boost::tolower( find( s, "UPPERCASE STRING" ) ); williamr@2: \endcode williamr@2: williamr@2: Many algorithms working with sequences take a pair of iterators, williamr@2: delimiting a working range, as an arguments. The \c iterator_range class is an williamr@2: encapsulation of a range identified by a pair of iterators. williamr@2: It provides a collection interface, williamr@2: so it is possible to pass an instance to an algorithm requiring a collection as an input. williamr@2: */ williamr@2: template williamr@2: class iterator_range williamr@2: { williamr@2: protected: // Used by sub_range williamr@2: //! implementation class williamr@2: typedef iterator_range_detail::iterator_range_impl impl; williamr@2: public: williamr@2: williamr@2: //! this type williamr@2: typedef iterator_range type; williamr@2: //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type); williamr@2: williamr@2: //! Encapsulated value type williamr@2: typedef BOOST_DEDUCED_TYPENAME williamr@2: iterator_value::type value_type; williamr@2: williamr@2: //! Difference type williamr@2: typedef BOOST_DEDUCED_TYPENAME williamr@2: iterator_difference::type difference_type; williamr@2: williamr@2: //! Size type williamr@2: typedef std::size_t size_type; // note: must be unsigned williamr@2: williamr@2: //! This type williamr@2: typedef iterator_range this_type; williamr@2: williamr@2: //! Refence type williamr@2: // williamr@2: // Needed because value-type is the same for williamr@2: // const and non-const iterators williamr@2: // williamr@2: typedef BOOST_DEDUCED_TYPENAME williamr@2: iterator_reference::type reference; williamr@2: williamr@2: //! const_iterator type williamr@2: /*! williamr@2: There is no distinction between const_iterator and iterator. williamr@2: These typedefs are provides to fulfill container interface williamr@2: */ williamr@2: typedef IteratorT const_iterator; williamr@2: //! iterator type williamr@2: typedef IteratorT iterator; williamr@2: williamr@2: iterator_range() : m_Begin( iterator() ), m_End( iterator() ), williamr@2: singular( true ) williamr@2: { } williamr@2: /* williamr@2: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) williamr@2: iterator_range( this_type r ) : williamr@2: : m_Begin(r.begin()), m_End(r.end()) williamr@2: { } williamr@2: williamr@2: this_type& operator=( this_type r ) williamr@2: { williamr@2: m_Begin = r.begin(); williamr@2: m_End = r.end(); williamr@2: return *this; williamr@2: } williamr@2: #endif williamr@2: */ williamr@2: //! Constructor from a pair of iterators williamr@2: template< class Iterator > williamr@2: iterator_range( Iterator Begin, Iterator End ) : williamr@2: m_Begin(Begin), m_End(End), singular(false) {} williamr@2: williamr@2: //! Constructor from a Range williamr@2: template< class Range > williamr@2: iterator_range( const Range& r ) : williamr@2: m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), williamr@2: singular(false) {} williamr@2: williamr@2: //! Constructor from a Range williamr@2: template< class Range > williamr@2: iterator_range( Range& r ) : williamr@2: m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), williamr@2: singular(false) {} williamr@2: williamr@2: //! Constructor from a Range williamr@2: template< class Range > williamr@2: iterator_range( const Range& r, iterator_range_detail::const_range_tag ) : williamr@2: m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), williamr@2: singular(false) {} williamr@2: williamr@2: //! Constructor from a Range williamr@2: template< class Range > williamr@2: iterator_range( Range& r, iterator_range_detail::range_tag ) : williamr@2: m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), williamr@2: singular(false) {} williamr@2: williamr@2: #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300) williamr@2: this_type& operator=( const this_type& r ) williamr@2: { williamr@2: m_Begin = r.begin(); williamr@2: m_End = r.end(); williamr@2: // williamr@2: // remark: this need not necessarily be true, but it does no harm williamr@2: // williamr@2: singular = r.singular; williamr@2: return *this; williamr@2: } williamr@2: #endif williamr@2: williamr@2: template< class Iterator > williamr@2: iterator_range& operator=( const iterator_range& r ) williamr@2: { williamr@2: m_Begin = r.begin(); williamr@2: m_End = r.end(); williamr@2: // williamr@2: // remark: this need not necessarily be true, but it does no harm williamr@2: // williamr@2: singular = r.empty(); williamr@2: return *this; williamr@2: } williamr@2: williamr@2: template< class ForwardRange > williamr@2: iterator_range& operator=( ForwardRange& r ) williamr@2: { williamr@2: m_Begin = impl::adl_begin( r ); williamr@2: m_End = impl::adl_end( r ); williamr@2: singular = false; williamr@2: return *this; williamr@2: } williamr@2: williamr@2: template< class ForwardRange > williamr@2: iterator_range& operator=( const ForwardRange& r ) williamr@2: { williamr@2: m_Begin = impl::adl_begin( r ); williamr@2: m_End = impl::adl_end( r ); williamr@2: singular = false; williamr@2: return *this; williamr@2: } williamr@2: williamr@2: IteratorT begin() const williamr@2: { williamr@2: return m_Begin; williamr@2: } williamr@2: williamr@2: IteratorT end() const williamr@2: { williamr@2: return m_End; williamr@2: } williamr@2: williamr@2: size_type size() const williamr@2: { williamr@2: if( singular ) williamr@2: return 0; williamr@2: williamr@2: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582)) williamr@2: return std::distance( m_Begin, m_End ); williamr@2: #else williamr@2: return std::distance( m_Begin, m_End ); williamr@2: #endif williamr@2: } williamr@2: williamr@2: bool empty() const williamr@2: { williamr@2: if( singular ) williamr@2: return true; williamr@2: williamr@2: return m_Begin == m_End; williamr@2: } williamr@2: williamr@2: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) williamr@2: operator bool() const williamr@2: { williamr@2: return !empty(); williamr@2: } williamr@2: #else williamr@2: typedef iterator (iterator_range::*unspecified_bool_type) () const; williamr@2: operator unspecified_bool_type() const williamr@2: { williamr@2: return empty() ? 0: &iterator_range::end; williamr@2: } williamr@2: #endif williamr@2: williamr@2: bool equal( const iterator_range& r ) const williamr@2: { williamr@2: return singular == r.singular && m_Begin == r.m_Begin && m_End == r.m_End; williamr@2: } williamr@2: williamr@2: williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: bool operator==( const iterator_range& r ) const williamr@2: { williamr@2: return iterator_range_detail::equal( *this, r ); williamr@2: } williamr@2: williamr@2: bool operator!=( const iterator_range& r ) const williamr@2: { williamr@2: return !operator==(r); williamr@2: } williamr@2: williamr@2: bool operator<( const iterator_range& r ) const williamr@2: { williamr@2: return iterator_range_detail::less_than( *this, r ); williamr@2: } williamr@2: williamr@2: #endif williamr@2: williamr@2: public: // convenience williamr@2: reference front() const williamr@2: { williamr@2: BOOST_ASSERT( !empty() ); williamr@2: return *m_Begin; williamr@2: } williamr@2: williamr@2: reference back() const williamr@2: { williamr@2: BOOST_ASSERT( !empty() ); williamr@2: IteratorT last( m_End ); williamr@2: return *--last; williamr@2: } williamr@2: williamr@2: reference operator[]( size_type sz ) const williamr@2: { williamr@2: //BOOST_STATIC_ASSERT( is_random_access ); williamr@2: BOOST_ASSERT( sz < size() ); williamr@2: return m_Begin[sz]; williamr@2: } williamr@2: williamr@2: iterator_range& advance_begin( difference_type n ) williamr@2: { williamr@2: std::advance( m_Begin, n ); williamr@2: return *this; williamr@2: } williamr@2: williamr@2: iterator_range& advance_end( difference_type n ) williamr@2: { williamr@2: std::advance( m_End, n ); williamr@2: return *this; williamr@2: } williamr@2: williamr@2: private: williamr@2: // begin and end iterators williamr@2: IteratorT m_Begin; williamr@2: IteratorT m_End; williamr@2: bool singular; williamr@2: }; williamr@2: williamr@2: // iterator range free-standing operators ---------------------------// williamr@2: williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: #else williamr@2: template< class Iterator > williamr@2: inline bool empty( const iterator_range& r ) williamr@2: { williamr@2: // williamr@2: // this will preserve the well-defined empty() even williamr@2: // though 'r' is singular. williamr@2: // williamr@2: return r.empty(); williamr@2: } williamr@2: #endif williamr@2: williamr@2: #ifndef BOOST_OLD_IOSTREAMS williamr@2: williamr@2: //! iterator_range output operator williamr@2: /*! williamr@2: Output the range to an ostream. Elements are outputed williamr@2: in a sequence without separators. williamr@2: */ williamr@2: template< typename IteratorT, typename Elem, typename Traits > williamr@2: inline std::basic_ostream& operator<<( williamr@2: std::basic_ostream& Os, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: std::copy( r.begin(), r.end(), williamr@2: std::ostream_iterator< BOOST_DEDUCED_TYPENAME williamr@2: iterator_value::type, williamr@2: Elem, Traits>(Os) ); williamr@2: return Os; williamr@2: } williamr@2: williamr@2: #else williamr@2: williamr@2: //! iterator_range output operator williamr@2: /*! williamr@2: Output the range to an ostream. Elements are outputed williamr@2: in a sequence without separators. williamr@2: */ williamr@2: template< typename IteratorT > williamr@2: inline std::ostream& operator<<( williamr@2: std::ostream& Os, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: std::copy( r.begin(), r.end(), std::ostream_iterator(Os)); williamr@2: return Os; williamr@2: } williamr@2: williamr@2: #endif williamr@2: williamr@2: ///////////////////////////////////////////////////////////////////// williamr@2: // comparison operators williamr@2: ///////////////////////////////////////////////////////////////////// williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator==( const ForwardRange& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator!=( const ForwardRange& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return !iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator<( const ForwardRange& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return iterator_range_detail::less_than( l, r ); williamr@2: } williamr@2: williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: #else williamr@2: template< class Iterator1T, class Iterator2T > williamr@2: inline bool operator==( const iterator_range& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator==( const iterator_range& l, williamr@2: const ForwardRange& r ) williamr@2: { williamr@2: return iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: williamr@2: template< class Iterator1T, class Iterator2T > williamr@2: inline bool operator!=( const iterator_range& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return !iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator!=( const iterator_range& l, williamr@2: const ForwardRange& r ) williamr@2: { williamr@2: return !iterator_range_detail::equal( l, r ); williamr@2: } williamr@2: williamr@2: williamr@2: template< class Iterator1T, class Iterator2T > williamr@2: inline bool operator<( const iterator_range& l, williamr@2: const iterator_range& r ) williamr@2: { williamr@2: return iterator_range_detail::less_than( l, r ); williamr@2: } williamr@2: williamr@2: template< class IteratorT, class ForwardRange > williamr@2: inline bool operator<( const iterator_range& l, williamr@2: const ForwardRange& r ) williamr@2: { williamr@2: return iterator_range_detail::less_than( l, r ); williamr@2: } williamr@2: williamr@2: #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: // iterator range utilities -----------------------------------------// williamr@2: williamr@2: //! iterator_range construct helper williamr@2: /*! williamr@2: Construct an \c iterator_range from a pair of iterators williamr@2: williamr@2: \param Begin A begin iterator williamr@2: \param End An end iterator williamr@2: \return iterator_range object williamr@2: */ williamr@2: template< typename IteratorT > williamr@2: inline iterator_range< IteratorT > williamr@2: make_iterator_range( IteratorT Begin, IteratorT End ) williamr@2: { williamr@2: return iterator_range( Begin, End ); williamr@2: } williamr@2: williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: template< typename Range > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator::type > williamr@2: make_iterator_range( Range& r ) williamr@2: { williamr@2: return iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator::type > williamr@2: ( boost::begin( r ), boost::end( r ) ); williamr@2: } williamr@2: williamr@2: #else williamr@2: //! iterator_range construct helper williamr@2: /*! williamr@2: Construct an \c iterator_range from a \c Range containing the begin williamr@2: and end iterators. williamr@2: */ williamr@2: template< class ForwardRange > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator::type > williamr@2: make_iterator_range( ForwardRange& r ) williamr@2: { williamr@2: return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator::type > williamr@2: ( r, iterator_range_detail::range_tag() ); williamr@2: } williamr@2: williamr@2: template< class ForwardRange > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator::type > williamr@2: make_iterator_range( const ForwardRange& r ) williamr@2: { williamr@2: return iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator::type > williamr@2: ( r, iterator_range_detail::const_range_tag() ); williamr@2: } williamr@2: williamr@2: #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: namespace iterator_range_detail williamr@2: { williamr@2: template< class Range > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator::type > williamr@2: make_range_impl( Range& r, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_begin, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_end ) williamr@2: { williamr@2: if( advance_begin == 0 && advance_end == 0 ) williamr@2: return make_iterator_range( r ); williamr@2: williamr@2: BOOST_DEDUCED_TYPENAME range_result_iterator::type williamr@2: new_begin = boost::begin( r ), williamr@2: new_end = boost::end( r ); williamr@2: std::advance( new_begin, advance_begin ); williamr@2: std::advance( new_end, advance_end ); williamr@2: return make_iterator_range( new_begin, new_end ); williamr@2: } williamr@2: } williamr@2: williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: template< class Range > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator::type > williamr@2: make_iterator_range( Range& r, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_begin, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_end ) williamr@2: { williamr@2: //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); williamr@2: return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); williamr@2: } williamr@2: williamr@2: #else williamr@2: williamr@2: template< class Range > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator::type > williamr@2: make_iterator_range( Range& r, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_begin, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_end ) williamr@2: { williamr@2: //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); williamr@2: return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); williamr@2: } williamr@2: williamr@2: template< class Range > williamr@2: inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator::type > williamr@2: make_iterator_range( const Range& r, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_begin, williamr@2: BOOST_DEDUCED_TYPENAME range_difference::type advance_end ) williamr@2: { williamr@2: //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); williamr@2: return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); williamr@2: } williamr@2: williamr@2: #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING williamr@2: williamr@2: //! copy a range into a sequence williamr@2: /*! williamr@2: Construct a new sequence of the specified type from the elements williamr@2: in the given range williamr@2: williamr@2: \param Range An input range williamr@2: \return New sequence williamr@2: */ williamr@2: template< typename SeqT, typename Range > williamr@2: inline SeqT copy_range( const Range& r ) williamr@2: { williamr@2: return SeqT( boost::begin( r ), boost::end( r ) ); williamr@2: } williamr@2: williamr@2: } // namespace 'boost' williamr@2: williamr@2: #undef BOOST_OLD_IOSTREAMS williamr@2: williamr@2: #endif