1 | // Boost.Range library |
2 | // |
3 | // Copyright Neil Groves 2009. Use, modification and |
4 | // distribution is subject to the Boost Software License, Version |
5 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | // |
8 | // Acknowledgements: |
9 | // aschoedl contributed an improvement to the determination |
10 | // of the Reference type parameter. |
11 | // |
12 | // Leonid Gershanovich reported Trac ticket 7376 about the dereference operator |
13 | // requiring identical reference types due to using the ternary if. |
14 | // |
15 | // For more information, see http://www.boost.org/libs/range/ |
16 | // |
17 | #ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED |
18 | #define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED |
19 | |
20 | #include <iterator> |
21 | #include <boost/assert.hpp> |
22 | #include <boost/iterator/iterator_traits.hpp> |
23 | #include <boost/iterator/iterator_facade.hpp> |
24 | #include <boost/range/begin.hpp> |
25 | #include <boost/range/end.hpp> |
26 | #include <boost/range/empty.hpp> |
27 | #include <boost/range/detail/demote_iterator_traversal_tag.hpp> |
28 | #include <boost/range/value_type.hpp> |
29 | #include <boost/type_traits/add_const.hpp> |
30 | #include <boost/type_traits/add_reference.hpp> |
31 | #include <boost/type_traits/remove_const.hpp> |
32 | #include <boost/type_traits/remove_reference.hpp> |
33 | #include <boost/next_prior.hpp> |
34 | |
35 | namespace boost |
36 | { |
37 | namespace range_detail |
38 | { |
39 | |
40 | template<typename Iterator1, typename Iterator2> |
41 | struct join_iterator_link |
42 | { |
43 | public: |
44 | join_iterator_link(Iterator1 last1, Iterator2 first2) |
45 | : last1(last1) |
46 | , first2(first2) |
47 | { |
48 | } |
49 | |
50 | Iterator1 last1; |
51 | Iterator2 first2; |
52 | |
53 | private: |
54 | join_iterator_link() /* = delete */ ; |
55 | }; |
56 | |
57 | class join_iterator_begin_tag {}; |
58 | class join_iterator_end_tag {}; |
59 | |
60 | template<typename Iterator1 |
61 | , typename Iterator2 |
62 | , typename Reference |
63 | > |
64 | class join_iterator_union |
65 | { |
66 | public: |
67 | typedef Iterator1 iterator1_t; |
68 | typedef Iterator2 iterator2_t; |
69 | |
70 | join_iterator_union() {} |
71 | join_iterator_union(unsigned int /*selected*/, const iterator1_t& it1, const iterator2_t& it2) : m_it1(it1), m_it2(it2) {} |
72 | |
73 | iterator1_t& it1() { return m_it1; } |
74 | const iterator1_t& it1() const { return m_it1; } |
75 | |
76 | iterator2_t& it2() { return m_it2; } |
77 | const iterator2_t& it2() const { return m_it2; } |
78 | |
79 | Reference dereference(unsigned int selected) const |
80 | { |
81 | if (selected) |
82 | return *m_it2; |
83 | return *m_it1; |
84 | } |
85 | |
86 | bool equal(const join_iterator_union& other, unsigned int selected) const |
87 | { |
88 | return selected |
89 | ? m_it2 == other.m_it2 |
90 | : m_it1 == other.m_it1; |
91 | } |
92 | |
93 | private: |
94 | iterator1_t m_it1; |
95 | iterator2_t m_it2; |
96 | }; |
97 | |
98 | template<class Iterator, class Reference> |
99 | class join_iterator_union<Iterator, Iterator, Reference> |
100 | { |
101 | public: |
102 | typedef Iterator iterator1_t; |
103 | typedef Iterator iterator2_t; |
104 | |
105 | join_iterator_union() {} |
106 | |
107 | join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2) |
108 | : m_it(selected ? it2 : it1) |
109 | { |
110 | } |
111 | |
112 | iterator1_t& it1() { return m_it; } |
113 | const iterator1_t& it1() const { return m_it; } |
114 | |
115 | iterator2_t& it2() { return m_it; } |
116 | const iterator2_t& it2() const { return m_it; } |
117 | |
118 | Reference dereference(unsigned int) const |
119 | { |
120 | return *m_it; |
121 | } |
122 | |
123 | bool equal(const join_iterator_union& other, |
124 | unsigned int /*selected*/) const |
125 | { |
126 | return m_it == other.m_it; |
127 | } |
128 | |
129 | private: |
130 | iterator1_t m_it; |
131 | }; |
132 | |
133 | template<typename Iterator1 |
134 | , typename Iterator2 |
135 | , typename ValueType = typename iterator_value<Iterator1>::type |
136 | // find least demanding, commonly supported reference type, in the order &, const&, and by-value: |
137 | , typename Reference = typename mpl::if_c< |
138 | !is_reference<typename iterator_reference<Iterator1>::type>::value |
139 | || !is_reference<typename iterator_reference<Iterator2>::type>::value, |
140 | typename remove_const< |
141 | typename remove_reference< |
142 | typename iterator_reference<Iterator1>::type |
143 | >::type |
144 | >::type, |
145 | typename mpl::if_c< |
146 | is_const< |
147 | typename remove_reference< |
148 | typename iterator_reference<Iterator1>::type |
149 | >::type |
150 | >::value |
151 | || is_const< |
152 | typename remove_reference< |
153 | typename iterator_reference<Iterator2>::type |
154 | >::type |
155 | >::value, |
156 | typename add_const< |
157 | typename iterator_reference<Iterator1>::type |
158 | >::type, |
159 | typename iterator_reference<Iterator1>::type |
160 | >::type |
161 | >::type |
162 | , typename Traversal = typename demote_iterator_traversal_tag< |
163 | typename iterator_traversal<Iterator1>::type |
164 | , typename iterator_traversal<Iterator2>::type>::type |
165 | > |
166 | class join_iterator |
167 | : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference> |
168 | { |
169 | typedef join_iterator_link<Iterator1, Iterator2> link_t; |
170 | typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union; |
171 | public: |
172 | typedef Iterator1 iterator1_t; |
173 | typedef Iterator2 iterator2_t; |
174 | |
175 | join_iterator() |
176 | : m_section(0u) |
177 | , m_it(0u, iterator1_t(), iterator2_t()) |
178 | , m_link(link_t(iterator1_t(), iterator2_t())) |
179 | {} |
180 | |
181 | join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2) |
182 | : m_section(section) |
183 | , m_it(section, current1, current2) |
184 | , m_link(link_t(last1, first2)) |
185 | { |
186 | } |
187 | |
188 | template<typename Range1, typename Range2> |
189 | join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag) |
190 | : m_section(boost::empty(r1) ? 1u : 0u) |
191 | , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2)) |
192 | , m_link(link_t(boost::end(r1), boost::begin(r2))) |
193 | { |
194 | } |
195 | |
196 | template<typename Range1, typename Range2> |
197 | join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag) |
198 | : m_section(boost::empty(r1) ? 1u : 0u) |
199 | , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2)) |
200 | , m_link(link_t(boost::const_end(r1), boost::const_begin(r2))) |
201 | { |
202 | } |
203 | |
204 | template<typename Range1, typename Range2> |
205 | join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag) |
206 | : m_section(1u) |
207 | , m_it(1u, boost::end(r1), boost::end(r2)) |
208 | , m_link(link_t(boost::end(r1), boost::begin(r2))) |
209 | { |
210 | } |
211 | |
212 | template<typename Range1, typename Range2> |
213 | join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag) |
214 | : m_section(1u) |
215 | , m_it(1u, boost::const_end(r1), boost::const_end(r2)) |
216 | , m_link(link_t(boost::const_end(r1), boost::const_begin(r2))) |
217 | { |
218 | } |
219 | |
220 | private: |
221 | void increment() |
222 | { |
223 | if (m_section) |
224 | ++m_it.it2(); |
225 | else |
226 | { |
227 | ++m_it.it1(); |
228 | if (m_it.it1() == m_link.last1) |
229 | { |
230 | m_it.it2() = m_link.first2; |
231 | m_section = 1u; |
232 | } |
233 | } |
234 | } |
235 | |
236 | void decrement() |
237 | { |
238 | if (m_section) |
239 | { |
240 | if (m_it.it2() == m_link.first2) |
241 | { |
242 | m_it.it1() = boost::prior(m_link.last1); |
243 | m_section = 0u; |
244 | } |
245 | else |
246 | --m_it.it2(); |
247 | } |
248 | else |
249 | --m_it.it1(); |
250 | } |
251 | |
252 | typename join_iterator::reference dereference() const |
253 | { |
254 | return m_it.dereference(m_section); |
255 | } |
256 | |
257 | bool equal(const join_iterator& other) const |
258 | { |
259 | return m_section == other.m_section |
260 | && m_it.equal(other.m_it, m_section); |
261 | } |
262 | |
263 | void advance(typename join_iterator::difference_type offset) |
264 | { |
265 | if (m_section) |
266 | advance_from_range2(offset); |
267 | else |
268 | advance_from_range1(offset); |
269 | } |
270 | |
271 | typename join_iterator::difference_type distance_to(const join_iterator& other) const |
272 | { |
273 | typename join_iterator::difference_type result; |
274 | if (m_section) |
275 | { |
276 | if (other.m_section) |
277 | result = other.m_it.it2() - m_it.it2(); |
278 | else |
279 | { |
280 | result = (m_link.first2 - m_it.it2()) |
281 | + (other.m_it.it1() - m_link.last1); |
282 | |
283 | BOOST_ASSERT( result <= 0 ); |
284 | } |
285 | } |
286 | else |
287 | { |
288 | if (other.m_section) |
289 | { |
290 | result = (m_link.last1 - m_it.it1()) |
291 | + (other.m_it.it2() - m_link.first2); |
292 | } |
293 | else |
294 | result = other.m_it.it1() - m_it.it1(); |
295 | } |
296 | return result; |
297 | } |
298 | |
299 | void advance_from_range2(typename join_iterator::difference_type offset) |
300 | { |
301 | typedef typename join_iterator::difference_type difference_t; |
302 | BOOST_ASSERT( m_section == 1u ); |
303 | if (offset < 0) |
304 | { |
305 | difference_t r2_dist = m_link.first2 - m_it.it2(); |
306 | BOOST_ASSERT( r2_dist <= 0 ); |
307 | if (offset >= r2_dist) |
308 | std::advance(m_it.it2(), offset); |
309 | else |
310 | { |
311 | difference_t r1_dist = offset - r2_dist; |
312 | BOOST_ASSERT( r1_dist <= 0 ); |
313 | m_it.it1() = m_link.last1 + r1_dist; |
314 | m_section = 0u; |
315 | } |
316 | } |
317 | else |
318 | std::advance(m_it.it2(), offset); |
319 | } |
320 | |
321 | void advance_from_range1(typename join_iterator::difference_type offset) |
322 | { |
323 | typedef typename join_iterator::difference_type difference_t; |
324 | BOOST_ASSERT( m_section == 0u ); |
325 | if (offset > 0) |
326 | { |
327 | difference_t r1_dist = m_link.last1 - m_it.it1(); |
328 | BOOST_ASSERT( r1_dist >= 0 ); |
329 | if (offset < r1_dist) |
330 | std::advance(m_it.it1(), offset); |
331 | else |
332 | { |
333 | difference_t r2_dist = offset - r1_dist; |
334 | BOOST_ASSERT( r2_dist >= 0 ); |
335 | m_it.it2() = m_link.first2 + r2_dist; |
336 | m_section = 1u; |
337 | } |
338 | } |
339 | else |
340 | std::advance(m_it.it1(), offset); |
341 | } |
342 | |
343 | unsigned int m_section; |
344 | iterator_union m_it; |
345 | link_t m_link; |
346 | |
347 | friend class ::boost::iterator_core_access; |
348 | }; |
349 | |
350 | } // namespace range_detail |
351 | |
352 | } // namespace boost |
353 | |
354 | #endif // include guard |
355 | |