3 // Copyright Neil Groves & Thorsten Ottosen & Pavol Droba 2003-2004.
4 // Use, modification and distribution is subject to the Boost Software
5 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
8 // For more information, see http://www.boost.org/libs/range/
10 #ifndef BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
11 #define BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
13 #include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
14 #include <boost/detail/workaround.hpp>
16 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
17 #pragma warning( push )
18 #pragma warning( disable : 4996 )
21 #include <boost/assert.hpp>
22 #include <boost/iterator/iterator_traits.hpp>
23 #include <boost/iterator/iterator_facade.hpp>
24 #include <boost/mpl/or.hpp>
25 #include <boost/type_traits/is_abstract.hpp>
26 #include <boost/type_traits/is_array.hpp>
27 #include <boost/type_traits/is_pointer.hpp>
28 #include <boost/range/functions.hpp>
29 #include <boost/range/iterator.hpp>
30 #include <boost/range/difference_type.hpp>
31 #include <boost/range/algorithm/equal.hpp>
32 #include <boost/range/detail/safe_bool.hpp>
33 #include <boost/utility/enable_if.hpp>
39 Defines the \c iterator_class and related functions.
40 \c iterator_range is a simple wrapper of iterator pair idiom. It provides
41 a rich subset of Container interface.
47 namespace iterator_range_detail
50 // The functions adl_begin and adl_end are implemented in a separate
53 template<class IteratorT>
54 struct iterator_range_impl {
55 template< class ForwardRange >
56 static IteratorT adl_begin( ForwardRange& r )
58 return static_cast<IteratorT>( boost::begin( r ) );
61 template< class ForwardRange >
62 static IteratorT adl_end( ForwardRange& r )
64 return static_cast<IteratorT>( boost::end( r ) );
68 template< class Left, class Right >
69 inline bool less_than( const Left& l, const Right& r )
71 return std::lexicographical_compare( boost::begin(l),
77 template< class Left, class Right >
78 inline bool greater_than( const Left& l, const Right& r )
80 return less_than(r,l);
83 template< class Left, class Right >
84 inline bool less_or_equal_than( const Left& l, const Right& r )
86 return !iterator_range_detail::less_than(r,l);
89 template< class Left, class Right >
90 inline bool greater_or_equal_than( const Left& l, const Right& r )
92 return !iterator_range_detail::less_than(l,r);
95 // This version is maintained since it is used in other boost libraries
96 // such as Boost.Assign
97 template< class Left, class Right >
98 inline bool equal(const Left& l, const Right& r)
100 return boost::equal(l, r);
103 struct range_tag { };
104 struct const_range_tag { };
107 // iterator range template class -----------------------------------------//
109 //! iterator_range class
111 An \c iterator_range delimits a range in a sequence by beginning and ending iterators.
112 An iterator_range can be passed to an algorithm which requires a sequence as an input.
113 For example, the \c toupper() function may be used most frequently on strings,
114 but can also be used on iterator_ranges:
117 boost::tolower( find( s, "UPPERCASE STRING" ) );
120 Many algorithms working with sequences take a pair of iterators,
121 delimiting a working range, as an arguments. The \c iterator_range class is an
122 encapsulation of a range identified by a pair of iterators.
123 It provides a collection interface,
124 so it is possible to pass an instance to an algorithm requiring a collection as an input.
126 template<class IteratorT>
129 typedef range_detail::safe_bool< IteratorT iterator_range<IteratorT>::* > safe_bool_t;
130 protected: // Used by sub_range
131 //! implementation class
132 typedef iterator_range_detail::iterator_range_impl<IteratorT> impl;
135 typedef iterator_range<IteratorT> type;
136 typedef BOOST_DEDUCED_TYPENAME safe_bool_t::unspecified_bool_type unspecified_bool_type;
137 //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type);
139 //! Encapsulated value type
140 typedef BOOST_DEDUCED_TYPENAME
141 iterator_value<IteratorT>::type value_type;
144 typedef BOOST_DEDUCED_TYPENAME
145 iterator_difference<IteratorT>::type difference_type;
148 typedef std::size_t size_type; // note: must be unsigned
151 typedef iterator_range<IteratorT> this_type;
155 // Needed because value-type is the same for
156 // const and non-const iterators
158 typedef BOOST_DEDUCED_TYPENAME
159 iterator_reference<IteratorT>::type reference;
161 //! const_iterator type
163 There is no distinction between const_iterator and iterator.
164 These typedefs are provides to fulfill container interface
166 typedef IteratorT const_iterator;
168 typedef IteratorT iterator;
170 private: // for return value of operator()()
171 typedef BOOST_DEDUCED_TYPENAME
172 boost::mpl::if_< boost::mpl::or_< boost::is_abstract< value_type >,
173 boost::is_array< value_type > >,
174 reference, value_type >::type abstract_value_type;
177 iterator_range() : m_Begin( iterator() ), m_End( iterator() )
180 //! Constructor from a pair of iterators
181 template< class Iterator >
182 iterator_range( Iterator Begin, Iterator End ) :
183 m_Begin(Begin), m_End(End)
186 //! Constructor from a Range
187 template< class Range >
188 iterator_range( const Range& r ) :
189 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
192 //! Constructor from a Range
193 template< class Range >
194 iterator_range( Range& r ) :
195 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
198 //! Constructor from a Range
199 template< class Range >
200 iterator_range( const Range& r, iterator_range_detail::const_range_tag ) :
201 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
204 //! Constructor from a Range
205 template< class Range >
206 iterator_range( Range& r, iterator_range_detail::range_tag ) :
207 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
210 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
211 this_type& operator=( const this_type& r )
219 template< class Iterator >
220 iterator_range& operator=( const iterator_range<Iterator>& r )
227 template< class ForwardRange >
228 iterator_range& operator=( ForwardRange& r )
230 m_Begin = impl::adl_begin( r );
231 m_End = impl::adl_end( r );
235 template< class ForwardRange >
236 iterator_range& operator=( const ForwardRange& r )
238 m_Begin = impl::adl_begin( r );
239 m_End = impl::adl_end( r );
243 IteratorT begin() const
248 IteratorT end() const
253 difference_type size() const
255 return m_End - m_Begin;
260 return m_Begin == m_End;
263 operator unspecified_bool_type() const
265 return safe_bool_t::to_unspecified_bool(m_Begin != m_End, &iterator_range::m_Begin);
268 bool operator!() const
273 bool equal( const iterator_range& r ) const
275 return m_Begin == r.m_Begin && m_End == r.m_End;
279 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
281 bool operator==( const iterator_range& r ) const
283 return boost::equal( *this, r );
286 bool operator!=( const iterator_range& r ) const
288 return !operator==(r);
291 bool operator<( const iterator_range& r ) const
293 return iterator_range_detail::less_than( *this, r );
296 bool operator>( const iterator_range& r ) const
298 return iterator_range_detail::greater_than( *this, r );
301 bool operator<=( const iterator_range& r ) const
303 return iterator_range_detail::less_or_equal_than( *this, r );
306 bool operator>=( const iterator_range& r ) const
308 return iterator_range_detail::greater_or_equal_than( *this, r );
313 public: // convenience
314 reference front() const
316 BOOST_ASSERT( !empty() );
320 reference back() const
322 BOOST_ASSERT( !empty() );
323 IteratorT last( m_End );
327 // pop_front() - added to model the SinglePassRangePrimitiveConcept
330 BOOST_ASSERT( !empty() );
334 // pop_back() - added to model the BidirectionalRangePrimitiveConcept
337 BOOST_ASSERT( !empty() );
341 reference operator[]( difference_type at ) const
343 BOOST_ASSERT( at >= 0 && at < size() );
348 // When storing transform iterators, operator[]()
349 // fails because it returns by reference. Therefore
350 // operator()() is provided for these cases.
352 abstract_value_type operator()( difference_type at ) const
354 BOOST_ASSERT( at >= 0 && at < size() );
358 iterator_range& advance_begin( difference_type n )
360 std::advance( m_Begin, n );
364 iterator_range& advance_end( difference_type n )
366 std::advance( m_End, n );
371 // begin and end iterators
377 // Allow subclasses an easy way to access the
380 typedef iterator_range iterator_range_;
383 // iterator range free-standing operators ---------------------------//
385 /////////////////////////////////////////////////////////////////////
386 // comparison operators
387 /////////////////////////////////////////////////////////////////////
389 template< class IteratorT, class ForwardRange >
390 inline bool operator==( const ForwardRange& l,
391 const iterator_range<IteratorT>& r )
393 return boost::equal( l, r );
396 template< class IteratorT, class ForwardRange >
397 inline bool operator!=( const ForwardRange& l,
398 const iterator_range<IteratorT>& r )
400 return !boost::equal( l, r );
403 template< class IteratorT, class ForwardRange >
404 inline bool operator<( const ForwardRange& l,
405 const iterator_range<IteratorT>& r )
407 return iterator_range_detail::less_than( l, r );
410 template< class IteratorT, class ForwardRange >
411 inline bool operator<=( const ForwardRange& l,
412 const iterator_range<IteratorT>& r )
414 return iterator_range_detail::less_or_equal_than( l, r );
417 template< class IteratorT, class ForwardRange >
418 inline bool operator>( const ForwardRange& l,
419 const iterator_range<IteratorT>& r )
421 return iterator_range_detail::greater_than( l, r );
424 template< class IteratorT, class ForwardRange >
425 inline bool operator>=( const ForwardRange& l,
426 const iterator_range<IteratorT>& r )
428 return iterator_range_detail::greater_or_equal_than( l, r );
431 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
433 template< class Iterator1T, class Iterator2T >
434 inline bool operator==( const iterator_range<Iterator1T>& l,
435 const iterator_range<Iterator2T>& r )
437 return boost::equal( l, r );
440 template< class IteratorT, class ForwardRange >
441 inline bool operator==( const iterator_range<IteratorT>& l,
442 const ForwardRange& r )
444 return boost::equal( l, r );
448 template< class Iterator1T, class Iterator2T >
449 inline bool operator!=( const iterator_range<Iterator1T>& l,
450 const iterator_range<Iterator2T>& r )
452 return !boost::equal( l, r );
455 template< class IteratorT, class ForwardRange >
456 inline bool operator!=( const iterator_range<IteratorT>& l,
457 const ForwardRange& r )
459 return !boost::equal( l, r );
463 template< class Iterator1T, class Iterator2T >
464 inline bool operator<( const iterator_range<Iterator1T>& l,
465 const iterator_range<Iterator2T>& r )
467 return iterator_range_detail::less_than( l, r );
470 template< class IteratorT, class ForwardRange >
471 inline bool operator<( const iterator_range<IteratorT>& l,
472 const ForwardRange& r )
474 return iterator_range_detail::less_than( l, r );
477 template< class Iterator1T, class Iterator2T >
478 inline bool operator<=( const iterator_range<Iterator1T>& l,
479 const iterator_range<Iterator2T>& r )
481 return iterator_range_detail::less_or_equal_than( l, r );
484 template< class IteratorT, class ForwardRange >
485 inline bool operator<=( const iterator_range<IteratorT>& l,
486 const ForwardRange& r )
488 return iterator_range_detail::less_or_equal_than( l, r );
491 template< class Iterator1T, class Iterator2T >
492 inline bool operator>( const iterator_range<Iterator1T>& l,
493 const iterator_range<Iterator2T>& r )
495 return iterator_range_detail::greater_than( l, r );
498 template< class IteratorT, class ForwardRange >
499 inline bool operator>( const iterator_range<IteratorT>& l,
500 const ForwardRange& r )
502 return iterator_range_detail::greater_than( l, r );
505 template< class Iterator1T, class Iterator2T >
506 inline bool operator>=( const iterator_range<Iterator1T>& l,
507 const iterator_range<Iterator2T>& r )
509 return iterator_range_detail::greater_or_equal_than( l, r );
512 template< class IteratorT, class ForwardRange >
513 inline bool operator>=( const iterator_range<IteratorT>& l,
514 const ForwardRange& r )
516 return iterator_range_detail::greater_or_equal_than( l, r );
519 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
521 // iterator range utilities -----------------------------------------//
523 //! iterator_range construct helper
525 Construct an \c iterator_range from a pair of iterators
527 \param Begin A begin iterator
528 \param End An end iterator
529 \return iterator_range object
531 template< typename IteratorT >
532 inline iterator_range< IteratorT >
533 make_iterator_range( IteratorT Begin, IteratorT End )
535 return iterator_range<IteratorT>( Begin, End );
538 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
540 template< typename Range >
541 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
542 make_iterator_range( Range& r )
544 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
545 ( boost::begin( r ), boost::end( r ) );
549 //! iterator_range construct helper
551 Construct an \c iterator_range from a \c Range containing the begin
554 template< class ForwardRange >
555 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
556 make_iterator_range( ForwardRange& r )
558 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
559 ( r, iterator_range_detail::range_tag() );
562 template< class ForwardRange >
563 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
564 make_iterator_range( const ForwardRange& r )
566 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
567 ( r, iterator_range_detail::const_range_tag() );
570 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
572 namespace iterator_range_detail
574 template< class Range >
575 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
576 make_range_impl( Range& r,
577 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
578 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
581 // Not worth the effort
583 //if( advance_begin == 0 && advance_end == 0 )
584 // return make_iterator_range( r );
587 BOOST_DEDUCED_TYPENAME range_iterator<Range>::type
588 new_begin = boost::begin( r ),
589 new_end = boost::end( r );
590 std::advance( new_begin, advance_begin );
591 std::advance( new_end, advance_end );
592 return make_iterator_range( new_begin, new_end );
596 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
598 template< class Range >
599 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
600 make_iterator_range( Range& r,
601 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
602 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
604 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
605 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
610 template< class Range >
611 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
612 make_iterator_range( Range& r,
613 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
614 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
616 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
617 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
620 template< class Range >
621 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const Range>::type >
622 make_iterator_range( const Range& r,
623 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
624 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
626 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
627 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
630 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
632 //! copy a range into a sequence
634 Construct a new sequence of the specified type from the elements
637 \param Range An input range
640 template< typename SeqT, typename Range >
641 inline SeqT copy_range( const Range& r )
643 return SeqT( boost::begin( r ), boost::end( r ) );
646 } // namespace 'boost'
648 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
649 #pragma warning( pop )