1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/detail/iterator.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,494 @@
1.4 +// (C) Copyright David Abrahams 2002.
1.5 +// Distributed under the Boost Software License, Version 1.0. (See
1.6 +// accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +
1.9 +// Boost versions of
1.10 +//
1.11 +// std::iterator_traits<>::iterator_category
1.12 +// std::iterator_traits<>::difference_type
1.13 +// std::distance()
1.14 +//
1.15 +// ...for all compilers and iterators
1.16 +//
1.17 +// Additionally, if X is a pointer
1.18 +// std::iterator_traits<X>::pointer
1.19 +
1.20 +// Otherwise, if partial specialization is supported or X is not a pointer
1.21 +// std::iterator_traits<X>::value_type
1.22 +// std::iterator_traits<X>::pointer
1.23 +// std::iterator_traits<X>::reference
1.24 +//
1.25 +// See http://www.boost.org for most recent version including documentation.
1.26 +
1.27 +// Revision History
1.28 +// 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)
1.29 +// 03 Mar 2001 - Put all implementation into namespace
1.30 +// boost::detail::iterator_traits_. Some progress made on fixes
1.31 +// for Intel compiler. (David Abrahams)
1.32 +// 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few
1.33 +// places. (Jeremy Siek)
1.34 +// 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and
1.35 +// no_type from type_traits.hpp; stopped trying to remove_cv
1.36 +// before detecting is_pointer, in honor of the new type_traits
1.37 +// semantics. (David Abrahams)
1.38 +// 13 Feb 2001 - Make it work with nearly all standard-conforming iterators
1.39 +// under raw VC6. The one category remaining which will fail is
1.40 +// that of iterators derived from std::iterator but not
1.41 +// boost::iterator and which redefine difference_type.
1.42 +// 11 Feb 2001 - Clean away code which can never be used (David Abrahams)
1.43 +// 09 Feb 2001 - Always have a definition for each traits member, even if it
1.44 +// can't be properly deduced. These will be incomplete types in
1.45 +// some cases (undefined<void>), but it helps suppress MSVC errors
1.46 +// elsewhere (David Abrahams)
1.47 +// 07 Feb 2001 - Support for more of the traits members where possible, making
1.48 +// this useful as a replacement for std::iterator_traits<T> when
1.49 +// used as a default template parameter.
1.50 +// 06 Feb 2001 - Removed useless #includes of standard library headers
1.51 +// (David Abrahams)
1.52 +
1.53 +#ifndef ITERATOR_DWA122600_HPP_
1.54 +# define ITERATOR_DWA122600_HPP_
1.55 +
1.56 +# include <boost/config.hpp>
1.57 +# include <iterator>
1.58 +
1.59 +// STLPort 4.0 and betas have a bug when debugging is enabled and there is no
1.60 +// partial specialization: instead of an iterator_category typedef, the standard
1.61 +// container iterators have _Iterator_category.
1.62 +//
1.63 +// Also, whether debugging is enabled or not, there is a broken specialization
1.64 +// of std::iterator<output_iterator_tag,void,void,void,void> which has no
1.65 +// typedefs but iterator_category.
1.66 +# if defined(__SGI_STL_PORT)
1.67 +
1.68 +# if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)
1.69 +# define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.70 +# endif
1.71 +
1.72 +# define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
1.73 +
1.74 +# endif // STLPort <= 4.1b4 && no partial specialization
1.75 +
1.76 +# if !defined(BOOST_NO_STD_ITERATOR_TRAITS) \
1.77 + && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
1.78 + && !defined(BOOST_MSVC_STD_ITERATOR)
1.79 +
1.80 +namespace boost { namespace detail {
1.81 +
1.82 +// Define a new template so it can be specialized
1.83 +template <class Iterator>
1.84 +struct iterator_traits
1.85 + : std::iterator_traits<Iterator>
1.86 +{};
1.87 +using std::distance;
1.88 +
1.89 +}} // namespace boost::detail
1.90 +
1.91 +# else
1.92 +
1.93 +# if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
1.94 + && !defined(BOOST_MSVC_STD_ITERATOR)
1.95 +
1.96 +// This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS
1.97 +
1.98 +namespace boost { namespace detail {
1.99 +
1.100 +// Rogue Wave Standard Library fools itself into thinking partial
1.101 +// specialization is missing on some platforms (e.g. Sun), so fails to
1.102 +// supply iterator_traits!
1.103 +template <class Iterator>
1.104 +struct iterator_traits
1.105 +{
1.106 + typedef typename Iterator::value_type value_type;
1.107 + typedef typename Iterator::reference reference;
1.108 + typedef typename Iterator::pointer pointer;
1.109 + typedef typename Iterator::difference_type difference_type;
1.110 + typedef typename Iterator::iterator_category iterator_category;
1.111 +};
1.112 +
1.113 +template <class T>
1.114 +struct iterator_traits<T*>
1.115 +{
1.116 + typedef T value_type;
1.117 + typedef T& reference;
1.118 + typedef T* pointer;
1.119 + typedef std::ptrdiff_t difference_type;
1.120 + typedef std::random_access_iterator_tag iterator_category;
1.121 +};
1.122 +
1.123 +template <class T>
1.124 +struct iterator_traits<T const*>
1.125 +{
1.126 + typedef T value_type;
1.127 + typedef T const& reference;
1.128 + typedef T const* pointer;
1.129 + typedef std::ptrdiff_t difference_type;
1.130 + typedef std::random_access_iterator_tag iterator_category;
1.131 +};
1.132 +
1.133 +}} // namespace boost::detail
1.134 +
1.135 +# else
1.136 +
1.137 +# include <boost/type_traits/remove_const.hpp>
1.138 +# include <boost/type_traits/detail/yes_no_type.hpp>
1.139 +# include <boost/type_traits/is_pointer.hpp>
1.140 +
1.141 +# ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.142 +# include <boost/type_traits/is_same.hpp>
1.143 +# include <boost/type_traits/remove_pointer.hpp>
1.144 +# endif
1.145 +# ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
1.146 +# include <boost/type_traits/is_base_and_derived.hpp>
1.147 +# endif
1.148 +
1.149 +# include <boost/mpl/if.hpp>
1.150 +# include <boost/mpl/has_xxx.hpp>
1.151 +# include <cstddef>
1.152 +
1.153 +// should be the last #include
1.154 +# include "boost/type_traits/detail/bool_trait_def.hpp"
1.155 +
1.156 +namespace boost { namespace detail {
1.157 +
1.158 +BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
1.159 +BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
1.160 +BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
1.161 +BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
1.162 +BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
1.163 +
1.164 +// is_mutable_iterator --
1.165 +//
1.166 +// A metafunction returning true iff T is a mutable iterator type
1.167 +// with a nested value_type. Will only work portably with iterators
1.168 +// whose operator* returns a reference, but that seems to be OK for
1.169 +// the iterators supplied by Dinkumware. Some input iterators may
1.170 +// compile-time if they arrive here, and if the compiler is strict
1.171 +// about not taking the address of an rvalue.
1.172 +
1.173 +// This one detects ordinary mutable iterators - the result of
1.174 +// operator* is convertible to the value_type.
1.175 +template <class T>
1.176 +type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);
1.177 +
1.178 +// Since you can't take the address of an rvalue, the guts of
1.179 +// is_mutable_iterator_impl will fail if we use &*t directly. This
1.180 +// makes sure we can still work with non-lvalue iterators.
1.181 +template <class T> T* mutable_iterator_lvalue_helper(T& x);
1.182 +int mutable_iterator_lvalue_helper(...);
1.183 +
1.184 +
1.185 +// This one detects output iterators such as ostream_iterator which
1.186 +// return references to themselves.
1.187 +template <class T>
1.188 +type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
1.189 +
1.190 +type_traits::no_type is_mutable_iterator_helper(...);
1.191 +
1.192 +template <class T>
1.193 +struct is_mutable_iterator_impl
1.194 +{
1.195 + static T t;
1.196 +
1.197 + BOOST_STATIC_CONSTANT(
1.198 + bool, value = sizeof(
1.199 + detail::is_mutable_iterator_helper(
1.200 + (T*)0
1.201 + , mutable_iterator_lvalue_helper(*t) // like &*t
1.202 + ))
1.203 + == sizeof(type_traits::yes_type)
1.204 + );
1.205 +};
1.206 +
1.207 +BOOST_TT_AUX_BOOL_TRAIT_DEF1(
1.208 + is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)
1.209 +
1.210 +
1.211 +// is_full_iterator_traits --
1.212 +//
1.213 +// A metafunction returning true iff T has all the requisite nested
1.214 +// types to satisfy the requirements for a fully-conforming
1.215 +// iterator_traits implementation.
1.216 +template <class T>
1.217 +struct is_full_iterator_traits_impl
1.218 +{
1.219 + enum { value =
1.220 + has_value_type<T>::value
1.221 + & has_reference<T>::value
1.222 + & has_pointer<T>::value
1.223 + & has_difference_type<T>::value
1.224 + & has_iterator_category<T>::value
1.225 + };
1.226 +};
1.227 +
1.228 +BOOST_TT_AUX_BOOL_TRAIT_DEF1(
1.229 + is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)
1.230 +
1.231 +
1.232 +# ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.233 +BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
1.234 +
1.235 +// is_stlport_40_debug_iterator --
1.236 +//
1.237 +// A metafunction returning true iff T has all the requisite nested
1.238 +// types to satisfy the requirements of an STLPort 4.0 debug iterator
1.239 +// iterator_traits implementation.
1.240 +template <class T>
1.241 +struct is_stlport_40_debug_iterator_impl
1.242 +{
1.243 + enum { value =
1.244 + has_value_type<T>::value
1.245 + & has_reference<T>::value
1.246 + & has_pointer<T>::value
1.247 + & has_difference_type<T>::value
1.248 + & has__Iterator_category<T>::value
1.249 + };
1.250 +};
1.251 +
1.252 +BOOST_TT_AUX_BOOL_TRAIT_DEF1(
1.253 + is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
1.254 +
1.255 +template <class T>
1.256 +struct stlport_40_debug_iterator_traits
1.257 +{
1.258 + typedef typename T::value_type value_type;
1.259 + typedef typename T::reference reference;
1.260 + typedef typename T::pointer pointer;
1.261 + typedef typename T::difference_type difference_type;
1.262 + typedef typename T::_Iterator_category iterator_category;
1.263 +};
1.264 +# endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.265 +
1.266 +template <class T> struct pointer_iterator_traits;
1.267 +
1.268 +# ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.269 +template <class T>
1.270 +struct pointer_iterator_traits<T*>
1.271 +{
1.272 + typedef typename remove_const<T>::type value_type;
1.273 + typedef T* pointer;
1.274 + typedef T& reference;
1.275 + typedef std::random_access_iterator_tag iterator_category;
1.276 + typedef std::ptrdiff_t difference_type;
1.277 +};
1.278 +# else
1.279 +
1.280 +// In case of no template partial specialization, and if T is a
1.281 +// pointer, iterator_traits<T>::value_type can still be computed. For
1.282 +// some basic types, remove_pointer is manually defined in
1.283 +// type_traits/broken_compiler_spec.hpp. For others, do it yourself.
1.284 +
1.285 +template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
1.286 +
1.287 +template<class P>
1.288 +struct pointer_value_type
1.289 + : mpl::if_<
1.290 + is_same<P, typename remove_pointer<P>::type>
1.291 + , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
1.292 + , typename remove_const<
1.293 + typename remove_pointer<P>::type
1.294 + >::type
1.295 + >
1.296 +{
1.297 +};
1.298 +
1.299 +
1.300 +template<class P>
1.301 +struct pointer_reference
1.302 + : mpl::if_<
1.303 + is_same<P, typename remove_pointer<P>::type>
1.304 + , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
1.305 + , typename remove_pointer<P>::type&
1.306 + >
1.307 +{
1.308 +};
1.309 +
1.310 +template <class T>
1.311 +struct pointer_iterator_traits
1.312 +{
1.313 + typedef T pointer;
1.314 + typedef std::random_access_iterator_tag iterator_category;
1.315 + typedef std::ptrdiff_t difference_type;
1.316 +
1.317 + typedef typename pointer_value_type<T>::type value_type;
1.318 + typedef typename pointer_reference<T>::type reference;
1.319 +};
1.320 +
1.321 +# endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.322 +
1.323 +// We'll sort iterator types into one of these classifications, from which we
1.324 +// can determine the difference_type, pointer, reference, and value_type
1.325 +template <class Iterator>
1.326 +struct standard_iterator_traits
1.327 +{
1.328 + typedef typename Iterator::difference_type difference_type;
1.329 + typedef typename Iterator::value_type value_type;
1.330 + typedef typename Iterator::pointer pointer;
1.331 + typedef typename Iterator::reference reference;
1.332 + typedef typename Iterator::iterator_category iterator_category;
1.333 +};
1.334 +
1.335 +template <class Iterator>
1.336 +struct msvc_stdlib_mutable_traits
1.337 + : std::iterator_traits<Iterator>
1.338 +{
1.339 + typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
1.340 + typedef typename std::iterator_traits<Iterator>::value_type* pointer;
1.341 + typedef typename std::iterator_traits<Iterator>::value_type& reference;
1.342 +};
1.343 +
1.344 +template <class Iterator>
1.345 +struct msvc_stdlib_const_traits
1.346 + : std::iterator_traits<Iterator>
1.347 +{
1.348 + typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
1.349 + typedef const typename std::iterator_traits<Iterator>::value_type* pointer;
1.350 + typedef const typename std::iterator_traits<Iterator>::value_type& reference;
1.351 +};
1.352 +
1.353 +# ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
1.354 +template <class Iterator>
1.355 +struct is_bad_output_iterator
1.356 + : is_base_and_derived<
1.357 + std::iterator<std::output_iterator_tag,void,void,void,void>
1.358 + , Iterator>
1.359 +{
1.360 +};
1.361 +
1.362 +struct bad_output_iterator_traits
1.363 +{
1.364 + typedef void value_type;
1.365 + typedef void difference_type;
1.366 + typedef std::output_iterator_tag iterator_category;
1.367 + typedef void pointer;
1.368 + typedef void reference;
1.369 +};
1.370 +# endif
1.371 +
1.372 +// If we're looking at an MSVC6 (old Dinkumware) ``standard''
1.373 +// iterator, this will generate an appropriate traits class.
1.374 +template <class Iterator>
1.375 +struct msvc_stdlib_iterator_traits
1.376 + : mpl::if_<
1.377 + is_mutable_iterator<Iterator>
1.378 + , msvc_stdlib_mutable_traits<Iterator>
1.379 + , msvc_stdlib_const_traits<Iterator>
1.380 + >::type
1.381 +{};
1.382 +
1.383 +template <class Iterator>
1.384 +struct non_pointer_iterator_traits
1.385 + : mpl::if_<
1.386 + // if the iterator contains all the right nested types...
1.387 + is_full_iterator_traits<Iterator>
1.388 + // Use a standard iterator_traits implementation
1.389 + , standard_iterator_traits<Iterator>
1.390 +# ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.391 + // Check for STLPort 4.0 broken _Iterator_category type
1.392 + , mpl::if_<
1.393 + is_stlport_40_debug_iterator<Iterator>
1.394 + , stlport_40_debug_iterator_traits<Iterator>
1.395 +# endif
1.396 + // Otherwise, assume it's a Dinkum iterator
1.397 + , msvc_stdlib_iterator_traits<Iterator>
1.398 +# ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.399 + >::type
1.400 +# endif
1.401 + >::type
1.402 +{
1.403 +};
1.404 +
1.405 +template <class Iterator>
1.406 +struct iterator_traits_aux
1.407 + : mpl::if_<
1.408 + is_pointer<Iterator>
1.409 + , pointer_iterator_traits<Iterator>
1.410 + , non_pointer_iterator_traits<Iterator>
1.411 + >::type
1.412 +{
1.413 +};
1.414 +
1.415 +template <class Iterator>
1.416 +struct iterator_traits
1.417 +{
1.418 + // Explicit forwarding from base class needed to keep MSVC6 happy
1.419 + // under some circumstances.
1.420 + private:
1.421 +# ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
1.422 + typedef
1.423 + typename mpl::if_<
1.424 + is_bad_output_iterator<Iterator>
1.425 + , bad_output_iterator_traits
1.426 + , iterator_traits_aux<Iterator>
1.427 + >::type base;
1.428 +# else
1.429 + typedef iterator_traits_aux<Iterator> base;
1.430 +# endif
1.431 + public:
1.432 + typedef typename base::value_type value_type;
1.433 + typedef typename base::pointer pointer;
1.434 + typedef typename base::reference reference;
1.435 + typedef typename base::difference_type difference_type;
1.436 + typedef typename base::iterator_category iterator_category;
1.437 +};
1.438 +
1.439 +// This specialization cuts off ETI (Early Template Instantiation) for MSVC.
1.440 +template <> struct iterator_traits<int>
1.441 +{
1.442 + typedef int value_type;
1.443 + typedef int pointer;
1.444 + typedef int reference;
1.445 + typedef int difference_type;
1.446 + typedef int iterator_category;
1.447 +};
1.448 +
1.449 +}} // namespace boost::detail
1.450 +
1.451 +# endif // workarounds
1.452 +
1.453 +namespace boost { namespace detail {
1.454 +
1.455 +namespace iterator_traits_
1.456 +{
1.457 + template <class Iterator, class Difference>
1.458 + struct distance_select
1.459 + {
1.460 + static Difference execute(Iterator i1, const Iterator i2, ...)
1.461 + {
1.462 + Difference result = 0;
1.463 + while (i1 != i2)
1.464 + {
1.465 + ++i1;
1.466 + ++result;
1.467 + }
1.468 + return result;
1.469 + }
1.470 +
1.471 + static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)
1.472 + {
1.473 + return i2 - i1;
1.474 + }
1.475 + };
1.476 +} // namespace boost::detail::iterator_traits_
1.477 +
1.478 +template <class Iterator>
1.479 +inline typename iterator_traits<Iterator>::difference_type
1.480 +distance(Iterator first, Iterator last)
1.481 +{
1.482 + typedef typename iterator_traits<Iterator>::difference_type diff_t;
1.483 + typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
1.484 +
1.485 + return iterator_traits_::distance_select<Iterator,diff_t>::execute(
1.486 + first, last, (iterator_category*)0);
1.487 +}
1.488 +
1.489 +}}
1.490 +
1.491 +# endif
1.492 +
1.493 +
1.494 +# undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
1.495 +# undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
1.496 +
1.497 +#endif // ITERATOR_DWA122600_HPP_