range/detail/join_iterator.hpp

0001 // Boost.Range library
0002 //
0003 //  Copyright Neil Groves 2009. Use, modification and
0004 //  distribution is subject to the Boost Software License, Version
0005 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // Acknowledgements:
0009 // aschoedl contributed an improvement to the determination
0010 // of the Reference type parameter.
0011 //
0012 // Leonid Gershanovich reported Trac ticket 7376 about the dereference operator
0013 // requiring identical reference types due to using the ternary if.
0014 //
0015 // For more information, see http://www.boost.org/libs/range/
0016 //
0017 #ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
0018 #define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
0019
0020 #include <iterator>
0021 #include <boost/assert.hpp>
0022 #include <boost/mpl/if.hpp>
0023 #include <boost/iterator/iterator_traits.hpp>
0024 #include <boost/iterator/iterator_facade.hpp>
0025 #include <boost/range/begin.hpp>
0026 #include <boost/range/end.hpp>
0027 #include <boost/range/empty.hpp>
0028 #include <boost/range/detail/demote_iterator_traversal_tag.hpp>
0029 #include <boost/range/value_type.hpp>
0030 #include <boost/type_traits/add_const.hpp>
0031 #include <boost/type_traits/add_reference.hpp>
0032 #include <boost/type_traits/remove_const.hpp>
0033 #include <boost/type_traits/remove_reference.hpp>
0034 #include <boost/next_prior.hpp>
0035
0036 namespace boost
0037 {
0038     namespace range_detail
0039     {
0040
0041 template<typename Iterator1, typename Iterator2>
0042 struct join_iterator_link
0043 {
0044 public:
0045     join_iterator_link(Iterator1 last1, Iterator2 first2)
0046         :    last1(last1)
0047         ,    first2(first2)
0048     {
0049     }
0050
0051     Iterator1 last1;
0052     Iterator2 first2;
0053
0054 private:
0055     join_iterator_link() /* = delete */ ;
0056 };
0057
0058 class join_iterator_begin_tag {};
0059 class join_iterator_end_tag {};
0060
0061 template<typename Iterator1
0062        , typename Iterator2
0063        , typename Reference
0064 >
0065 class join_iterator_union
0066 {
0067 public:
0068     typedef Iterator1 iterator1_t;
0069     typedef Iterator2 iterator2_t;
0070
0071     join_iterator_union() {}
0072     join_iterator_union(unsigned int /*selected*/, const iterator1_t& it1, const iterator2_t& it2) : m_it1(it1), m_it2(it2) {}
0073
0074     iterator1_t& it1() { return m_it1; }
0075     const iterator1_t& it1() const { return m_it1; }
0076
0077     iterator2_t& it2() { return m_it2; }
0078     const iterator2_t& it2() const { return m_it2; }
0079
0080     Reference dereference(unsigned int selected) const
0081     {
0082         if (selected)
0083             return *m_it2;
0084         return *m_it1;
0085     }
0086
0087     bool equal(const join_iterator_union& other, unsigned int selected) const
0088     {
0089         return selected
0090             ? m_it2 == other.m_it2
0091             : m_it1 == other.m_it1;
0092     }
0093
0094 private:
0095     iterator1_t m_it1;
0096     iterator2_t m_it2;
0097 };
0098
0099 template<class Iterator, class Reference>
0100 class join_iterator_union<Iterator, Iterator, Reference>
0101 {
0102 public:
0103     typedef Iterator iterator1_t;
0104     typedef Iterator iterator2_t;
0105
0106     join_iterator_union() {}
0107
0108     join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
0109         : m_it(selected ? it2 : it1)
0110     {
0111     }
0112
0113     iterator1_t& it1() { return m_it; }
0114     const iterator1_t& it1() const { return m_it; }
0115
0116     iterator2_t& it2() { return m_it; }
0117     const iterator2_t& it2() const { return m_it; }
0118
0119     Reference dereference(unsigned int) const
0120     {
0121         return *m_it;
0122     }
0123
0124     bool equal(const join_iterator_union& other,
0125                unsigned int /*selected*/) const
0126     {
0127         return m_it == other.m_it;
0128     }
0129
0130 private:
0131     iterator1_t m_it;
0132 };
0133
0134 template<typename Iterator1
0135        , typename Iterator2
0136        , typename ValueType = typename iterator_value<Iterator1>::type
0137        // find least demanding, commonly supported reference type, in the order &, const&, and by-value:
0138        , typename Reference = typename mpl::if_c<
0139                 !is_reference<typename iterator_reference<Iterator1>::type>::value
0140              || !is_reference<typename iterator_reference<Iterator2>::type>::value,
0141                         typename remove_const<
0142                             typename remove_reference<
0143                                 typename iterator_reference<Iterator1>::type
0144                             >::type
0145                         >::type,
0146                         typename mpl::if_c<
0147                             is_const<
0148                                 typename remove_reference<
0149                                     typename iterator_reference<Iterator1>::type
0150                                 >::type
0151                             >::value
0152                             || is_const<
0153                                 typename remove_reference<
0154                                     typename iterator_reference<Iterator2>::type
0155                                 >::type
0156                             >::value,
0157                             typename add_reference<
0158                                 typename add_const<
0159                                     typename remove_reference<
0160                                         typename iterator_reference<Iterator1>::type
0161                                     >::type
0162                                 >::type
0163                             >::type,
0164                             typename iterator_reference<Iterator1>::type
0165                         >::type
0166                     >::type
0167        , typename Traversal = typename demote_iterator_traversal_tag<
0168                                   typename iterator_traversal<Iterator1>::type
0169                                 , typename iterator_traversal<Iterator2>::type>::type
0170 >
0171 class join_iterator
0172     : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
0173 {
0174     typedef join_iterator_link<Iterator1, Iterator2> link_t;
0175     typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
0176 public:
0177     typedef Iterator1 iterator1_t;
0178     typedef Iterator2 iterator2_t;
0179
0180     join_iterator()
0181         : m_section(0u)
0182         , m_it(0u, iterator1_t(), iterator2_t())
0183         , m_link(link_t(iterator1_t(), iterator2_t()))
0184     {}
0185
0186     join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
0187         : m_section(section)
0188         , m_it(section, current1, current2)
0189         , m_link(link_t(last1, first2))
0190         {
0191         }
0192
0193     template<typename Range1, typename Range2>
0194     join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag)
0195         : m_section(boost::empty(r1) ? 1u : 0u)
0196         , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2))
0197         , m_link(link_t(boost::end(r1), boost::begin(r2)))
0198     {
0199     }
0200
0201     template<typename Range1, typename Range2>
0202     join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag)
0203         : m_section(boost::empty(r1) ? 1u : 0u)
0204         , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2))
0205         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
0206     {
0207     }
0208
0209     template<typename Range1, typename Range2>
0210     join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
0211         : m_section(1u)
0212         , m_it(1u, boost::end(r1), boost::end(r2))
0213         , m_link(link_t(boost::end(r1), boost::begin(r2)))
0214     {
0215     }
0216
0217     template<typename Range1, typename Range2>
0218     join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
0219         : m_section(1u)
0220         , m_it(1u, boost::const_end(r1), boost::const_end(r2))
0221         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
0222     {
0223     }
0224
0225 private:
0226     void increment()
0227     {
0228         if (m_section)
0229             ++m_it.it2();
0230         else
0231         {
0232             ++m_it.it1();
0233             if (m_it.it1() == m_link.last1)
0234             {
0235                 m_it.it2() = m_link.first2;
0236                 m_section = 1u;
0237             }
0238         }
0239     }
0240
0241     void decrement()
0242     {
0243         if (m_section)
0244         {
0245             if (m_it.it2() == m_link.first2)
0246             {
0247                 m_it.it1() = boost::prior(m_link.last1);
0248                 m_section = 0u;
0249             }
0250             else
0251                 --m_it.it2();
0252         }
0253         else
0254             --m_it.it1();
0255     }
0256
0257     typename join_iterator::reference dereference() const
0258     {
0259         return m_it.dereference(m_section);
0260     }
0261
0262     bool equal(const join_iterator& other) const
0263     {
0264         return m_section == other.m_section
0265             && m_it.equal(other.m_it, m_section);
0266     }
0267
0268     void advance(typename join_iterator::difference_type offset)
0269     {
0270         if (m_section)
0271             advance_from_range2(offset);
0272         else
0273             advance_from_range1(offset);
0274     }
0275
0276     typename join_iterator::difference_type distance_to(const join_iterator& other) const
0277     {
0278         typename join_iterator::difference_type result;
0279         if (m_section)
0280         {
0281             if (other.m_section)
0282                 result = other.m_it.it2() - m_it.it2();
0283             else
0284             {
0285                 result = (m_link.first2 - m_it.it2())
0286                        + (other.m_it.it1() - m_link.last1);
0287
0288                 BOOST_ASSERT( result <= 0 );
0289             }
0290         }
0291         else
0292         {
0293             if (other.m_section)
0294             {
0295                 result = (m_link.last1 - m_it.it1())
0296                        + (other.m_it.it2() - m_link.first2);
0297             }
0298             else
0299                 result = other.m_it.it1() - m_it.it1();
0300         }
0301         return result;
0302     }
0303
0304     void advance_from_range2(typename join_iterator::difference_type offset)
0305     {
0306         typedef typename join_iterator::difference_type difference_t;
0307         BOOST_ASSERT( m_section == 1u );
0308         if (offset < 0)
0309         {
0310             difference_t r2_dist = m_link.first2 - m_it.it2();
0311             BOOST_ASSERT( r2_dist <= 0 );
0312             if (offset >= r2_dist)
0313                 std::advance(m_it.it2(), offset);
0314             else
0315             {
0316                 difference_t r1_dist = offset - r2_dist;
0317                 BOOST_ASSERT( r1_dist <= 0 );
0318                 m_it.it1() = m_link.last1 + r1_dist;
0319                 m_section = 0u;
0320             }
0321         }
0322         else
0323             std::advance(m_it.it2(), offset);
0324     }
0325
0326     void advance_from_range1(typename join_iterator::difference_type offset)
0327     {
0328         typedef typename join_iterator::difference_type difference_t;
0329         BOOST_ASSERT( m_section == 0u );
0330         if (offset > 0)
0331         {
0332             difference_t r1_dist = m_link.last1 - m_it.it1();
0333             BOOST_ASSERT( r1_dist >= 0 );
0334             if (offset < r1_dist)
0335                 std::advance(m_it.it1(), offset);
0336             else
0337             {
0338                 difference_t r2_dist = offset - r1_dist;
0339                 BOOST_ASSERT( r2_dist >= 0 );
0340                 m_it.it2() = m_link.first2 + r2_dist;
0341                 m_section = 1u;
0342             }
0343         }
0344         else
0345             std::advance(m_it.it1(), offset);
0346     }
0347
0348     unsigned int m_section;
0349     iterator_union m_it;
0350     link_t m_link;
0351
0352     friend class ::boost::iterator_core_access;
0353 };
0354
0355     } // namespace range_detail
0356
0357 } // namespace boost
0358
0359 #endif // include guard