boost/range/iterator_range_core.hpp

   1 // Boost.Range library
   2 //
   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)
   7 //
   8 // For more information, see http://www.boost.org/libs/range/
   9 //
  10 #ifndef BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
  11 #define BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
  12
  13 #include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
  14 #include <boost/detail/workaround.hpp>
  15
  16 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
  17     #pragma warning( push )
  18     #pragma warning( disable : 4996 )
  19 #endif
  20
  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>
  34 #include <iterator>
  35 #include <algorithm>
  36 #include <cstddef>
  37
  38 /*! \file
  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.
  42 */
  43
  44
  45 namespace boost
  46 {
  47     namespace iterator_range_detail
  48     {
  49         //
  50         // The functions adl_begin and adl_end are implemented in a separate
  51         // class for gcc-2.9x
  52         //
  53         template<class IteratorT>
  54         struct iterator_range_impl {
  55             template< class ForwardRange >
  56             static IteratorT adl_begin( ForwardRange& r )
  57             {
  58                 return static_cast<IteratorT>( boost::begin( r ) );
  59             }
  60
  61             template< class ForwardRange >
  62             static IteratorT adl_end( ForwardRange& r )
  63             {
  64                 return static_cast<IteratorT>( boost::end( r ) );
  65             }
  66         };
  67
  68         template< class Left, class Right >
  69         inline bool less_than( const Left& l, const Right& r )
  70         {
  71             return std::lexicographical_compare( boost::begin(l),
  72                                                  boost::end(l),
  73                                                  boost::begin(r),
  74                                                  boost::end(r) );
  75         }
  76
  77         template< class Left, class Right >
  78         inline bool greater_than( const Left& l, const Right& r )
  79         {
  80             return less_than(r,l);
  81         }
  82
  83         template< class Left, class Right >
  84         inline bool less_or_equal_than( const Left& l, const Right& r )
  85         {
  86             return !iterator_range_detail::less_than(r,l);
  87         }
  88
  89         template< class Left, class Right >
  90         inline bool greater_or_equal_than( const Left& l, const Right& r )
  91         {
  92             return !iterator_range_detail::less_than(l,r);
  93         }
  94
  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)
  99         {
 100             return boost::equal(l, r);
 101         }
 102
 103         struct range_tag { };
 104         struct const_range_tag { };
 105     }
 106
 107 //  iterator range template class -----------------------------------------//
 108
 109         //! iterator_range class
 110         /*!
 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:
 115
 116             \code
 117                 boost::tolower( find( s, "UPPERCASE STRING" ) );
 118             \endcode
 119
 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.
 125         */
 126         template<class IteratorT>
 127         class iterator_range
 128         {
 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;
 133         public:
 134             //! this type
 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);
 138
 139             //! Encapsulated value type
 140             typedef BOOST_DEDUCED_TYPENAME
 141                 iterator_value<IteratorT>::type value_type;
 142
 143             //! Difference type
 144             typedef BOOST_DEDUCED_TYPENAME
 145                 iterator_difference<IteratorT>::type difference_type;
 146
 147             //! Size type
 148             typedef std::size_t size_type; // note: must be unsigned
 149
 150             //! This type
 151             typedef iterator_range<IteratorT> this_type;
 152
 153             //! Reference type
 154             //
 155             // Needed because value-type is the same for
 156             // const and non-const iterators
 157             //
 158             typedef BOOST_DEDUCED_TYPENAME
 159                 iterator_reference<IteratorT>::type reference;
 160
 161             //! const_iterator type
 162             /*!
 163                 There is no distinction between const_iterator and iterator.
 164                 These typedefs are provides to fulfill container interface
 165             */
 166             typedef IteratorT const_iterator;
 167             //! iterator type
 168             typedef IteratorT iterator;
 169
 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;
 175
 176         public:
 177             iterator_range() : m_Begin( iterator() ), m_End( iterator() )
 178             { }
 179
 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)
 184             {}
 185
 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 ) )
 190             {}
 191
 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 ) )
 196             {}
 197
 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 ) )
 202             {}
 203
 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 ) )
 208             {}
 209
 210             #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 211             this_type& operator=( const this_type& r )
 212             {
 213                 m_Begin  = r.begin();
 214                 m_End    = r.end();
 215                 return *this;
 216             }
 217             #endif
 218
 219             template< class Iterator >
 220             iterator_range& operator=( const iterator_range<Iterator>& r )
 221             {
 222                 m_Begin  = r.begin();
 223                 m_End    = r.end();
 224                 return *this;
 225             }
 226
 227             template< class ForwardRange >
 228             iterator_range& operator=( ForwardRange& r )
 229             {
 230                 m_Begin  = impl::adl_begin( r );
 231                 m_End    = impl::adl_end( r );
 232                 return *this;
 233             }
 234
 235             template< class ForwardRange >
 236             iterator_range& operator=( const ForwardRange& r )
 237             {
 238                 m_Begin  = impl::adl_begin( r );
 239                 m_End    = impl::adl_end( r );
 240                 return *this;
 241             }
 242
 243             IteratorT begin() const
 244             {
 245                 return m_Begin;
 246             }
 247
 248             IteratorT end() const
 249             {
 250                 return m_End;
 251             }
 252
 253             difference_type size() const
 254             {
 255                 return m_End - m_Begin;
 256             }
 257
 258             bool empty() const
 259             {
 260                 return m_Begin == m_End;
 261             }
 262
 263             operator unspecified_bool_type() const
 264             {
 265                 return safe_bool_t::to_unspecified_bool(m_Begin != m_End, &iterator_range::m_Begin);
 266             }
 267
 268             bool operator!() const
 269             {
 270                 return empty();
 271             }
 272
 273             bool equal( const iterator_range& r ) const
 274             {
 275                 return m_Begin == r.m_Begin && m_End == r.m_End;
 276             }
 277
 278
 279 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 280
 281             bool operator==( const iterator_range& r ) const
 282             {
 283                 return boost::equal( *this, r );
 284             }
 285
 286             bool operator!=( const iterator_range& r ) const
 287             {
 288                 return !operator==(r);
 289             }
 290
 291            bool operator<( const iterator_range& r ) const
 292            {
 293                return iterator_range_detail::less_than( *this, r );
 294            }
 295
 296            bool operator>( const iterator_range& r ) const
 297            {
 298                return iterator_range_detail::greater_than( *this, r );
 299            }
 300
 301            bool operator<=( const iterator_range& r ) const
 302            {
 303                return iterator_range_detail::less_or_equal_than( *this, r );
 304            }
 305
 306            bool operator>=( const iterator_range& r ) const
 307            {
 308                return iterator_range_detail::greater_or_equal_than( *this, r );
 309            }
 310
 311 #endif
 312
 313         public: // convenience
 314            reference front() const
 315            {
 316                BOOST_ASSERT( !empty() );
 317                return *m_Begin;
 318            }
 319
 320            reference back() const
 321            {
 322                BOOST_ASSERT( !empty() );
 323                IteratorT last( m_End );
 324                return *--last;
 325            }
 326
 327            // pop_front() - added to model the SinglePassRangePrimitiveConcept
 328            void pop_front()
 329            {
 330                BOOST_ASSERT( !empty() );
 331                ++m_Begin;
 332            }
 333
 334            // pop_back() - added to model the BidirectionalRangePrimitiveConcept
 335            void pop_back()
 336            {
 337                BOOST_ASSERT( !empty() );
 338                --m_End;
 339            }
 340
 341            reference operator[]( difference_type at ) const
 342            {
 343                BOOST_ASSERT( at >= 0 && at < size() );
 344                return m_Begin[at];
 345            }
 346
 347            //
 348            // When storing transform iterators, operator[]()
 349            // fails because it returns by reference. Therefore
 350            // operator()() is provided for these cases.
 351            //
 352            abstract_value_type operator()( difference_type at ) const
 353            {
 354                BOOST_ASSERT( at >= 0 && at < size() );
 355                return m_Begin[at];
 356            }
 357
 358            iterator_range& advance_begin( difference_type n )
 359            {
 360                std::advance( m_Begin, n );
 361                return *this;
 362            }
 363
 364            iterator_range& advance_end( difference_type n )
 365            {
 366                std::advance( m_End, n );
 367                return *this;
 368            }
 369
 370         private:
 371             // begin and end iterators
 372             IteratorT m_Begin;
 373             IteratorT m_End;
 374
 375         protected:
 376             //
 377             // Allow subclasses an easy way to access the
 378             // base type
 379             //
 380             typedef iterator_range iterator_range_;
 381         };
 382
 383 //  iterator range free-standing operators ---------------------------//
 384
 385         /////////////////////////////////////////////////////////////////////
 386         // comparison operators
 387         /////////////////////////////////////////////////////////////////////
 388
 389         template< class IteratorT, class ForwardRange >
 390         inline bool operator==( const ForwardRange& l,
 391                                 const iterator_range<IteratorT>& r )
 392         {
 393             return boost::equal( l, r );
 394         }
 395
 396         template< class IteratorT, class ForwardRange >
 397         inline bool operator!=( const ForwardRange& l,
 398                                 const iterator_range<IteratorT>& r )
 399         {
 400             return !boost::equal( l, r );
 401         }
 402
 403         template< class IteratorT, class ForwardRange >
 404         inline bool operator<( const ForwardRange& l,
 405                                const iterator_range<IteratorT>& r )
 406         {
 407             return iterator_range_detail::less_than( l, r );
 408         }
 409
 410         template< class IteratorT, class ForwardRange >
 411         inline bool operator<=( const ForwardRange& l,
 412                                 const iterator_range<IteratorT>& r )
 413         {
 414             return iterator_range_detail::less_or_equal_than( l, r );
 415         }
 416
 417         template< class IteratorT, class ForwardRange >
 418         inline bool operator>( const ForwardRange& l,
 419                                const iterator_range<IteratorT>& r )
 420         {
 421             return iterator_range_detail::greater_than( l, r );
 422         }
 423
 424         template< class IteratorT, class ForwardRange >
 425         inline bool operator>=( const ForwardRange& l,
 426                                 const iterator_range<IteratorT>& r )
 427         {
 428             return iterator_range_detail::greater_or_equal_than( l, r );
 429         }
 430
 431 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 432 #else
 433         template< class Iterator1T, class Iterator2T >
 434         inline bool operator==( const iterator_range<Iterator1T>& l,
 435                                 const iterator_range<Iterator2T>& r )
 436         {
 437             return boost::equal( l, r );
 438         }
 439
 440         template< class IteratorT, class ForwardRange >
 441         inline bool operator==( const iterator_range<IteratorT>& l,
 442                                 const ForwardRange& r )
 443         {
 444             return boost::equal( l, r );
 445         }
 446
 447
 448         template< class Iterator1T, class Iterator2T >
 449         inline bool operator!=( const iterator_range<Iterator1T>& l,
 450                                 const iterator_range<Iterator2T>& r )
 451         {
 452             return !boost::equal( l, r );
 453         }
 454
 455         template< class IteratorT, class ForwardRange >
 456         inline bool operator!=( const iterator_range<IteratorT>& l,
 457                                 const ForwardRange& r )
 458         {
 459             return !boost::equal( l, r );
 460         }
 461
 462
 463         template< class Iterator1T, class Iterator2T >
 464         inline bool operator<( const iterator_range<Iterator1T>& l,
 465                                const iterator_range<Iterator2T>& r )
 466         {
 467             return iterator_range_detail::less_than( l, r );
 468         }
 469
 470         template< class IteratorT, class ForwardRange >
 471         inline bool operator<( const iterator_range<IteratorT>& l,
 472                                const ForwardRange& r )
 473         {
 474             return iterator_range_detail::less_than( l, r );
 475         }
 476
 477         template< class Iterator1T, class Iterator2T >
 478         inline bool operator<=( const iterator_range<Iterator1T>& l,
 479                                 const iterator_range<Iterator2T>& r )
 480         {
 481             return iterator_range_detail::less_or_equal_than( l, r );
 482         }
 483
 484         template< class IteratorT, class ForwardRange >
 485         inline bool operator<=( const iterator_range<IteratorT>& l,
 486                                 const ForwardRange& r )
 487         {
 488             return iterator_range_detail::less_or_equal_than( l, r );
 489         }
 490
 491         template< class Iterator1T, class Iterator2T >
 492         inline bool operator>( const iterator_range<Iterator1T>& l,
 493                                const iterator_range<Iterator2T>& r )
 494         {
 495             return iterator_range_detail::greater_than( l, r );
 496         }
 497
 498         template< class IteratorT, class ForwardRange >
 499         inline bool operator>( const iterator_range<IteratorT>& l,
 500                                const ForwardRange& r )
 501         {
 502             return iterator_range_detail::greater_than( l, r );
 503         }
 504
 505         template< class Iterator1T, class Iterator2T >
 506         inline bool operator>=( const iterator_range<Iterator1T>& l,
 507                                 const iterator_range<Iterator2T>& r )
 508         {
 509             return iterator_range_detail::greater_or_equal_than( l, r );
 510         }
 511
 512         template< class IteratorT, class ForwardRange >
 513         inline bool operator>=( const iterator_range<IteratorT>& l,
 514                                 const ForwardRange& r )
 515         {
 516             return iterator_range_detail::greater_or_equal_than( l, r );
 517         }
 518
 519 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 520
 521 //  iterator range utilities -----------------------------------------//
 522
 523         //! iterator_range construct helper
 524         /*!
 525             Construct an \c iterator_range from a pair of iterators
 526
 527             \param Begin A begin iterator
 528             \param End An end iterator
 529             \return iterator_range object
 530         */
 531         template< typename IteratorT >
 532         inline iterator_range< IteratorT >
 533         make_iterator_range( IteratorT Begin, IteratorT End )
 534         {
 535             return iterator_range<IteratorT>( Begin, End );
 536         }
 537
 538 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 539
 540         template< typename Range >
 541         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 542         make_iterator_range( Range& r )
 543         {
 544             return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 545                 ( boost::begin( r ), boost::end( r ) );
 546         }
 547
 548 #else
 549         //! iterator_range construct helper
 550         /*!
 551             Construct an \c iterator_range from a \c Range containing the begin
 552             and end iterators.
 553         */
 554         template< class ForwardRange >
 555         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 556         make_iterator_range( ForwardRange& r )
 557         {
 558            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 559                 ( r, iterator_range_detail::range_tag() );
 560         }
 561
 562         template< class ForwardRange >
 563         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 564         make_iterator_range( const ForwardRange& r )
 565         {
 566            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 567                 ( r, iterator_range_detail::const_range_tag() );
 568         }
 569
 570 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 571
 572         namespace iterator_range_detail
 573         {
 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 )
 579             {
 580                 //
 581                 // Not worth the effort
 582                 //
 583                 //if( advance_begin == 0 && advance_end == 0 )
 584                 //    return make_iterator_range( r );
 585                 //
 586
 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 );
 593             }
 594         }
 595
 596 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 597
 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 )
 603         {
 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 );
 606         }
 607
 608 #else
 609
 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 )
 615         {
 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 );
 618         }
 619
 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 )
 625         {
 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 );
 628         }
 629
 630 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 631
 632         //! copy a range into a sequence
 633         /*!
 634             Construct a new sequence of the specified type from the elements
 635             in the given range
 636
 637             \param Range An input range
 638             \return New sequence
 639         */
 640         template< typename SeqT, typename Range >
 641         inline SeqT copy_range( const Range& r )
 642         {
 643             return SeqT( boost::begin( r ), boost::end( r ) );
 644         }
 645
 646 } // namespace 'boost'
 647
 648 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
 649     #pragma warning( pop )
 650 #endif
 651
 652 #endif
 653