boost/boost/iterator/iterator_archetypes.hpp

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