// (C) Copyright David Abrahams 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)

// Boost versions of

//

//    std::iterator_traits<>::iterator_category

//    std::iterator_traits<>::difference_type

//    std::distance()

//

// ...for all compilers and iterators

//

// Additionally, if X is a pointer

//    std::iterator_traits<X>::pointer

// Otherwise, if partial specialization is supported or X is not a pointer

//    std::iterator_traits<X>::value_type

//    std::iterator_traits<X>::pointer

//    std::iterator_traits<X>::reference

//

// See http://www.boost.org for most recent version including documentation.

// Revision History

// 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)

// 03 Mar 2001 - Put all implementation into namespace

//               boost::detail::iterator_traits_. Some progress made on fixes

//               for Intel compiler. (David Abrahams)

// 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few

//               places. (Jeremy Siek)

// 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and

//               no_type from type_traits.hpp; stopped trying to remove_cv

//               before detecting is_pointer, in honor of the new type_traits

//               semantics. (David Abrahams)

// 13 Feb 2001 - Make it work with nearly all standard-conforming iterators

//               under raw VC6. The one category remaining which will fail is

//               that of iterators derived from std::iterator but not

//               boost::iterator and which redefine difference_type.

// 11 Feb 2001 - Clean away code which can never be used (David Abrahams)

// 09 Feb 2001 - Always have a definition for each traits member, even if it

//               can't be properly deduced. These will be incomplete types in

//               some cases (undefined<void>), but it helps suppress MSVC errors

//               elsewhere (David Abrahams)

// 07 Feb 2001 - Support for more of the traits members where possible, making

//               this useful as a replacement for std::iterator_traits<T> when

//               used as a default template parameter.

// 06 Feb 2001 - Removed useless #includes of standard library headers

//               (David Abrahams)

#ifndef ITERATOR_DWA122600_HPP_

# define ITERATOR_DWA122600_HPP_

# include <boost/config.hpp>

# include <iterator>

// STLPort 4.0 and betas have a bug when debugging is enabled and there is no

// partial specialization: instead of an iterator_category typedef, the standard

// container iterators have _Iterator_category.

//

// Also, whether debugging is enabled or not, there is a broken specialization

// of std::iterator<output_iterator_tag,void,void,void,void> which has no

// typedefs but iterator_category.

# if defined(__SGI_STL_PORT)

#  if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)

#   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF

#  endif

#  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION

# endif // STLPort <= 4.1b4 && no partial specialization

# if !defined(BOOST_NO_STD_ITERATOR_TRAITS)             \

  && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \

  && !defined(BOOST_MSVC_STD_ITERATOR)

namespace boost { namespace detail {

// Define a new template so it can be specialized

template <class Iterator>

struct iterator_traits

    : std::iterator_traits<Iterator>

{};

using std::distance;

}} // namespace boost::detail

# else

#  if  !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)  \

    && !defined(BOOST_MSVC_STD_ITERATOR)

// This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS

namespace boost { namespace detail {

// Rogue Wave Standard Library fools itself into thinking partial

// specialization is missing on some platforms (e.g. Sun), so fails to

// supply iterator_traits!

template <class Iterator>

struct iterator_traits

{

    typedef typename Iterator::value_type value_type;

    typedef typename Iterator::reference reference;

    typedef typename Iterator::pointer pointer;

    typedef typename Iterator::difference_type difference_type;

    typedef typename Iterator::iterator_category iterator_category;

};

template <class T>

struct iterator_traits<T*>

{

    typedef T value_type;

    typedef T& reference;

    typedef T* pointer;

    typedef std::ptrdiff_t difference_type;

    typedef std::random_access_iterator_tag iterator_category;

};

template <class T>

struct iterator_traits<T const*>

{

    typedef T value_type;

    typedef T const& reference;

    typedef T const* pointer;

    typedef std::ptrdiff_t difference_type;

    typedef std::random_access_iterator_tag iterator_category;

};

}} // namespace boost::detail

#  else

# include <boost/type_traits/remove_const.hpp>

# include <boost/type_traits/detail/yes_no_type.hpp>

# include <boost/type_traits/is_pointer.hpp>

# ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

#  include <boost/type_traits/is_same.hpp>

#  include <boost/type_traits/remove_pointer.hpp>

# endif

# ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION

#  include <boost/type_traits/is_base_and_derived.hpp>

# endif

# include <boost/mpl/if.hpp>

# include <boost/mpl/has_xxx.hpp>

# include <cstddef>

