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)
9 // aschoedl contributed an improvement to the determination
10 // of the Reference type parameter.
12 // Leonid Gershanovich reported Trac ticket 7376 about the dereference operator
13 // requiring identical reference types due to using the ternary if.
15 // For more information, see http://www.boost.org/libs/range/
17 #ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
18 #define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
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>
37 namespace range_detail
40 template<typename Iterator1, typename Iterator2>
41 struct join_iterator_link
44 join_iterator_link(Iterator1 last1, Iterator2 first2)
54 join_iterator_link() /* = delete */ ;
57 class join_iterator_begin_tag {};
58 class join_iterator_end_tag {};
60 template<typename Iterator1
64 class join_iterator_union
67 typedef Iterator1 iterator1_t;
68 typedef Iterator2 iterator2_t;
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) {}
73 iterator1_t& it1() { return m_it1; }
74 const iterator1_t& it1() const { return m_it1; }
76 iterator2_t& it2() { return m_it2; }
77 const iterator2_t& it2() const { return m_it2; }
79 Reference dereference(unsigned int selected) const
86 bool equal(const join_iterator_union& other, unsigned int selected) const
89 ? m_it2 == other.m_it2
90 : m_it1 == other.m_it1;
98 template<class Iterator, class Reference>
99 class join_iterator_union<Iterator, Iterator, Reference>
102 typedef Iterator iterator1_t;
103 typedef Iterator iterator2_t;
105 join_iterator_union() {}
107 join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
108 : m_it(selected ? it2 : it1)
112 iterator1_t& it1() { return m_it; }
113 const iterator1_t& it1() const { return m_it; }
115 iterator2_t& it2() { return m_it; }
116 const iterator2_t& it2() const { return m_it; }
118 Reference dereference(unsigned int) const
123 bool equal(const join_iterator_union& other,
124 unsigned int /*selected*/) const
126 return m_it == other.m_it;
133 template<typename Iterator1
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
147 typename remove_reference<
148 typename iterator_reference<Iterator1>::type
152 typename remove_reference<
153 typename iterator_reference<Iterator2>::type
157 typename iterator_reference<Iterator1>::type
159 typename iterator_reference<Iterator1>::type
162 , typename Traversal = typename demote_iterator_traversal_tag<
163 typename iterator_traversal<Iterator1>::type
164 , typename iterator_traversal<Iterator2>::type>::type
167 : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
169 typedef join_iterator_link<Iterator1, Iterator2> link_t;
170 typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
172 typedef Iterator1 iterator1_t;
173 typedef Iterator2 iterator2_t;
177 , m_it(0u, iterator1_t(), iterator2_t())
178 , m_link(link_t(iterator1_t(), iterator2_t()))
181 join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
183 , m_it(section, current1, current2)
184 , m_link(link_t(last1, first2))
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)))
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)))
204 template<typename Range1, typename Range2>
205 join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
207 , m_it(1u, boost::end(r1), boost::end(r2))
208 , m_link(link_t(boost::end(r1), boost::begin(r2)))
212 template<typename Range1, typename Range2>
213 join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
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)))
228 if (m_it.it1() == m_link.last1)
230 m_it.it2() = m_link.first2;
240 if (m_it.it2() == m_link.first2)
242 m_it.it1() = boost::prior(m_link.last1);
252 typename join_iterator::reference dereference() const
254 return m_it.dereference(m_section);
257 bool equal(const join_iterator& other) const
259 return m_section == other.m_section
260 && m_it.equal(other.m_it, m_section);
263 void advance(typename join_iterator::difference_type offset)
266 advance_from_range2(offset);
268 advance_from_range1(offset);
271 typename join_iterator::difference_type distance_to(const join_iterator& other) const
273 typename join_iterator::difference_type result;
277 result = other.m_it.it2() - m_it.it2();
280 result = (m_link.first2 - m_it.it2())
281 + (other.m_it.it1() - m_link.last1);
283 BOOST_ASSERT( result <= 0 );
290 result = (m_link.last1 - m_it.it1())
291 + (other.m_it.it2() - m_link.first2);
294 result = other.m_it.it1() - m_it.it1();
299 void advance_from_range2(typename join_iterator::difference_type offset)
301 typedef typename join_iterator::difference_type difference_t;
302 BOOST_ASSERT( m_section == 1u );
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);
311 difference_t r1_dist = offset - r2_dist;
312 BOOST_ASSERT( r1_dist <= 0 );
313 m_it.it1() = m_link.last1 + r1_dist;
318 std::advance(m_it.it2(), offset);
321 void advance_from_range1(typename join_iterator::difference_type offset)
323 typedef typename join_iterator::difference_type difference_t;
324 BOOST_ASSERT( m_section == 0u );
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);
333 difference_t r2_dist = offset - r1_dist;
334 BOOST_ASSERT( r2_dist >= 0 );
335 m_it.it2() = m_link.first2 + r2_dist;
340 std::advance(m_it.it1(), offset);
343 unsigned int m_section;
347 friend class ::boost::iterator_core_access;
350 } // namespace range_detail
354 #endif // include guard