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