// should be the last #include

# include "boost/type_traits/detail/bool_trait_def.hpp"

namespace boost { namespace detail {

BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)

BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)

BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)

BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)

BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)

// is_mutable_iterator --

//

//   A metafunction returning true iff T is a mutable iterator type

//   with a nested value_type. Will only work portably with iterators

//   whose operator* returns a reference, but that seems to be OK for

//   the iterators supplied by Dinkumware. Some input iterators may

//   compile-time if they arrive here, and if the compiler is strict

//   about not taking the address of an rvalue.

// This one detects ordinary mutable iterators - the result of

// operator* is convertible to the value_type.

template <class T>

type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);

// Since you can't take the address of an rvalue, the guts of

// is_mutable_iterator_impl will fail if we use &*t directly.  This

// makes sure we can still work with non-lvalue iterators.

template <class T> T* mutable_iterator_lvalue_helper(T& x);

int mutable_iterator_lvalue_helper(...);

// This one detects output iterators such as ostream_iterator which

// return references to themselves.

template <class T>

type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);

type_traits::no_type is_mutable_iterator_helper(...);

template <class T>

struct is_mutable_iterator_impl

{

    static T t;

    BOOST_STATIC_CONSTANT(

        bool, value = sizeof(

            detail::is_mutable_iterator_helper(

                (T*)0

              , mutable_iterator_lvalue_helper(*t) // like &*t

            ))

        == sizeof(type_traits::yes_type)

    );

};

BOOST_TT_AUX_BOOL_TRAIT_DEF1(

    is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)

// is_full_iterator_traits --

//

//   A metafunction returning true iff T has all the requisite nested

//   types to satisfy the requirements for a fully-conforming

//   iterator_traits implementation.

template <class T>

struct is_full_iterator_traits_impl

{

    enum { value = 

           has_value_type<T>::value 

           & has_reference<T>::value 

           & has_pointer<T>::value 

           & has_difference_type<T>::value

           & has_iterator_category<T>::value

    };

};

BOOST_TT_AUX_BOOL_TRAIT_DEF1(

    is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)

#   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF

BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)

// is_stlport_40_debug_iterator --

//

//   A metafunction returning true iff T has all the requisite nested

//   types to satisfy the requirements of an STLPort 4.0 debug iterator

//   iterator_traits implementation.

template <class T>

struct is_stlport_40_debug_iterator_impl

{

    enum { value = 

           has_value_type<T>::value 

           & has_reference<T>::value 

           & has_pointer<T>::value 

           & has_difference_type<T>::value

           & has__Iterator_category<T>::value

    };

};

BOOST_TT_AUX_BOOL_TRAIT_DEF1(

    is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)

template <class T>

struct stlport_40_debug_iterator_traits

{

    typedef typename T::value_type value_type;

    typedef typename T::reference reference;

    typedef typename T::pointer pointer;

    typedef typename T::difference_type difference_type;

    typedef typename T::_Iterator_category iterator_category;

};

#   endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF 

template <class T> struct pointer_iterator_traits;

#   ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

template <class T>

struct pointer_iterator_traits<T*>

{

    typedef typename remove_const<T>::type value_type;

    typedef T* pointer;

    typedef T& reference;

    typedef std::random_access_iterator_tag iterator_category;

    typedef std::ptrdiff_t difference_type;

};

#   else

// In case of no template partial specialization, and if T is a

// pointer, iterator_traits<T>::value_type can still be computed.  For

// some basic types, remove_pointer is manually defined in

// type_traits/broken_compiler_spec.hpp. For others, do it yourself.

template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;

template<class P>

struct pointer_value_type

  : mpl::if_<

        is_same<P, typename remove_pointer<P>::type>

      , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>

      , typename remove_const<

            typename remove_pointer<P>::type

        >::type

    >

{

};

template<class P>

struct pointer_reference

  : mpl::if_<

        is_same<P, typename remove_pointer<P>::type>

      , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>

      , typename remove_pointer<P>::type&

    >

{

};

template <class T>

struct pointer_iterator_traits

{

    typedef T pointer;

    typedef std::random_access_iterator_tag iterator_category;

    typedef std::ptrdiff_t difference_type;

    typedef typename pointer_value_type<T>::type value_type;

    typedef typename pointer_reference<T>::type reference;

};

#   endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

// We'll sort iterator types into one of these classifications, from which we

// can determine the difference_type, pointer, reference, and value_type

template <class Iterator>

struct standard_iterator_traits

{

