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:
join_iterator_linkboost::range_detail::join_iterator_link44     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 
join_iterator_union()70     join_iterator_union() {}
join_iterator_union(unsigned int,const iterator1_t & it1,const iterator2_t & it2)71     join_iterator_union(unsigned int /*selected*/, const iterator1_t& it1, const iterator2_t& it2) : m_it1(it1), m_it2(it2) {}
72 
it1()73     iterator1_t& it1() { return m_it1; }
it1() const74     const iterator1_t& it1() const { return m_it1; }
75 
it2()76     iterator2_t& it2() { return m_it2; }
it2() const77     const iterator2_t& it2() const { return m_it2; }
78 
dereference(unsigned int selected) const79     Reference dereference(unsigned int selected) const
80     {
81         if (selected)
82             return *m_it2;
83         return *m_it1;
84     }
85 
equal(const join_iterator_union & other,unsigned int selected) const86     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 
join_iterator_union()105     join_iterator_union() {}
106 
join_iterator_union(unsigned int selected,const iterator1_t & it1,const iterator2_t & it2)107     join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
108         : m_it(selected ? it2 : it1)
109     {
110     }
111 
it1()112     iterator1_t& it1() { return m_it; }
it1() const113     const iterator1_t& it1() const { return m_it; }
114 
it2()115     iterator2_t& it2() { return m_it; }
it2() const116     const iterator2_t& it2() const { return m_it; }
117 
dereference(unsigned int) const118     Reference dereference(unsigned int) const
119     {
120         return *m_it;
121     }
122 
equal(const join_iterator_union & other,unsigned int) const123     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_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 >
170 class 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;
175 public:
176     typedef Iterator1 iterator1_t;
177     typedef Iterator2 iterator2_t;
178 
join_iterator()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 
join_iterator(unsigned int section,Iterator1 current1,Iterator1 last1,Iterator2 first2,Iterator2 current2)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>
join_iterator(Range1 & r1,Range2 & r2,join_iterator_begin_tag)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>
join_iterator(const Range1 & r1,const Range2 & r2,join_iterator_begin_tag)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>
join_iterator(Range1 & r1,Range2 & r2,join_iterator_end_tag)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>
join_iterator(const Range1 & r1,const Range2 & r2,join_iterator_end_tag)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 
224 private:
increment()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 
decrement()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 
dereference() const256     typename join_iterator::reference dereference() const
257     {
258         return m_it.dereference(m_section);
259     }
260 
equal(const join_iterator & other) const261     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 
advance(typename join_iterator::difference_type offset)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 
distance_to(const join_iterator & other) const275     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 
advance_from_range2(typename join_iterator::difference_type offset)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 
advance_from_range1(typename join_iterator::difference_type offset)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