// (C) Copyright David Abrahams 2002. // (C) Copyright Jeremy Siek 2002. // (C) Copyright Thomas Witt 2002. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_ITERATOR_FACADE_23022003THW_HPP #define BOOST_ITERATOR_FACADE_23022003THW_HPP #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // this goes last namespace cutl_details_boost { // This forward declaration is required for the friend declaration // in iterator_core_access template class iterator_facade; namespace detail { // A binary metafunction class that always returns bool. VC6 // ICEs on mpl::always, probably because of the default // parameters. struct always_bool2 { template struct apply { typedef bool type; }; }; // // enable if for use in operator implementation. // template < class Facade1 , class Facade2 , class Return > struct enable_if_interoperable #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) { typedef typename mpl::if_< mpl::or_< is_convertible , is_convertible > , Return , int[3] >::type type; }; #else : ::cutl_details_boost::iterators::enable_if< mpl::or_< is_convertible , is_convertible > , Return > {}; #endif // // Generates associated types for an iterator_facade with the // given parameters. // template < class ValueParam , class CategoryOrTraversal , class Reference , class Difference > struct iterator_facade_types { typedef typename facade_iterator_category< CategoryOrTraversal, ValueParam, Reference >::type iterator_category; typedef typename remove_const::type value_type; // Not the real associated pointer type typedef typename mpl::eval_if< cutl_details_boost::detail::iterator_writability_disabled , add_pointer , add_pointer >::type pointer; # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ && (BOOST_WORKAROUND(_STLPORT_VERSION, BOOST_TESTED_AT(0x452)) \ || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, BOOST_TESTED_AT(310))) \ || BOOST_WORKAROUND(BOOST_RWSTD_VER, BOOST_TESTED_AT(0x20101)) \ || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, <= 310) // To interoperate with some broken library/compiler // combinations, user-defined iterators must be derived from // std::iterator. It is possible to implement a standard // library for broken compilers without this limitation. # define BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE 1 typedef iterator base; # endif }; // iterators whose dereference operators reference the same value // for all iterators into the same sequence (like many input // iterators) need help with their postfix ++: the referenced // value must be read and stored away before the increment occurs // so that *a++ yields the originally referenced element and not // the next one. template class postfix_increment_proxy { typedef typename iterator_value::type value_type; public: explicit postfix_increment_proxy(Iterator const& x) : stored_value(*x) {} // Returning a mutable reference allows nonsense like // (*r++).mutate(), but it imposes fewer assumptions about the // behavior of the value_type. In particular, recall that // (*r).mutate() is legal if operator* returns by value. value_type& operator*() const { return this->stored_value; } private: mutable value_type stored_value; }; // // In general, we can't determine that such an iterator isn't // writable -- we also need to store a copy of the old iterator so // that it can be written into. template class writable_postfix_increment_proxy { typedef typename iterator_value::type value_type; public: explicit writable_postfix_increment_proxy(Iterator const& x) : stored_value(*x) , stored_iterator(x) {} // Dereferencing must return a proxy so that both *r++ = o and // value_type(*r++) can work. In this case, *r is the same as // *r++, and the conversion operator below is used to ensure // readability. writable_postfix_increment_proxy const& operator*() const { return *this; } // Provides readability of *r++ operator value_type&() const { return stored_value; } // Provides writability of *r++ template T const& operator=(T const& x) const { *this->stored_iterator = x; return x; } // This overload just in case only non-const objects are writable template T& operator=(T& x) const { *this->stored_iterator = x; return x; } // Provides X(r++) operator Iterator const&() const { return stored_iterator; } private: mutable value_type stored_value; Iterator stored_iterator; }; # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION template struct is_non_proxy_reference_impl { static Reference r; template static typename mpl::if_< is_convertible< R const volatile* , Value const volatile* > , char[1] , char[2] >::type& helper(R const&); BOOST_STATIC_CONSTANT(bool, value = sizeof(helper(r)) == 1); }; template struct is_non_proxy_reference : mpl::bool_< is_non_proxy_reference_impl::value > {}; # else template struct is_non_proxy_reference : is_convertible< typename remove_reference::type const volatile* , Value const volatile* > {}; # endif // A metafunction to choose the result type of postfix ++ // // Because the C++98 input iterator requirements say that *r++ has // type T (value_type), implementations of some standard // algorithms like lexicographical_compare may use constructions // like: // // *r++ < *s++ // // If *r++ returns a proxy (as required if r is writable but not // multipass), this sort of expression will fail unless the proxy // supports the operator<. Since there are any number of such // operations, we're not going to try to support them. Therefore, // even if r++ returns a proxy, *r++ will only return a proxy if // *r also returns a proxy. template struct postfix_increment_result : mpl::eval_if< mpl::and_< // A proxy is only needed for readable iterators is_convertible // No multipass iterator can have values that disappear // before positions can be re-visited , mpl::not_< is_convertible< typename iterator_category_to_traversal::type , forward_traversal_tag > > > , mpl::if_< is_non_proxy_reference , postfix_increment_proxy , writable_postfix_increment_proxy > , mpl::identity > {}; // operator->() needs special support for input iterators to strictly meet the // standard's requirements. If *i is not a reference type, we must still // produce an lvalue to which a pointer can be formed. We do that by // returning a proxy object containing an instance of the reference object. template struct operator_arrow_dispatch // proxy references { struct proxy { explicit proxy(Reference const & x) : m_ref(x) {} Reference* operator->() { return cutl_details_boost::addressof(m_ref); } // This function is needed for MWCW and BCC, which won't call // operator-> again automatically per 13.3.1.2 para 8 operator Reference*() { return cutl_details_boost::addressof(m_ref); } Reference m_ref; }; typedef proxy result_type; static result_type apply(Reference const & x) { return result_type(x); } }; template struct operator_arrow_dispatch // "real" references { typedef Pointer result_type; static result_type apply(T& x) { return cutl_details_boost::addressof(x); } }; # if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // Deal with ETI template<> struct operator_arrow_dispatch { typedef int result_type; }; # endif // A proxy return type for operator[], needed to deal with // iterators that may invalidate referents upon destruction. // Consider the temporary iterator in *(a + n) template class operator_brackets_proxy { // Iterator is actually an iterator_facade, so we do not have to // go through iterator_traits to access the traits. typedef typename Iterator::reference reference; typedef typename Iterator::value_type value_type; public: operator_brackets_proxy(Iterator const& iter) : m_iter(iter) {} operator reference() const { return *m_iter; } operator_brackets_proxy& operator=(value_type const& val) { *m_iter = val; return *this; } private: Iterator m_iter; }; // A metafunction that determines whether operator[] must return a // proxy, or whether it can simply return a copy of the value_type. template struct use_operator_brackets_proxy : mpl::not_< mpl::and_< // Really we want an is_copy_constructible trait here, // but is_POD will have to suffice in the meantime. cutl_details_boost::is_POD , iterator_writability_disabled > > {}; template struct operator_brackets_result { typedef typename mpl::if_< use_operator_brackets_proxy , operator_brackets_proxy , Value >::type type; }; template operator_brackets_proxy make_operator_brackets_result(Iterator const& iter, mpl::true_) { return operator_brackets_proxy(iter); } template typename Iterator::value_type make_operator_brackets_result(Iterator const& iter, mpl::false_) { return *iter; } struct choose_difference_type { template struct apply : # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP iterator_difference # elif BOOST_WORKAROUND(BOOST_MSVC, < 1300) mpl::if_< is_convertible , typename I1::difference_type , typename I2::difference_type > # else mpl::eval_if< is_convertible , iterator_difference , iterator_difference > # endif {}; }; } // namespace detail // Macros which describe the declarations of binary operators # ifdef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY # define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \ template < \ class Derived1, class V1, class TC1, class Reference1, class Difference1 \ , class Derived2, class V2, class TC2, class Reference2, class Difference2 \ > \ prefix typename mpl::apply2::type \ operator op( \ iterator_facade const& lhs \ , iterator_facade const& rhs) # else # define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \ template < \ class Derived1, class V1, class TC1, class Reference1, class Difference1 \ , class Derived2, class V2, class TC2, class Reference2, class Difference2 \ > \ prefix typename cutl_details_boost::detail::enable_if_interoperable< \ Derived1, Derived2 \ , typename mpl::apply2::type \ >::type \ operator op( \ iterator_facade const& lhs \ , iterator_facade const& rhs) # endif # define BOOST_ITERATOR_FACADE_PLUS_HEAD(prefix,args) \ template \ prefix Derived operator+ args // // Helper class for granting access to the iterator core interface. // // The simple core interface is used by iterator_facade. The core // interface of a user/library defined iterator type should not be made public // so that it does not clutter the public interface. Instead iterator_core_access // should be made friend so that iterator_facade can access the core // interface through iterator_core_access. // class iterator_core_access { # if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) // Tasteless as this may seem, making all members public allows member templates // to work in the absence of member template friends. public: # else template friend class iterator_facade; # define BOOST_ITERATOR_FACADE_RELATION(op) \ BOOST_ITERATOR_FACADE_INTEROP_HEAD(friend,op, cutl_details_boost::detail::always_bool2); BOOST_ITERATOR_FACADE_RELATION(==) BOOST_ITERATOR_FACADE_RELATION(!=) BOOST_ITERATOR_FACADE_RELATION(<) BOOST_ITERATOR_FACADE_RELATION(>) BOOST_ITERATOR_FACADE_RELATION(<=) BOOST_ITERATOR_FACADE_RELATION(>=) # undef BOOST_ITERATOR_FACADE_RELATION BOOST_ITERATOR_FACADE_INTEROP_HEAD( friend, -, cutl_details_boost::detail::choose_difference_type) ; BOOST_ITERATOR_FACADE_PLUS_HEAD( friend inline , (iterator_facade const& , typename Derived::difference_type) ) ; BOOST_ITERATOR_FACADE_PLUS_HEAD( friend inline , (typename Derived::difference_type , iterator_facade const&) ) ; # endif template static typename Facade::reference dereference(Facade const& f) { return f.dereference(); } template static void increment(Facade& f) { f.increment(); } template static void decrement(Facade& f) { f.decrement(); } template static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::true_) { return f1.equal(f2); } template static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::false_) { return f2.equal(f1); } template static void advance(Facade& f, typename Facade::difference_type n) { f.advance(n); } template static typename Facade1::difference_type distance_from( Facade1 const& f1, Facade2 const& f2, mpl::true_) { return -f1.distance_to(f2); } template static typename Facade2::difference_type distance_from( Facade1 const& f1, Facade2 const& f2, mpl::false_) { return f2.distance_to(f1); } // // Curiously Recurring Template interface. // template static I& derived(iterator_facade& facade) { return *static_cast(&facade); } template static I const& derived(iterator_facade const& facade) { return *static_cast(&facade); } private: // objects of this class are useless iterator_core_access(); //undefined }; // // iterator_facade - use as a public base class for defining new // standard-conforming iterators. // template < class Derived // The derived iterator type being constructed , class Value , class CategoryOrTraversal , class Reference = Value& , class Difference = std::ptrdiff_t > class iterator_facade # ifdef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE : public cutl_details_boost::detail::iterator_facade_types< Value, CategoryOrTraversal, Reference, Difference >::base # undef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE # endif { private: // // Curiously Recurring Template interface. // Derived& derived() { return *static_cast(this); } Derived const& derived() const { return *static_cast(this); } typedef cutl_details_boost::detail::iterator_facade_types< Value, CategoryOrTraversal, Reference, Difference > associated_types; typedef cutl_details_boost::detail::operator_arrow_dispatch< Reference , typename associated_types::pointer > operator_arrow_dispatch_; protected: // For use by derived classes typedef iterator_facade iterator_facade_; public: typedef typename associated_types::value_type value_type; typedef Reference reference; typedef Difference difference_type; typedef typename operator_arrow_dispatch_::result_type pointer; typedef typename associated_types::iterator_category iterator_category; reference operator*() const { return iterator_core_access::dereference(this->derived()); } pointer operator->() const { return operator_arrow_dispatch_::apply(*this->derived()); } typename cutl_details_boost::detail::operator_brackets_result::type operator[](difference_type n) const { typedef cutl_details_boost::detail::use_operator_brackets_proxy use_proxy; return cutl_details_boost::detail::make_operator_brackets_result( this->derived() + n , use_proxy() ); } Derived& operator++() { iterator_core_access::increment(this->derived()); return this->derived(); } # if BOOST_WORKAROUND(BOOST_MSVC, < 1300) typename cutl_details_boost::detail::postfix_increment_result::type operator++(int) { typename cutl_details_boost::detail::postfix_increment_result::type tmp(this->derived()); ++*this; return tmp; } # endif Derived& operator--() { iterator_core_access::decrement(this->derived()); return this->derived(); } Derived operator--(int) { Derived tmp(this->derived()); --*this; return tmp; } Derived& operator+=(difference_type n) { iterator_core_access::advance(this->derived(), n); return this->derived(); } Derived& operator-=(difference_type n) { iterator_core_access::advance(this->derived(), -n); return this->derived(); } Derived operator-(difference_type x) const { Derived result(this->derived()); return result -= x; } # if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // There appears to be a bug which trashes the data of classes // derived from iterator_facade when they are assigned unless we // define this assignment operator. This bug is only revealed // (so far) in STLPort debug mode, but it's clearly a codegen // problem so we apply the workaround for all MSVC6. iterator_facade& operator=(iterator_facade const&) { return *this; } # endif }; # if !BOOST_WORKAROUND(BOOST_MSVC, < 1300) template inline typename cutl_details_boost::detail::postfix_increment_result::type operator++( iterator_facade& i , int ) { typename cutl_details_boost::detail::postfix_increment_result::type tmp(*static_cast(&i)); ++i; return tmp; } # endif // // Comparison operator implementation. The library supplied operators // enables the user to provide fully interoperable constant/mutable // iterator types. I.e. the library provides all operators // for all mutable/constant iterator combinations. // // Note though that this kind of interoperability for constant/mutable // iterators is not required by the standard for container iterators. // All the standard asks for is a conversion mutable -> constant. // Most standard library implementations nowadays provide fully interoperable // iterator implementations, but there are still heavily used implementations // that do not provide them. (Actually it's even worse, they do not provide // them for only a few iterators.) // // ?? Maybe a BOOST_ITERATOR_NO_FULL_INTEROPERABILITY macro should // enable the user to turn off mixed type operators // // The library takes care to provide only the right operator overloads. // I.e. // // bool operator==(Iterator, Iterator); // bool operator==(ConstIterator, Iterator); // bool operator==(Iterator, ConstIterator); // bool operator==(ConstIterator, ConstIterator); // // ... // // In order to do so it uses c++ idioms that are not yet widely supported // by current compiler releases. The library is designed to degrade gracefully // in the face of compiler deficiencies. In general compiler // deficiencies result in less strict error checking and more obscure // error messages, functionality is not affected. // // For full operation compiler support for "Substitution Failure Is Not An Error" // (aka. enable_if) and cutl_details_boost::is_convertible is required. // // The following problems occur if support is lacking. // // Pseudo code // // --------------- // AdaptorA a1; // AdaptorA a2; // // // This will result in a no such overload error in full operation // // If enable_if or is_convertible is not supported // // The instantiation will fail with an error hopefully indicating that // // there is no operator== for Iterator1, Iterator2 // // The same will happen if no enable_if is used to remove // // false overloads from the templated conversion constructor // // of AdaptorA. // // a1 == a2; // ---------------- // // AdaptorA a; // AdaptorB b; // // // This will result in a no such overload error in full operation // // If enable_if is not supported the static assert used // // in the operator implementation will fail. // // This will accidently work if is_convertible is not supported. // // a == b; // ---------------- // # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP # define BOOST_ITERATOR_CONVERTIBLE(a,b) mpl::true_() # else # define BOOST_ITERATOR_CONVERTIBLE(a,b) is_convertible() # endif # define BOOST_ITERATOR_FACADE_INTEROP(op, result_type, return_prefix, base_op) \ BOOST_ITERATOR_FACADE_INTEROP_HEAD(inline, op, result_type) \ { \ /* For those compilers that do not support enable_if */ \ BOOST_STATIC_ASSERT(( \ is_interoperable< Derived1, Derived2 >::value \ )); \ return_prefix iterator_core_access::base_op( \ *static_cast(&lhs) \ , *static_cast(&rhs) \ , BOOST_ITERATOR_CONVERTIBLE(Derived2,Derived1) \ ); \ } # define BOOST_ITERATOR_FACADE_RELATION(op, return_prefix, base_op) \ BOOST_ITERATOR_FACADE_INTEROP( \ op \ , cutl_details_boost::detail::always_bool2 \ , return_prefix \ , base_op \ ) BOOST_ITERATOR_FACADE_RELATION(==, return, equal) BOOST_ITERATOR_FACADE_RELATION(!=, return !, equal) BOOST_ITERATOR_FACADE_RELATION(<, return 0 >, distance_from) BOOST_ITERATOR_FACADE_RELATION(>, return 0 <, distance_from) BOOST_ITERATOR_FACADE_RELATION(<=, return 0 >=, distance_from) BOOST_ITERATOR_FACADE_RELATION(>=, return 0 <=, distance_from) # undef BOOST_ITERATOR_FACADE_RELATION // operator- requires an additional part in the static assertion BOOST_ITERATOR_FACADE_INTEROP( - , cutl_details_boost::detail::choose_difference_type , return , distance_from ) # undef BOOST_ITERATOR_FACADE_INTEROP # undef BOOST_ITERATOR_FACADE_INTEROP_HEAD # define BOOST_ITERATOR_FACADE_PLUS(args) \ BOOST_ITERATOR_FACADE_PLUS_HEAD(inline, args) \ { \ Derived tmp(static_cast(i)); \ return tmp += n; \ } BOOST_ITERATOR_FACADE_PLUS(( iterator_facade const& i , typename Derived::difference_type n )) BOOST_ITERATOR_FACADE_PLUS(( typename Derived::difference_type n , iterator_facade const& i )) # undef BOOST_ITERATOR_FACADE_PLUS # undef BOOST_ITERATOR_FACADE_PLUS_HEAD } // namespace cutl_details_boost #include #endif // BOOST_ITERATOR_FACADE_23022003THW_HPP