1 // Boost.TypeErasure library
2 //
3 // Copyright 2011 Steven Watanabe
4 //
5 // Distributed under the Boost Software License Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // $Id$
10 
11 #ifndef BOOST_TYPE_ERASURE_ITERATOR_HPP_INCLUDED
12 #define BOOST_TYPE_ERASURE_ITERATOR_HPP_INCLUDED
13 
14 #include <iterator>
15 #include <boost/mpl/vector.hpp>
16 #include <boost/mpl/if.hpp>
17 #include <boost/iterator/iterator_adaptor.hpp>
18 #include <boost/iterator/iterator_categories.hpp>
19 #include <boost/type_traits/remove_const.hpp>
20 #include <boost/type_traits/remove_reference.hpp>
21 #include <boost/type_erasure/operators.hpp>
22 #include <boost/type_erasure/builtin.hpp>
23 #include <boost/type_erasure/deduced.hpp>
24 #include <boost/type_erasure/is_placeholder.hpp>
25 
26 namespace boost {
27 
28 namespace type_erasure {
29 
30 /** INTERNAL ONLY */
31 template<>
32 struct is_placeholder< ::boost::use_default> : ::boost::mpl::false_ {};
33 
34 namespace detail {
35 
36 template<class T>
37 struct iterator_value_type_impl
38 {
39     typedef typename ::std::iterator_traits<T>::value_type type;
40 };
41 
42 }
43 
44 /** INTERNAL ONLY */
45 template<class T>
46 struct iterator_value_type
47 {
48     typedef typename ::boost::mpl::eval_if<
49         ::boost::type_erasure::is_placeholder<T>,
50         ::boost::mpl::identity<void>,
51         ::boost::type_erasure::detail::iterator_value_type_impl<T>
52     >::type type;
53 };
54 
55 template<
56     class Traversal,
57     class T = _self,
58     class Reference = ::boost::use_default,
59     class DifferenceType = ::std::ptrdiff_t,
60     class ValueType = typename deduced<iterator_value_type<T> >::type
61 >
62 struct iterator;
63 
64 #ifdef BOOST_TYPE_ERASURE_DOXYGEN
65 
66 /**
67  * The @ref iterator concept can be used for any iterator category.
68  *
69  * \tparam Traversal must be one of @c boost::incrementable_traversal_tag,
70  *         @c boost::single_pass_traversal_tag, @c boost::forward_traversal_tag,
71  *         @c boost::bidirectional_traversal_tag, and @c boost::random_access_traversal_tag.
72  * \tparam T The placeholder representing the iterator.
73  * \tparam Reference The reference type.  If it is boost::use_default, then
74  *         reference will be value_type&.
75  * \tparam DifferenceType The iterator's difference type.
76  *
77  * The value_type of the iterator is deduced.  To force it to be
78  * a specific type, use the @ref same_type concept.
79  *
80  * Example:
81  *
82  * \code
83  * mpl::vector<
84  *   iterator<boost::forward_traversal_tag>,
85  *   same_type<iterator<boost::forward_traversal_tag>::value_type, int> > int_it;
86  * \endcode
87  */
88 template<
89     class Traversal,
90     class T = _self,
91     class Reference = boost::use_default,
92     class DifferenceType = std::ptrdiff_t
93 >
94 struct iterator
95 {
96     typedef detail::unspecified value_type;
97     typedef Reference reference;
98     typedef DifferenceType difference_type;
99 };
100 
101 template<
102     class T = _self,
103     class Reference = boost::use_default,
104     class DifferenceType = std::ptrdiff_t
105 >
106 struct forward_iterator :
107     iterator<boost::forward_traversal_tag, T, Reference, DifferenceType>
108 {};
109 
110 template<
111     class T = _self,
112     class Reference = boost::use_default,
113     class DifferenceType = std::ptrdiff_t
114 >
115 struct bidirectional_iterator :
116     iterator<boost::bidirectional_traversal_tag, T, Reference, DifferenceType>
117 {};
118 
119 template<
120     class T = _self,
121     class Reference = boost::use_default,
122     class DifferenceType = std::ptrdiff_t
123 >
124 struct random_access_iterator :
125     iterator<boost::random_access_traversal_tag, T, Reference, DifferenceType>
126 {
127 };
128 
129 #else
130 
131 /** INTERNAL ONLY */
132 template<class Reference, class ValueType>
133 struct iterator_reference
134 {
135     typedef Reference type;
136 };
137 
138 /** INTERNAL ONLY */
139 template<class ValueType>
140 struct iterator_reference< ::boost::use_default, ValueType>
141 {
142     typedef ValueType& type;
143 };
144 
145 template<class T, class Reference, class DifferenceType, class ValueType>
146 struct iterator< ::boost::no_traversal_tag, T, Reference, DifferenceType, ValueType> :
147     boost::mpl::vector<
148         copy_constructible<T>,
149         constructible<T()>,
150         equality_comparable<T>,
151         dereferenceable<typename iterator_reference<Reference, ValueType>::type, T>,
152         assignable<T>
153     >
154 {
155     typedef ValueType value_type;
156     typedef typename iterator_reference<Reference, ValueType>::type reference;
157     typedef DifferenceType difference_type;
158 };
159 
160 template<class T, class Reference, class DifferenceType, class ValueType>
161 struct iterator< ::boost::incrementable_traversal_tag, T, Reference, DifferenceType, ValueType> :
162     boost::mpl::vector<
163         iterator< ::boost::no_traversal_tag, T, Reference, DifferenceType>,
164         incrementable<T>
165     >
166 {
167     typedef ValueType value_type;
168     typedef typename iterator_reference<Reference, ValueType>::type reference;
169     typedef DifferenceType difference_type;
170 };
171 
172 template<class T, class Reference, class DifferenceType, class ValueType>
173 struct iterator< ::boost::single_pass_traversal_tag, T, Reference, DifferenceType, ValueType> :
174     iterator< ::boost::incrementable_traversal_tag, T, Reference, DifferenceType, ValueType>
175 {};
176 
177 template<class T, class Reference, class DifferenceType, class ValueType>
178 struct iterator< ::boost::forward_traversal_tag, T, Reference, DifferenceType, ValueType> :
179     iterator< ::boost::incrementable_traversal_tag, T, Reference, DifferenceType, ValueType>
180 {};
181 
182 template<class T, class Reference, class DifferenceType, class ValueType>
183 struct iterator< ::boost::bidirectional_traversal_tag, T, Reference, DifferenceType, ValueType> :
184     boost::mpl::vector<
185         iterator< ::boost::incrementable_traversal_tag, T, Reference, DifferenceType, ValueType>,
186         decrementable<T>
187     >
188 {
189     typedef ValueType value_type;
190     typedef typename iterator_reference<Reference, ValueType>::type reference;
191     typedef DifferenceType difference_type;
192 };
193 
194 template<class T, class Reference, class DifferenceType, class ValueType>
195 struct iterator< ::boost::random_access_traversal_tag, T, Reference, DifferenceType, ValueType> :
196     boost::mpl::vector<
197         iterator< ::boost::bidirectional_traversal_tag, T, Reference, DifferenceType, ValueType>,
198         addable<T, DifferenceType, T>,
199         addable<DifferenceType, T, T>,
200         subtractable<T, DifferenceType, T>,
201         subtractable<T, T, DifferenceType>,
202         subscriptable<typename iterator_reference<Reference, ValueType>::type, T, DifferenceType>
203     >
204 {
205     typedef ValueType value_type;
206     typedef typename iterator_reference<Reference, ValueType>::type reference;
207     typedef DifferenceType difference_type;
208 };
209 
210 template<
211     class T = _self,
212     class Reference = ::boost::use_default,
213     class DifferenceType = ::std::ptrdiff_t,
214     class ValueType = typename deduced<iterator_value_type<T> >::type
215 >
216 struct forward_iterator :
217     iterator< ::boost::forward_traversal_tag, T, Reference, DifferenceType, ValueType>
218 {};
219 
220 template<
221     class T = _self,
222     class Reference = ::boost::use_default,
223     class DifferenceType = ::std::ptrdiff_t,
224     class ValueType = typename deduced<iterator_value_type<T> >::type
225 >
226 struct bidirectional_iterator :
227     iterator< ::boost::bidirectional_traversal_tag, T, Reference, DifferenceType, ValueType>
228 {};
229 
230 template<
231     class T = _self,
232     class Reference = ::boost::use_default,
233     class DifferenceType = ::std::ptrdiff_t,
234     class ValueType = typename deduced<iterator_value_type<T> >::type
235 >
236 struct random_access_iterator :
237     iterator< ::boost::random_access_traversal_tag, T, Reference, DifferenceType, ValueType>
238 {
239 };
240 
241 #endif
242 
243 /// \cond show_operators
244 
245 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
246 struct concept_interface<iterator< ::boost::no_traversal_tag, T, Reference, DifferenceType, ValueType>, Base, T>
247     : Base
248 {
249     typedef typename rebind_any<Base, ValueType>::type value_type;
250     typedef typename rebind_any<
251         Base,
252         typename iterator_reference<Reference, ValueType>::type
253     >::type reference;
254     typedef DifferenceType difference_type;
255     typedef typename ::boost::mpl::if_< ::boost::is_reference<reference>,
256         typename ::boost::remove_reference<reference>::type*,
257         value_type*
258     >::type pointer;
259 };
260 
261 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
262 struct concept_interface<iterator< ::boost::forward_traversal_tag, T, Reference, DifferenceType, ValueType>, Base, T>
263     : Base
264 {
265     typedef std::forward_iterator_tag iterator_category;
266 };
267 
268 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
269 struct concept_interface<forward_iterator<T, Reference, DifferenceType, ValueType>, Base, T>
270     : Base
271 {
272     typedef std::forward_iterator_tag iterator_category;
273 };
274 
275 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
276 struct concept_interface<iterator< ::boost::bidirectional_traversal_tag, T, Reference, DifferenceType, ValueType>, Base, T>
277     : Base
278 {
279     typedef std::bidirectional_iterator_tag iterator_category;
280 };
281 
282 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
283 struct concept_interface<bidirectional_iterator<T, Reference, DifferenceType, ValueType>, Base, T>
284     : Base
285 {
286     typedef std::bidirectional_iterator_tag iterator_category;
287 };
288 
289 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
290 struct concept_interface<iterator< ::boost::random_access_traversal_tag, T, Reference, DifferenceType, ValueType>, Base, T>
291     : Base
292 {
293     typedef std::random_access_iterator_tag iterator_category;
294 };
295 
296 template<class T, class Reference, class DifferenceType, class ValueType, class Base>
297 struct concept_interface<random_access_iterator<T, Reference, DifferenceType, ValueType>, Base, T>
298     : Base
299 {
300     typedef std::random_access_iterator_tag iterator_category;
301 };
302 
303 /// \endcond
304 
305 }
306 }
307 
308 #endif
309