williamr@4: // (C) Copyright David Abrahams 2002.
williamr@4: // Distributed under the Boost Software License, Version 1.0. (See
williamr@4: // accompanying file LICENSE_1_0.txt or copy at
williamr@4: // http://www.boost.org/LICENSE_1_0.txt)
williamr@4: 
williamr@4: // Boost versions of
williamr@2: //
williamr@4: //    std::iterator_traits<>::iterator_category
williamr@4: //    std::iterator_traits<>::difference_type
williamr@4: //    std::distance()
williamr@2: //
williamr@4: // ...for all compilers and iterators
williamr@2: //
williamr@4: // Additionally, if X is a pointer
williamr@4: //    std::iterator_traits<X>::pointer
williamr@2: 
williamr@4: // Otherwise, if partial specialization is supported or X is not a pointer
williamr@4: //    std::iterator_traits<X>::value_type
williamr@4: //    std::iterator_traits<X>::pointer
williamr@4: //    std::iterator_traits<X>::reference
williamr@4: //
williamr@4: // See http://www.boost.org for most recent version including documentation.
williamr@2: 
williamr@4: // Revision History
williamr@4: // 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)
williamr@4: // 03 Mar 2001 - Put all implementation into namespace
williamr@4: //               boost::detail::iterator_traits_. Some progress made on fixes
williamr@4: //               for Intel compiler. (David Abrahams)
williamr@4: // 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few
williamr@4: //               places. (Jeremy Siek)
williamr@4: // 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and
williamr@4: //               no_type from type_traits.hpp; stopped trying to remove_cv
williamr@4: //               before detecting is_pointer, in honor of the new type_traits
williamr@4: //               semantics. (David Abrahams)
williamr@4: // 13 Feb 2001 - Make it work with nearly all standard-conforming iterators
williamr@4: //               under raw VC6. The one category remaining which will fail is
williamr@4: //               that of iterators derived from std::iterator but not
williamr@4: //               boost::iterator and which redefine difference_type.
williamr@4: // 11 Feb 2001 - Clean away code which can never be used (David Abrahams)
williamr@4: // 09 Feb 2001 - Always have a definition for each traits member, even if it
williamr@4: //               can't be properly deduced. These will be incomplete types in
williamr@4: //               some cases (undefined<void>), but it helps suppress MSVC errors
williamr@4: //               elsewhere (David Abrahams)
williamr@4: // 07 Feb 2001 - Support for more of the traits members where possible, making
williamr@4: //               this useful as a replacement for std::iterator_traits<T> when
williamr@4: //               used as a default template parameter.
williamr@4: // 06 Feb 2001 - Removed useless #includes of standard library headers
williamr@4: //               (David Abrahams)
williamr@2: 
williamr@4: #ifndef ITERATOR_DWA122600_HPP_
williamr@4: # define ITERATOR_DWA122600_HPP_
williamr@2: 
williamr@4: # include <boost/config.hpp>
williamr@4: # include <iterator>
williamr@2: 
williamr@4: // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
williamr@4: // partial specialization: instead of an iterator_category typedef, the standard
williamr@4: // container iterators have _Iterator_category.
williamr@4: //
williamr@4: // Also, whether debugging is enabled or not, there is a broken specialization
williamr@4: // of std::iterator<output_iterator_tag,void,void,void,void> which has no
williamr@4: // typedefs but iterator_category.
williamr@4: # if defined(__SGI_STL_PORT)
williamr@2: 
williamr@4: #  if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)
williamr@4: #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
williamr@4: #  endif
williamr@4: 
williamr@4: #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
williamr@4: 
williamr@4: # endif // STLPort <= 4.1b4 && no partial specialization
williamr@4: 
williamr@4: # if !defined(BOOST_NO_STD_ITERATOR_TRAITS)             \
williamr@4:   && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
williamr@4:   && !defined(BOOST_MSVC_STD_ITERATOR)
williamr@4:     
williamr@4: namespace boost { namespace detail {
williamr@4: 
williamr@4: // Define a new template so it can be specialized
williamr@4: template <class Iterator>
williamr@4: struct iterator_traits
williamr@4:     : std::iterator_traits<Iterator>
williamr@4: {};
williamr@4: using std::distance;
williamr@4: 
williamr@4: }} // namespace boost::detail
williamr@4: 
williamr@4: # else
williamr@4: 
williamr@4: #  if  !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)  \
williamr@4:     && !defined(BOOST_MSVC_STD_ITERATOR)
williamr@4: 
williamr@4: // This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS
williamr@4: 
williamr@4: namespace boost { namespace detail {
williamr@4: 
williamr@4: // Rogue Wave Standard Library fools itself into thinking partial
williamr@4: // specialization is missing on some platforms (e.g. Sun), so fails to
williamr@4: // supply iterator_traits!
williamr@4: template <class Iterator>
williamr@4: struct iterator_traits
williamr@2: {
williamr@4:     typedef typename Iterator::value_type value_type;
williamr@4:     typedef typename Iterator::reference reference;
williamr@4:     typedef typename Iterator::pointer pointer;
williamr@4:     typedef typename Iterator::difference_type difference_type;
williamr@4:     typedef typename Iterator::iterator_category iterator_category;
williamr@4: };
williamr@4: 
williamr@4: template <class T>
williamr@4: struct iterator_traits<T*>
williamr@4: {
williamr@4:     typedef T value_type;
williamr@4:     typedef T& reference;
williamr@4:     typedef T* pointer;
williamr@4:     typedef std::ptrdiff_t difference_type;
williamr@4:     typedef std::random_access_iterator_tag iterator_category;
williamr@4: };
williamr@4: 
williamr@4: template <class T>
williamr@4: struct iterator_traits<T const*>
williamr@4: {
williamr@4:     typedef T value_type;
williamr@4:     typedef T const& reference;
williamr@4:     typedef T const* pointer;
williamr@4:     typedef std::ptrdiff_t difference_type;
williamr@4:     typedef std::random_access_iterator_tag iterator_category;
williamr@4: };
williamr@4: 
williamr@4: }} // namespace boost::detail
williamr@4: 
williamr@4: #  else
williamr@4: 
williamr@4: # include <boost/type_traits/remove_const.hpp>
williamr@4: # include <boost/type_traits/detail/yes_no_type.hpp>
williamr@4: # include <boost/type_traits/is_pointer.hpp>
williamr@4: 
williamr@4: # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
williamr@4: #  include <boost/type_traits/is_same.hpp>
williamr@4: #  include <boost/type_traits/remove_pointer.hpp>
williamr@4: # endif
williamr@4: # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
williamr@4: #  include <boost/type_traits/is_base_and_derived.hpp>
williamr@4: # endif
williamr@4: 
williamr@4: # include <boost/mpl/if.hpp>
williamr@4: # include <boost/mpl/has_xxx.hpp>
williamr@4: # include <cstddef>
williamr@4: 
williamr@4: // should be the last #include
williamr@4: # include "boost/type_traits/detail/bool_trait_def.hpp"
williamr@4: 
williamr@4: namespace boost { namespace detail {
williamr@4: 
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
williamr@4: 
williamr@4: // is_mutable_iterator --
williamr@4: //
williamr@4: //   A metafunction returning true iff T is a mutable iterator type
williamr@4: //   with a nested value_type. Will only work portably with iterators
williamr@4: //   whose operator* returns a reference, but that seems to be OK for
williamr@4: //   the iterators supplied by Dinkumware. Some input iterators may
williamr@4: //   compile-time if they arrive here, and if the compiler is strict
williamr@4: //   about not taking the address of an rvalue.
williamr@4: 
williamr@4: // This one detects ordinary mutable iterators - the result of
williamr@4: // operator* is convertible to the value_type.
williamr@4: template <class T>
williamr@4: type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);
williamr@4: 
williamr@4: // Since you can't take the address of an rvalue, the guts of
williamr@4: // is_mutable_iterator_impl will fail if we use &*t directly.  This
williamr@4: // makes sure we can still work with non-lvalue iterators.
williamr@4: template <class T> T* mutable_iterator_lvalue_helper(T& x);
williamr@4: int mutable_iterator_lvalue_helper(...);
williamr@4: 
williamr@4: 
williamr@4: // This one detects output iterators such as ostream_iterator which
williamr@4: // return references to themselves.
williamr@4: template <class T>
williamr@4: type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
williamr@4: 
williamr@4: type_traits::no_type is_mutable_iterator_helper(...);
williamr@4: 
williamr@4: template <class T>
williamr@4: struct is_mutable_iterator_impl
williamr@4: {
williamr@4:     static T t;
williamr@2:     
williamr@4:     BOOST_STATIC_CONSTANT(
williamr@4:         bool, value = sizeof(
williamr@4:             detail::is_mutable_iterator_helper(
williamr@4:                 (T*)0
williamr@4:               , mutable_iterator_lvalue_helper(*t) // like &*t
williamr@4:             ))
williamr@4:         == sizeof(type_traits::yes_type)
williamr@4:     );
williamr@4: };
williamr@4: 
williamr@4: BOOST_TT_AUX_BOOL_TRAIT_DEF1(
williamr@4:     is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)
williamr@4: 
williamr@4: 
williamr@4: // is_full_iterator_traits --
williamr@4: //
williamr@4: //   A metafunction returning true iff T has all the requisite nested
williamr@4: //   types to satisfy the requirements for a fully-conforming
williamr@4: //   iterator_traits implementation.
williamr@4: template <class T>
williamr@4: struct is_full_iterator_traits_impl
williamr@4: {
williamr@4:     enum { value = 
williamr@4:            has_value_type<T>::value 
williamr@4:            & has_reference<T>::value 
williamr@4:            & has_pointer<T>::value 
williamr@4:            & has_difference_type<T>::value
williamr@4:            & has_iterator_category<T>::value
williamr@2:     };
williamr@4: };
williamr@4: 
williamr@4: BOOST_TT_AUX_BOOL_TRAIT_DEF1(
williamr@4:     is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)
williamr@4: 
williamr@4: 
williamr@4: #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
williamr@4: BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
williamr@2:     
williamr@4: // is_stlport_40_debug_iterator --
williamr@4: //
williamr@4: //   A metafunction returning true iff T has all the requisite nested
williamr@4: //   types to satisfy the requirements of an STLPort 4.0 debug iterator
williamr@4: //   iterator_traits implementation.
williamr@4: template <class T>
williamr@4: struct is_stlport_40_debug_iterator_impl
williamr@4: {
williamr@4:     enum { value = 
williamr@4:            has_value_type<T>::value 
williamr@4:            & has_reference<T>::value 
williamr@4:            & has_pointer<T>::value 
williamr@4:            & has_difference_type<T>::value
williamr@4:            & has__Iterator_category<T>::value
williamr@4:     };
williamr@4: };
williamr@2: 
williamr@4: BOOST_TT_AUX_BOOL_TRAIT_DEF1(
williamr@4:     is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
williamr@4: 
williamr@4: template <class T>
williamr@4: struct stlport_40_debug_iterator_traits
williamr@4: {
williamr@4:     typedef typename T::value_type value_type;
williamr@4:     typedef typename T::reference reference;
williamr@4:     typedef typename T::pointer pointer;
williamr@4:     typedef typename T::difference_type difference_type;
williamr@4:     typedef typename T::_Iterator_category iterator_category;
williamr@4: };
williamr@4: #   endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF 
williamr@4: 
williamr@4: template <class T> struct pointer_iterator_traits;
williamr@4: 
williamr@4: #   ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
williamr@4: template <class T>
williamr@4: struct pointer_iterator_traits<T*>
williamr@4: {
williamr@4:     typedef typename remove_const<T>::type value_type;
williamr@4:     typedef T* pointer;
williamr@4:     typedef T& reference;
williamr@4:     typedef std::random_access_iterator_tag iterator_category;
williamr@4:     typedef std::ptrdiff_t difference_type;
williamr@4: };
williamr@4: #   else
williamr@4: 
williamr@4: // In case of no template partial specialization, and if T is a
williamr@4: // pointer, iterator_traits<T>::value_type can still be computed.  For
williamr@4: // some basic types, remove_pointer is manually defined in
williamr@4: // type_traits/broken_compiler_spec.hpp. For others, do it yourself.
williamr@4: 
williamr@4: template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
williamr@4: 
williamr@4: template<class P>
williamr@4: struct pointer_value_type
williamr@4:   : mpl::if_<
williamr@4:         is_same<P, typename remove_pointer<P>::type>
williamr@4:       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
williamr@4:       , typename remove_const<
williamr@4:             typename remove_pointer<P>::type
williamr@4:         >::type
williamr@4:     >
williamr@4: {
williamr@4: };
williamr@4: 
williamr@4: 
williamr@4: template<class P>
williamr@4: struct pointer_reference
williamr@4:   : mpl::if_<
williamr@4:         is_same<P, typename remove_pointer<P>::type>
williamr@4:       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
williamr@4:       , typename remove_pointer<P>::type&
williamr@4:     >
williamr@4: {
williamr@4: };
williamr@4: 
williamr@4: template <class T>
williamr@4: struct pointer_iterator_traits
williamr@4: {
williamr@4:     typedef T pointer;
williamr@4:     typedef std::random_access_iterator_tag iterator_category;
williamr@4:     typedef std::ptrdiff_t difference_type;
williamr@4: 
williamr@4:     typedef typename pointer_value_type<T>::type value_type;
williamr@4:     typedef typename pointer_reference<T>::type reference;
williamr@4: };
williamr@4: 
williamr@4: #   endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
williamr@4: 
williamr@4: // We'll sort iterator types into one of these classifications, from which we
williamr@4: // can determine the difference_type, pointer, reference, and value_type
williamr@4: template <class Iterator>
williamr@4: struct standard_iterator_traits
williamr@4: {
williamr@4:     typedef typename Iterator::difference_type difference_type;
williamr@4:     typedef typename Iterator::value_type value_type;
williamr@4:     typedef typename Iterator::pointer pointer;
williamr@4:     typedef typename Iterator::reference reference;
williamr@4:     typedef typename Iterator::iterator_category iterator_category;
williamr@4: };
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: struct msvc_stdlib_mutable_traits
williamr@4:     : std::iterator_traits<Iterator>
williamr@4: {
williamr@4:     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
williamr@4:     typedef typename std::iterator_traits<Iterator>::value_type* pointer;
williamr@4:     typedef typename std::iterator_traits<Iterator>::value_type& reference;
williamr@4: };
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: struct msvc_stdlib_const_traits
williamr@4:     : std::iterator_traits<Iterator>
williamr@4: {
williamr@4:     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
williamr@4:     typedef const typename std::iterator_traits<Iterator>::value_type* pointer;
williamr@4:     typedef const typename std::iterator_traits<Iterator>::value_type& reference;
williamr@4: };
williamr@4: 
williamr@4: #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
williamr@4: template <class Iterator>
williamr@4: struct is_bad_output_iterator
williamr@4:     : is_base_and_derived<
williamr@4:         std::iterator<std::output_iterator_tag,void,void,void,void>
williamr@4:         , Iterator>
williamr@4: {
williamr@4: };
williamr@4: 
williamr@4: struct bad_output_iterator_traits
williamr@4: {
williamr@4:     typedef void value_type;
williamr@4:     typedef void difference_type;
williamr@4:     typedef std::output_iterator_tag iterator_category;
williamr@4:     typedef void pointer;
williamr@4:     typedef void reference;
williamr@4: };
williamr@4: #   endif
williamr@4: 
williamr@4: // If we're looking at an MSVC6 (old Dinkumware) ``standard''
williamr@4: // iterator, this will generate an appropriate traits class. 
williamr@4: template <class Iterator>
williamr@4: struct msvc_stdlib_iterator_traits
williamr@4:     : mpl::if_<
williamr@4:        is_mutable_iterator<Iterator>
williamr@4:        , msvc_stdlib_mutable_traits<Iterator>
williamr@4:        , msvc_stdlib_const_traits<Iterator>
williamr@4:       >::type
williamr@4: {};
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: struct non_pointer_iterator_traits
williamr@4:     : mpl::if_<
williamr@4:         // if the iterator contains all the right nested types...
williamr@4:         is_full_iterator_traits<Iterator>
williamr@4:         // Use a standard iterator_traits implementation
williamr@4:         , standard_iterator_traits<Iterator>
williamr@4: #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
williamr@4:         // Check for STLPort 4.0 broken _Iterator_category type
williamr@4:         , mpl::if_<
williamr@4:              is_stlport_40_debug_iterator<Iterator>
williamr@4:              , stlport_40_debug_iterator_traits<Iterator>
williamr@4: #   endif
williamr@4:         // Otherwise, assume it's a Dinkum iterator
williamr@4:         , msvc_stdlib_iterator_traits<Iterator>
williamr@4: #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
williamr@4:         >::type
williamr@4: #   endif 
williamr@4:     >::type
williamr@4: {
williamr@4: };
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: struct iterator_traits_aux
williamr@4:     : mpl::if_<
williamr@4:         is_pointer<Iterator>
williamr@4:         , pointer_iterator_traits<Iterator>
williamr@4:         , non_pointer_iterator_traits<Iterator>
williamr@4:     >::type
williamr@4: {
williamr@4: };
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: struct iterator_traits
williamr@4: {
williamr@4:     // Explicit forwarding from base class needed to keep MSVC6 happy
williamr@4:     // under some circumstances.
williamr@4:  private:
williamr@4: #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
williamr@4:     typedef 
williamr@4:     typename mpl::if_<
williamr@4:         is_bad_output_iterator<Iterator>
williamr@4:         , bad_output_iterator_traits
williamr@4:         , iterator_traits_aux<Iterator>
williamr@4:     >::type base;
williamr@4: #   else
williamr@4:     typedef iterator_traits_aux<Iterator> base;
williamr@4: #   endif
williamr@4:  public:
williamr@4:     typedef typename base::value_type value_type;
williamr@4:     typedef typename base::pointer pointer;
williamr@4:     typedef typename base::reference reference;
williamr@4:     typedef typename base::difference_type difference_type;
williamr@4:     typedef typename base::iterator_category iterator_category;
williamr@4: };
williamr@4: 
williamr@4: // This specialization cuts off ETI (Early Template Instantiation) for MSVC.
williamr@4: template <> struct iterator_traits<int>
williamr@4: {
williamr@4:     typedef int value_type;
williamr@4:     typedef int pointer;
williamr@4:     typedef int reference;
williamr@4:     typedef int difference_type;
williamr@4:     typedef int iterator_category;
williamr@4: };
williamr@4: 
williamr@4: }} // namespace boost::detail
williamr@4: 
williamr@4: #  endif // workarounds
williamr@4: 
williamr@4: namespace boost { namespace detail {
williamr@4: 
williamr@4: namespace iterator_traits_
williamr@4: {
williamr@4:   template <class Iterator, class Difference>
williamr@4:   struct distance_select
williamr@4:   {
williamr@4:       static Difference execute(Iterator i1, const Iterator i2, ...)
williamr@4:       {
williamr@4:           Difference result = 0;
williamr@4:           while (i1 != i2)
williamr@4:           {
williamr@4:               ++i1;
williamr@4:               ++result;
williamr@4:           }
williamr@4:           return result;
williamr@4:       }
williamr@4: 
williamr@4:       static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)
williamr@4:       {
williamr@4:           return i2 - i1;
williamr@4:       }
williamr@4:   };
williamr@4: } // namespace boost::detail::iterator_traits_
williamr@4: 
williamr@4: template <class Iterator>
williamr@4: inline typename iterator_traits<Iterator>::difference_type
williamr@4: distance(Iterator first, Iterator last)
williamr@4: {
williamr@4:     typedef typename iterator_traits<Iterator>::difference_type diff_t;
williamr@4:     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
williamr@2:     
williamr@4:     return iterator_traits_::distance_select<Iterator,diff_t>::execute(
williamr@4:         first, last, (iterator_category*)0);
williamr@4: }
williamr@2: 
williamr@4: }}
williamr@2: 
williamr@4: # endif
williamr@2: 
williamr@2: 
williamr@4: # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
williamr@4: # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
williamr@2: 
williamr@4: #endif // ITERATOR_DWA122600_HPP_