epoc32/include/stdapis/boost/detail/iterator.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     1 // (C) Copyright David Abrahams 2002.
     2 // Distributed under the Boost Software License, Version 1.0. (See
     3 // accompanying file LICENSE_1_0.txt or copy at
     4 // http://www.boost.org/LICENSE_1_0.txt)
     5 
     6 // Boost versions of
     7 //
     8 //    std::iterator_traits<>::iterator_category
     9 //    std::iterator_traits<>::difference_type
    10 //    std::distance()
    11 //
    12 // ...for all compilers and iterators
    13 //
    14 // Additionally, if X is a pointer
    15 //    std::iterator_traits<X>::pointer
    16 
    17 // Otherwise, if partial specialization is supported or X is not a pointer
    18 //    std::iterator_traits<X>::value_type
    19 //    std::iterator_traits<X>::pointer
    20 //    std::iterator_traits<X>::reference
    21 //
    22 // See http://www.boost.org for most recent version including documentation.
    23 
    24 // Revision History
    25 // 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)
    26 // 03 Mar 2001 - Put all implementation into namespace
    27 //               boost::detail::iterator_traits_. Some progress made on fixes
    28 //               for Intel compiler. (David Abrahams)
    29 // 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few
    30 //               places. (Jeremy Siek)
    31 // 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and
    32 //               no_type from type_traits.hpp; stopped trying to remove_cv
    33 //               before detecting is_pointer, in honor of the new type_traits
    34 //               semantics. (David Abrahams)
    35 // 13 Feb 2001 - Make it work with nearly all standard-conforming iterators
    36 //               under raw VC6. The one category remaining which will fail is
    37 //               that of iterators derived from std::iterator but not
    38 //               boost::iterator and which redefine difference_type.
    39 // 11 Feb 2001 - Clean away code which can never be used (David Abrahams)
    40 // 09 Feb 2001 - Always have a definition for each traits member, even if it
    41 //               can't be properly deduced. These will be incomplete types in
    42 //               some cases (undefined<void>), but it helps suppress MSVC errors
    43 //               elsewhere (David Abrahams)
    44 // 07 Feb 2001 - Support for more of the traits members where possible, making
    45 //               this useful as a replacement for std::iterator_traits<T> when
    46 //               used as a default template parameter.
    47 // 06 Feb 2001 - Removed useless #includes of standard library headers
    48 //               (David Abrahams)
    49 
    50 #ifndef ITERATOR_DWA122600_HPP_
    51 # define ITERATOR_DWA122600_HPP_
    52 
    53 # include <boost/config.hpp>
    54 # include <iterator>
    55 
    56 // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
    57 // partial specialization: instead of an iterator_category typedef, the standard
    58 // container iterators have _Iterator_category.
    59 //
    60 // Also, whether debugging is enabled or not, there is a broken specialization
    61 // of std::iterator<output_iterator_tag,void,void,void,void> which has no
    62 // typedefs but iterator_category.
    63 # if defined(__SGI_STL_PORT)
    64 
    65 #  if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)
    66 #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
    67 #  endif
    68 
    69 #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
    70 
    71 # endif // STLPort <= 4.1b4 && no partial specialization
    72 
    73 # if !defined(BOOST_NO_STD_ITERATOR_TRAITS)             \
    74   && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
    75   && !defined(BOOST_MSVC_STD_ITERATOR)
    76     
    77 namespace boost { namespace detail {
    78 
    79 // Define a new template so it can be specialized
    80 template <class Iterator>
    81 struct iterator_traits
    82     : std::iterator_traits<Iterator>
    83 {};
    84 using std::distance;
    85 
    86 }} // namespace boost::detail
    87 
    88 # else
    89 
    90 #  if  !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)  \
    91     && !defined(BOOST_MSVC_STD_ITERATOR)
    92 
    93 // This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS
    94 
    95 namespace boost { namespace detail {
    96 
    97 // Rogue Wave Standard Library fools itself into thinking partial
    98 // specialization is missing on some platforms (e.g. Sun), so fails to
    99 // supply iterator_traits!
   100 template <class Iterator>
   101 struct iterator_traits
   102 {
   103     typedef typename Iterator::value_type value_type;
   104     typedef typename Iterator::reference reference;
   105     typedef typename Iterator::pointer pointer;
   106     typedef typename Iterator::difference_type difference_type;
   107     typedef typename Iterator::iterator_category iterator_category;
   108 };
   109 
   110 template <class T>
   111 struct iterator_traits<T*>
   112 {
   113     typedef T value_type;
   114     typedef T& reference;
   115     typedef T* pointer;
   116     typedef std::ptrdiff_t difference_type;
   117     typedef std::random_access_iterator_tag iterator_category;
   118 };
   119 
   120 template <class T>
   121 struct iterator_traits<T const*>
   122 {
   123     typedef T value_type;
   124     typedef T const& reference;
   125     typedef T const* pointer;
   126     typedef std::ptrdiff_t difference_type;
   127     typedef std::random_access_iterator_tag iterator_category;
   128 };
   129 
   130 }} // namespace boost::detail
   131 
   132 #  else
   133 
   134 # include <boost/type_traits/remove_const.hpp>
   135 # include <boost/type_traits/detail/yes_no_type.hpp>
   136 # include <boost/type_traits/is_pointer.hpp>
   137 
   138 # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
   139 #  include <boost/type_traits/is_same.hpp>
   140 #  include <boost/type_traits/remove_pointer.hpp>
   141 # endif
   142 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
   143 #  include <boost/type_traits/is_base_and_derived.hpp>
   144 # endif
   145 
   146 # include <boost/mpl/if.hpp>
   147 # include <boost/mpl/has_xxx.hpp>
   148 # include <cstddef>
   149 
   150 // should be the last #include
   151 # include "boost/type_traits/detail/bool_trait_def.hpp"
   152 
   153 namespace boost { namespace detail {
   154 
   155 BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
   156 BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
   157 BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
   158 BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
   159 BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
   160 
   161 // is_mutable_iterator --
   162 //
   163 //   A metafunction returning true iff T is a mutable iterator type
   164 //   with a nested value_type. Will only work portably with iterators
   165 //   whose operator* returns a reference, but that seems to be OK for
   166 //   the iterators supplied by Dinkumware. Some input iterators may
   167 //   compile-time if they arrive here, and if the compiler is strict
   168 //   about not taking the address of an rvalue.
   169 
   170 // This one detects ordinary mutable iterators - the result of
   171 // operator* is convertible to the value_type.
   172 template <class T>
   173 type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);
   174 
   175 // Since you can't take the address of an rvalue, the guts of
   176 // is_mutable_iterator_impl will fail if we use &*t directly.  This
   177 // makes sure we can still work with non-lvalue iterators.
   178 template <class T> T* mutable_iterator_lvalue_helper(T& x);
   179 int mutable_iterator_lvalue_helper(...);
   180 
   181 
   182 // This one detects output iterators such as ostream_iterator which
   183 // return references to themselves.
   184 template <class T>
   185 type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
   186 
   187 type_traits::no_type is_mutable_iterator_helper(...);
   188 
   189 template <class T>
   190 struct is_mutable_iterator_impl
   191 {
   192     static T t;
   193     
   194     BOOST_STATIC_CONSTANT(
   195         bool, value = sizeof(
   196             detail::is_mutable_iterator_helper(
   197                 (T*)0
   198               , mutable_iterator_lvalue_helper(*t) // like &*t
   199             ))
   200         == sizeof(type_traits::yes_type)
   201     );
   202 };
   203 
   204 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
   205     is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)
   206 
   207 
   208 // is_full_iterator_traits --
   209 //
   210 //   A metafunction returning true iff T has all the requisite nested
   211 //   types to satisfy the requirements for a fully-conforming
   212 //   iterator_traits implementation.
   213 template <class T>
   214 struct is_full_iterator_traits_impl
   215 {
   216     enum { value = 
   217            has_value_type<T>::value 
   218            & has_reference<T>::value 
   219            & has_pointer<T>::value 
   220            & has_difference_type<T>::value
   221            & has_iterator_category<T>::value
   222     };
   223 };
   224 
   225 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
   226     is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)
   227 
   228 
   229 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
   230 BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
   231     
   232 // is_stlport_40_debug_iterator --
   233 //
   234 //   A metafunction returning true iff T has all the requisite nested
   235 //   types to satisfy the requirements of an STLPort 4.0 debug iterator
   236 //   iterator_traits implementation.
   237 template <class T>
   238 struct is_stlport_40_debug_iterator_impl
   239 {
   240     enum { value = 
   241            has_value_type<T>::value 
   242            & has_reference<T>::value 
   243            & has_pointer<T>::value 
   244            & has_difference_type<T>::value
   245            & has__Iterator_category<T>::value
   246     };
   247 };
   248 
   249 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
   250     is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
   251 
   252 template <class T>
   253 struct stlport_40_debug_iterator_traits
   254 {
   255     typedef typename T::value_type value_type;
   256     typedef typename T::reference reference;
   257     typedef typename T::pointer pointer;
   258     typedef typename T::difference_type difference_type;
   259     typedef typename T::_Iterator_category iterator_category;
   260 };
   261 #   endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF 
   262 
   263 template <class T> struct pointer_iterator_traits;
   264 
   265 #   ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
   266 template <class T>
   267 struct pointer_iterator_traits<T*>
   268 {
   269     typedef typename remove_const<T>::type value_type;
   270     typedef T* pointer;
   271     typedef T& reference;
   272     typedef std::random_access_iterator_tag iterator_category;
   273     typedef std::ptrdiff_t difference_type;
   274 };
   275 #   else
   276 
   277 // In case of no template partial specialization, and if T is a
   278 // pointer, iterator_traits<T>::value_type can still be computed.  For
   279 // some basic types, remove_pointer is manually defined in
   280 // type_traits/broken_compiler_spec.hpp. For others, do it yourself.
   281 
   282 template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
   283 
   284 template<class P>
   285 struct pointer_value_type
   286   : mpl::if_<
   287         is_same<P, typename remove_pointer<P>::type>
   288       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
   289       , typename remove_const<
   290             typename remove_pointer<P>::type
   291         >::type
   292     >
   293 {
   294 };
   295 
   296 
   297 template<class P>
   298 struct pointer_reference
   299   : mpl::if_<
   300         is_same<P, typename remove_pointer<P>::type>
   301       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
   302       , typename remove_pointer<P>::type&
   303     >
   304 {
   305 };
   306 
   307 template <class T>
   308 struct pointer_iterator_traits
   309 {
   310     typedef T pointer;
   311     typedef std::random_access_iterator_tag iterator_category;
   312     typedef std::ptrdiff_t difference_type;
   313 
   314     typedef typename pointer_value_type<T>::type value_type;
   315     typedef typename pointer_reference<T>::type reference;
   316 };
   317 
   318 #   endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
   319 
   320 // We'll sort iterator types into one of these classifications, from which we
   321 // can determine the difference_type, pointer, reference, and value_type
   322 template <class Iterator>
   323 struct standard_iterator_traits
   324 {
   325     typedef typename Iterator::difference_type difference_type;
   326     typedef typename Iterator::value_type value_type;
   327     typedef typename Iterator::pointer pointer;
   328     typedef typename Iterator::reference reference;
   329     typedef typename Iterator::iterator_category iterator_category;
   330 };
   331 
   332 template <class Iterator>
   333 struct msvc_stdlib_mutable_traits
   334     : std::iterator_traits<Iterator>
   335 {
   336     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
   337     typedef typename std::iterator_traits<Iterator>::value_type* pointer;
   338     typedef typename std::iterator_traits<Iterator>::value_type& reference;
   339 };
   340 
   341 template <class Iterator>
   342 struct msvc_stdlib_const_traits
   343     : std::iterator_traits<Iterator>
   344 {
   345     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
   346     typedef const typename std::iterator_traits<Iterator>::value_type* pointer;
   347     typedef const typename std::iterator_traits<Iterator>::value_type& reference;
   348 };
   349 
   350 #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
   351 template <class Iterator>
   352 struct is_bad_output_iterator
   353     : is_base_and_derived<
   354         std::iterator<std::output_iterator_tag,void,void,void,void>
   355         , Iterator>
   356 {
   357 };
   358 
   359 struct bad_output_iterator_traits
   360 {
   361     typedef void value_type;
   362     typedef void difference_type;
   363     typedef std::output_iterator_tag iterator_category;
   364     typedef void pointer;
   365     typedef void reference;
   366 };
   367 #   endif
   368 
   369 // If we're looking at an MSVC6 (old Dinkumware) ``standard''
   370 // iterator, this will generate an appropriate traits class. 
   371 template <class Iterator>
   372 struct msvc_stdlib_iterator_traits
   373     : mpl::if_<
   374        is_mutable_iterator<Iterator>
   375        , msvc_stdlib_mutable_traits<Iterator>
   376        , msvc_stdlib_const_traits<Iterator>
   377       >::type
   378 {};
   379 
   380 template <class Iterator>
   381 struct non_pointer_iterator_traits
   382     : mpl::if_<
   383         // if the iterator contains all the right nested types...
   384         is_full_iterator_traits<Iterator>
   385         // Use a standard iterator_traits implementation
   386         , standard_iterator_traits<Iterator>
   387 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
   388         // Check for STLPort 4.0 broken _Iterator_category type
   389         , mpl::if_<
   390              is_stlport_40_debug_iterator<Iterator>
   391              , stlport_40_debug_iterator_traits<Iterator>
   392 #   endif
   393         // Otherwise, assume it's a Dinkum iterator
   394         , msvc_stdlib_iterator_traits<Iterator>
   395 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
   396         >::type
   397 #   endif 
   398     >::type
   399 {
   400 };
   401 
   402 template <class Iterator>
   403 struct iterator_traits_aux
   404     : mpl::if_<
   405         is_pointer<Iterator>
   406         , pointer_iterator_traits<Iterator>
   407         , non_pointer_iterator_traits<Iterator>
   408     >::type
   409 {
   410 };
   411 
   412 template <class Iterator>
   413 struct iterator_traits
   414 {
   415     // Explicit forwarding from base class needed to keep MSVC6 happy
   416     // under some circumstances.
   417  private:
   418 #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
   419     typedef 
   420     typename mpl::if_<
   421         is_bad_output_iterator<Iterator>
   422         , bad_output_iterator_traits
   423         , iterator_traits_aux<Iterator>
   424     >::type base;
   425 #   else
   426     typedef iterator_traits_aux<Iterator> base;
   427 #   endif
   428  public:
   429     typedef typename base::value_type value_type;
   430     typedef typename base::pointer pointer;
   431     typedef typename base::reference reference;
   432     typedef typename base::difference_type difference_type;
   433     typedef typename base::iterator_category iterator_category;
   434 };
   435 
   436 // This specialization cuts off ETI (Early Template Instantiation) for MSVC.
   437 template <> struct iterator_traits<int>
   438 {
   439     typedef int value_type;
   440     typedef int pointer;
   441     typedef int reference;
   442     typedef int difference_type;
   443     typedef int iterator_category;
   444 };
   445 
   446 }} // namespace boost::detail
   447 
   448 #  endif // workarounds
   449 
   450 namespace boost { namespace detail {
   451 
   452 namespace iterator_traits_
   453 {
   454   template <class Iterator, class Difference>
   455   struct distance_select
   456   {
   457       static Difference execute(Iterator i1, const Iterator i2, ...)
   458       {
   459           Difference result = 0;
   460           while (i1 != i2)
   461           {
   462               ++i1;
   463               ++result;
   464           }
   465           return result;
   466       }
   467 
   468       static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)
   469       {
   470           return i2 - i1;
   471       }
   472   };
   473 } // namespace boost::detail::iterator_traits_
   474 
   475 template <class Iterator>
   476 inline typename iterator_traits<Iterator>::difference_type
   477 distance(Iterator first, Iterator last)
   478 {
   479     typedef typename iterator_traits<Iterator>::difference_type diff_t;
   480     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
   481     
   482     return iterator_traits_::distance_select<Iterator,diff_t>::execute(
   483         first, last, (iterator_category*)0);
   484 }
   485 
   486 }}
   487 
   488 # endif
   489 
   490 
   491 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
   492 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
   493 
   494 #endif // ITERATOR_DWA122600_HPP_