src/boost/range/iterator_range.hpp

   1 // Boost.Range library
   2 //
   3 //  Copyright Thorsten Ottosen & Pavol Droba 2003-2004. Use, modification and
   4 //  distribution is subject to the Boost Software License, Version
   5 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 //  http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // For more information, see http://www.boost.org/libs/range/
   9 //
  10
  11 #ifndef BOOST_RANGE_ITERATOR_RANGE_HPP
  12 #define BOOST_RANGE_ITERATOR_RANGE_HPP
  13
  14 // From boost/dynamic_bitset.hpp; thanks to Matthias Troyer for Cray X1 patch.
  15 #include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
  16 #ifndef BOOST_OLD_IOSTREAMS
  17 # if defined(__STL_CONFIG_H) && \
  18     !defined (__STL_USE_NEW_IOSTREAMS) && !defined(__crayx1) \
  19     /**/
  20 #  define BOOST_OLD_IOSTREAMS
  21 # endif
  22 #endif // #ifndef BOOST_OLD_IOSTREAMS
  23
  24 #include <boost/detail/workaround.hpp>
  25 #include <boost/range/functions.hpp>
  26 #include <boost/range/result_iterator.hpp>
  27 #include <boost/range/difference_type.hpp>
  28 #include <boost/iterator/iterator_traits.hpp>
  29 #include <boost/assert.hpp>
  30 #include <iterator>
  31 #include <algorithm>
  32 #ifndef BOOST_OLD_IOSTREAMS
  33 # include <ostream>
  34 #else
  35 # include <ostream.h>
  36 #endif
  37 #include <cstddef>
  38
  39
  40 /*! \file
  41     Defines the \c iterator_class and related functions.
  42     \c iterator_range is a simple wrapper of iterator pair idiom. It provides
  43     a rich subset of Container interface.
  44 */
  45
  46
  47 namespace boost
  48 {
  49     namespace iterator_range_detail
  50     {
  51         //
  52         // The functions adl_begin and adl_end are implemented in a separate
  53         // class for gcc-2.9x
  54         //
  55         template<typename IteratorT>
  56         struct iterator_range_impl {
  57             template< class ForwardRange >
  58             static IteratorT adl_begin( ForwardRange& r )
  59             {
  60                 return IteratorT( boost::begin( r ) );
  61             }
  62
  63             template< class ForwardRange >
  64             static IteratorT adl_end( ForwardRange& r )
  65             {
  66                 return IteratorT( boost::end( r ) );
  67             }
  68         };
  69
  70         template< class Left, class Right >
  71         inline bool equal( const Left& l, const Right& r )
  72         {
  73             typedef BOOST_DEDUCED_TYPENAME boost::range_size<Left>::type sz_type;
  74
  75             sz_type l_size = boost::size( l ),
  76                     r_size = boost::size( r );
  77
  78             if( l_size != r_size )
  79                 return false;
  80
  81             return std::equal( boost::begin(l), boost::end(l),
  82                                boost::begin(r) );
  83         }
  84
  85         template< class Left, class Right >
  86         inline bool less_than( const Left& l, const Right& r )
  87         {
  88             return std::lexicographical_compare( boost::begin(l),
  89                                                  boost::end(l),
  90                                                  boost::begin(r),
  91                                                  boost::end(r) );
  92         }
  93
  94         struct range_tag { };
  95         struct const_range_tag { };
  96
  97     }
  98
  99 //  iterator range template class -----------------------------------------//
 100
 101         //! iterator_range class
 102         /*!
 103             An \c iterator_range delimits a range in a sequence by beginning and ending iterators.
 104             An iterator_range can be passed to an algorithm which requires a sequence as an input.
 105             For example, the \c toupper() function may be used most frequently on strings,
 106             but can also be used on iterator_ranges:
 107
 108             \code
 109                 boost::tolower( find( s, "UPPERCASE STRING" ) );
 110             \endcode
 111
 112             Many algorithms working with sequences take a pair of iterators,
 113             delimiting a working range, as an arguments. The \c iterator_range class is an
 114             encapsulation of a range identified by a pair of iterators.
 115             It provides a collection interface,
 116             so it is possible to pass an instance to an algorithm requiring a collection as an input.
 117         */
 118         template<typename IteratorT>
 119         class iterator_range
 120         {
 121         protected: // Used by sub_range
 122             //! implementation class
 123             typedef iterator_range_detail::iterator_range_impl<IteratorT> impl;
 124         public:
 125
 126             //! this type
 127             typedef iterator_range<IteratorT> type;
 128             //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type);
 129
 130             //! Encapsulated value type
 131             typedef BOOST_DEDUCED_TYPENAME
 132                 iterator_value<IteratorT>::type value_type;
 133
 134             //! Difference type
 135             typedef BOOST_DEDUCED_TYPENAME
 136                 iterator_difference<IteratorT>::type difference_type;
 137
 138             //! Size type
 139             typedef std::size_t size_type; // note: must be unsigned
 140
 141             //! This type
 142             typedef iterator_range<IteratorT> this_type;
 143
 144             //! Refence type
 145             //
 146             // Needed because value-type is the same for
 147             // const and non-const iterators
 148             //
 149             typedef BOOST_DEDUCED_TYPENAME
 150                 iterator_reference<IteratorT>::type reference;
 151
 152             //! const_iterator type
 153             /*!
 154                 There is no distinction between const_iterator and iterator.
 155                 These typedefs are provides to fulfill container interface
 156             */
 157             typedef IteratorT const_iterator;
 158             //! iterator type
 159             typedef IteratorT iterator;
 160
 161             iterator_range() : m_Begin( iterator() ), m_End( iterator() ),
 162                                singular( true )
 163             { }
 164 /*
 165 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
 166             iterator_range( this_type r ) :
 167             : m_Begin(r.begin()), m_End(r.end())
 168             { }
 169
 170             this_type& operator=( this_type r )
 171             {
 172                 m_Begin = r.begin();
 173                 m_End   = r.end();
 174                 return *this;
 175             }
 176 #endif
 177 */
 178             //! Constructor from a pair of iterators
 179             template< class Iterator >
 180             iterator_range( Iterator Begin, Iterator End ) :
 181                 m_Begin(Begin), m_End(End), singular(false) {}
 182
 183             //! Constructor from a Range
 184             template< class Range >
 185             iterator_range( const Range& r ) :
 186                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
 187                 singular(false) {}
 188
 189             //! Constructor from a Range
 190             template< class Range >
 191             iterator_range( Range& r ) :
 192                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
 193                 singular(false) {}
 194
 195             //! Constructor from a Range
 196             template< class Range >
 197             iterator_range( const Range& r, iterator_range_detail::const_range_tag ) :
 198                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
 199                 singular(false) {}
 200
 201             //! Constructor from a Range
 202             template< class Range >
 203             iterator_range( Range& r, iterator_range_detail::range_tag ) :
 204                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
 205                 singular(false) {}
 206
 207             #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 208             this_type& operator=( const this_type& r )
 209             {
 210                 m_Begin  = r.begin();
 211                 m_End    = r.end();
 212                 //
 213                 // remark: this need not necessarily be true, but it does no harm
 214                 //
 215                 singular = r.singular;
 216                 return *this;
 217             }
 218             #endif
 219
 220             template< class Iterator >
 221             iterator_range& operator=( const iterator_range<Iterator>& r )
 222             {
 223                 m_Begin  = r.begin();
 224                 m_End    = r.end();
 225                 //
 226                 // remark: this need not necessarily be true, but it does no harm
 227                 //
 228                 singular = r.empty();
 229                 return *this;
 230             }
 231
 232             template< class ForwardRange >
 233             iterator_range& operator=( ForwardRange& r )
 234             {
 235                 m_Begin  = impl::adl_begin( r );
 236                 m_End    = impl::adl_end( r );
 237                 singular = false;
 238                 return *this;
 239             }
 240
 241             template< class ForwardRange >
 242             iterator_range& operator=( const ForwardRange& r )
 243             {
 244                 m_Begin  = impl::adl_begin( r );
 245                 m_End    = impl::adl_end( r );
 246                 singular = false;
 247                 return *this;
 248             }
 249
 250             IteratorT begin() const
 251             {
 252                 return m_Begin;
 253             }
 254
 255             IteratorT end() const
 256             {
 257                 return m_End;
 258             }
 259
 260             size_type size() const
 261             {
 262                 if( singular )
 263                     return 0;
 264
 265 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
 266                 return std::distance<IteratorT>( m_Begin, m_End );
 267 #else
 268                 return std::distance( m_Begin, m_End );
 269 #endif
 270             }
 271
 272             bool empty() const
 273             {
 274                 if( singular )
 275                     return true;
 276
 277                 return m_Begin == m_End;
 278             }
 279
 280 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
 281             operator bool() const
 282             {
 283                 return !empty();
 284             }
 285 #else
 286             typedef iterator (iterator_range::*unspecified_bool_type) () const;
 287             operator unspecified_bool_type() const
 288             {
 289                 return empty() ? 0: &iterator_range::end;
 290             }
 291 #endif
 292
 293             bool equal( const iterator_range& r ) const
 294             {
 295                 return singular == r.singular && m_Begin == r.m_Begin && m_End == r.m_End;
 296             }
 297
 298
 299 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 300
 301             bool operator==( const iterator_range& r ) const
 302             {
 303                 return iterator_range_detail::equal( *this, r );
 304             }
 305
 306             bool operator!=( const iterator_range& r ) const
 307             {
 308                 return !operator==(r);
 309             }
 310
 311            bool operator<( const iterator_range& r ) const
 312            {
 313                 return iterator_range_detail::less_than( *this, r );
 314            }
 315
 316 #endif
 317
 318         public: // convenience
 319            reference front() const
 320            {
 321                BOOST_ASSERT( !empty() );
 322                return *m_Begin;
 323            }
 324
 325            reference back() const
 326            {
 327                BOOST_ASSERT( !empty() );
 328                IteratorT last( m_End );
 329                return *--last;
 330            }
 331
 332            reference operator[]( size_type sz ) const
 333            {
 334                //BOOST_STATIC_ASSERT( is_random_access );
 335                BOOST_ASSERT( sz < size() );
 336                return m_Begin[sz];
 337            }
 338
 339            iterator_range& advance_begin( difference_type n )
 340            {
 341                std::advance( m_Begin, n );
 342                return *this;
 343            }
 344
 345            iterator_range& advance_end( difference_type n )
 346            {
 347                std::advance( m_End, n );
 348                return *this;
 349            }
 350
 351         private:
 352             // begin and end iterators
 353             IteratorT m_Begin;
 354             IteratorT m_End;
 355             bool      singular;
 356         };
 357
 358 //  iterator range free-standing operators ---------------------------//
 359
 360 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 361 #else
 362         template< class Iterator >
 363         inline bool empty( const iterator_range<Iterator>& r )
 364         {
 365             //
 366             // this will preserve the well-defined empty() even
 367             // though 'r' is singular.
 368             //
 369             return r.empty();
 370         }
 371 #endif
 372
 373 #ifndef BOOST_OLD_IOSTREAMS
 374
 375         //! iterator_range output operator
 376         /*!
 377             Output the range to an ostream. Elements are outputed
 378             in a sequence without separators.
 379         */
 380         template< typename IteratorT, typename Elem, typename Traits >
 381         inline std::basic_ostream<Elem,Traits>& operator<<(
 382                     std::basic_ostream<Elem, Traits>& Os,
 383                     const iterator_range<IteratorT>& r )
 384         {
 385             std::copy( r.begin(), r.end(),
 386                        std::ostream_iterator< BOOST_DEDUCED_TYPENAME
 387                                             iterator_value<IteratorT>::type,
 388                                               Elem, Traits>(Os) );
 389             return Os;
 390         }
 391
 392 #else
 393
 394         //! iterator_range output operator
 395         /*!
 396             Output the range to an ostream. Elements are outputed
 397             in a sequence without separators.
 398         */
 399         template< typename IteratorT >
 400         inline std::ostream& operator<<(
 401                     std::ostream& Os,
 402                     const iterator_range<IteratorT>& r )
 403         {
 404             std::copy( r.begin(), r.end(), std::ostream_iterator<char>(Os));
 405             return Os;
 406         }
 407
 408 #endif
 409
 410         /////////////////////////////////////////////////////////////////////
 411         // comparison operators
 412         /////////////////////////////////////////////////////////////////////
 413
 414         template< class IteratorT, class ForwardRange >
 415         inline bool operator==( const ForwardRange& l,
 416                                 const iterator_range<IteratorT>& r )
 417         {
 418             return iterator_range_detail::equal( l, r );
 419         }
 420
 421         template< class IteratorT, class ForwardRange >
 422         inline bool operator!=( const ForwardRange& l,
 423                                 const iterator_range<IteratorT>& r )
 424         {
 425             return !iterator_range_detail::equal( l, r );
 426         }
 427
 428         template< class IteratorT, class ForwardRange >
 429         inline bool operator<( const ForwardRange& l,
 430                                const iterator_range<IteratorT>& r )
 431         {
 432             return iterator_range_detail::less_than( l, r );
 433         }
 434
 435 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 436 #else
 437         template< class Iterator1T, class Iterator2T >
 438         inline bool operator==( const iterator_range<Iterator1T>& l,
 439                                 const iterator_range<Iterator2T>& r )
 440         {
 441             return iterator_range_detail::equal( l, r );
 442         }
 443
 444         template< class IteratorT, class ForwardRange >
 445         inline bool operator==( const iterator_range<IteratorT>& l,
 446                                 const ForwardRange& r )
 447         {
 448             return iterator_range_detail::equal( l, r );
 449         }
 450
 451
 452         template< class Iterator1T, class Iterator2T >
 453         inline bool operator!=( const iterator_range<Iterator1T>& l,
 454                                 const iterator_range<Iterator2T>& r )
 455         {
 456             return !iterator_range_detail::equal( l, r );
 457         }
 458
 459         template< class IteratorT, class ForwardRange >
 460         inline bool operator!=( const iterator_range<IteratorT>& l,
 461                                 const ForwardRange& r )
 462         {
 463             return !iterator_range_detail::equal( l, r );
 464         }
 465
 466
 467         template< class Iterator1T, class Iterator2T >
 468         inline bool operator<( const iterator_range<Iterator1T>& l,
 469                                const iterator_range<Iterator2T>& r )
 470         {
 471             return iterator_range_detail::less_than( l, r );
 472         }
 473
 474         template< class IteratorT, class ForwardRange >
 475         inline bool operator<( const iterator_range<IteratorT>& l,
 476                                const ForwardRange& r )
 477         {
 478             return iterator_range_detail::less_than( l, r );
 479         }
 480
 481 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 482
 483 //  iterator range utilities -----------------------------------------//
 484
 485         //! iterator_range construct helper
 486         /*!
 487             Construct an \c iterator_range from a pair of iterators
 488
 489             \param Begin A begin iterator
 490             \param End An end iterator
 491             \return iterator_range object
 492         */
 493         template< typename IteratorT >
 494         inline iterator_range< IteratorT >
 495         make_iterator_range( IteratorT Begin, IteratorT End )
 496         {
 497             return iterator_range<IteratorT>( Begin, End );
 498         }
 499
 500 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 501
 502         template< typename Range >
 503         inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
 504         make_iterator_range( Range& r )
 505         {
 506             return iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
 507                 ( boost::begin( r ), boost::end( r ) );
 508         }
 509
 510 #else
 511         //! iterator_range construct helper
 512         /*!
 513             Construct an \c iterator_range from a \c Range containing the begin
 514             and end iterators.
 515         */
 516         template< class ForwardRange >
 517         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 518         make_iterator_range( ForwardRange& r )
 519         {
 520            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 521                 ( r, iterator_range_detail::range_tag() );
 522         }
 523
 524         template< class ForwardRange >
 525         inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type >
 526         make_iterator_range( const ForwardRange& r )
 527         {
 528            return iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type >
 529                 ( r, iterator_range_detail::const_range_tag() );
 530         }
 531
 532 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 533
 534         namespace iterator_range_detail
 535         {
 536             template< class Range >
 537             inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
 538             make_range_impl( Range& r,
 539                              BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 540                              BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 541             {
 542                 if( advance_begin == 0 && advance_end == 0 )
 543                     return make_iterator_range( r );
 544
 545                 BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type
 546                     new_begin = boost::begin( r ),
 547                     new_end   = boost::end( r );
 548                 std::advance( new_begin, advance_begin );
 549                 std::advance( new_end, advance_end );
 550                 return make_iterator_range( new_begin, new_end );
 551             }
 552         }
 553
 554 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 555
 556         template< class Range >
 557         inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
 558         make_iterator_range( Range& r,
 559                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 560                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 561         {
 562             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 563             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 564         }
 565
 566 #else
 567
 568         template< class Range >
 569         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 570         make_iterator_range( Range& r,
 571                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 572                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 573         {
 574             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 575             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 576         }
 577
 578         template< class Range >
 579         inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<Range>::type >
 580         make_iterator_range( const Range& r,
 581                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 582                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 583         {
 584             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 585             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 586         }
 587
 588 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 589
 590         //! copy a range into a sequence
 591         /*!
 592             Construct a new sequence of the specified type from the elements
 593             in the given range
 594
 595             \param Range An input range
 596             \return New sequence
 597         */
 598         template< typename SeqT, typename Range >
 599         inline SeqT copy_range( const Range& r )
 600         {
 601             return SeqT( boost::begin( r ), boost::end( r ) );
 602         }
 603
 604 } // namespace 'boost'
 605
 606 #undef BOOST_OLD_IOSTREAMS
 607
 608 #endif