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/type_traits/is_abstract.hpp> 25 #include <boost/type_traits/is_pointer.hpp> 26 #include <boost/range/functions.hpp> 27 #include <boost/range/iterator.hpp> 28 #include <boost/range/difference_type.hpp> 29 #include <boost/range/algorithm/equal.hpp> 30 #include <boost/range/detail/safe_bool.hpp> 31 #include <boost/utility/enable_if.hpp> 32 #include <iterator> 33 #include <algorithm> 34 #include <cstddef> 35 36 /*! \file 37 Defines the \c iterator_class and related functions. 38 \c iterator_range is a simple wrapper of iterator pair idiom. It provides 39 a rich subset of Container interface. 40 */ 41 42 43 namespace boost 44 { 45 namespace iterator_range_detail 46 { 47 // 48 // The functions adl_begin and adl_end are implemented in a separate 49 // class for gcc-2.9x 50 // 51 template<class IteratorT> 52 struct iterator_range_impl { 53 template< class ForwardRange > 54 static IteratorT adl_begin( ForwardRange& r ) 55 { 56 return static_cast<IteratorT>( boost::begin( r ) ); 57 } 58 59 template< class ForwardRange > 60 static IteratorT adl_end( ForwardRange& r ) 61 { 62 return static_cast<IteratorT>( boost::end( r ) ); 63 } 64 }; 65 66 template< class Left, class Right > 67 inline bool less_than( const Left& l, const Right& r ) 68 { 69 return std::lexicographical_compare( boost::begin(l), 70 boost::end(l), 71 boost::begin(r), 72 boost::end(r) ); 73 } 74 75 template< class Left, class Right > 76 inline bool greater_than( const Left& l, const Right& r ) 77 { 78 return less_than(r,l); 79 } 80 81 template< class Left, class Right > 82 inline bool less_or_equal_than( const Left& l, const Right& r ) 83 { 84 return !iterator_range_detail::less_than(r,l); 85 } 86 87 template< class Left, class Right > 88 inline bool greater_or_equal_than( const Left& l, const Right& r ) 89 { 90 return !iterator_range_detail::less_than(l,r); 91 } 92 93 // This version is maintained since it is used in other boost libraries 94 // such as Boost.Assign 95 template< class Left, class Right > 96 inline bool equal(const Left& l, const Right& r) 97 { 98 return boost::equal(l, r); 99 } 100 101 struct range_tag { }; 102 struct const_range_tag { }; 103 } 104 105 // iterator range template class -----------------------------------------// 106 107 //! iterator_range class 108 /*! 109 An \c iterator_range delimits a range in a sequence by beginning and ending iterators. 110 An iterator_range can be passed to an algorithm which requires a sequence as an input. 111 For example, the \c toupper() function may be used most frequently on strings, 112 but can also be used on iterator_ranges: 113 114 \code 115 boost::tolower( find( s, "UPPERCASE STRING" ) ); 116 \endcode 117 118 Many algorithms working with sequences take a pair of iterators, 119 delimiting a working range, as an arguments. The \c iterator_range class is an 120 encapsulation of a range identified by a pair of iterators. 121 It provides a collection interface, 122 so it is possible to pass an instance to an algorithm requiring a collection as an input. 123 */ 124 template<class IteratorT> 125 class iterator_range 126 { 127 typedef range_detail::safe_bool< IteratorT iterator_range<IteratorT>::* > safe_bool_t; 128 protected: // Used by sub_range 129 //! implementation class 130 typedef iterator_range_detail::iterator_range_impl<IteratorT> impl; 131 public: 132 //! this type 133 typedef iterator_range<IteratorT> type; 134 typedef BOOST_DEDUCED_TYPENAME safe_bool_t::unspecified_bool_type unspecified_bool_type; 135 //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type); 136 137 //! Encapsulated value type 138 typedef BOOST_DEDUCED_TYPENAME 139 iterator_value<IteratorT>::type value_type; 140 141 //! Difference type 142 typedef BOOST_DEDUCED_TYPENAME 143 iterator_difference<IteratorT>::type difference_type; 144 145 //! Size type 146 typedef std::size_t size_type; // note: must be unsigned 147 148 //! This type 149 typedef iterator_range<IteratorT> this_type; 150 151 //! Reference type 152 // 153 // Needed because value-type is the same for 154 // const and non-const iterators 155 // 156 typedef BOOST_DEDUCED_TYPENAME 157 iterator_reference<IteratorT>::type reference; 158 159 //! const_iterator type 160 /*! 161 There is no distinction between const_iterator and iterator. 162 These typedefs are provides to fulfill container interface 163 */ 164 typedef IteratorT const_iterator; 165 //! iterator type 166 typedef IteratorT iterator; 167 168 private: // for return value of operator()() 169 typedef BOOST_DEDUCED_TYPENAME 170 boost::mpl::if_< boost::is_abstract<value_type>, 171 reference, value_type >::type abstract_value_type; 172 173 public: 174 iterator_range() : m_Begin( iterator() ), m_End( iterator() ) 175 { } 176 177 //! Constructor from a pair of iterators 178 template< class Iterator > 179 iterator_range( Iterator Begin, Iterator End ) : 180 m_Begin(Begin), m_End(End) 181 {} 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 {} 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 {} 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 {} 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 {} 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 return *this; 213 } 214 #endif 215 216 template< class Iterator > 217 iterator_range& operator=( const iterator_range<Iterator>& r ) 218 { 219 m_Begin = r.begin(); 220 m_End = r.end(); 221 return *this; 222 } 223 224 template< class ForwardRange > 225 iterator_range& operator=( ForwardRange& r ) 226 { 227 m_Begin = impl::adl_begin( r ); 228 m_End = impl::adl_end( r ); 229 return *this; 230 } 231 232 template< class ForwardRange > 233 iterator_range& operator=( const ForwardRange& r ) 234 { 235 m_Begin = impl::adl_begin( r ); 236 m_End = impl::adl_end( r ); 237 return *this; 238 } 239 240 IteratorT begin() const 241 { 242 return m_Begin; 243 } 244 245 IteratorT end() const 246 { 247 return m_End; 248 } 249 250 difference_type size() const 251 { 252 return m_End - m_Begin; 253 } 254 255 bool empty() const 256 { 257 return m_Begin == m_End; 258 } 259 260 operator unspecified_bool_type() const 261 { 262 return safe_bool_t::to_unspecified_bool(m_Begin != m_End, &iterator_range::m_Begin); 263 } 264 265 bool operator!() const 266 { 267 return empty(); 268 } 269 270 bool equal( const iterator_range& r ) const 271 { 272 return m_Begin == r.m_Begin && m_End == r.m_End; 273 } 274 275 276 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 277 278 bool operator==( const iterator_range& r ) const 279 { 280 return boost::equal( *this, r ); 281 } 282 283 bool operator!=( const iterator_range& r ) const 284 { 285 return !operator==(r); 286 } 287 288 bool operator<( const iterator_range& r ) const 289 { 290 return iterator_range_detail::less_than( *this, r ); 291 } 292 293 bool operator>( const iterator_range& r ) const 294 { 295 return iterator_range_detail::greater_than( *this, r ); 296 } 297 298 bool operator<=( const iterator_range& r ) const 299 { 300 return iterator_range_detail::less_or_equal_than( *this, r ); 301 } 302 303 bool operator>=( const iterator_range& r ) const 304 { 305 return iterator_range_detail::greater_or_equal_than( *this, r ); 306 } 307 308 #endif 309 310 public: // convenience 311 reference front() const 312 { 313 BOOST_ASSERT( !empty() ); 314 return *m_Begin; 315 } 316 317 reference back() const 318 { 319 BOOST_ASSERT( !empty() ); 320 IteratorT last( m_End ); 321 return *--last; 322 } 323 324 // pop_front() - added to model the SinglePassRangePrimitiveConcept 325 void pop_front() 326 { 327 BOOST_ASSERT( !empty() ); 328 ++m_Begin; 329 } 330 331 // pop_back() - added to model the BidirectionalRangePrimitiveConcept 332 void pop_back() 333 { 334 BOOST_ASSERT( !empty() ); 335 --m_End; 336 } 337 338 reference operator[]( difference_type at ) const 339 { 340 BOOST_ASSERT( at >= 0 && at < size() ); 341 return m_Begin[at]; 342 } 343 344 // 345 // When storing transform iterators, operator[]() 346 // fails because it returns by reference. Therefore 347 // operator()() is provided for these cases. 348 // 349 abstract_value_type operator()( difference_type at ) const 350 { 351 BOOST_ASSERT( at >= 0 && at < size() ); 352 return m_Begin[at]; 353 } 354 355 iterator_range& advance_begin( difference_type n ) 356 { 357 std::advance( m_Begin, n ); 358 return *this; 359 } 360 361 iterator_range& advance_end( difference_type n ) 362 { 363 std::advance( m_End, n ); 364 return *this; 365 } 366 367 private: 368 // begin and end iterators 369 IteratorT m_Begin; 370 IteratorT m_End; 371 372 protected: 373 // 374 // Allow subclasses an easy way to access the 375 // base type 376 // 377 typedef iterator_range iterator_range_; 378 }; 379 380 // iterator range free-standing operators ---------------------------// 381 382 ///////////////////////////////////////////////////////////////////// 383 // comparison operators 384 ///////////////////////////////////////////////////////////////////// 385 386 template< class IteratorT, class ForwardRange > 387 inline bool operator==( const ForwardRange& l, 388 const iterator_range<IteratorT>& r ) 389 { 390 return boost::equal( l, r ); 391 } 392 393 template< class IteratorT, class ForwardRange > 394 inline bool operator!=( const ForwardRange& l, 395 const iterator_range<IteratorT>& r ) 396 { 397 return !boost::equal( l, r ); 398 } 399 400 template< class IteratorT, class ForwardRange > 401 inline bool operator<( const ForwardRange& l, 402 const iterator_range<IteratorT>& r ) 403 { 404 return iterator_range_detail::less_than( l, r ); 405 } 406 407 template< class IteratorT, class ForwardRange > 408 inline bool operator<=( const ForwardRange& l, 409 const iterator_range<IteratorT>& r ) 410 { 411 return iterator_range_detail::less_or_equal_than( l, r ); 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::greater_than( 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::greater_or_equal_than( l, r ); 426 } 427 428 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 429 #else 430 template< class Iterator1T, class Iterator2T > 431 inline bool operator==( const iterator_range<Iterator1T>& l, 432 const iterator_range<Iterator2T>& r ) 433 { 434 return boost::equal( l, r ); 435 } 436 437 template< class IteratorT, class ForwardRange > 438 inline bool operator==( const iterator_range<IteratorT>& l, 439 const ForwardRange& r ) 440 { 441 return boost::equal( l, r ); 442 } 443 444 445 template< class Iterator1T, class Iterator2T > 446 inline bool operator!=( const iterator_range<Iterator1T>& l, 447 const iterator_range<Iterator2T>& r ) 448 { 449 return !boost::equal( l, r ); 450 } 451 452 template< class IteratorT, class ForwardRange > 453 inline bool operator!=( const iterator_range<IteratorT>& l, 454 const ForwardRange& r ) 455 { 456 return !boost::equal( l, r ); 457 } 458 459 460 template< class Iterator1T, class Iterator2T > 461 inline bool operator<( const iterator_range<Iterator1T>& l, 462 const iterator_range<Iterator2T>& r ) 463 { 464 return iterator_range_detail::less_than( l, r ); 465 } 466 467 template< class IteratorT, class ForwardRange > 468 inline bool operator<( const iterator_range<IteratorT>& l, 469 const ForwardRange& r ) 470 { 471 return iterator_range_detail::less_than( l, r ); 472 } 473 474 template< class Iterator1T, class Iterator2T > 475 inline bool operator<=( const iterator_range<Iterator1T>& l, 476 const iterator_range<Iterator2T>& r ) 477 { 478 return iterator_range_detail::less_or_equal_than( l, r ); 479 } 480 481 template< class IteratorT, class ForwardRange > 482 inline bool operator<=( const iterator_range<IteratorT>& l, 483 const ForwardRange& r ) 484 { 485 return iterator_range_detail::less_or_equal_than( l, r ); 486 } 487 488 template< class Iterator1T, class Iterator2T > 489 inline bool operator>( const iterator_range<Iterator1T>& l, 490 const iterator_range<Iterator2T>& r ) 491 { 492 return iterator_range_detail::greater_than( l, r ); 493 } 494 495 template< class IteratorT, class ForwardRange > 496 inline bool operator>( const iterator_range<IteratorT>& l, 497 const ForwardRange& r ) 498 { 499 return iterator_range_detail::greater_than( l, r ); 500 } 501 502 template< class Iterator1T, class Iterator2T > 503 inline bool operator>=( const iterator_range<Iterator1T>& l, 504 const iterator_range<Iterator2T>& r ) 505 { 506 return iterator_range_detail::greater_or_equal_than( l, r ); 507 } 508 509 template< class IteratorT, class ForwardRange > 510 inline bool operator>=( const iterator_range<IteratorT>& l, 511 const ForwardRange& r ) 512 { 513 return iterator_range_detail::greater_or_equal_than( l, r ); 514 } 515 516 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 517 518 // iterator range utilities -----------------------------------------// 519 520 //! iterator_range construct helper 521 /*! 522 Construct an \c iterator_range from a pair of iterators 523 524 \param Begin A begin iterator 525 \param End An end iterator 526 \return iterator_range object 527 */ 528 template< typename IteratorT > 529 inline iterator_range< IteratorT > 530 make_iterator_range( IteratorT Begin, IteratorT End ) 531 { 532 return iterator_range<IteratorT>( Begin, End ); 533 } 534 535 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 536 537 template< typename Range > 538 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > 539 make_iterator_range( Range& r ) 540 { 541 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > 542 ( boost::begin( r ), boost::end( r ) ); 543 } 544 545 #else 546 //! iterator_range construct helper 547 /*! 548 Construct an \c iterator_range from a \c Range containing the begin 549 and end iterators. 550 */ 551 template< class ForwardRange > 552 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type > 553 make_iterator_range( ForwardRange& r ) 554 { 555 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type > 556 ( r, iterator_range_detail::range_tag() ); 557 } 558 559 template< class ForwardRange > 560 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type > 561 make_iterator_range( const ForwardRange& r ) 562 { 563 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type > 564 ( r, iterator_range_detail::const_range_tag() ); 565 } 566 567 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 568 569 namespace iterator_range_detail 570 { 571 template< class Range > 572 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > 573 make_range_impl( Range& r, 574 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 575 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 576 { 577 // 578 // Not worth the effort 579 // 580 //if( advance_begin == 0 && advance_end == 0 ) 581 // return make_iterator_range( r ); 582 // 583 584 BOOST_DEDUCED_TYPENAME range_iterator<Range>::type 585 new_begin = boost::begin( r ), 586 new_end = boost::end( r ); 587 std::advance( new_begin, advance_begin ); 588 std::advance( new_end, advance_end ); 589 return make_iterator_range( new_begin, new_end ); 590 } 591 } 592 593 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 594 595 template< class Range > 596 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > 597 make_iterator_range( Range& r, 598 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 599 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 600 { 601 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 602 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 603 } 604 605 #else 606 607 template< class Range > 608 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > 609 make_iterator_range( Range& r, 610 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 611 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 612 { 613 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 614 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 615 } 616 617 template< class Range > 618 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const Range>::type > 619 make_iterator_range( const Range& r, 620 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 621 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 622 { 623 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 624 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 625 } 626 627 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 628 629 //! copy a range into a sequence 630 /*! 631 Construct a new sequence of the specified type from the elements 632 in the given range 633 634 \param Range An input range 635 \return New sequence 636 */ 637 template< typename SeqT, typename Range > 638 inline SeqT copy_range( const Range& r ) 639 { 640 return SeqT( boost::begin( r ), boost::end( r ) ); 641 } 642 643 } // namespace 'boost' 644 645 #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500)) 646 #pragma warning( pop ) 647 #endif 648 649 #endif 650 651
