1 // Boost.Range library 2 // 3 // Copyright Neil Groves 2010. 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 #ifndef BOOST_RANGE_DETAIL_ANY_ITERATOR_HPP_INCLUDED 11 #define BOOST_RANGE_DETAIL_ANY_ITERATOR_HPP_INCLUDED 12 13 #include <boost/mpl/and.hpp> 14 #include <boost/mpl/or.hpp> 15 #include <boost/mpl/not.hpp> 16 #include <boost/iterator/iterator_facade.hpp> 17 #include <boost/type_traits/is_const.hpp> 18 #include <boost/type_traits/is_reference.hpp> 19 #include <boost/type_traits/remove_reference.hpp> 20 #include <boost/range/detail/any_iterator_buffer.hpp> 21 #include <boost/range/detail/any_iterator_interface.hpp> 22 #include <boost/range/detail/any_iterator_wrapper.hpp> 23 #include <boost/utility/enable_if.hpp> 24 25 namespace boost 26 { 27 namespace range_detail 28 { 29 // metafunction to determine if T is a const reference 30 template<class T> 31 struct is_const_reference 32 { 33 typedef typename mpl::and_< 34 typename is_reference<T>::type, 35 typename is_const< 36 typename remove_reference<T>::type 37 >::type 38 >::type type; 39 }; 40 41 // metafunction to determine if T is a mutable reference 42 template<class T> 43 struct is_mutable_reference 44 { 45 typedef typename mpl::and_< 46 typename is_reference<T>::type, 47 typename mpl::not_< 48 typename is_const< 49 typename remove_reference<T>::type 50 >::type 51 >::type 52 >::type type; 53 }; 54 55 // metafunction to evaluate if a source 'reference' can be 56 // converted to a target 'reference' as a value. 57 // 58 // This is true, when the target reference type is actually 59 // not a reference, and the source reference is convertible 60 // to the target type. 61 template<class SourceReference, class TargetReference> 62 struct is_convertible_to_value_as_reference 63 { 64 typedef typename mpl::and_< 65 typename mpl::not_< 66 typename is_reference<TargetReference>::type 67 >::type 68 , typename is_convertible< 69 SourceReference 70 , TargetReference 71 >::type 72 >::type type; 73 }; 74 75 template< 76 class Value 77 , class Traversal 78 , class Reference 79 , class Difference 80 , class Buffer = any_iterator_default_buffer 81 > 82 class any_iterator; 83 84 // metafunction to determine if SomeIterator is an 85 // any_iterator. 86 // 87 // This is the general implementation which evaluates to false. 88 template<class SomeIterator> 89 struct is_any_iterator 90 : mpl::bool_<false> 91 { 92 }; 93 94 // specialization of is_any_iterator to return true for 95 // any_iterator classes regardless of template parameters. 96 template< 97 class Value 98 , class Traversal 99 , class Reference 100 , class Difference 101 , class Buffer 102 > 103 struct is_any_iterator< 104 any_iterator< 105 Value 106 , Traversal 107 , Reference 108 , Difference 109 , Buffer 110 > 111 > 112 : mpl::bool_<true> 113 { 114 }; 115 } // namespace range_detail 116 117 namespace iterators 118 { 119 namespace detail 120 { 121 // Rationale: 122 // These are specialized since the iterator_facade versions lack 123 // the requisite typedefs to allow wrapping to determine the types 124 // if a user copy constructs from a postfix increment. 125 126 template< 127 class Value 128 , class Traversal 129 , class Reference 130 , class Difference 131 , class Buffer 132 > 133 class postfix_increment_proxy< 134 range_detail::any_iterator< 135 Value 136 , Traversal 137 , Reference 138 , Difference 139 , Buffer 140 > 141 > 142 { 143 typedef range_detail::any_iterator< 144 Value 145 , Traversal 146 , Reference 147 , Difference 148 , Buffer 149 > any_iterator_type; 150 151 public: 152 typedef Value value_type; 153 typedef typename std::iterator_traits<any_iterator_type>::iterator_category iterator_category; 154 typedef Difference difference_type; 155 typedef typename iterator_pointer<any_iterator_type>::type pointer; 156 typedef Reference reference; 157 postfix_increment_proxy(any_iterator_type const & x)158 explicit postfix_increment_proxy(any_iterator_type const& x) 159 : stored_value(*x) 160 {} 161 162 value_type& operator *() const163 operator*() const 164 { 165 return this->stored_value; 166 } 167 private: 168 mutable value_type stored_value; 169 }; 170 171 template< 172 class Value 173 , class Traversal 174 , class Reference 175 , class Difference 176 , class Buffer 177 > 178 class writable_postfix_increment_proxy< 179 range_detail::any_iterator< 180 Value 181 , Traversal 182 , Reference 183 , Difference 184 , Buffer 185 > 186 > 187 { 188 typedef range_detail::any_iterator< 189 Value 190 , Traversal 191 , Reference 192 , Difference 193 , Buffer 194 > any_iterator_type; 195 public: 196 typedef Value value_type; 197 typedef typename std::iterator_traits<any_iterator_type>::iterator_category iterator_category; 198 typedef Difference difference_type; 199 typedef typename iterator_pointer<any_iterator_type>::type pointer; 200 typedef Reference reference; 201 writable_postfix_increment_proxy(any_iterator_type const & x)202 explicit writable_postfix_increment_proxy(any_iterator_type const& x) 203 : stored_value(*x) 204 , stored_iterator(x) 205 {} 206 207 // Dereferencing must return a proxy so that both *r++ = o and 208 // value_type(*r++) can work. In this case, *r is the same as 209 // *r++, and the conversion operator below is used to ensure 210 // readability. 211 writable_postfix_increment_proxy const& operator *() const212 operator*() const 213 { 214 return *this; 215 } 216 217 // Provides readability of *r++ operator value_type&() const218 operator value_type&() const 219 { 220 return stored_value; 221 } 222 223 // Provides writability of *r++ 224 template <class T> operator =(T const & x) const225 T const& operator=(T const& x) const 226 { 227 *this->stored_iterator = x; 228 return x; 229 } 230 231 // This overload just in case only non-const objects are writable 232 template <class T> operator =(T & x) const233 T& operator=(T& x) const 234 { 235 *this->stored_iterator = x; 236 return x; 237 } 238 239 // Provides X(r++) operator any_iterator_type const&() const240 operator any_iterator_type const&() const 241 { 242 return stored_iterator; 243 } 244 245 private: 246 mutable value_type stored_value; 247 any_iterator_type stored_iterator; 248 }; 249 250 } //namespace detail 251 } //namespace iterators 252 253 namespace range_detail 254 { 255 template< 256 class Value 257 , class Traversal 258 , class Reference 259 , class Difference 260 , class Buffer 261 > 262 class any_iterator 263 : public iterator_facade< 264 any_iterator< 265 Value 266 , Traversal 267 , Reference 268 , Difference 269 , Buffer 270 > 271 , Value 272 , Traversal 273 , Reference 274 , Difference 275 > 276 { 277 template< 278 class OtherValue 279 , class OtherTraversal 280 , class OtherReference 281 , class OtherDifference 282 , class OtherBuffer 283 > 284 friend class any_iterator; 285 286 struct enabler {}; 287 struct disabler {}; 288 289 typedef typename any_iterator_interface_type_generator< 290 Traversal 291 , Reference 292 , Difference 293 , Buffer 294 >::type abstract_base_type; 295 296 typedef iterator_facade< 297 any_iterator< 298 Value 299 , Traversal 300 , Reference 301 , Difference 302 , Buffer 303 > 304 , Value 305 , Traversal 306 , Reference 307 , Difference 308 > base_type; 309 310 typedef Buffer buffer_type; 311 312 public: 313 typedef typename base_type::value_type value_type; 314 typedef typename base_type::reference reference; 315 typedef typename base_type::difference_type difference_type; 316 317 // Default constructor any_iterator()318 any_iterator() 319 : m_impl(0) {} 320 321 // Simple copy construction without conversion any_iterator(const any_iterator & other)322 any_iterator(const any_iterator& other) 323 : base_type(other) 324 , m_impl(other.m_impl 325 ? other.m_impl->clone(m_buffer) 326 : 0) 327 { 328 } 329 330 // Simple assignment operator without conversion operator =(const any_iterator & other)331 any_iterator& operator=(const any_iterator& other) 332 { 333 if (this != &other) 334 { 335 if (m_impl) 336 m_impl->~abstract_base_type(); 337 m_buffer.deallocate(); 338 m_impl = 0; 339 if (other.m_impl) 340 m_impl = other.m_impl->clone(m_buffer); 341 } 342 return *this; 343 } 344 345 // Implicit conversion from another any_iterator where the 346 // conversion is from a non-const reference to a const reference 347 template< 348 class OtherValue 349 , class OtherTraversal 350 , class OtherReference 351 , class OtherDifference 352 > any_iterator(const any_iterator<OtherValue,OtherTraversal,OtherReference,OtherDifference,Buffer> & other,typename::boost::enable_if<typename mpl::and_<typename is_mutable_reference<OtherReference>::type,typename is_const_reference<Reference>::type>::type,enabler>::type * =0)353 any_iterator(const any_iterator< 354 OtherValue, 355 OtherTraversal, 356 OtherReference, 357 OtherDifference, 358 Buffer 359 >& other, 360 typename ::boost::enable_if< 361 typename mpl::and_< 362 typename is_mutable_reference<OtherReference>::type, 363 typename is_const_reference<Reference>::type 364 >::type, 365 enabler 366 >::type* = 0 367 ) 368 : m_impl(other.m_impl 369 ? other.m_impl->clone_const_ref(m_buffer) 370 : 0 371 ) 372 { 373 } 374 375 // Implicit conversion from another any_iterator where the 376 // reference types of the source and the target are references 377 // that are either both const, or both non-const. 378 template< 379 class OtherValue 380 , class OtherTraversal 381 , class OtherReference 382 , class OtherDifference 383 > any_iterator(const any_iterator<OtherValue,OtherTraversal,OtherReference,OtherDifference,Buffer> & other,typename::boost::enable_if<typename mpl::or_<typename mpl::and_<typename is_mutable_reference<OtherReference>::type,typename is_mutable_reference<Reference>::type>::type,typename mpl::and_<typename is_const_reference<OtherReference>::type,typename is_const_reference<Reference>::type>::type>::type,enabler>::type * =0)384 any_iterator(const any_iterator< 385 OtherValue 386 , OtherTraversal 387 , OtherReference 388 , OtherDifference 389 , Buffer 390 >& other, 391 typename ::boost::enable_if< 392 typename mpl::or_< 393 typename mpl::and_< 394 typename is_mutable_reference<OtherReference>::type, 395 typename is_mutable_reference<Reference>::type 396 >::type, 397 typename mpl::and_< 398 typename is_const_reference<OtherReference>::type, 399 typename is_const_reference<Reference>::type 400 >::type 401 >::type, 402 enabler 403 >::type* = 0 404 ) 405 : m_impl(other.m_impl 406 ? other.m_impl->clone(m_buffer) 407 : 0 408 ) 409 { 410 } 411 412 // Implicit conversion to an any_iterator that uses a value for 413 // the reference type. 414 template< 415 class OtherValue 416 , class OtherTraversal 417 , class OtherReference 418 , class OtherDifference 419 > any_iterator(const any_iterator<OtherValue,OtherTraversal,OtherReference,OtherDifference,Buffer> & other,typename::boost::enable_if<typename is_convertible_to_value_as_reference<OtherReference,Reference>::type,enabler>::type * =0)420 any_iterator(const any_iterator< 421 OtherValue 422 , OtherTraversal 423 , OtherReference 424 , OtherDifference 425 , Buffer 426 >& other, 427 typename ::boost::enable_if< 428 typename is_convertible_to_value_as_reference< 429 OtherReference 430 , Reference 431 >::type, 432 enabler 433 >::type* = 0 434 ) 435 : m_impl(other.m_impl 436 ? other.m_impl->clone_reference_as_value(m_buffer) 437 : 0 438 ) 439 { 440 } 441 clone() const442 any_iterator clone() const 443 { 444 any_iterator result; 445 if (m_impl) 446 result.m_impl = m_impl->clone(result.m_buffer); 447 return result; 448 } 449 450 any_iterator< 451 Value 452 , Traversal 453 , typename abstract_base_type::const_reference 454 , Difference 455 , Buffer 456 > clone_const_ref() const457 clone_const_ref() const 458 { 459 typedef any_iterator< 460 Value 461 , Traversal 462 , typename abstract_base_type::const_reference 463 , Difference 464 , Buffer 465 > result_type; 466 467 result_type result; 468 469 if (m_impl) 470 result.m_impl = m_impl->clone_const_ref(result.m_buffer); 471 472 return result; 473 } 474 475 // implicit conversion and construction from type-erasure-compatible 476 // iterators 477 template<class WrappedIterator> any_iterator(const WrappedIterator & wrapped_iterator,typename disable_if<typename is_any_iterator<WrappedIterator>::type,disabler>::type * =0)478 explicit any_iterator( 479 const WrappedIterator& wrapped_iterator, 480 typename disable_if< 481 typename is_any_iterator<WrappedIterator>::type 482 , disabler 483 >::type* = 0 484 ) 485 { 486 typedef typename any_iterator_wrapper_type_generator< 487 WrappedIterator 488 , Traversal 489 , Reference 490 , Difference 491 , Buffer 492 >::type wrapper_type; 493 494 void* ptr = m_buffer.allocate(sizeof(wrapper_type)); 495 m_impl = new(ptr) wrapper_type(wrapped_iterator); 496 } 497 ~any_iterator()498 ~any_iterator() 499 { 500 // manually run the destructor, the deallocation is automatically 501 // handled by the any_iterator_small_buffer base class. 502 if (m_impl) 503 m_impl->~abstract_base_type(); 504 } 505 506 private: 507 friend class ::boost::iterator_core_access; 508 dereference() const509 Reference dereference() const 510 { 511 BOOST_ASSERT( m_impl ); 512 return m_impl->dereference(); 513 } 514 equal(const any_iterator & other) const515 bool equal(const any_iterator& other) const 516 { 517 return (m_impl == other.m_impl) 518 || (m_impl && other.m_impl && m_impl->equal(*other.m_impl)); 519 } 520 increment()521 void increment() 522 { 523 BOOST_ASSERT( m_impl ); 524 m_impl->increment(); 525 } 526 decrement()527 void decrement() 528 { 529 BOOST_ASSERT( m_impl ); 530 m_impl->decrement(); 531 } 532 distance_to(const any_iterator & other) const533 Difference distance_to(const any_iterator& other) const 534 { 535 return m_impl && other.m_impl 536 ? m_impl->distance_to(*other.m_impl) 537 : 0; 538 } 539 advance(Difference offset)540 void advance(Difference offset) 541 { 542 BOOST_ASSERT( m_impl ); 543 m_impl->advance(offset); 544 } 545 swap(any_iterator & other)546 any_iterator& swap(any_iterator& other) 547 { 548 BOOST_ASSERT( this != &other ); 549 // grab a temporary copy of the other iterator 550 any_iterator tmp(other); 551 552 // deallocate the other iterator, taking care to obey the 553 // class-invariants in-case of exceptions later 554 if (other.m_impl) 555 { 556 other.m_impl->~abstract_base_type(); 557 other.m_buffer.deallocate(); 558 other.m_impl = 0; 559 } 560 561 // If this is a non-null iterator then we need to put 562 // a clone of this iterators implementation into the other 563 // iterator. 564 // We can't just swap because of the small buffer optimization. 565 if (m_impl) 566 { 567 other.m_impl = m_impl->clone(other.m_buffer); 568 m_impl->~abstract_base_type(); 569 m_buffer.deallocate(); 570 m_impl = 0; 571 } 572 573 // assign to this instance a clone of the temporarily held 574 // tmp which represents the input other parameter at the 575 // start of execution of this function. 576 if (tmp.m_impl) 577 m_impl = tmp.m_impl->clone(m_buffer); 578 579 return *this; 580 } 581 582 buffer_type m_buffer; 583 abstract_base_type* m_impl; 584 }; 585 586 } // namespace range_detail 587 } // namespace boost 588 589 #endif // include guard 590