1 // (C) Copyright Jeremy Siek 2002. 2 // Distributed under the Boost Software License, Version 1.0. (See 3 // accompanying file LICENSE_1_0.txt or copy at 4 // http://www.boost.org/LICENSE_1_0.txt) 5 6 #ifndef BOOST_ITERATOR_ARCHETYPES_HPP 7 #define BOOST_ITERATOR_ARCHETYPES_HPP 8 9 #include <boost/iterator/iterator_categories.hpp> 10 #include <boost/operators.hpp> 11 #include <boost/static_assert.hpp> 12 13 #include <boost/iterator/detail/facade_iterator_category.hpp> 14 15 #include <boost/type_traits/is_const.hpp> 16 #include <boost/type_traits/add_const.hpp> 17 #include <boost/type_traits/remove_const.hpp> 18 #include <boost/type_traits/remove_cv.hpp> 19 20 #include <boost/concept_archetype.hpp> 21 22 #include <boost/mpl/bitand.hpp> 23 #include <boost/mpl/int.hpp> 24 #include <boost/mpl/equal_to.hpp> 25 #include <boost/mpl/if.hpp> 26 #include <boost/mpl/eval_if.hpp> 27 #include <boost/mpl/and.hpp> 28 #include <boost/mpl/identity.hpp> 29 30 #include <cstddef> 31 32 namespace boost { 33 namespace iterators { 34 35 template <class Value, class AccessCategory> 36 struct access_archetype; 37 38 template <class Derived, class Value, class AccessCategory, class TraversalCategory> 39 struct traversal_archetype; 40 41 namespace archetypes 42 { 43 enum { 44 readable_iterator_bit = 1 45 , writable_iterator_bit = 2 46 , swappable_iterator_bit = 4 47 , lvalue_iterator_bit = 8 48 }; 49 50 // Not quite tags, since dispatching wouldn't work. 51 typedef mpl::int_<readable_iterator_bit>::type readable_iterator_t; 52 typedef mpl::int_<writable_iterator_bit>::type writable_iterator_t; 53 54 typedef mpl::int_< 55 (readable_iterator_bit|writable_iterator_bit) 56 >::type readable_writable_iterator_t; 57 58 typedef mpl::int_< 59 (readable_iterator_bit|lvalue_iterator_bit) 60 >::type readable_lvalue_iterator_t; 61 62 typedef mpl::int_< 63 (lvalue_iterator_bit|writable_iterator_bit) 64 >::type writable_lvalue_iterator_t; 65 66 typedef mpl::int_<swappable_iterator_bit>::type swappable_iterator_t; 67 typedef mpl::int_<lvalue_iterator_bit>::type lvalue_iterator_t; 68 69 template <class Derived, class Base> 70 struct has_access 71 : mpl::equal_to< 72 mpl::bitand_<Derived,Base> 73 , Base 74 > 75 {}; 76 } 77 78 namespace detail 79 { 80 template <class T> 81 struct assign_proxy 82 { operator =boost::iterators::detail::assign_proxy83 assign_proxy& operator=(T) { return *this; } 84 }; 85 86 template <class T> 87 struct read_proxy 88 { operator Tboost::iterators::detail::read_proxy89 operator T() { return static_object<T>::get(); } 90 }; 91 92 template <class T> 93 struct read_write_proxy 94 : read_proxy<T> // Use to inherit from assign_proxy, but that doesn't work. -JGS 95 { operator =boost::iterators::detail::read_write_proxy96 read_write_proxy& operator=(T) { return *this; } 97 }; 98 99 template <class T> 100 struct arrow_proxy 101 { operator ->boost::iterators::detail::arrow_proxy102 T const* operator->() const { return 0; } 103 }; 104 105 struct no_operator_brackets {}; 106 107 template <class ValueType> 108 struct readable_operator_brackets 109 { operator []boost::iterators::detail::readable_operator_brackets110 read_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_proxy<ValueType>(); } 111 }; 112 113 template <class ValueType> 114 struct writable_operator_brackets 115 { operator []boost::iterators::detail::writable_operator_brackets116 read_write_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_write_proxy<ValueType>(); } 117 }; 118 119 template <class Value, class AccessCategory, class TraversalCategory> 120 struct operator_brackets 121 : mpl::eval_if< 122 is_convertible<TraversalCategory, random_access_traversal_tag> 123 , mpl::eval_if< 124 archetypes::has_access< 125 AccessCategory 126 , archetypes::writable_iterator_t 127 > 128 , mpl::identity<writable_operator_brackets<Value> > 129 , mpl::if_< 130 archetypes::has_access< 131 AccessCategory 132 , archetypes::readable_iterator_t 133 > 134 , readable_operator_brackets<Value> 135 , no_operator_brackets 136 > 137 > 138 , mpl::identity<no_operator_brackets> 139 >::type 140 {}; 141 142 template <class TraversalCategory> 143 struct traversal_archetype_impl 144 { 145 template <class Derived,class Value> struct archetype; 146 }; 147 148 // Constructor argument for those iterators that 149 // are not default constructible 150 struct ctor_arg {}; 151 152 template <class Derived, class Value, class TraversalCategory> 153 struct traversal_archetype_ 154 : traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value> 155 { 156 typedef typename 157 traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value> 158 base; 159 traversal_archetype_boost::iterators::detail::traversal_archetype_160 traversal_archetype_() {} 161 traversal_archetype_boost::iterators::detail::traversal_archetype_162 traversal_archetype_(ctor_arg arg) 163 : base(arg) 164 {} 165 }; 166 167 template <> 168 struct traversal_archetype_impl<incrementable_traversal_tag> 169 { 170 template<class Derived, class Value> 171 struct archetype 172 { archetypeboost::iterators::detail::traversal_archetype_impl::archetype173 explicit archetype(ctor_arg) {} 174 175 struct bogus { }; // This use to be void, but that causes trouble for iterator_facade. Need more research. -JGS 176 typedef bogus difference_type; 177 operator ++boost::iterators::detail::traversal_archetype_impl::archetype178 Derived& operator++() { return (Derived&)static_object<Derived>::get(); } operator ++boost::iterators::detail::traversal_archetype_impl::archetype179 Derived operator++(int) const { return (Derived&)static_object<Derived>::get(); } 180 }; 181 }; 182 183 template <> 184 struct traversal_archetype_impl<single_pass_traversal_tag> 185 { 186 template<class Derived, class Value> 187 struct archetype 188 : public equality_comparable< traversal_archetype_<Derived, Value, single_pass_traversal_tag> >, 189 public traversal_archetype_<Derived, Value, incrementable_traversal_tag> 190 { archetypeboost::iterators::detail::traversal_archetype_impl::archetype191 explicit archetype(ctor_arg arg) 192 : traversal_archetype_<Derived, Value, incrementable_traversal_tag>(arg) 193 {} 194 195 typedef std::ptrdiff_t difference_type; 196 }; 197 }; 198 199 template <class Derived, class Value> operator ==(traversal_archetype_<Derived,Value,single_pass_traversal_tag> const &,traversal_archetype_<Derived,Value,single_pass_traversal_tag> const &)200 bool operator==(traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&, 201 traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&) { return true; } 202 203 template <> 204 struct traversal_archetype_impl<forward_traversal_tag> 205 { 206 template<class Derived, class Value> 207 struct archetype 208 : public traversal_archetype_<Derived, Value, single_pass_traversal_tag> 209 { archetypeboost::iterators::detail::traversal_archetype_impl::archetype210 archetype() 211 : traversal_archetype_<Derived, Value, single_pass_traversal_tag>(ctor_arg()) 212 {} 213 }; 214 }; 215 216 template <> 217 struct traversal_archetype_impl<bidirectional_traversal_tag> 218 { 219 template<class Derived, class Value> 220 struct archetype 221 : public traversal_archetype_<Derived, Value, forward_traversal_tag> 222 { operator --boost::iterators::detail::traversal_archetype_impl::archetype223 Derived& operator--() { return static_object<Derived>::get(); } operator --boost::iterators::detail::traversal_archetype_impl::archetype224 Derived operator--(int) const { return static_object<Derived>::get(); } 225 }; 226 }; 227 228 template <> 229 struct traversal_archetype_impl<random_access_traversal_tag> 230 { 231 template<class Derived, class Value> 232 struct archetype 233 : public traversal_archetype_<Derived, Value, bidirectional_traversal_tag> 234 { operator +=boost::iterators::detail::traversal_archetype_impl::archetype235 Derived& operator+=(std::ptrdiff_t) { return static_object<Derived>::get(); } operator -=boost::iterators::detail::traversal_archetype_impl::archetype236 Derived& operator-=(std::ptrdiff_t) { return static_object<Derived>::get(); } 237 }; 238 }; 239 240 template <class Derived, class Value> operator +(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,std::ptrdiff_t)241 Derived& operator+(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 242 std::ptrdiff_t) { return static_object<Derived>::get(); } 243 244 template <class Derived, class Value> operator +(std::ptrdiff_t,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)245 Derived& operator+(std::ptrdiff_t, 246 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 247 { return static_object<Derived>::get(); } 248 249 template <class Derived, class Value> operator -(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,std::ptrdiff_t)250 Derived& operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 251 std::ptrdiff_t) 252 { return static_object<Derived>::get(); } 253 254 template <class Derived, class Value> operator -(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)255 std::ptrdiff_t operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 256 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 257 { return 0; } 258 259 template <class Derived, class Value> operator <(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)260 bool operator<(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 261 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 262 { return true; } 263 264 template <class Derived, class Value> operator >(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)265 bool operator>(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 266 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 267 { return true; } 268 269 template <class Derived, class Value> operator <=(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)270 bool operator<=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 271 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 272 { return true; } 273 274 template <class Derived, class Value> operator >=(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)275 bool operator>=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, 276 traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) 277 { return true; } 278 279 struct bogus_type; 280 281 template <class Value> 282 struct convertible_type 283 : mpl::if_< is_const<Value>, 284 typename remove_const<Value>::type, 285 bogus_type > 286 {}; 287 288 } // namespace detail 289 290 291 template <class> struct undefined; 292 293 template <class AccessCategory> 294 struct iterator_access_archetype_impl 295 { 296 template <class Value> struct archetype; 297 }; 298 299 template <class Value, class AccessCategory> 300 struct iterator_access_archetype 301 : iterator_access_archetype_impl< 302 AccessCategory 303 >::template archetype<Value> 304 { 305 }; 306 307 template <> 308 struct iterator_access_archetype_impl< 309 archetypes::readable_iterator_t 310 > 311 { 312 template <class Value> 313 struct archetype 314 { 315 typedef typename remove_cv<Value>::type value_type; 316 typedef Value reference; 317 typedef Value* pointer; 318 operator *boost::iterators::iterator_access_archetype_impl::archetype319 value_type operator*() const { return static_object<value_type>::get(); } 320 operator ->boost::iterators::iterator_access_archetype_impl::archetype321 detail::arrow_proxy<Value> operator->() const { return detail::arrow_proxy<Value>(); } 322 }; 323 }; 324 325 template <> 326 struct iterator_access_archetype_impl< 327 archetypes::writable_iterator_t 328 > 329 { 330 template <class Value> 331 struct archetype 332 { 333 BOOST_STATIC_ASSERT(!is_const<Value>::value); 334 typedef void value_type; 335 typedef void reference; 336 typedef void pointer; 337 operator *boost::iterators::iterator_access_archetype_impl::archetype338 detail::assign_proxy<Value> operator*() const { return detail::assign_proxy<Value>(); } 339 }; 340 }; 341 342 template <> 343 struct iterator_access_archetype_impl< 344 archetypes::readable_writable_iterator_t 345 > 346 { 347 template <class Value> 348 struct archetype 349 : public virtual iterator_access_archetype< 350 Value, archetypes::readable_iterator_t 351 > 352 { 353 typedef detail::read_write_proxy<Value> reference; 354 operator *boost::iterators::iterator_access_archetype_impl::archetype355 detail::read_write_proxy<Value> operator*() const { return detail::read_write_proxy<Value>(); } 356 }; 357 }; 358 359 template <> 360 struct iterator_access_archetype_impl<archetypes::readable_lvalue_iterator_t> 361 { 362 template <class Value> 363 struct archetype 364 : public virtual iterator_access_archetype< 365 Value, archetypes::readable_iterator_t 366 > 367 { 368 typedef Value& reference; 369 operator *boost::iterators::iterator_access_archetype_impl::archetype370 Value& operator*() const { return static_object<Value>::get(); } operator ->boost::iterators::iterator_access_archetype_impl::archetype371 Value* operator->() const { return 0; } 372 }; 373 }; 374 375 template <> 376 struct iterator_access_archetype_impl<archetypes::writable_lvalue_iterator_t> 377 { 378 template <class Value> 379 struct archetype 380 : public virtual iterator_access_archetype< 381 Value, archetypes::readable_lvalue_iterator_t 382 > 383 { 384 BOOST_STATIC_ASSERT((!is_const<Value>::value)); 385 }; 386 }; 387 388 389 template <class Value, class AccessCategory, class TraversalCategory> 390 struct iterator_archetype; 391 392 template <class Value, class AccessCategory, class TraversalCategory> 393 struct traversal_archetype_base 394 : detail::operator_brackets< 395 typename remove_cv<Value>::type 396 , AccessCategory 397 , TraversalCategory 398 > 399 , detail::traversal_archetype_< 400 iterator_archetype<Value, AccessCategory, TraversalCategory> 401 , Value 402 , TraversalCategory 403 > 404 { 405 }; 406 407 namespace detail 408 { 409 template <class Value, class AccessCategory, class TraversalCategory> 410 struct iterator_archetype_base 411 : iterator_access_archetype<Value, AccessCategory> 412 , traversal_archetype_base<Value, AccessCategory, TraversalCategory> 413 { 414 typedef iterator_access_archetype<Value, AccessCategory> access; 415 416 typedef typename detail::facade_iterator_category< 417 TraversalCategory 418 , typename mpl::eval_if< 419 archetypes::has_access< 420 AccessCategory, archetypes::writable_iterator_t 421 > 422 , remove_const<Value> 423 , add_const<Value> 424 >::type 425 , typename access::reference 426 >::type iterator_category; 427 428 // Needed for some broken libraries (see below) 429 struct workaround_iterator_base 430 { 431 typedef typename iterator_archetype_base::iterator_category iterator_category; 432 typedef Value value_type; 433 typedef typename traversal_archetype_base< 434 Value, AccessCategory, TraversalCategory 435 >::difference_type difference_type; 436 typedef typename access::pointer pointer; 437 typedef typename access::reference reference; 438 }; 439 }; 440 } 441 442 template <class Value, class AccessCategory, class TraversalCategory> 443 struct iterator_archetype 444 : public detail::iterator_archetype_base<Value, AccessCategory, TraversalCategory> 445 446 // These broken libraries require derivation from std::iterator 447 // (or related magic) in order to handle iter_swap and other 448 // iterator operations 449 # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310) \ 450 || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101)) 451 , public detail::iterator_archetype_base< 452 Value, AccessCategory, TraversalCategory 453 >::workaround_iterator_base 454 # endif 455 { 456 // Derivation from std::iterator above caused references to nested 457 // types to be ambiguous, so now we have to redeclare them all 458 // here. 459 # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310) \ 460 || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101)) 461 462 typedef detail::iterator_archetype_base< 463 Value,AccessCategory,TraversalCategory 464 > base; 465 466 typedef typename base::value_type value_type; 467 typedef typename base::reference reference; 468 typedef typename base::pointer pointer; 469 typedef typename base::difference_type difference_type; 470 typedef typename base::iterator_category iterator_category; 471 # endif 472 iterator_archetypeboost::iterators::iterator_archetype473 iterator_archetype() { } iterator_archetypeboost::iterators::iterator_archetype474 iterator_archetype(iterator_archetype const& x) 475 : detail::iterator_archetype_base< 476 Value 477 , AccessCategory 478 , TraversalCategory 479 >(x) 480 {} 481 operator =boost::iterators::iterator_archetype482 iterator_archetype& operator=(iterator_archetype const&) 483 { return *this; } 484 485 # if 0 486 // Optional conversion from mutable 487 iterator_archetype( 488 iterator_archetype< 489 typename detail::convertible_type<Value>::type 490 , AccessCategory 491 , TraversalCategory> const& 492 ); 493 # endif 494 }; 495 496 } // namespace iterators 497 498 // Backward compatibility names 499 namespace iterator_archetypes = iterators::archetypes; 500 using iterators::access_archetype; 501 using iterators::traversal_archetype; 502 using iterators::iterator_archetype; 503 using iterators::undefined; 504 using iterators::iterator_access_archetype_impl; 505 using iterators::traversal_archetype_base; 506 507 } // namespace boost 508 509 #endif // BOOST_ITERATOR_ARCHETYPES_HPP 510