blob: 388a89b2dee5c13a2e044894633669b4f0e44fa8 [file] [log] [blame]
Jeff Thompsona28eed82013-08-22 16:21:10 -07001// (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// ndnboost::detail::iterator_traits_. Some progress made on fixes
28// for Intel compiler. (David Abrahams)
Jeff Thompson3d613fd2013-10-15 15:39:04 -070029// 02 Mar 2001 - Changed NDNBOOST_MSVC to NDNBOOST_MSVC_STD_ITERATOR in a few
Jeff Thompsona28eed82013-08-22 16:21:10 -070030// 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// ndnboost::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
Jeff Thompson2491bd62013-10-15 17:10:24 -070050#ifndef ITERATOR_NDNBOOST_DWA122600_HPP_
51# define ITERATOR_NDNBOOST_DWA122600_HPP_
Jeff Thompsona28eed82013-08-22 16:21:10 -070052
53# include <ndnboost/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)
Jeff Thompson3d613fd2013-10-15 15:39:04 -070066# define NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
Jeff Thompsona28eed82013-08-22 16:21:10 -070067# endif
68
Jeff Thompson3d613fd2013-10-15 15:39:04 -070069# define NDNBOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -070070
71# endif // STLPort <= 4.1b4 && no partial specialization
72
Jeff Thompson3d613fd2013-10-15 15:39:04 -070073# if !defined(NDNBOOST_NO_STD_ITERATOR_TRAITS) \
74 && !defined(NDNBOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
75 && !defined(NDNBOOST_MSVC_STD_ITERATOR)
Jeff Thompsona28eed82013-08-22 16:21:10 -070076
77namespace ndnboost { namespace detail {
78
79// Define a new template so it can be specialized
80template <class Iterator>
81struct iterator_traits
82 : std::iterator_traits<Iterator>
83{};
84using std::distance;
85
86}} // namespace ndnboost::detail
87
88# else
89
Jeff Thompson3d613fd2013-10-15 15:39:04 -070090# if !defined(NDNBOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
91 && !defined(NDNBOOST_MSVC_STD_ITERATOR)
Jeff Thompsona28eed82013-08-22 16:21:10 -070092
Jeff Thompson3d613fd2013-10-15 15:39:04 -070093// This is the case where everything conforms except NDNBOOST_NO_STD_ITERATOR_TRAITS
Jeff Thompsona28eed82013-08-22 16:21:10 -070094
95namespace ndnboost { 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!
100template <class Iterator>
101struct 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
110template <class T>
111struct 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
120template <class T>
121struct 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 ndnboost::detail
131
132# else
133
134# include <ndnboost/type_traits/remove_const.hpp>
135# include <ndnboost/type_traits/detail/yes_no_type.hpp>
136# include <ndnboost/type_traits/is_pointer.hpp>
137
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700138# ifdef NDNBOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700139# include <ndnboost/type_traits/is_same.hpp>
140# include <ndnboost/type_traits/remove_pointer.hpp>
141# endif
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700142# ifdef NDNBOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700143# include <ndnboost/type_traits/is_base_and_derived.hpp>
144# endif
145
146# include <ndnboost/mpl/if.hpp>
147# include <ndnboost/mpl/has_xxx.hpp>
148# include <cstddef>
149
150// should be the last #include
151# include "ndnboost/type_traits/detail/bool_trait_def.hpp"
152
153namespace ndnboost { namespace detail {
154
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700155NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
156NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
157NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
158NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
159NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
Jeff Thompsona28eed82013-08-22 16:21:10 -0700160
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.
172template <class T>
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700173type_traits::yes_type is_mutable_iterator_helper(T const*, NDNBOOST_DEDUCED_TYPENAME T::value_type*);
Jeff Thompsona28eed82013-08-22 16:21:10 -0700174
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.
178template <class T> T* mutable_iterator_lvalue_helper(T& x);
179int mutable_iterator_lvalue_helper(...);
180
181
182// This one detects output iterators such as ostream_iterator which
183// return references to themselves.
184template <class T>
185type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
186
187type_traits::no_type is_mutable_iterator_helper(...);
188
189template <class T>
190struct is_mutable_iterator_impl
191{
192 static T t;
193
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700194 NDNBOOST_STATIC_CONSTANT(
Jeff Thompsona28eed82013-08-22 16:21:10 -0700195 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700204NDNBOOST_TT_AUX_BOOL_TRAIT_DEF1(
Jeff Thompsona28eed82013-08-22 16:21:10 -0700205 is_mutable_iterator,T,::ndnboost::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.
213template <class T>
214struct 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700225NDNBOOST_TT_AUX_BOOL_TRAIT_DEF1(
Jeff Thompsona28eed82013-08-22 16:21:10 -0700226 is_full_iterator_traits,T,::ndnboost::detail::is_full_iterator_traits_impl<T>::value)
227
228
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700229# ifdef NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
230NDNBOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
Jeff Thompsona28eed82013-08-22 16:21:10 -0700231
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.
237template <class T>
238struct 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700249NDNBOOST_TT_AUX_BOOL_TRAIT_DEF1(
Jeff Thompsona28eed82013-08-22 16:21:10 -0700250 is_stlport_40_debug_iterator,T,::ndnboost::detail::is_stlport_40_debug_iterator_impl<T>::value)
251
252template <class T>
253struct 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};
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700261# endif // NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
Jeff Thompsona28eed82013-08-22 16:21:10 -0700262
263template <class T> struct pointer_iterator_traits;
264
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700265# ifndef NDNBOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700266template <class T>
267struct 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700282template<class P> class please_invoke_NDNBOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
Jeff Thompsona28eed82013-08-22 16:21:10 -0700283
284template<class P>
285struct pointer_value_type
286 : mpl::if_<
287 is_same<P, typename remove_pointer<P>::type>
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700288 , please_invoke_NDNBOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
Jeff Thompsona28eed82013-08-22 16:21:10 -0700289 , typename remove_const<
290 typename remove_pointer<P>::type
291 >::type
292 >
293{
294};
295
296
297template<class P>
298struct pointer_reference
299 : mpl::if_<
300 is_same<P, typename remove_pointer<P>::type>
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700301 , please_invoke_NDNBOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
Jeff Thompsona28eed82013-08-22 16:21:10 -0700302 , typename remove_pointer<P>::type&
303 >
304{
305};
306
307template <class T>
308struct 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700318# endif // NDNBOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700319
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
322template <class Iterator>
323struct 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
332template <class Iterator>
333struct 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
341template <class Iterator>
342struct 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700350# ifdef NDNBOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700351template <class Iterator>
352struct 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
359struct 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.
371template <class Iterator>
372struct 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
380template <class Iterator>
381struct 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>
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700387# ifdef NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
Jeff Thompsona28eed82013-08-22 16:21:10 -0700388 // 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>
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700395# ifdef NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
Jeff Thompsona28eed82013-08-22 16:21:10 -0700396 >::type
397# endif
398 >::type
399{
400};
401
402template <class Iterator>
403struct 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
412template <class Iterator>
413struct iterator_traits
414{
415 // Explicit forwarding from base class needed to keep MSVC6 happy
416 // under some circumstances.
417 private:
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700418# ifdef NDNBOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700419 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.
437template <> 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 ndnboost::detail
447
448# endif // workarounds
449
450namespace ndnboost { namespace detail {
451
452namespace 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 ndnboost::detail::iterator_traits_
474
475template <class Iterator>
476inline typename iterator_traits<Iterator>::difference_type
477distance(Iterator first, Iterator last)
478{
479 typedef typename iterator_traits<Iterator>::difference_type diff_t;
480 typedef typename ::ndnboost::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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700491# undef NDNBOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
492# undef NDNBOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
Jeff Thompsona28eed82013-08-22 16:21:10 -0700493
Jeff Thompson2491bd62013-10-15 17:10:24 -0700494#endif // ITERATOR_NDNBOOST_DWA122600_HPP_