Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / detail / iterator.hpp
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_