boost/boost/iterator/iterator_facade.hpp

   1 // (C) Copyright David Abrahams 2002.
   2 // (C) Copyright Jeremy Siek    2002.
   3 // (C) Copyright Thomas Witt    2002.
   4 // Permission to copy, use, modify,
   5 // sell and distribute this software is granted provided this
   6 // copyright notice appears in all copies. This software is provided
   7 // "as is" without express or implied warranty, and with no claim as
   8 // to its suitability for any purpose.
   9 #ifndef BOOST_ITERATOR_FACADE_23022003THW_HPP
  10 #define BOOST_ITERATOR_FACADE_23022003THW_HPP
  11
  12 #include <boost/static_assert.hpp>
  13
  14 #include <boost/iterator.hpp>
  15 #include <boost/iterator/interoperable.hpp>
  16 #include <boost/iterator/iterator_traits.hpp>
  17
  18 #include <boost/iterator/detail/facade_iterator_category.hpp>
  19 #include <boost/iterator/detail/enable_if.hpp>
  20
  21 #include <boost/type_traits/is_same.hpp>
  22 #include <boost/type_traits/add_const.hpp>
  23 #include <boost/type_traits/add_pointer.hpp>
  24 #include <boost/type_traits/remove_const.hpp>
  25 #include <boost/type_traits/is_convertible.hpp>
  26 #include <boost/type_traits/is_pod.hpp>
  27
  28 #include <boost/mpl/apply_if.hpp>
  29 #include <boost/mpl/or.hpp>
  30 #include <boost/mpl/and.hpp>
  31 #include <boost/mpl/always.hpp>
  32 #include <boost/mpl/apply.hpp>
  33
  34 #if BOOST_WORKAROUND(BOOST_MSVC, == 1200)
  35 # include <boost/mpl/if.hpp>
  36 #endif
  37
  38 #include <boost/iterator/detail/config_def.hpp> // this goes last
  39
  40 namespace boost
  41 {
  42   // This forward declaration is required for the friend declaration
  43   // in iterator_core_access
  44   template <class I, class V, class TC, class R, class D> class iterator_facade;
  45
  46   namespace detail
  47   {
  48     // A binary metafunction class that always returns bool.  VC6
  49     // ICEs on mpl::always<bool>, probably because of the default
  50     // parameters.
  51     struct always_bool2
  52     {
  53         template <class T, class U>
  54         struct apply
  55         {
  56             typedef bool type;
  57         };
  58     };
  59
  60     //
  61     // enable if for use in operator implementation.
  62     //
  63     template <
  64         class Facade1
  65       , class Facade2
  66       , class Return
  67     >
  68     struct enable_if_interoperable
  69       : ::boost::iterators::enable_if<
  70            mpl::or_<
  71                is_convertible<Facade1, Facade2>
  72              , is_convertible<Facade2, Facade1>
  73            >
  74          , Return
  75         >
  76     {
  77     };
  78
  79     //
  80     // Generates associated types for an iterator_facade with the
  81     // given parameters.
  82     //
  83     template <
  84         class ValueParam
  85       , class CategoryOrTraversal
  86       , class Reference
  87       , class Difference
  88     >
  89     struct iterator_facade_types
  90     {
  91         typedef typename facade_iterator_category<
  92             CategoryOrTraversal, ValueParam, Reference
  93         >::type iterator_category;
  94
  95         typedef typename remove_const<ValueParam>::type value_type;
  96
  97         typedef typename mpl::apply_if<
  98             detail::iterator_writability_disabled<ValueParam,Reference>
  99           , add_pointer<typename add_const<value_type>::type>
 100           , add_pointer<value_type>
 101         >::type pointer;
 102
 103 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)                          \
 104     && (BOOST_WORKAROUND(_STLPORT_VERSION, BOOST_TESTED_AT(0x452))              \
 105         || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, BOOST_TESTED_AT(310)))     \
 106     || BOOST_WORKAROUND(BOOST_RWSTD_VER, BOOST_TESTED_AT(0x20101))              \
 107     || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, <= 310)
 108
 109         // To interoperate with some broken library/compiler
 110         // combinations, user-defined iterators must be derived from
 111         // std::iterator.  It is possible to implement a standard
 112         // library for broken compilers without this limitation.
 113 #  define BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE 1
 114
 115         typedef
 116            iterator<iterator_category, value_type, Difference, pointer, Reference>
 117         base;
 118 # endif
 119     };
 120
 121
 122     // operator->() needs special support for input iterators to strictly meet the
 123     // standard's requirements. If *i is not a reference type, we must still
 124     // produce a (constant) lvalue to which a pointer can be formed. We do that by
 125     // returning an instantiation of this special proxy class template.
 126
 127     template <class T>
 128     struct operator_arrow_proxy
 129     {
 130         operator_arrow_proxy(T const* px) : m_value(*px) {}
 131         const T* operator->() const { return &m_value; }
 132         // This function is needed for MWCW and BCC, which won't call operator->
 133         // again automatically per 13.3.1.2 para 8
 134         operator const T*() const { return &m_value; }
 135         T m_value;
 136     };
 137
 138     // A metafunction that gets the result type for operator->.  Also
 139     // has a static function make() which builds the result from a
 140     // Reference
 141     template <class Value, class Reference, class Pointer>
 142     struct operator_arrow_result
 143     {
 144         // CWPro8.3 won't accept "operator_arrow_result::type", and we
 145         // need that type below, so metafunction forwarding would be a
 146         // losing proposition here.
 147         typedef typename mpl::if_<
 148             is_reference<Reference>
 149           , Pointer
 150           , operator_arrow_proxy<Value>
 151         >::type type;
 152
 153         static type make(Reference x)
 154         {
 155             return type(&x);
 156         }
 157     };
 158
 159 # if BOOST_WORKAROUND(BOOST_MSVC, <= 1200)
 160     // Deal with ETI
 161     template<>
 162     struct operator_arrow_result<int, int, int>
 163     {
 164         typedef int type;
 165     };
 166 # endif
 167
 168     //
 169     // Iterator is actually an iterator_facade, so we do not have to
 170     // go through iterator_traits to access the traits.
 171     //
 172     template <class Iterator>
 173     class operator_brackets_proxy
 174     {
 175         typedef typename Iterator::reference  reference;
 176         typedef typename Iterator::value_type value_type;
 177
 178      public:
 179         operator_brackets_proxy(Iterator const& iter)
 180           : m_iter(iter)
 181         {}
 182
 183         operator reference() const
 184         {
 185             return *m_iter;
 186         }
 187
 188         operator_brackets_proxy& operator=(value_type const& val)
 189         {
 190             *m_iter = val;
 191             return *this;
 192         }
 193
 194      private:
 195         Iterator m_iter;
 196     };
 197
 198     template <class Value, class Reference>
 199     struct use_operator_brackets_proxy
 200       : mpl::and_<
 201             // Really we want an is_copy_constructible trait here,
 202             // but is_POD will have to suffice in the meantime.
 203             boost::is_POD<Value>
 204           , iterator_writability_disabled<Value,Reference>
 205         >
 206     {};
 207
 208     template <class Iterator, class Value, class Reference>
 209     struct operator_brackets_result
 210     {
 211         typedef typename mpl::if_<
 212             use_operator_brackets_proxy<Value,Reference>
 213           , Value
 214           , operator_brackets_proxy<Iterator>
 215         >::type type;
 216     };
 217
 218     template <class Iterator>
 219     operator_brackets_proxy<Iterator> make_operator_brackets_result(Iterator const& iter, mpl::false_)
 220     {
 221         return operator_brackets_proxy<Iterator>(iter);
 222     }
 223
 224     template <class Iterator>
 225     typename Iterator::value_type make_operator_brackets_result(Iterator const& iter, mpl::true_)
 226     {
 227       return *iter;
 228     }
 229
 230     struct choose_difference_type
 231     {
 232         template <class I1, class I2>
 233         struct apply
 234           :
 235 # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP
 236           iterator_difference<I1>
 237 # elif BOOST_WORKAROUND(BOOST_MSVC, == 1200)
 238           mpl::if_<
 239               is_convertible<I2,I1>
 240             , typename I1::difference_type
 241             , typename I2::difference_type
 242           >
 243 # else
 244           mpl::apply_if<
 245               is_convertible<I2,I1>
 246             , iterator_difference<I1>
 247             , iterator_difference<I2>
 248           >
 249 # endif
 250         {};
 251
 252     };
 253   } // namespace detail
 254
 255
 256   // Macros which describe the declarations of binary operators
 257 # ifdef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY
 258 #  define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type)   \
 259     template <                                                          \
 260         class Derived1, class V1, class TC1, class R1, class D1         \
 261       , class Derived2, class V2, class TC2, class R2, class D2         \
 262     >                                                                   \
 263     prefix typename mpl::apply2<result_type,Derived1,Derived2>::type    \
 264     operator op(                                                        \
 265         iterator_facade<Derived1, V1, TC1, R1, D1> const& lhs           \
 266       , iterator_facade<Derived2, V2, TC2, R2, D2> const& rhs)
 267 # else
 268 #  define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type)   \
 269     template <                                                          \
 270         class Derived1, class V1, class TC1, class R1, class D1         \
 271       , class Derived2, class V2, class TC2, class R2, class D2         \
 272     >                                                                   \
 273     prefix typename detail::enable_if_interoperable<                    \
 274         Derived1, Derived2                                              \
 275       , typename mpl::apply2<result_type,Derived1,Derived2>::type       \
 276     >::type                                                             \
 277     operator op(                                                        \
 278         iterator_facade<Derived1, V1, TC1, R1, D1> const& lhs           \
 279       , iterator_facade<Derived2, V2, TC2, R2, D2> const& rhs)
 280 # endif
 281
 282 #  define BOOST_ITERATOR_FACADE_PLUS_HEAD(prefix,args)              \
 283     template <class Derived, class V, class TC, class R, class D>   \
 284     prefix Derived operator+ args
 285
 286   //
 287   // Helper class for granting access to the iterator core interface.
 288   //
 289   // The simple core interface is used by iterator_facade. The core
 290   // interface of a user/library defined iterator type should not be made public
 291   // so that it does not clutter the public interface. Instead iterator_core_access
 292   // should be made friend so that iterator_facade can access the core
 293   // interface through iterator_core_access.
 294   //
 295   class iterator_core_access
 296   {
 297 # if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)                  \
 298     || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))
 299       // Tasteless as this may seem, making all members public allows member templates
 300       // to work in the absence of member template friends.
 301    public:
 302 # else
 303
 304       template <class I, class V, class TC, class R, class D> friend class iterator_facade;
 305
 306 #  define BOOST_ITERATOR_FACADE_RELATION(op)                                \
 307       BOOST_ITERATOR_FACADE_INTEROP_HEAD(friend,op, detail::always_bool2);
 308
 309       BOOST_ITERATOR_FACADE_RELATION(==)
 310       BOOST_ITERATOR_FACADE_RELATION(!=)
 311
 312       BOOST_ITERATOR_FACADE_RELATION(<)
 313       BOOST_ITERATOR_FACADE_RELATION(>)
 314       BOOST_ITERATOR_FACADE_RELATION(<=)
 315       BOOST_ITERATOR_FACADE_RELATION(>=)
 316 #  undef BOOST_ITERATOR_FACADE_RELATION
 317
 318       BOOST_ITERATOR_FACADE_INTEROP_HEAD(
 319           friend, -, detail::choose_difference_type)
 320       ;
 321
 322       BOOST_ITERATOR_FACADE_PLUS_HEAD(
 323           friend
 324           , (iterator_facade<Derived, V, TC, R, D> const&
 325            , typename Derived::difference_type)
 326       )
 327       ;
 328
 329       BOOST_ITERATOR_FACADE_PLUS_HEAD(
 330           friend
 331         , (typename Derived::difference_type
 332            , iterator_facade<Derived, V, TC, R, D> const&)
 333       )
 334       ;
 335
 336 # endif
 337
 338       template <class Facade>
 339       static typename Facade::reference dereference(Facade const& f)
 340       {
 341           return f.dereference();
 342       }
 343
 344       template <class Facade>
 345       static void increment(Facade& f)
 346       {
 347           f.increment();
 348       }
 349
 350       template <class Facade>
 351       static void decrement(Facade& f)
 352       {
 353           f.decrement();
 354       }
 355
 356       template <class Facade1, class Facade2>
 357       static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::true_)
 358       {
 359           return f1.equal(f2);
 360       }
 361
 362       template <class Facade1, class Facade2>
 363       static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::false_)
 364       {
 365           return f2.equal(f1);
 366       }
 367
 368       template <class Facade>
 369       static void advance(Facade& f, typename Facade::difference_type n)
 370       {
 371           f.advance(n);
 372       }
 373
 374       template <class Facade1, class Facade2>
 375       static typename Facade1::difference_type distance_from(
 376           Facade1 const& f1, Facade2 const& f2, mpl::true_)
 377       {
 378           return -f1.distance_to(f2);
 379       }
 380
 381       template <class Facade1, class Facade2>
 382       static typename Facade2::difference_type distance_from(
 383           Facade1 const& f1, Facade2 const& f2, mpl::false_)
 384       {
 385           return f2.distance_to(f1);
 386       }
 387
 388    private:
 389       // objects of this class are useless
 390       iterator_core_access(); //undefined
 391   };
 392
 393   //
 394   // iterator_facade - use as a public base class for defining new
 395   // standard-conforming iterators.
 396   //
 397   template <
 398       class Derived             // The derived iterator type being constructed
 399     , class Value
 400     , class CategoryOrTraversal
 401     , class Reference   = Value&
 402     , class Difference  = std::ptrdiff_t
 403   >
 404   class iterator_facade
 405 # ifdef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE
 406     : public detail::iterator_facade_types<
 407          Value, CategoryOrTraversal, Reference, Difference
 408       >::base
 409 #  undef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE
 410 # endif
 411   {
 412    private:
 413       //
 414       // Curiously Recurring Template interface.
 415       //
 416       typedef Derived derived_t;
 417
 418       Derived& derived()
 419       {
 420           return static_cast<Derived&>(*this);
 421       }
 422
 423       Derived const& derived() const
 424       {
 425           return static_cast<Derived const&>(*this);
 426       }
 427
 428       typedef detail::iterator_facade_types<
 429          Value, CategoryOrTraversal, Reference, Difference
 430       > associated_types;
 431
 432    public:
 433
 434       typedef typename associated_types::value_type value_type;
 435       typedef Reference reference;
 436       typedef Difference difference_type;
 437       typedef typename associated_types::pointer pointer;
 438       typedef typename associated_types::iterator_category iterator_category;
 439
 440       reference operator*() const
 441       {
 442           return iterator_core_access::dereference(this->derived());
 443       }
 444
 445       typename detail::operator_arrow_result<
 446           value_type
 447         , reference
 448         , pointer
 449       >::type
 450       operator->() const
 451       {
 452           return detail::operator_arrow_result<
 453               value_type
 454             , reference
 455             , pointer
 456           >::make(*this->derived());
 457       }
 458
 459       typename detail::operator_brackets_result<Derived,Value,Reference>::type
 460       operator[](difference_type n) const
 461       {
 462           typedef detail::use_operator_brackets_proxy<Value,Reference> use_proxy;
 463
 464           return detail::make_operator_brackets_result<Derived>(
 465               this->derived() + n
 466             , use_proxy()
 467           );
 468       }
 469
 470       Derived& operator++()
 471       {
 472           iterator_core_access::increment(this->derived());
 473           return this->derived();
 474       }
 475
 476       Derived operator++(int)
 477       {
 478           Derived tmp(this->derived());
 479           ++*this;
 480           return tmp;
 481       }
 482
 483       Derived& operator--()
 484       {
 485           iterator_core_access::decrement(this->derived());
 486           return this->derived();
 487       }
 488
 489       Derived operator--(int)
 490       {
 491           Derived tmp(this->derived());
 492           --*this;
 493           return tmp;
 494       }
 495
 496       Derived& operator+=(difference_type n)
 497       {
 498           iterator_core_access::advance(this->derived(), n);
 499           return this->derived();
 500       }
 501
 502       Derived& operator-=(difference_type n)
 503       {
 504           iterator_core_access::advance(this->derived(), -n);
 505           return this->derived();
 506       }
 507
 508       Derived operator-(difference_type x) const
 509       {
 510           Derived result(this->derived());
 511           return result -= x;
 512       }
 513
 514 # if BOOST_WORKAROUND(BOOST_MSVC, <= 1200)
 515       // There appears to be a bug which trashes the data of classes
 516       // derived from iterator_facade when they are assigned unless we
 517       // define this assignment operator.  This bug is only revealed
 518       // (so far) in STLPort debug mode, but it's clearly a codegen
 519       // problem so we apply the workaround for all MSVC6.
 520       iterator_facade& operator=(iterator_facade const&)
 521       {
 522           return *this;
 523       }
 524 # endif
 525   };
 526
 527   //
 528   // Operator implementation. The library supplied operators
 529   // enables the user to provide fully interoperable constant/mutable
 530   // iterator types. I.e. the library provides all operators
 531   // for all mutable/constant iterator combinations.
 532   //
 533   // Note though that this kind of interoperability for constant/mutable
 534   // iterators is not required by the standard for container iterators.
 535   // All the standard asks for is a conversion mutable -> constant.
 536   // Most standard library implementations nowadays provide fully interoperable
 537   // iterator implementations, but there are still heavily used implementations
 538   // that do not provide them. (Actually it's even worse, they do not provide
 539   // them for only a few iterators.)
 540   //
 541   // ?? Maybe a BOOST_ITERATOR_NO_FULL_INTEROPERABILITY macro should
 542   //    enable the user to turn off mixed type operators
 543   //
 544   // The library takes care to provide only the right operator overloads.
 545   // I.e.
 546   //
 547   // bool operator==(Iterator,      Iterator);
 548   // bool operator==(ConstIterator, Iterator);
 549   // bool operator==(Iterator,      ConstIterator);
 550   // bool operator==(ConstIterator, ConstIterator);
 551   //
 552   //   ...
 553   //
 554   // In order to do so it uses c++ idioms that are not yet widely supported
 555   // by current compiler releases. The library is designed to degrade gracefully
 556   // in the face of compiler deficiencies. In general compiler
 557   // deficiencies result in less strict error checking and more obscure
 558   // error messages, functionality is not affected.
 559   //
 560   // For full operation compiler support for "Substitution Failure Is Not An Error"
 561   // (aka. enable_if) and boost::is_convertible is required.
 562   //
 563   // The following problems occur if support is lacking.
 564   //
 565   // Pseudo code
 566   //
 567   // ---------------
 568   // AdaptorA<Iterator1> a1;
 569   // AdaptorA<Iterator2> a2;
 570   //
 571   // // This will result in a no such overload error in full operation
 572   // // If enable_if or is_convertible is not supported
 573   // // The instantiation will fail with an error hopefully indicating that
 574   // // there is no operator== for Iterator1, Iterator2
 575   // // The same will happen if no enable_if is used to remove
 576   // // false overloads from the templated conversion constructor
 577   // // of AdaptorA.
 578   //
 579   // a1 == a2;
 580   // ----------------
 581   //
 582   // AdaptorA<Iterator> a;
 583   // AdaptorB<Iterator> b;
 584   //
 585   // // This will result in a no such overload error in full operation
 586   // // If enable_if is not supported the static assert used
 587   // // in the operator implementation will fail.
 588   // // This will accidently work if is_convertible is not supported.
 589   //
 590   // a == b;
 591   // ----------------
 592   //
 593
 594 # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP
 595 #  define BOOST_ITERATOR_CONVERTIBLE(a,b) mpl::true_()
 596 # else
 597 #  define BOOST_ITERATOR_CONVERTIBLE(a,b) is_convertible<a,b>()
 598 # endif
 599
 600 # define BOOST_ITERATOR_FACADE_INTEROP(op, result_type, return_prefix, base_op) \
 601   BOOST_ITERATOR_FACADE_INTEROP_HEAD(inline, op, result_type)                   \
 602   {                                                                             \
 603       /* For those compilers that do not support enable_if */                   \
 604       BOOST_STATIC_ASSERT((                                                     \
 605           is_interoperable< Derived1, Derived2 >::value                         \
 606       ));                                                                       \
 607       return_prefix iterator_core_access::base_op(                              \
 608           static_cast<Derived1 const&>(lhs)                                     \
 609         , static_cast<Derived2 const&>(rhs)                                     \
 610         , BOOST_ITERATOR_CONVERTIBLE(Derived2,Derived1)                         \
 611       );                                                                        \
 612   }
 613
 614 # define BOOST_ITERATOR_FACADE_RELATION(op, return_prefix, base_op) \
 615   BOOST_ITERATOR_FACADE_INTEROP(                                    \
 616       op                                                            \
 617     , detail::always_bool2                                          \
 618     , return_prefix                                                 \
 619     , base_op                                                       \
 620   )
 621
 622   BOOST_ITERATOR_FACADE_RELATION(==, return, equal)
 623   BOOST_ITERATOR_FACADE_RELATION(!=, return !, equal)
 624
 625   BOOST_ITERATOR_FACADE_RELATION(<, return 0 >, distance_from)
 626   BOOST_ITERATOR_FACADE_RELATION(>, return 0 <, distance_from)
 627   BOOST_ITERATOR_FACADE_RELATION(<=, return 0 >=, distance_from)
 628   BOOST_ITERATOR_FACADE_RELATION(>=, return 0 <=, distance_from)
 629 # undef BOOST_ITERATOR_FACADE_RELATION
 630
 631   // operator- requires an additional part in the static assertion
 632   BOOST_ITERATOR_FACADE_INTEROP(
 633       -
 634     , detail::choose_difference_type
 635     , return
 636     , distance_from
 637   )
 638 # undef BOOST_ITERATOR_FACADE_INTEROP
 639 # undef BOOST_ITERATOR_FACADE_INTEROP_HEAD
 640
 641 # define BOOST_ITERATOR_FACADE_PLUS(args)           \
 642   BOOST_ITERATOR_FACADE_PLUS_HEAD(inline, args)     \
 643   {                                                 \
 644       Derived tmp(static_cast<Derived const&>(i));  \
 645       return tmp += n;                              \
 646   }
 647
 648 BOOST_ITERATOR_FACADE_PLUS((
 649   iterator_facade<Derived, V, TC, R, D> const& i
 650   , typename Derived::difference_type n
 651 ))
 652
 653 BOOST_ITERATOR_FACADE_PLUS((
 654     typename Derived::difference_type n
 655     , iterator_facade<Derived, V, TC, R, D> const& i
 656 ))
 657 # undef BOOST_ITERATOR_FACADE_PLUS
 658 # undef BOOST_ITERATOR_FACADE_PLUS_HEAD
 659
 660 } // namespace boost
 661
 662 #include <boost/iterator/detail/config_undef.hpp>
 663
 664 #endif // BOOST_ITERATOR_FACADE_23022003THW_HPP