l4/pkg/boost-lite/include/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 #include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
  15 #include <boost/detail/workaround.hpp>
  16
  17 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
  18     #pragma warning( push )
  19     #pragma warning( disable : 4996 )
  20 #endif
  21
  22 // From boost/dynamic_bitset.hpp; thanks to Matthias Troyer for Cray X1 patch.
  23 #ifndef BOOST_OLD_IOSTREAMS
  24 # if defined(__STL_CONFIG_H) && \
  25     !defined (__STL_USE_NEW_IOSTREAMS) && !defined(__crayx1) \
  26     /**/
  27 #  define BOOST_OLD_IOSTREAMS
  28 # endif
  29 #endif // #ifndef BOOST_OLD_IOSTREAMS
  30
  31 #include <boost/assert.hpp>
  32 #include <boost/iterator/iterator_traits.hpp>
  33 #include <boost/type_traits/is_abstract.hpp>
  34 #include <boost/range/functions.hpp>
  35 #include <boost/range/iterator.hpp>
  36 #include <boost/range/difference_type.hpp>
  37 #include <boost/utility/enable_if.hpp>
  38 #include <iterator>
  39 #include <algorithm>
  40 #ifndef _STLP_NO_IOSTREAMS
  41 # ifndef BOOST_OLD_IOSTREAMS
  42 #  include <ostream>
  43 # else
  44 #  include <ostream.h>
  45 # endif
  46 #endif // _STLP_NO_IOSTREAMS
  47 #include <cstddef>
  48
  49 /*! \file
  50     Defines the \c iterator_class and related functions.
  51     \c iterator_range is a simple wrapper of iterator pair idiom. It provides
  52     a rich subset of Container interface.
  53 */
  54
  55
  56 namespace boost
  57 {
  58     namespace iterator_range_detail
  59     {
  60         //
  61         // The functions adl_begin and adl_end are implemented in a separate
  62         // class for gcc-2.9x
  63         //
  64         template<typename IteratorT>
  65         struct iterator_range_impl {
  66             template< class ForwardRange >
  67             static IteratorT adl_begin( ForwardRange& r )
  68             {
  69                 return IteratorT( boost::begin( r ) );
  70             }
  71
  72             template< class ForwardRange >
  73             static IteratorT adl_end( ForwardRange& r )
  74             {
  75                 return IteratorT( boost::end( r ) );
  76             }
  77         };
  78
  79         template< class Left, class Right >
  80         inline bool equal( const Left& l, const Right& r )
  81         {
  82             typedef BOOST_DEDUCED_TYPENAME boost::range_difference<Left>::type sz_type;
  83
  84             sz_type l_size = boost::distance( l ),
  85                     r_size = boost::distance( r );
  86
  87             if( l_size != r_size )
  88                 return false;
  89
  90             return std::equal( boost::begin(l), boost::end(l),
  91                                boost::begin(r) );
  92         }
  93
  94         template< class Left, class Right >
  95         inline bool less_than( const Left& l, const Right& r )
  96         {
  97             return std::lexicographical_compare( boost::begin(l),
  98                                                  boost::end(l),
  99                                                  boost::begin(r),
 100                                                  boost::end(r) );
 101         }
 102
 103         struct range_tag { };
 104         struct const_range_tag { };
 105
 106     }
 107
 108 //  iterator range template class -----------------------------------------//
 109
 110         //! iterator_range class
 111         /*!
 112             An \c iterator_range delimits a range in a sequence by beginning and ending iterators.
 113             An iterator_range can be passed to an algorithm which requires a sequence as an input.
 114             For example, the \c toupper() function may be used most frequently on strings,
 115             but can also be used on iterator_ranges:
 116
 117             \code
 118                 boost::tolower( find( s, "UPPERCASE STRING" ) );
 119             \endcode
 120
 121             Many algorithms working with sequences take a pair of iterators,
 122             delimiting a working range, as an arguments. The \c iterator_range class is an
 123             encapsulation of a range identified by a pair of iterators.
 124             It provides a collection interface,
 125             so it is possible to pass an instance to an algorithm requiring a collection as an input.
 126         */
 127         template<typename IteratorT>
 128         class iterator_range
 129         {
 130         protected: // Used by sub_range
 131             //! implementation class
 132             typedef iterator_range_detail::iterator_range_impl<IteratorT> impl;
 133         public:
 134
 135             //! this type
 136             typedef iterator_range<IteratorT> 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             //! Refence 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::is_abstract<value_type>,
 173                                  reference, value_type >::type abstract_value_type;
 174
 175         public:
 176             iterator_range() : m_Begin( iterator() ), m_End( iterator() )
 177                 #ifndef NDEBUG
 178             , singular( true )
 179                 #endif
 180             { }
 181
 182             //! Constructor from a pair of iterators
 183             template< class Iterator >
 184             iterator_range( Iterator Begin, Iterator End ) :
 185                 m_Begin(Begin), m_End(End)
 186                 #ifndef NDEBUG
 187             , singular(false)
 188                 #endif
 189             {}
 190
 191             //! Constructor from a Range
 192             template< class Range >
 193             iterator_range( const Range& r ) :
 194                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 195                 #ifndef NDEBUG
 196             , singular(false)
 197                 #endif
 198             {}
 199
 200             //! Constructor from a Range
 201             template< class Range >
 202             iterator_range( Range& r ) :
 203                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 204                 #ifndef NDEBUG
 205             , singular(false)
 206                 #endif
 207             {}
 208
 209             //! Constructor from a Range
 210             template< class Range >
 211             iterator_range( const Range& r, iterator_range_detail::const_range_tag ) :
 212                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 213                 #ifndef NDEBUG
 214             , singular(false)
 215                 #endif
 216             {}
 217
 218             //! Constructor from a Range
 219             template< class Range >
 220             iterator_range( Range& r, iterator_range_detail::range_tag ) :
 221                 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 222                 #ifndef NDEBUG
 223             , singular(false)
 224                 #endif
 225             {}
 226
 227             #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 228             this_type& operator=( const this_type& r )
 229             {
 230                 m_Begin  = r.begin();
 231                 m_End    = r.end();
 232
 233                 #ifndef NDEBUG
 234                 singular = r.singular;
 235                 #endif
 236                 return *this;
 237             }
 238             #endif
 239
 240             template< class Iterator >
 241             iterator_range& operator=( const iterator_range<Iterator>& r )
 242             {
 243                 m_Begin  = r.begin();
 244                 m_End    = r.end();
 245                 #ifndef NDEBUG
 246                 singular = r.is_singular();
 247                 #endif
 248                 return *this;
 249             }
 250
 251             template< class ForwardRange >
 252             iterator_range& operator=( ForwardRange& r )
 253             {
 254                 m_Begin  = impl::adl_begin( r );
 255                 m_End    = impl::adl_end( r );
 256                 #ifndef NDEBUG
 257                 singular = false;
 258                 #endif
 259                 return *this;
 260             }
 261
 262             template< class ForwardRange >
 263             iterator_range& operator=( const ForwardRange& r )
 264             {
 265                 m_Begin  = impl::adl_begin( r );
 266                 m_End    = impl::adl_end( r );
 267                 #ifndef NDEBUG
 268                 singular = false;
 269                 #endif
 270                 return *this;
 271             }
 272
 273             IteratorT begin() const
 274             {
 275                 BOOST_ASSERT( !is_singular() );
 276                 return m_Begin;
 277             }
 278
 279             IteratorT end() const
 280             {
 281                 BOOST_ASSERT( !is_singular() );
 282                 return m_End;
 283             }
 284
 285             difference_type size() const
 286             {
 287                 BOOST_ASSERT( !is_singular() );
 288                 return m_End - m_Begin;
 289             }
 290
 291             bool empty() const
 292             {
 293                 BOOST_ASSERT( !is_singular() );
 294                 return m_Begin == m_End;
 295             }
 296
 297 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
 298             operator bool() const
 299             {
 300                 return !empty();
 301             }
 302 #else
 303             typedef iterator (iterator_range::*unspecified_bool_type) () const;
 304             operator unspecified_bool_type() const
 305             {
 306                 return empty() ? 0: &iterator_range::end;
 307             }
 308 #endif
 309
 310             bool equal( const iterator_range& r ) const
 311             {
 312                 BOOST_ASSERT( !is_singular() );
 313                 return m_Begin == r.m_Begin && m_End == r.m_End;
 314             }
 315
 316
 317 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 318
 319             bool operator==( const iterator_range& r ) const
 320             {
 321                 BOOST_ASSERT( !is_singular() );
 322                 return iterator_range_detail::equal( *this, r );
 323             }
 324
 325             bool operator!=( const iterator_range& r ) const
 326             {
 327                 BOOST_ASSERT( !is_singular() );
 328                 return !operator==(r);
 329             }
 330
 331            bool operator<( const iterator_range& r ) const
 332            {
 333                BOOST_ASSERT( !is_singular() );
 334                return iterator_range_detail::less_than( *this, r );
 335            }
 336
 337 #endif
 338
 339         public: // convenience
 340            reference front() const
 341            {
 342                BOOST_ASSERT( !empty() );
 343                return *m_Begin;
 344            }
 345
 346            reference back() const
 347            {
 348                BOOST_ASSERT( !empty() );
 349                IteratorT last( m_End );
 350                return *--last;
 351            }
 352
 353            reference operator[]( difference_type at ) const
 354            {
 355                BOOST_ASSERT( at >= 0 && at < size() );
 356                return m_Begin[at];
 357            }
 358
 359            //
 360            // When storing transform iterators, operator[]()
 361            // fails because it returns by reference. Therefore
 362            // operator()() is provided for these cases.
 363            //
 364            abstract_value_type operator()( difference_type at ) const
 365            {
 366                BOOST_ASSERT( at >= 0 && at < size() );
 367                return m_Begin[at];
 368            }
 369
 370            iterator_range& advance_begin( difference_type n )
 371            {
 372                BOOST_ASSERT( !is_singular() );
 373                std::advance( m_Begin, n );
 374                return *this;
 375            }
 376
 377            iterator_range& advance_end( difference_type n )
 378            {
 379                BOOST_ASSERT( !is_singular() );
 380                std::advance( m_End, n );
 381                return *this;
 382            }
 383
 384         private:
 385             // begin and end iterators
 386             IteratorT m_Begin;
 387             IteratorT m_End;
 388
 389             #ifndef NDEBUG
 390             bool      singular;
 391             #endif
 392
 393         public:
 394             bool is_singular() const
 395             {
 396                  #ifndef NDEBUG
 397                  return singular;
 398                  #else
 399                  return false;
 400                  #endif
 401             }
 402
 403         protected:
 404             //
 405             // Allow subclasses an easy way to access the
 406             // base type
 407             //
 408             typedef iterator_range iterator_range_;
 409         };
 410
 411 //  iterator range free-standing operators ---------------------------//
 412
 413 #ifndef _STLP_NO_IOSTREAMS
 414 # ifndef BOOST_OLD_IOSTREAMS
 415
 416         //! iterator_range output operator
 417         /*!
 418             Output the range to an ostream. Elements are outputed
 419             in a sequence without separators.
 420         */
 421         template< typename IteratorT, typename Elem, typename Traits >
 422         inline std::basic_ostream<Elem,Traits>& operator<<(
 423                     std::basic_ostream<Elem, Traits>& Os,
 424                     const iterator_range<IteratorT>& r )
 425         {
 426             std::copy( r.begin(), r.end(),
 427                        std::ostream_iterator< BOOST_DEDUCED_TYPENAME
 428                                               iterator_value<IteratorT>::type,
 429                                               Elem, Traits>(Os) );
 430             return Os;
 431         }
 432
 433 # else
 434
 435         //! iterator_range output operator
 436         /*!
 437             Output the range to an ostream. Elements are outputed
 438             in a sequence without separators.
 439         */
 440         template< typename IteratorT >
 441         inline std::ostream& operator<<(
 442                     std::ostream& Os,
 443                     const iterator_range<IteratorT>& r )
 444         {
 445             std::copy( r.begin(), r.end(), std::ostream_iterator<char>(Os));
 446             return Os;
 447         }
 448
 449 # endif
 450 #endif // _STLP_NO_IOSTREAMS
 451
 452         /////////////////////////////////////////////////////////////////////
 453         // comparison operators
 454         /////////////////////////////////////////////////////////////////////
 455
 456         template< class IteratorT, class ForwardRange >
 457         inline bool operator==( const ForwardRange& l,
 458                                 const iterator_range<IteratorT>& r )
 459         {
 460             return iterator_range_detail::equal( l, r );
 461         }
 462
 463         template< class IteratorT, class ForwardRange >
 464         inline bool operator!=( const ForwardRange& l,
 465                                 const iterator_range<IteratorT>& r )
 466         {
 467             return !iterator_range_detail::equal( l, r );
 468         }
 469
 470         template< class IteratorT, class ForwardRange >
 471         inline bool operator<( const ForwardRange& l,
 472                                const iterator_range<IteratorT>& r )
 473         {
 474             return iterator_range_detail::less_than( l, r );
 475         }
 476
 477 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 478 #else
 479         template< class Iterator1T, class Iterator2T >
 480         inline bool operator==( const iterator_range<Iterator1T>& l,
 481                                 const iterator_range<Iterator2T>& r )
 482         {
 483             return iterator_range_detail::equal( l, r );
 484         }
 485
 486         template< class IteratorT, class ForwardRange >
 487         inline bool operator==( const iterator_range<IteratorT>& l,
 488                                 const ForwardRange& r )
 489         {
 490             return iterator_range_detail::equal( l, r );
 491         }
 492
 493
 494         template< class Iterator1T, class Iterator2T >
 495         inline bool operator!=( const iterator_range<Iterator1T>& l,
 496                                 const iterator_range<Iterator2T>& r )
 497         {
 498             return !iterator_range_detail::equal( l, r );
 499         }
 500
 501         template< class IteratorT, class ForwardRange >
 502         inline bool operator!=( const iterator_range<IteratorT>& l,
 503                                 const ForwardRange& r )
 504         {
 505             return !iterator_range_detail::equal( l, r );
 506         }
 507
 508
 509         template< class Iterator1T, class Iterator2T >
 510         inline bool operator<( const iterator_range<Iterator1T>& l,
 511                                const iterator_range<Iterator2T>& r )
 512         {
 513             return iterator_range_detail::less_than( l, r );
 514         }
 515
 516         template< class IteratorT, class ForwardRange >
 517         inline bool operator<( const iterator_range<IteratorT>& l,
 518                                const ForwardRange& r )
 519         {
 520             return iterator_range_detail::less_than( l, r );
 521         }
 522
 523 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 524
 525 //  iterator range utilities -----------------------------------------//
 526
 527         //! iterator_range construct helper
 528         /*!
 529             Construct an \c iterator_range from a pair of iterators
 530
 531             \param Begin A begin iterator
 532             \param End An end iterator
 533             \return iterator_range object
 534         */
 535         template< typename IteratorT >
 536         inline iterator_range< IteratorT >
 537         make_iterator_range( IteratorT Begin, IteratorT End )
 538         {
 539             return iterator_range<IteratorT>( Begin, End );
 540         }
 541
 542 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 543
 544         template< typename Range >
 545         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 546         make_iterator_range( Range& r )
 547         {
 548             return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 549                 ( boost::begin( r ), boost::end( r ) );
 550         }
 551
 552 #else
 553         //! iterator_range construct helper
 554         /*!
 555             Construct an \c iterator_range from a \c Range containing the begin
 556             and end iterators.
 557         */
 558         template< class ForwardRange >
 559         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 560         make_iterator_range( ForwardRange& r )
 561         {
 562            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 563                 ( r, iterator_range_detail::range_tag() );
 564         }
 565
 566         template< class ForwardRange >
 567         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 568         make_iterator_range( const ForwardRange& r )
 569         {
 570            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 571                 ( r, iterator_range_detail::const_range_tag() );
 572         }
 573
 574 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 575
 576         namespace iterator_range_detail
 577         {
 578             template< class Range >
 579             inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 580             make_range_impl( Range& r,
 581                              BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 582                              BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 583             {
 584                 //
 585                 // Not worth the effort
 586                 //
 587                 //if( advance_begin == 0 && advance_end == 0 )
 588                 //    return make_iterator_range( r );
 589                 //
 590
 591                 BOOST_DEDUCED_TYPENAME range_iterator<Range>::type
 592                     new_begin = boost::begin( r ),
 593                     new_end   = boost::end( r );
 594                 std::advance( new_begin, advance_begin );
 595                 std::advance( new_end, advance_end );
 596                 return make_iterator_range( new_begin, new_end );
 597             }
 598         }
 599
 600 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 601
 602         template< class Range >
 603         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 604         make_iterator_range( Range& r,
 605                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 606                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 607         {
 608             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 609             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 610         }
 611
 612 #else
 613
 614         template< class Range >
 615         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 616         make_iterator_range( Range& r,
 617                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 618                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 619         {
 620             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 621             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 622         }
 623
 624         template< class Range >
 625         inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const Range>::type >
 626         make_iterator_range( const Range& r,
 627                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 628                     BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 629         {
 630             //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 631             return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 632         }
 633
 634 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 635
 636         //! copy a range into a sequence
 637         /*!
 638             Construct a new sequence of the specified type from the elements
 639             in the given range
 640
 641             \param Range An input range
 642             \return New sequence
 643         */
 644         template< typename SeqT, typename Range >
 645         inline SeqT copy_range( const Range& r )
 646         {
 647             return SeqT( boost::begin( r ), boost::end( r ) );
 648         }
 649
 650 } // namespace 'boost'
 651
 652 #undef BOOST_OLD_IOSTREAMS
 653
 654 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
 655     #pragma warning( pop )
 656 #endif
 657
 658 #endif
 659