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 > adl_beginboost::iterator_range_detail::iterator_range_impl58 static IteratorT adl_begin( ForwardRange& r ) 59 { 60 using boost::begin; 61 return IteratorT( begin( r ) ); 62 } 63 64 template< class ForwardRange > adl_endboost::iterator_range_detail::iterator_range_impl65 static IteratorT adl_end( ForwardRange& r ) 66 { 67 using boost::end; 68 return IteratorT( end( r ) ); 69 } 70 }; 71 72 template< class Left, class Right > equal(const Left & l,const Right & r)73 inline bool equal( const Left& l, const Right& r ) 74 { 75 typedef BOOST_DEDUCED_TYPENAME boost::range_size<Left>::type sz_type; 76 77 sz_type l_size = size( l ), 78 r_size = size( r ); 79 80 if( l_size != r_size ) 81 return false; 82 83 return std::equal( begin(l), end(l), 84 begin(r) ); 85 } 86 87 template< class Left, class Right > less_than(const Left & l,const Right & r)88 inline bool less_than( const Left& l, const Right& r ) 89 { 90 return std::lexicographical_compare( begin(l), 91 end(l), 92 begin(r), 93 end(r) ); 94 } 95 96 struct range_tag { }; 97 struct const_range_tag { }; 98 99 } 100 101 // iterator range template class -----------------------------------------// 102 103 //! iterator_range class 104 /*! 105 An \c iterator_range delimits a range in a sequence by beginning and ending iterators. 106 An iterator_range can be passed to an algorithm which requires a sequence as an input. 107 For example, the \c toupper() function may be used most frequently on strings, 108 but can also be used on iterator_ranges: 109 110 \code 111 boost::tolower( find( s, "UPPERCASE STRING" ) ); 112 \endcode 113 114 Many algorithms working with sequences take a pair of iterators, 115 delimiting a working range, as an arguments. The \c iterator_range class is an 116 encapsulation of a range identified by a pair of iterators. 117 It provides a collection interface, 118 so it is possible to pass an instance to an algorithm requiring a collection as an input. 119 */ 120 template<typename IteratorT> 121 class iterator_range 122 { 123 protected: // Used by sub_range 124 //! implementation class 125 typedef iterator_range_detail::iterator_range_impl<IteratorT> impl; 126 public: 127 128 //! this type 129 typedef iterator_range<IteratorT> type; 130 //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type); 131 132 //! Encapsulated value type 133 typedef BOOST_DEDUCED_TYPENAME 134 iterator_value<IteratorT>::type value_type; 135 136 //! Difference type 137 typedef BOOST_DEDUCED_TYPENAME 138 iterator_difference<IteratorT>::type difference_type; 139 140 //! Size type 141 typedef std::size_t size_type; // note: must be unsigned 142 143 //! This type 144 typedef iterator_range<IteratorT> this_type; 145 146 //! const_iterator type 147 /*! 148 There is no distinction between const_iterator and iterator. 149 These typedefs are provides to fulfill container interface 150 */ 151 typedef IteratorT const_iterator; 152 //! iterator type 153 typedef IteratorT iterator; 154 iterator_range()155 iterator_range() : m_Begin( iterator() ), m_End( iterator() ), 156 singular( true ) 157 { } 158 /* 159 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) 160 iterator_range( this_type r ) : 161 : m_Begin(r.begin()), m_End(r.end()) 162 { } 163 164 this_type& operator=( this_type r ) 165 { 166 m_Begin = r.begin(); 167 m_End = r.end(); 168 return *this; 169 } 170 #endif 171 */ 172 //! Constructor from a pair of iterators 173 template< class Iterator > iterator_range(Iterator Begin,Iterator End)174 iterator_range( Iterator Begin, Iterator End ) : 175 m_Begin(Begin), m_End(End), singular(false) {} 176 177 //! Constructor from a Range 178 template< class Range > iterator_range(const Range & r)179 iterator_range( const Range& r ) : 180 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), 181 singular(false) {} 182 183 //! Constructor from a Range 184 template< class Range > iterator_range(Range & r)185 iterator_range( 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 > iterator_range(const Range & r,iterator_range_detail::const_range_tag)191 iterator_range( const Range& r, iterator_range_detail::const_range_tag ) : 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 > iterator_range(Range & r,iterator_range_detail::range_tag)197 iterator_range( Range& r, iterator_range_detail::range_tag ) : 198 m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ), 199 singular(false) {} 200 201 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300) operator =(const this_type & r)202 this_type& operator=( const this_type& r ) 203 { 204 m_Begin = r.begin(); 205 m_End = r.end(); 206 // 207 // remark: this need not necessarily be true, but it does no harm 208 // 209 singular = r.singular; 210 return *this; 211 } 212 #endif 213 214 template< class Iterator > operator =(const iterator_range<Iterator> & r)215 iterator_range& operator=( const iterator_range<Iterator>& r ) 216 { 217 m_Begin = r.begin(); 218 m_End = r.end(); 219 // 220 // remark: this need not necessarily be true, but it does no harm 221 // 222 singular = r.empty(); 223 return *this; 224 } 225 226 template< class ForwardRange > operator =(ForwardRange & r)227 iterator_range& operator=( ForwardRange& r ) 228 { 229 m_Begin = impl::adl_begin( r ); 230 m_End = impl::adl_end( r ); 231 singular = false; 232 return *this; 233 } 234 235 template< class ForwardRange > operator =(const ForwardRange & r)236 iterator_range& operator=( const ForwardRange& r ) 237 { 238 m_Begin = impl::adl_begin( r ); 239 m_End = impl::adl_end( r ); 240 singular = false; 241 return *this; 242 } 243 begin() const244 IteratorT begin() const 245 { 246 return m_Begin; 247 } 248 end() const249 IteratorT end() const 250 { 251 return m_End; 252 } 253 size() const254 size_type size() const 255 { 256 if( singular ) 257 return 0; 258 259 return std::distance( m_Begin, m_End ); 260 } 261 empty() const262 bool empty() const 263 { 264 if( singular ) 265 return true; 266 267 return m_Begin == m_End; 268 } 269 270 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) operator bool() const271 operator bool() const 272 { 273 return !empty(); 274 } 275 #else 276 typedef iterator (iterator_range::*unspecified_bool_type) () const; operator unspecified_bool_type() const277 operator unspecified_bool_type() const 278 { 279 return empty() ? 0: &iterator_range::end; 280 } 281 #endif 282 equal(const iterator_range & r) const283 bool equal( const iterator_range& r ) const 284 { 285 return singular == r.singular && m_Begin == r.m_Begin && m_End == r.m_End; 286 } 287 288 289 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 290 operator ==(const iterator_range & r) const291 bool operator==( const iterator_range& r ) const 292 { 293 return iterator_range_detail::equal( *this, r ); 294 } 295 operator !=(const iterator_range & r) const296 bool operator!=( const iterator_range& r ) const 297 { 298 return !operator==(r); 299 } 300 operator <(const iterator_range & r) const301 bool operator<( const iterator_range& r ) const 302 { 303 return iterator_range_detail::less_than( *this, r ); 304 } 305 306 #endif 307 308 public: // convenience front() const309 value_type& front() const 310 { 311 BOOST_ASSERT( !empty() ); 312 return *m_Begin; 313 } 314 back() const315 value_type& back() const 316 { 317 BOOST_ASSERT( !empty() ); 318 IteratorT last( m_End ); 319 return *--last; 320 } 321 operator [](size_type sz) const322 value_type& operator[]( size_type sz ) const 323 { 324 //BOOST_STATIC_ASSERT( is_random_access ); 325 BOOST_ASSERT( sz < size() ); 326 return m_Begin[sz]; 327 } 328 329 private: 330 // begin and end iterators 331 IteratorT m_Begin; 332 IteratorT m_End; 333 bool singular; 334 }; 335 336 // iterator range free-standing operators ---------------------------// 337 338 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 339 #else 340 template< class Iterator > empty(const iterator_range<Iterator> & r)341 inline bool empty( const iterator_range<Iterator>& r ) 342 { 343 // 344 // this will preserve the well-defined empty() even 345 // though 'r' is singular. 346 // 347 return r.empty(); 348 } 349 #endif 350 351 #ifndef BOOST_OLD_IOSTREAMS 352 353 //! iterator_range output operator 354 /*! 355 Output the range to an ostream. Elements are outputed 356 in a sequence without separators. 357 */ 358 template< typename IteratorT, typename Elem, typename Traits > operator <<(std::basic_ostream<Elem,Traits> & Os,const iterator_range<IteratorT> & r)359 inline std::basic_ostream<Elem,Traits>& operator<<( 360 std::basic_ostream<Elem, Traits>& Os, 361 const iterator_range<IteratorT>& r ) 362 { 363 std::copy( r.begin(), r.end(), std::ostream_iterator<Elem>(Os)); 364 return Os; 365 } 366 367 #else 368 369 //! iterator_range output operator 370 /*! 371 Output the range to an ostream. Elements are outputed 372 in a sequence without separators. 373 */ 374 template< typename IteratorT > operator <<(std::ostream & Os,const iterator_range<IteratorT> & r)375 inline std::ostream& operator<<( 376 std::ostream& Os, 377 const iterator_range<IteratorT>& r ) 378 { 379 std::copy( r.begin(), r.end(), std::ostream_iterator<char>(Os)); 380 return Os; 381 } 382 383 #endif 384 385 ///////////////////////////////////////////////////////////////////// 386 // comparison operators 387 ///////////////////////////////////////////////////////////////////// 388 389 template< class IteratorT, class ForwardRange > operator ==(const ForwardRange & l,const iterator_range<IteratorT> & r)390 inline bool operator==( const ForwardRange& l, 391 const iterator_range<IteratorT>& r ) 392 { 393 return iterator_range_detail::equal( l, r ); 394 } 395 396 template< class IteratorT, class ForwardRange > operator !=(const ForwardRange & l,const iterator_range<IteratorT> & r)397 inline bool operator!=( const ForwardRange& l, 398 const iterator_range<IteratorT>& r ) 399 { 400 return !iterator_range_detail::equal( l, r ); 401 } 402 403 template< class IteratorT, class ForwardRange > operator <(const ForwardRange & l,const iterator_range<IteratorT> & r)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 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 411 #else 412 template< class Iterator1T, class Iterator2T > operator ==(const iterator_range<Iterator1T> & l,const iterator_range<Iterator2T> & r)413 inline bool operator==( const iterator_range<Iterator1T>& l, 414 const iterator_range<Iterator2T>& r ) 415 { 416 return iterator_range_detail::equal( l, r ); 417 } 418 419 template< class IteratorT, class ForwardRange > operator ==(const iterator_range<IteratorT> & l,const ForwardRange & r)420 inline bool operator==( const iterator_range<IteratorT>& l, 421 const ForwardRange& r ) 422 { 423 return iterator_range_detail::equal( l, r ); 424 } 425 426 427 template< class Iterator1T, class Iterator2T > operator !=(const iterator_range<Iterator1T> & l,const iterator_range<Iterator2T> & r)428 inline bool operator!=( const iterator_range<Iterator1T>& l, 429 const iterator_range<Iterator2T>& r ) 430 { 431 return !iterator_range_detail::equal( l, r ); 432 } 433 434 template< class IteratorT, class ForwardRange > operator !=(const iterator_range<IteratorT> & l,const ForwardRange & r)435 inline bool operator!=( const iterator_range<IteratorT>& l, 436 const ForwardRange& r ) 437 { 438 return !iterator_range_detail::equal( l, r ); 439 } 440 441 442 template< class Iterator1T, class Iterator2T > operator <(const iterator_range<Iterator1T> & l,const iterator_range<Iterator2T> & r)443 inline bool operator<( const iterator_range<Iterator1T>& l, 444 const iterator_range<Iterator2T>& r ) 445 { 446 return iterator_range_detail::less_than( l, r ); 447 } 448 449 template< class IteratorT, class ForwardRange > operator <(const iterator_range<IteratorT> & l,const ForwardRange & r)450 inline bool operator<( const iterator_range<IteratorT>& l, 451 const ForwardRange& r ) 452 { 453 return iterator_range_detail::less_than( l, r ); 454 } 455 456 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 457 458 // iterator range utilities -----------------------------------------// 459 460 //! iterator_range construct helper 461 /*! 462 Construct an \c iterator_range from a pair of iterators 463 464 \param Begin A begin iterator 465 \param End An end iterator 466 \return iterator_range object 467 */ 468 template< typename IteratorT > 469 inline iterator_range< IteratorT > make_iterator_range(IteratorT Begin,IteratorT End)470 make_iterator_range( IteratorT Begin, IteratorT End ) 471 { 472 return iterator_range<IteratorT>( Begin, End ); 473 } 474 475 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 476 477 template< typename Range > 478 inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type > make_iterator_range(Range & r)479 make_iterator_range( Range& r ) 480 { 481 return iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type > 482 ( begin( r ), end( r ) ); 483 } 484 485 #else 486 //! iterator_range construct helper 487 /*! 488 Construct an \c iterator_range from a \c Range containing the begin 489 and end iterators. 490 */ 491 template< class ForwardRange > 492 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type > make_iterator_range(ForwardRange & r)493 make_iterator_range( ForwardRange& r ) 494 { 495 return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type > 496 ( r, iterator_range_detail::range_tag() ); 497 } 498 499 template< class ForwardRange > 500 inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type > make_iterator_range(const ForwardRange & r)501 make_iterator_range( const ForwardRange& r ) 502 { 503 return iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type > 504 ( r, iterator_range_detail::const_range_tag() ); 505 } 506 507 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 508 509 namespace iterator_range_detail 510 { 511 template< class Range > 512 inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type > make_range_impl(Range & r,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end)513 make_range_impl( Range& r, 514 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 515 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 516 { 517 if( advance_begin == 0 && advance_end == 0 ) 518 return make_iterator_range( r ); 519 520 BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type 521 new_begin = begin( r ), 522 new_end = end( r ); 523 std::advance( new_begin, advance_begin ); 524 std::advance( new_end, advance_end ); 525 return make_iterator_range( new_begin, new_end ); 526 } 527 } 528 529 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING 530 531 template< class Range > 532 inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type > make_iterator_range(Range & r,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end)533 make_iterator_range( Range& r, 534 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 535 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 536 { 537 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 538 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 539 } 540 541 #else 542 543 template< class Range > 544 inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type > make_iterator_range(Range & r,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end)545 make_iterator_range( Range& r, 546 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 547 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 548 { 549 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 550 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 551 } 552 553 template< class Range > 554 inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<Range>::type > make_iterator_range(const Range & r,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end)555 make_iterator_range( const Range& r, 556 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin, 557 BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end ) 558 { 559 //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" ); 560 return iterator_range_detail::make_range_impl( r, advance_begin, advance_end ); 561 } 562 563 #endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING 564 565 //! copy a range into a sequence 566 /*! 567 Construct a new sequence of the specified type from the elements 568 in the given range 569 570 \param Range An input range 571 \return New sequence 572 */ 573 template< typename SeqT, typename Range > copy_range(const Range & r)574 inline SeqT copy_range( const Range& r ) 575 { 576 return SeqT( begin( r ), end( r ) ); 577 } 578 579 } // namespace 'boost' 580 581 #undef BOOST_OLD_IOSTREAMS 582 583 #endif 584