    typedef typename Iterator::difference_type difference_type;

    typedef typename Iterator::value_type value_type;

    typedef typename Iterator::pointer pointer;

    typedef typename Iterator::reference reference;

    typedef typename Iterator::iterator_category iterator_category;

};

template <class Iterator>

struct msvc_stdlib_mutable_traits

    : std::iterator_traits<Iterator>

{

    typedef typename std::iterator_traits<Iterator>::distance_type difference_type;

    typedef typename std::iterator_traits<Iterator>::value_type* pointer;

    typedef typename std::iterator_traits<Iterator>::value_type& reference;

};

template <class Iterator>

struct msvc_stdlib_const_traits

    : std::iterator_traits<Iterator>

{

    typedef typename std::iterator_traits<Iterator>::distance_type difference_type;

    typedef const typename std::iterator_traits<Iterator>::value_type* pointer;

    typedef const typename std::iterator_traits<Iterator>::value_type& reference;

};

#   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION

template <class Iterator>

struct is_bad_output_iterator

    : is_base_and_derived<

        std::iterator<std::output_iterator_tag,void,void,void,void>

        , Iterator>

{

};

struct bad_output_iterator_traits

{

    typedef void value_type;

    typedef void difference_type;

    typedef std::output_iterator_tag iterator_category;

    typedef void pointer;

    typedef void reference;

};

#   endif

// If we're looking at an MSVC6 (old Dinkumware) ``standard''

// iterator, this will generate an appropriate traits class. 

template <class Iterator>

struct msvc_stdlib_iterator_traits

    : mpl::if_<

       is_mutable_iterator<Iterator>

       , msvc_stdlib_mutable_traits<Iterator>

       , msvc_stdlib_const_traits<Iterator>

      >::type

{};

template <class Iterator>

struct non_pointer_iterator_traits

    : mpl::if_<

        // if the iterator contains all the right nested types...

        is_full_iterator_traits<Iterator>

        // Use a standard iterator_traits implementation

        , standard_iterator_traits<Iterator>

#   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF

        // Check for STLPort 4.0 broken _Iterator_category type

        , mpl::if_<

             is_stlport_40_debug_iterator<Iterator>

             , stlport_40_debug_iterator_traits<Iterator>

#   endif

        // Otherwise, assume it's a Dinkum iterator

        , msvc_stdlib_iterator_traits<Iterator>

#   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF

        >::type

#   endif 

    >::type

{

};

template <class Iterator>

struct iterator_traits_aux

    : mpl::if_<

        is_pointer<Iterator>

        , pointer_iterator_traits<Iterator>

        , non_pointer_iterator_traits<Iterator>

    >::type

{

};

template <class Iterator>

struct iterator_traits

{

    // Explicit forwarding from base class needed to keep MSVC6 happy

    // under some circumstances.

 private:

#   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION

    typedef 

    typename mpl::if_<

        is_bad_output_iterator<Iterator>

        , bad_output_iterator_traits

        , iterator_traits_aux<Iterator>

    >::type base;

#   else

    typedef iterator_traits_aux<Iterator> base;

#   endif

 public:

    typedef typename base::value_type value_type;

    typedef typename base::pointer pointer;

    typedef typename base::reference reference;

    typedef typename base::difference_type difference_type;

    typedef typename base::iterator_category iterator_category;

};

// This specialization cuts off ETI (Early Template Instantiation) for MSVC.

template <> struct iterator_traits<int>

{

    typedef int value_type;

    typedef int pointer;

    typedef int reference;

    typedef int difference_type;

    typedef int iterator_category;

};

}} // namespace boost::detail

#  endif // workarounds

namespace boost { namespace detail {

namespace iterator_traits_

{

  template <class Iterator, class Difference>

  struct distance_select

  {

      static Difference execute(Iterator i1, const Iterator i2, ...)

      {

          Difference result = 0;

          while (i1 != i2)

          {

              ++i1;

              ++result;

          }

          return result;

      }

      static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)

      {

          return i2 - i1;

      }

  };

} // namespace boost::detail::iterator_traits_

template <class Iterator>

inline typename iterator_traits<Iterator>::difference_type

distance(Iterator first, Iterator last)

{

    typedef typename iterator_traits<Iterator>::difference_type diff_t;

    typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;

    return iterator_traits_::distance_select<Iterator,diff_t>::execute(

        first, last, (iterator_category*)0);

}

}}

# endif

# undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF

# undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION

#endif // ITERATOR_DWA122600_HPP_