1 /*************************************************************************** 2 * Copyright (c) Johan Mabille, Sylvain Corlay and Wolf Vollprecht * 3 * Copyright (c) QuantStack * 4 * * 5 * Distributed under the terms of the BSD 3-Clause License. * 6 * * 7 * The full license is in the file LICENSE, distributed with this software. * 8 ****************************************************************************/ 9 10 #ifndef XTL_XITERATOR_BASE_HPP 11 #define XTL_XITERATOR_BASE_HPP 12 13 #include <cstddef> 14 #include <iterator> 15 16 namespace xtl 17 { 18 /************************************** 19 * class xbidirectional_iterator_base * 20 **************************************/ 21 22 template <class I, class T, class D = std::ptrdiff_t, class P = T*, class R = T&> 23 class xbidirectional_iterator_base 24 { 25 public: 26 27 using derived_type = I; 28 using value_type = T; 29 using reference = R; 30 using pointer = P; 31 using difference_type = D; 32 using iterator_category = std::bidirectional_iterator_tag; 33 operator ++(derived_type & d,int)34 inline friend derived_type operator++(derived_type& d, int) 35 { 36 derived_type tmp(d); 37 ++d; 38 return tmp; 39 } 40 operator --(derived_type & d,int)41 inline friend derived_type operator--(derived_type& d, int) 42 { 43 derived_type tmp(d); 44 --d; 45 return tmp; 46 47 } 48 operator !=(const derived_type & lhs,const derived_type & rhs)49 inline friend bool operator!=(const derived_type& lhs, const derived_type& rhs) 50 { 51 return !(lhs == rhs); 52 } 53 }; 54 55 template <class T> 56 using xbidirectional_iterator_base2 = xbidirectional_iterator_base<typename T::iterator_type, 57 typename T::value_type, 58 typename T::difference_type, 59 typename T::pointer, 60 typename T::reference>; 61 62 template <class I, class T> 63 using xbidirectional_iterator_base3 = xbidirectional_iterator_base<I, 64 typename T::value_type, 65 typename T::difference_type, 66 typename T::pointer, 67 typename T::reference>; 68 69 /******************************** 70 * xrandom_access_iterator_base * 71 ********************************/ 72 73 template <class I, class T, class D = std::ptrdiff_t, class P = T*, class R = T&> 74 class xrandom_access_iterator_base : public xbidirectional_iterator_base<I, T, D, P, R> 75 { 76 public: 77 78 using derived_type = I; 79 using value_type = T; 80 using reference = R; 81 using pointer = P; 82 using difference_type = D; 83 using iterator_category = std::random_access_iterator_tag; 84 operator [](difference_type n) const85 inline reference operator[](difference_type n) const 86 { 87 return *(*static_cast<const derived_type*>(this) + n); 88 } 89 operator +(const derived_type & it,difference_type n)90 inline friend derived_type operator+(const derived_type& it, difference_type n) 91 { 92 derived_type tmp(it); 93 return tmp += n; 94 } 95 operator +(difference_type n,const derived_type & it)96 inline friend derived_type operator+(difference_type n, const derived_type& it) 97 { 98 derived_type tmp(it); 99 return tmp += n; 100 } 101 operator -(const derived_type & it,difference_type n)102 inline friend derived_type operator-(const derived_type& it, difference_type n) 103 { 104 derived_type tmp(it); 105 return tmp -= n; 106 } 107 operator <=(const derived_type & lhs,const derived_type & rhs)108 inline friend bool operator<=(const derived_type& lhs, const derived_type& rhs) 109 { 110 return !(rhs < lhs); 111 } 112 operator >=(const derived_type & lhs,const derived_type & rhs)113 inline friend bool operator>=(const derived_type& lhs, const derived_type& rhs) 114 { 115 return !(lhs < rhs); 116 } 117 operator >(const derived_type & lhs,const derived_type & rhs)118 inline friend bool operator>(const derived_type& lhs, const derived_type& rhs) 119 { 120 return rhs < lhs; 121 } 122 123 }; 124 125 template <class T> 126 using xrandom_access_iterator_base2 = xrandom_access_iterator_base<typename T::iterator_type, 127 typename T::value_type, 128 typename T::difference_type, 129 typename T::pointer, 130 typename T::reference>; 131 132 template <class I, class T> 133 using xrandom_access_iterator_base3 = xrandom_access_iterator_base<I, 134 typename T::value_type, 135 typename T::difference_type, 136 typename T::pointer, 137 typename T::reference>; 138 139 /******************************* 140 * xrandom_access_iterator_ext * 141 *******************************/ 142 143 // Extension for random access iterators defining operator[] and operator+ overloads 144 // accepting size_t arguments. 145 template <class I, class R> 146 class xrandom_access_iterator_ext 147 { 148 public: 149 150 using derived_type = I; 151 using reference = R; 152 using size_type = std::size_t; 153 operator [](size_type n) const154 inline reference operator[](size_type n) const 155 { 156 return *(*static_cast<const derived_type*>(this) + n); 157 } 158 operator +(const derived_type & it,size_type n)159 inline friend derived_type operator+(const derived_type& it, size_type n) 160 { 161 derived_type tmp(it); 162 return tmp += n; 163 } 164 operator +(size_type n,const derived_type & it)165 inline friend derived_type operator+(size_type n, const derived_type& it) 166 { 167 derived_type tmp(it); 168 return tmp += n; 169 } 170 operator -(const derived_type & it,size_type n)171 inline friend derived_type operator-(const derived_type& it, size_type n) 172 { 173 derived_type tmp(it); 174 return tmp -= n; 175 } 176 }; 177 178 /***************** 179 * xkey_iterator * 180 *****************/ 181 182 template <class M> 183 class xkey_iterator : public xbidirectional_iterator_base<xkey_iterator<M>, const typename M::key_type> 184 { 185 public: 186 187 using self_type = xkey_iterator; 188 using base_type = xbidirectional_iterator_base<self_type, const typename M::key_type>; 189 using value_type = typename base_type::value_type; 190 using reference = typename base_type::reference; 191 using pointer = typename base_type::pointer; 192 using difference_type = typename base_type::difference_type; 193 using iterator_category = typename base_type::iterator_category; 194 using subiterator = typename M::const_iterator; 195 xkey_iterator(subiterator it)196 inline xkey_iterator(subiterator it) noexcept 197 : m_it(it) 198 { 199 } 200 operator ++()201 inline self_type& operator++() 202 { 203 ++m_it; 204 return *this; 205 } 206 operator --()207 inline self_type& operator--() 208 { 209 --m_it; 210 return *this; 211 } 212 operator *() const213 inline reference operator*() const 214 { 215 return m_it->first; 216 } 217 operator ->() const218 inline pointer operator->() const 219 { 220 return&(m_it->first); 221 } 222 operator ==(const self_type & rhs) const223 inline bool operator==(const self_type& rhs) const 224 { 225 return m_it == rhs.m_it; 226 } 227 228 private: 229 230 subiterator m_it; 231 }; 232 233 /******************* 234 * xvalue_iterator * 235 *******************/ 236 237 namespace detail 238 { 239 template <class M> 240 struct xvalue_iterator_types 241 { 242 using subiterator = typename M::iterator; 243 using value_type = typename M::mapped_type; 244 using reference = value_type&; 245 using pointer = value_type*; 246 using difference_type = typename subiterator::difference_type; 247 }; 248 249 template <class M> 250 struct xvalue_iterator_types<const M> 251 { 252 using subiterator = typename M::const_iterator; 253 using value_type = typename M::mapped_type; 254 using reference = const value_type&; 255 using pointer = const value_type*; 256 using difference_type = typename subiterator::difference_type; 257 }; 258 } 259 260 template <class M> 261 class xvalue_iterator : xbidirectional_iterator_base3<xvalue_iterator<M>, 262 detail::xvalue_iterator_types<M>> 263 { 264 public: 265 266 using self_type = xvalue_iterator<M>; 267 using base_type = xbidirectional_iterator_base3<self_type, detail::xvalue_iterator_types<M>>; 268 using value_type = typename base_type::value_type; 269 using reference = typename base_type::reference; 270 using pointer = typename base_type::pointer; 271 using difference_type = typename base_type::difference_type; 272 using subiterator = typename detail::xvalue_iterator_types<M>::subiterator; 273 xvalue_iterator(subiterator it)274 inline xvalue_iterator(subiterator it) noexcept 275 : m_it(it) 276 { 277 } 278 operator ++()279 inline self_type& operator++() 280 { 281 ++m_it; 282 return *this; 283 } 284 operator --()285 inline self_type& operator--() 286 { 287 --m_it; 288 return *this; 289 } 290 operator *() const291 inline reference operator*() const 292 { 293 return m_it->second; 294 } 295 operator ->() const296 inline pointer operator->() const 297 { 298 return&(m_it->second); 299 } 300 operator ==(const self_type & rhs) const301 inline bool operator==(const self_type& rhs) const 302 { 303 return m_it == rhs.m_it; 304 } 305 private: 306 307 subiterator m_it; 308 }; 309 310 /********************** 311 * xstepping_iterator * 312 **********************/ 313 314 template <class It> 315 class xstepping_iterator : public xrandom_access_iterator_base3<xstepping_iterator<It>, 316 std::iterator_traits<It>> 317 { 318 public: 319 320 using self_type = xstepping_iterator; 321 using base_type = xrandom_access_iterator_base3<self_type, std::iterator_traits<It>>; 322 using value_type = typename base_type::value_type; 323 using reference = typename base_type::reference; 324 using pointer = typename base_type::pointer; 325 using difference_type = typename base_type::difference_type; 326 using iterator_category = typename base_type::iterator_category; 327 using subiterator = It; 328 329 xstepping_iterator() = default; 330 xstepping_iterator(subiterator it,difference_type step)331 inline xstepping_iterator(subiterator it, difference_type step) noexcept 332 : m_it(it), m_step(step) 333 { 334 } 335 operator ++()336 inline self_type& operator++() 337 { 338 std::advance(m_it, m_step); 339 return *this; 340 } 341 operator --()342 inline self_type& operator--() 343 { 344 std::advance(m_it, -m_step); 345 return *this; 346 } 347 operator +=(difference_type n)348 inline self_type& operator+=(difference_type n) 349 { 350 std::advance(m_it, n*m_step); 351 return *this; 352 } 353 operator -=(difference_type n)354 inline self_type& operator-=(difference_type n) 355 { 356 std::advance(m_it, -n*m_step); 357 return *this; 358 } 359 operator -(const self_type & rhs) const360 inline difference_type operator-(const self_type& rhs) const 361 { 362 return std::distance(rhs.m_it, m_it) / m_step; 363 } 364 operator *() const365 inline reference operator*() const 366 { 367 return *m_it; 368 } 369 operator ->() const370 inline pointer operator->() const 371 { 372 return m_it; 373 } 374 equal(const self_type & rhs) const375 inline bool equal(const self_type& rhs) const 376 { 377 return m_it == rhs.m_it && m_step == rhs.m_step; 378 } 379 less_than(const self_type & rhs) const380 inline bool less_than(const self_type& rhs) const 381 { 382 return m_it < rhs.m_it && m_step == rhs.m_step; 383 } 384 385 private: 386 387 subiterator m_it; 388 difference_type m_step; 389 }; 390 391 template <class It> operator ==(const xstepping_iterator<It> & lhs,const xstepping_iterator<It> & rhs)392 inline bool operator==(const xstepping_iterator<It>& lhs, const xstepping_iterator<It>& rhs) 393 { 394 return lhs.equal(rhs); 395 } 396 397 template <class It> operator <(const xstepping_iterator<It> & lhs,const xstepping_iterator<It> & rhs)398 inline bool operator<(const xstepping_iterator<It>& lhs, const xstepping_iterator<It>& rhs) 399 { 400 return lhs.less_than(rhs); 401 } 402 403 template <class It> make_stepping_iterator(It it,typename std::iterator_traits<It>::difference_type step)404 inline xstepping_iterator<It> make_stepping_iterator(It it, typename std::iterator_traits<It>::difference_type step) 405 { 406 return xstepping_iterator<It>(it, step); 407 } 408 409 /*********************** 410 * common_iterator_tag * 411 ***********************/ 412 413 template <class... Its> 414 struct common_iterator_tag : std::common_type<typename std::iterator_traits<Its>::iterator_category...> 415 { 416 }; 417 418 template <class... Its> 419 using common_iterator_tag_t = typename common_iterator_tag<Its...>::type; 420 } 421 422 #endif 423