1 // Copyright David Abrahams and Thomas Becker 2000-2006. 2 // Copyright Kohei Takahashi 2012-2014. 3 // 4 // Distributed under the Boost Software License, Version 1.0. (See 5 // accompanying file LICENSE_1_0.txt or copy at 6 // http://www.boost.org/LICENSE_1_0.txt) 7 8 #ifndef BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_ 9 # define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_ 10 11 #include <stddef.h> 12 #include <boost/iterator/iterator_traits.hpp> 13 #include <boost/iterator/iterator_facade.hpp> 14 #include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible 15 #include <boost/iterator/iterator_categories.hpp> 16 17 #include <boost/iterator/minimum_category.hpp> 18 19 #include <utility> // for std::pair 20 #include <boost/fusion/adapted/boost_tuple.hpp> // for backward compatibility 21 22 #include <boost/type_traits/remove_reference.hpp> 23 #include <boost/type_traits/remove_cv.hpp> 24 25 #include <boost/mpl/at.hpp> 26 #include <boost/mpl/fold.hpp> 27 #include <boost/mpl/transform.hpp> 28 #include <boost/mpl/placeholders.hpp> 29 30 #include <boost/fusion/algorithm/iteration/for_each.hpp> 31 #include <boost/fusion/algorithm/transformation/transform.hpp> 32 #include <boost/fusion/sequence/convert.hpp> 33 #include <boost/fusion/sequence/intrinsic/at_c.hpp> 34 #include <boost/fusion/sequence/comparison/equal_to.hpp> 35 #include <boost/fusion/support/tag_of_fwd.hpp> 36 37 namespace boost { 38 namespace iterators { 39 40 // Zip iterator forward declaration for zip_iterator_base 41 template<typename IteratorTuple> 42 class zip_iterator; 43 44 namespace detail 45 { 46 47 // Functors to be used with tuple algorithms 48 // 49 template<typename DiffType> 50 class advance_iterator 51 { 52 public: advance_iterator(DiffType step)53 advance_iterator(DiffType step) : m_step(step) {} 54 55 template<typename Iterator> operator ()(Iterator & it) const56 void operator()(Iterator& it) const 57 { it += m_step; } 58 59 private: 60 DiffType m_step; 61 }; 62 // 63 struct increment_iterator 64 { 65 template<typename Iterator> operator ()boost::iterators::detail::increment_iterator66 void operator()(Iterator& it) const 67 { ++it; } 68 }; 69 // 70 struct decrement_iterator 71 { 72 template<typename Iterator> operator ()boost::iterators::detail::decrement_iterator73 void operator()(Iterator& it) const 74 { --it; } 75 }; 76 // 77 struct dereference_iterator 78 { 79 template<typename> 80 struct result; 81 82 template<typename This, typename Iterator> 83 struct result<This(Iterator)> 84 { 85 typedef typename 86 remove_cv<typename remove_reference<Iterator>::type>::type 87 iterator; 88 89 typedef typename iterator_reference<iterator>::type type; 90 }; 91 92 template<typename Iterator> 93 typename result<dereference_iterator(Iterator)>::type operator ()boost::iterators::detail::dereference_iterator94 operator()(Iterator const& it) const 95 { return *it; } 96 }; 97 98 // Metafunction to obtain the type of the tuple whose element types 99 // are the reference types of an iterator tuple. 100 // 101 template<typename IteratorTuple> 102 struct tuple_of_references 103 : mpl::transform< 104 IteratorTuple, 105 iterator_reference<mpl::_1> 106 > 107 { 108 }; 109 110 // Specialization for std::pair 111 template<typename Iterator1, typename Iterator2> 112 struct tuple_of_references<std::pair<Iterator1, Iterator2> > 113 { 114 typedef std::pair< 115 typename iterator_reference<Iterator1>::type 116 , typename iterator_reference<Iterator2>::type 117 > type; 118 }; 119 120 // Metafunction to obtain the minimal traversal tag in a tuple 121 // of iterators. 122 // 123 template<typename IteratorTuple> 124 struct minimum_traversal_category_in_iterator_tuple 125 { 126 typedef typename mpl::transform< 127 IteratorTuple 128 , pure_traversal_tag<iterator_traversal<> > 129 >::type tuple_of_traversal_tags; 130 131 typedef typename mpl::fold< 132 tuple_of_traversal_tags 133 , random_access_traversal_tag 134 , minimum_category<> 135 >::type type; 136 }; 137 138 template<typename Iterator1, typename Iterator2> 139 struct minimum_traversal_category_in_iterator_tuple<std::pair<Iterator1, Iterator2> > 140 { 141 typedef typename pure_traversal_tag< 142 typename iterator_traversal<Iterator1>::type 143 >::type iterator1_traversal; 144 typedef typename pure_traversal_tag< 145 typename iterator_traversal<Iterator2>::type 146 >::type iterator2_traversal; 147 148 typedef typename minimum_category< 149 iterator1_traversal 150 , typename minimum_category< 151 iterator2_traversal 152 , random_access_traversal_tag 153 >::type 154 >::type type; 155 }; 156 157 /////////////////////////////////////////////////////////////////// 158 // 159 // Class zip_iterator_base 160 // 161 // Builds and exposes the iterator facade type from which the zip 162 // iterator will be derived. 163 // 164 template<typename IteratorTuple> 165 struct zip_iterator_base 166 { 167 private: 168 // Reference type is the type of the tuple obtained from the 169 // iterators' reference types. 170 typedef typename 171 detail::tuple_of_references<IteratorTuple>::type reference; 172 173 // Value type is the same as reference type. 174 typedef reference value_type; 175 176 // Difference type is the first iterator's difference type 177 typedef typename iterator_difference< 178 typename mpl::at_c<IteratorTuple, 0>::type 179 >::type difference_type; 180 181 // Traversal catetgory is the minimum traversal category in the 182 // iterator tuple. 183 typedef typename 184 detail::minimum_traversal_category_in_iterator_tuple< 185 IteratorTuple 186 >::type traversal_category; 187 public: 188 189 // The iterator facade type from which the zip iterator will 190 // be derived. 191 typedef iterator_facade< 192 zip_iterator<IteratorTuple>, 193 value_type, 194 traversal_category, 195 reference, 196 difference_type 197 > type; 198 }; 199 200 template <> 201 struct zip_iterator_base<int> 202 { 203 typedef int type; 204 }; 205 206 template <typename reference> 207 struct converter 208 { 209 template <typename Seq> callboost::iterators::detail::converter210 static reference call(Seq seq) 211 { 212 typedef typename fusion::traits::tag_of<reference>::type tag; 213 return fusion::convert<tag>(seq); 214 } 215 }; 216 217 template <typename Reference1, typename Reference2> 218 struct converter<std::pair<Reference1, Reference2> > 219 { 220 typedef std::pair<Reference1, Reference2> reference; 221 template <typename Seq> callboost::iterators::detail::converter222 static reference call(Seq seq) 223 { 224 return reference( 225 fusion::at_c<0>(seq) 226 , fusion::at_c<1>(seq)); 227 } 228 }; 229 } 230 231 ///////////////////////////////////////////////////////////////////// 232 // 233 // zip_iterator class definition 234 // 235 template<typename IteratorTuple> 236 class zip_iterator : 237 public detail::zip_iterator_base<IteratorTuple>::type 238 { 239 240 // Typedef super_t as our base class. 241 typedef typename 242 detail::zip_iterator_base<IteratorTuple>::type super_t; 243 244 // iterator_core_access is the iterator's best friend. 245 friend class iterator_core_access; 246 247 public: 248 249 // Construction 250 // ============ 251 252 // Default constructor zip_iterator()253 zip_iterator() { } 254 255 // Constructor from iterator tuple zip_iterator(IteratorTuple iterator_tuple)256 zip_iterator(IteratorTuple iterator_tuple) 257 : m_iterator_tuple(iterator_tuple) 258 { } 259 260 // Copy constructor 261 template<typename OtherIteratorTuple> zip_iterator(const zip_iterator<OtherIteratorTuple> & other,typename enable_if_convertible<OtherIteratorTuple,IteratorTuple>::type * =0)262 zip_iterator( 263 const zip_iterator<OtherIteratorTuple>& other, 264 typename enable_if_convertible< 265 OtherIteratorTuple, 266 IteratorTuple 267 >::type* = 0 268 ) : m_iterator_tuple(other.get_iterator_tuple()) 269 {} 270 271 // Get method for the iterator tuple. get_iterator_tuple() const272 const IteratorTuple& get_iterator_tuple() const 273 { return m_iterator_tuple; } 274 275 private: 276 277 // Implementation of Iterator Operations 278 // ===================================== 279 280 // Dereferencing returns a tuple built from the dereferenced 281 // iterators in the iterator tuple. dereference() const282 typename super_t::reference dereference() const 283 { 284 typedef typename super_t::reference reference; 285 typedef detail::converter<reference> gen; 286 return gen::call(fusion::transform( 287 get_iterator_tuple(), 288 detail::dereference_iterator())); 289 } 290 291 // Two zip iterators are equal if all iterators in the iterator 292 // tuple are equal. NOTE: It should be possible to implement this 293 // as 294 // 295 // return get_iterator_tuple() == other.get_iterator_tuple(); 296 // 297 // but equality of tuples currently (7/2003) does not compile 298 // under several compilers. No point in bringing in a bunch 299 // of #ifdefs here. 300 // 301 template<typename OtherIteratorTuple> equal(const zip_iterator<OtherIteratorTuple> & other) const302 bool equal(const zip_iterator<OtherIteratorTuple>& other) const 303 { 304 return fusion::equal_to( 305 get_iterator_tuple(), 306 other.get_iterator_tuple()); 307 } 308 309 // Advancing a zip iterator means to advance all iterators in the 310 // iterator tuple. advance(typename super_t::difference_type n)311 void advance(typename super_t::difference_type n) 312 { 313 fusion::for_each( 314 m_iterator_tuple, 315 detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n)); 316 } 317 // Incrementing a zip iterator means to increment all iterators in 318 // the iterator tuple. increment()319 void increment() 320 { 321 fusion::for_each( 322 m_iterator_tuple, 323 detail::increment_iterator()); 324 } 325 326 // Decrementing a zip iterator means to decrement all iterators in 327 // the iterator tuple. decrement()328 void decrement() 329 { 330 fusion::for_each( 331 m_iterator_tuple, 332 detail::decrement_iterator()); 333 } 334 335 // Distance is calculated using the first iterator in the tuple. 336 template<typename OtherIteratorTuple> distance_to(const zip_iterator<OtherIteratorTuple> & other) const337 typename super_t::difference_type distance_to( 338 const zip_iterator<OtherIteratorTuple>& other 339 ) const 340 { 341 return fusion::at_c<0>(other.get_iterator_tuple()) - 342 fusion::at_c<0>(this->get_iterator_tuple()); 343 } 344 345 // Data Members 346 // ============ 347 348 // The iterator tuple. 349 IteratorTuple m_iterator_tuple; 350 351 }; 352 353 // Make function for zip iterator 354 // 355 template<typename IteratorTuple> 356 inline zip_iterator<IteratorTuple> make_zip_iterator(IteratorTuple t)357 make_zip_iterator(IteratorTuple t) 358 { return zip_iterator<IteratorTuple>(t); } 359 360 } // namespace iterators 361 362 using iterators::zip_iterator; 363 using iterators::make_zip_iterator; 364 365 } // namespace boost 366 367 #endif 368