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
35namespace boost
36{
37 namespace range_detail
38 {
39
40template<typename Iterator1, typename Iterator2>
41struct join_iterator_link
42{
43public:
44 join_iterator_link(Iterator1 last1, Iterator2 first2)
45 : last1(last1)
46 , first2(first2)
47 {
48 }
49
50 Iterator1 last1;
51 Iterator2 first2;
52
53private:
54 join_iterator_link() /* = delete */ ;
55};
56
57class join_iterator_begin_tag {};
58class join_iterator_end_tag {};
59
60template<typename Iterator1
61 , typename Iterator2
62 , typename Reference
63>
64class join_iterator_union
65{
66public:
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
93private:
94 iterator1_t m_it1;
95 iterator2_t m_it2;
96};
97
98template<class Iterator, class Reference>
99class join_iterator_union<Iterator, Iterator, Reference>
100{
101public:
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
129private:
130 iterator1_t m_it;
131};
132
133template<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_reference<
157 typename add_const<
158 typename remove_reference<
159 typename iterator_reference<Iterator1>::type
160 >::type
161 >::type
162 >::type,
163 typename iterator_reference<Iterator1>::type
164 >::type
165 >::type
166 , typename Traversal = typename demote_iterator_traversal_tag<
167 typename iterator_traversal<Iterator1>::type
168 , typename iterator_traversal<Iterator2>::type>::type
169>
170class join_iterator
171 : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
172{
173 typedef join_iterator_link<Iterator1, Iterator2> link_t;
174 typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
175public:
176 typedef Iterator1 iterator1_t;
177 typedef Iterator2 iterator2_t;
178
179 join_iterator()
180 : m_section(0u)
181 , m_it(0u, iterator1_t(), iterator2_t())
182 , m_link(link_t(iterator1_t(), iterator2_t()))
183 {}
184
185 join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
186 : m_section(section)
187 , m_it(section, current1, current2)
188 , m_link(link_t(last1, first2))
189 {
190 }
191
192 template<typename Range1, typename Range2>
193 join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag)
194 : m_section(boost::empty(r1) ? 1u : 0u)
195 , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2))
196 , m_link(link_t(boost::end(r1), boost::begin(r2)))
197 {
198 }
199
200 template<typename Range1, typename Range2>
201 join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag)
202 : m_section(boost::empty(r1) ? 1u : 0u)
203 , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2))
204 , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
205 {
206 }
207
208 template<typename Range1, typename Range2>
209 join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
210 : m_section(1u)
211 , m_it(1u, boost::end(r1), boost::end(r2))
212 , m_link(link_t(boost::end(r1), boost::begin(r2)))
213 {
214 }
215
216 template<typename Range1, typename Range2>
217 join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
218 : m_section(1u)
219 , m_it(1u, boost::const_end(r1), boost::const_end(r2))
220 , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
221 {
222 }
223
224private:
225 void increment()
226 {
227 if (m_section)
228 ++m_it.it2();
229 else
230 {
231 ++m_it.it1();
232 if (m_it.it1() == m_link.last1)
233 {
234 m_it.it2() = m_link.first2;
235 m_section = 1u;
236 }
237 }
238 }
239
240 void decrement()
241 {
242 if (m_section)
243 {
244 if (m_it.it2() == m_link.first2)
245 {
246 m_it.it1() = boost::prior(m_link.last1);
247 m_section = 0u;
248 }
249 else
250 --m_it.it2();
251 }
252 else
253 --m_it.it1();
254 }
255
256 typename join_iterator::reference dereference() const
257 {
258 return m_it.dereference(m_section);
259 }
260
261 bool equal(const join_iterator& other) const
262 {
263 return m_section == other.m_section
264 && m_it.equal(other.m_it, m_section);
265 }
266
267 void advance(typename join_iterator::difference_type offset)
268 {
269 if (m_section)
270 advance_from_range2(offset);
271 else
272 advance_from_range1(offset);
273 }
274
275 typename join_iterator::difference_type distance_to(const join_iterator& other) const
276 {
277 typename join_iterator::difference_type result;
278 if (m_section)
279 {
280 if (other.m_section)
281 result = other.m_it.it2() - m_it.it2();
282 else
283 {
284 result = (m_link.first2 - m_it.it2())
285 + (other.m_it.it1() - m_link.last1);
286
287 BOOST_ASSERT( result <= 0 );
288 }
289 }
290 else
291 {
292 if (other.m_section)
293 {
294 result = (m_link.last1 - m_it.it1())
295 + (other.m_it.it2() - m_link.first2);
296 }
297 else
298 result = other.m_it.it1() - m_it.it1();
299 }
300 return result;
301 }
302
303 void advance_from_range2(typename join_iterator::difference_type offset)
304 {
305 typedef typename join_iterator::difference_type difference_t;
306 BOOST_ASSERT( m_section == 1u );
307 if (offset < 0)
308 {
309 difference_t r2_dist = m_link.first2 - m_it.it2();
310 BOOST_ASSERT( r2_dist <= 0 );
311 if (offset >= r2_dist)
312 std::advance(m_it.it2(), offset);
313 else
314 {
315 difference_t r1_dist = offset - r2_dist;
316 BOOST_ASSERT( r1_dist <= 0 );
317 m_it.it1() = m_link.last1 + r1_dist;
318 m_section = 0u;
319 }
320 }
321 else
322 std::advance(m_it.it2(), offset);
323 }
324
325 void advance_from_range1(typename join_iterator::difference_type offset)
326 {
327 typedef typename join_iterator::difference_type difference_t;
328 BOOST_ASSERT( m_section == 0u );
329 if (offset > 0)
330 {
331 difference_t r1_dist = m_link.last1 - m_it.it1();
332 BOOST_ASSERT( r1_dist >= 0 );
333 if (offset < r1_dist)
334 std::advance(m_it.it1(), offset);
335 else
336 {
337 difference_t r2_dist = offset - r1_dist;
338 BOOST_ASSERT( r2_dist >= 0 );
339 m_it.it2() = m_link.first2 + r2_dist;
340 m_section = 1u;
341 }
342 }
343 else
344 std::advance(m_it.it1(), offset);
345 }
346
347 unsigned int m_section;
348 iterator_union m_it;
349 link_t m_link;
350
351 friend class ::boost::iterator_core_access;
352};
353
354 } // namespace range_detail
355
356} // namespace boost
357
358#endif // include guard
359