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