• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // (C) Copyright Jeremy Siek 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 #ifndef BOOST_ITERATOR_ARCHETYPES_HPP
7 #define BOOST_ITERATOR_ARCHETYPES_HPP
8 
9 #include <boost/iterator/iterator_categories.hpp>
10 #include <boost/operators.hpp>
11 #include <boost/static_assert.hpp>
12 
13 #include <boost/iterator/detail/facade_iterator_category.hpp>
14 
15 #include <boost/type_traits/is_const.hpp>
16 #include <boost/type_traits/add_const.hpp>
17 #include <boost/type_traits/remove_const.hpp>
18 #include <boost/type_traits/remove_cv.hpp>
19 
20 #include <boost/concept_archetype.hpp>
21 
22 #include <boost/mpl/bitand.hpp>
23 #include <boost/mpl/int.hpp>
24 #include <boost/mpl/equal_to.hpp>
25 #include <boost/mpl/if.hpp>
26 #include <boost/mpl/eval_if.hpp>
27 #include <boost/mpl/and.hpp>
28 #include <boost/mpl/identity.hpp>
29 
30 #include <cstddef>
31 
32 namespace boost {
33 namespace iterators {
34 
35 template <class Value, class AccessCategory>
36 struct access_archetype;
37 
38 template <class Derived, class Value, class AccessCategory, class TraversalCategory>
39 struct traversal_archetype;
40 
41 namespace archetypes
42 {
43   enum {
44       readable_iterator_bit = 1
45     , writable_iterator_bit = 2
46     , swappable_iterator_bit = 4
47     , lvalue_iterator_bit = 8
48   };
49 
50   // Not quite tags, since dispatching wouldn't work.
51   typedef mpl::int_<readable_iterator_bit>::type readable_iterator_t;
52   typedef mpl::int_<writable_iterator_bit>::type writable_iterator_t;
53 
54   typedef mpl::int_<
55       (readable_iterator_bit|writable_iterator_bit)
56           >::type readable_writable_iterator_t;
57 
58   typedef mpl::int_<
59       (readable_iterator_bit|lvalue_iterator_bit)
60           >::type readable_lvalue_iterator_t;
61 
62   typedef mpl::int_<
63       (lvalue_iterator_bit|writable_iterator_bit)
64           >::type writable_lvalue_iterator_t;
65 
66   typedef mpl::int_<swappable_iterator_bit>::type swappable_iterator_t;
67   typedef mpl::int_<lvalue_iterator_bit>::type lvalue_iterator_t;
68 
69   template <class Derived, class Base>
70   struct has_access
71     : mpl::equal_to<
72           mpl::bitand_<Derived,Base>
73         , Base
74       >
75   {};
76 }
77 
78 namespace detail
79 {
80   template <class T>
81   struct assign_proxy
82   {
operator =boost::iterators::detail::assign_proxy83       assign_proxy& operator=(T) { return *this; }
84   };
85 
86   template <class T>
87   struct read_proxy
88   {
operator Tboost::iterators::detail::read_proxy89       operator T() { return static_object<T>::get(); }
90   };
91 
92   template <class T>
93   struct read_write_proxy
94     : read_proxy<T> // Use to inherit from assign_proxy, but that doesn't work. -JGS
95   {
operator =boost::iterators::detail::read_write_proxy96       read_write_proxy& operator=(T) { return *this; }
97   };
98 
99   template <class T>
100   struct arrow_proxy
101   {
operator ->boost::iterators::detail::arrow_proxy102       T const* operator->() const { return 0; }
103   };
104 
105   struct no_operator_brackets {};
106 
107   template <class ValueType>
108   struct readable_operator_brackets
109   {
operator []boost::iterators::detail::readable_operator_brackets110       read_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_proxy<ValueType>(); }
111   };
112 
113   template <class ValueType>
114   struct writable_operator_brackets
115   {
operator []boost::iterators::detail::writable_operator_brackets116       read_write_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_write_proxy<ValueType>(); }
117   };
118 
119   template <class Value, class AccessCategory, class TraversalCategory>
120   struct operator_brackets
121     : mpl::eval_if<
122           is_convertible<TraversalCategory, random_access_traversal_tag>
123         , mpl::eval_if<
124               archetypes::has_access<
125                   AccessCategory
126                 , archetypes::writable_iterator_t
127               >
128             , mpl::identity<writable_operator_brackets<Value> >
129             , mpl::if_<
130                   archetypes::has_access<
131                       AccessCategory
132                     , archetypes::readable_iterator_t
133                   >
134                 , readable_operator_brackets<Value>
135                 , no_operator_brackets
136               >
137           >
138         , mpl::identity<no_operator_brackets>
139       >::type
140   {};
141 
142   template <class TraversalCategory>
143   struct traversal_archetype_impl
144   {
145       template <class Derived,class Value> struct archetype;
146   };
147 
148   // Constructor argument for those iterators that
149   // are not default constructible
150   struct ctor_arg {};
151 
152   template <class Derived, class Value, class TraversalCategory>
153   struct traversal_archetype_
154     : traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value>
155   {
156       typedef typename
157         traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value>
158       base;
159 
traversal_archetype_boost::iterators::detail::traversal_archetype_160       traversal_archetype_() {}
161 
traversal_archetype_boost::iterators::detail::traversal_archetype_162       traversal_archetype_(ctor_arg arg)
163         : base(arg)
164       {}
165   };
166 
167   template <>
168   struct traversal_archetype_impl<incrementable_traversal_tag>
169   {
170       template<class Derived, class Value>
171       struct archetype
172       {
archetypeboost::iterators::detail::traversal_archetype_impl::archetype173           explicit archetype(ctor_arg) {}
174 
175           struct bogus { }; // This use to be void, but that causes trouble for iterator_facade. Need more research. -JGS
176           typedef bogus difference_type;
177 
operator ++boost::iterators::detail::traversal_archetype_impl::archetype178           Derived& operator++() { return (Derived&)static_object<Derived>::get(); }
operator ++boost::iterators::detail::traversal_archetype_impl::archetype179           Derived  operator++(int) const { return (Derived&)static_object<Derived>::get(); }
180       };
181   };
182 
183   template <>
184   struct traversal_archetype_impl<single_pass_traversal_tag>
185   {
186       template<class Derived, class Value>
187       struct archetype
188         : public equality_comparable< traversal_archetype_<Derived, Value, single_pass_traversal_tag> >,
189           public traversal_archetype_<Derived, Value, incrementable_traversal_tag>
190       {
archetypeboost::iterators::detail::traversal_archetype_impl::archetype191           explicit archetype(ctor_arg arg)
192             : traversal_archetype_<Derived, Value, incrementable_traversal_tag>(arg)
193           {}
194 
195           typedef std::ptrdiff_t difference_type;
196       };
197   };
198 
199   template <class Derived, class Value>
operator ==(traversal_archetype_<Derived,Value,single_pass_traversal_tag> const &,traversal_archetype_<Derived,Value,single_pass_traversal_tag> const &)200   bool operator==(traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&,
201                   traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&) { return true; }
202 
203   template <>
204   struct traversal_archetype_impl<forward_traversal_tag>
205   {
206       template<class Derived, class Value>
207       struct archetype
208         : public traversal_archetype_<Derived, Value, single_pass_traversal_tag>
209       {
archetypeboost::iterators::detail::traversal_archetype_impl::archetype210           archetype()
211             : traversal_archetype_<Derived, Value, single_pass_traversal_tag>(ctor_arg())
212           {}
213       };
214   };
215 
216   template <>
217   struct traversal_archetype_impl<bidirectional_traversal_tag>
218   {
219       template<class Derived, class Value>
220       struct archetype
221         : public traversal_archetype_<Derived, Value, forward_traversal_tag>
222       {
operator --boost::iterators::detail::traversal_archetype_impl::archetype223           Derived& operator--() { return static_object<Derived>::get(); }
operator --boost::iterators::detail::traversal_archetype_impl::archetype224           Derived  operator--(int) const { return static_object<Derived>::get(); }
225       };
226   };
227 
228   template <>
229   struct traversal_archetype_impl<random_access_traversal_tag>
230   {
231       template<class Derived, class Value>
232       struct archetype
233         : public traversal_archetype_<Derived, Value, bidirectional_traversal_tag>
234       {
operator +=boost::iterators::detail::traversal_archetype_impl::archetype235           Derived& operator+=(std::ptrdiff_t) { return static_object<Derived>::get(); }
operator -=boost::iterators::detail::traversal_archetype_impl::archetype236           Derived& operator-=(std::ptrdiff_t) { return static_object<Derived>::get(); }
237       };
238   };
239 
240   template <class Derived, class Value>
operator +(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,std::ptrdiff_t)241   Derived& operator+(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
242                      std::ptrdiff_t) { return static_object<Derived>::get(); }
243 
244   template <class Derived, class Value>
operator +(std::ptrdiff_t,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)245   Derived& operator+(std::ptrdiff_t,
246                      traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
247       { return static_object<Derived>::get(); }
248 
249   template <class Derived, class Value>
operator -(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,std::ptrdiff_t)250   Derived& operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
251                      std::ptrdiff_t)
252       { return static_object<Derived>::get(); }
253 
254   template <class Derived, class Value>
operator -(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)255   std::ptrdiff_t operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
256                            traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
257       { return 0; }
258 
259   template <class Derived, class Value>
operator <(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)260   bool operator<(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
261                  traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
262       { return true; }
263 
264   template <class Derived, class Value>
operator >(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)265   bool operator>(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
266                  traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
267       { return true; }
268 
269   template <class Derived, class Value>
operator <=(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)270   bool operator<=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
271                  traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
272       { return true; }
273 
274   template <class Derived, class Value>
operator >=(traversal_archetype_<Derived,Value,random_access_traversal_tag> const &,traversal_archetype_<Derived,Value,random_access_traversal_tag> const &)275   bool operator>=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&,
276                  traversal_archetype_<Derived, Value, random_access_traversal_tag> const&)
277       { return true; }
278 
279   struct bogus_type;
280 
281   template <class Value>
282   struct convertible_type
283     : mpl::if_< is_const<Value>,
284                 typename remove_const<Value>::type,
285                 bogus_type >
286   {};
287 
288 } // namespace detail
289 
290 
291 template <class> struct undefined;
292 
293 template <class AccessCategory>
294 struct iterator_access_archetype_impl
295 {
296     template <class Value> struct archetype;
297 };
298 
299 template <class Value, class AccessCategory>
300 struct iterator_access_archetype
301   : iterator_access_archetype_impl<
302         AccessCategory
303     >::template archetype<Value>
304 {
305 };
306 
307 template <>
308 struct iterator_access_archetype_impl<
309     archetypes::readable_iterator_t
310 >
311 {
312     template <class Value>
313     struct archetype
314     {
315         typedef typename remove_cv<Value>::type value_type;
316         typedef Value                           reference;
317         typedef Value*                          pointer;
318 
operator *boost::iterators::iterator_access_archetype_impl::archetype319         value_type operator*() const { return static_object<value_type>::get(); }
320 
operator ->boost::iterators::iterator_access_archetype_impl::archetype321         detail::arrow_proxy<Value> operator->() const { return detail::arrow_proxy<Value>(); }
322     };
323 };
324 
325 template <>
326 struct iterator_access_archetype_impl<
327     archetypes::writable_iterator_t
328 >
329 {
330     template <class Value>
331     struct archetype
332     {
333         BOOST_STATIC_ASSERT(!is_const<Value>::value);
334         typedef void value_type;
335         typedef void reference;
336         typedef void pointer;
337 
operator *boost::iterators::iterator_access_archetype_impl::archetype338         detail::assign_proxy<Value> operator*() const { return detail::assign_proxy<Value>(); }
339     };
340 };
341 
342 template <>
343 struct iterator_access_archetype_impl<
344     archetypes::readable_writable_iterator_t
345 >
346 {
347     template <class Value>
348     struct archetype
349       : public virtual iterator_access_archetype<
350             Value, archetypes::readable_iterator_t
351         >
352     {
353         typedef detail::read_write_proxy<Value>    reference;
354 
operator *boost::iterators::iterator_access_archetype_impl::archetype355         detail::read_write_proxy<Value> operator*() const { return detail::read_write_proxy<Value>(); }
356     };
357 };
358 
359 template <>
360 struct iterator_access_archetype_impl<archetypes::readable_lvalue_iterator_t>
361 {
362     template <class Value>
363     struct archetype
364       : public virtual iterator_access_archetype<
365             Value, archetypes::readable_iterator_t
366         >
367     {
368         typedef Value&    reference;
369 
operator *boost::iterators::iterator_access_archetype_impl::archetype370         Value& operator*() const { return static_object<Value>::get(); }
operator ->boost::iterators::iterator_access_archetype_impl::archetype371         Value* operator->() const { return 0; }
372     };
373 };
374 
375 template <>
376 struct iterator_access_archetype_impl<archetypes::writable_lvalue_iterator_t>
377 {
378     template <class Value>
379     struct archetype
380       : public virtual iterator_access_archetype<
381             Value, archetypes::readable_lvalue_iterator_t
382         >
383     {
384         BOOST_STATIC_ASSERT((!is_const<Value>::value));
385     };
386 };
387 
388 
389 template <class Value, class AccessCategory, class TraversalCategory>
390 struct iterator_archetype;
391 
392 template <class Value, class AccessCategory, class TraversalCategory>
393 struct traversal_archetype_base
394   : detail::operator_brackets<
395         typename remove_cv<Value>::type
396       , AccessCategory
397       , TraversalCategory
398     >
399   , detail::traversal_archetype_<
400         iterator_archetype<Value, AccessCategory, TraversalCategory>
401       , Value
402       , TraversalCategory
403     >
404 {
405 };
406 
407 namespace detail
408 {
409   template <class Value, class AccessCategory, class TraversalCategory>
410   struct iterator_archetype_base
411     : iterator_access_archetype<Value, AccessCategory>
412     , traversal_archetype_base<Value, AccessCategory, TraversalCategory>
413   {
414       typedef iterator_access_archetype<Value, AccessCategory> access;
415 
416       typedef typename detail::facade_iterator_category<
417           TraversalCategory
418         , typename mpl::eval_if<
419               archetypes::has_access<
420                   AccessCategory, archetypes::writable_iterator_t
421               >
422             , remove_const<Value>
423             , add_const<Value>
424           >::type
425         , typename access::reference
426       >::type iterator_category;
427 
428       // Needed for some broken libraries (see below)
429       struct workaround_iterator_base
430       {
431         typedef typename iterator_archetype_base::iterator_category iterator_category;
432         typedef Value value_type;
433         typedef typename traversal_archetype_base<
434               Value, AccessCategory, TraversalCategory
435           >::difference_type difference_type;
436         typedef typename access::pointer pointer;
437         typedef typename access::reference reference;
438       };
439   };
440 }
441 
442 template <class Value, class AccessCategory, class TraversalCategory>
443 struct iterator_archetype
444   : public detail::iterator_archetype_base<Value, AccessCategory, TraversalCategory>
445 
446     // These broken libraries require derivation from std::iterator
447     // (or related magic) in order to handle iter_swap and other
448     // iterator operations
449 # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310)           \
450     || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101))
451   , public detail::iterator_archetype_base<
452         Value, AccessCategory, TraversalCategory
453     >::workaround_iterator_base
454 # endif
455 {
456     // Derivation from std::iterator above caused references to nested
457     // types to be ambiguous, so now we have to redeclare them all
458     // here.
459 # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310)           \
460     || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101))
461 
462     typedef detail::iterator_archetype_base<
463         Value,AccessCategory,TraversalCategory
464     > base;
465 
466     typedef typename base::value_type value_type;
467     typedef typename base::reference reference;
468     typedef typename base::pointer pointer;
469     typedef typename base::difference_type difference_type;
470     typedef typename base::iterator_category iterator_category;
471 # endif
472 
iterator_archetypeboost::iterators::iterator_archetype473     iterator_archetype() { }
iterator_archetypeboost::iterators::iterator_archetype474     iterator_archetype(iterator_archetype const& x)
475       : detail::iterator_archetype_base<
476             Value
477           , AccessCategory
478           , TraversalCategory
479         >(x)
480     {}
481 
operator =boost::iterators::iterator_archetype482     iterator_archetype& operator=(iterator_archetype const&)
483         { return *this; }
484 
485 # if 0
486     // Optional conversion from mutable
487     iterator_archetype(
488         iterator_archetype<
489         typename detail::convertible_type<Value>::type
490       , AccessCategory
491       , TraversalCategory> const&
492     );
493 # endif
494 };
495 
496 } // namespace iterators
497 
498 // Backward compatibility names
499 namespace iterator_archetypes = iterators::archetypes;
500 using iterators::access_archetype;
501 using iterators::traversal_archetype;
502 using iterators::iterator_archetype;
503 using iterators::undefined;
504 using iterators::iterator_access_archetype_impl;
505 using iterators::traversal_archetype_base;
506 
507 } // namespace boost
508 
509 #endif // BOOST_ITERATOR_ARCHETYPES_HPP
510