// (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_