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