Chris@16: // Boost.Range library
Chris@16: //
Chris@16: //  Copyright Neil Groves 2009. Use, modification and
Chris@16: //  distribution is subject to the Boost Software License, Version
Chris@16: //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // Acknowledgements:
Chris@16: // aschoedl contributed an improvement to the determination
Chris@16: // of the Reference type parameter.
Chris@16: //
Chris@101: // Leonid Gershanovich reported Trac ticket 7376 about the dereference operator
Chris@101: // requiring identical reference types due to using the ternary if.
Chris@101: //
Chris@16: // For more information, see http://www.boost.org/libs/range/
Chris@16: //
Chris@16: #ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
Chris@16: #define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
Chris@16: 
Chris@16: #include <iterator>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/iterator/iterator_traits.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/range/begin.hpp>
Chris@16: #include <boost/range/end.hpp>
Chris@16: #include <boost/range/empty.hpp>
Chris@16: #include <boost/range/detail/demote_iterator_traversal_tag.hpp>
Chris@16: #include <boost/range/value_type.hpp>
Chris@101: #include <boost/type_traits/add_const.hpp>
Chris@101: #include <boost/type_traits/add_reference.hpp>
Chris@101: #include <boost/type_traits/remove_const.hpp>
Chris@101: #include <boost/type_traits/remove_reference.hpp>
Chris@16: #include <boost/next_prior.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:     namespace range_detail
Chris@16:     {
Chris@16: 
Chris@16: template<typename Iterator1, typename Iterator2>
Chris@16: struct join_iterator_link
Chris@16: {
Chris@16: public:
Chris@16:     join_iterator_link(Iterator1 last1, Iterator2 first2)
Chris@16:         :    last1(last1)
Chris@16:         ,    first2(first2)
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     Iterator1 last1;
Chris@16:     Iterator2 first2;
Chris@16: 
Chris@16: private:
Chris@16:     join_iterator_link() /* = delete */ ;
Chris@16: };
Chris@16: 
Chris@16: class join_iterator_begin_tag {};
Chris@16: class join_iterator_end_tag {};
Chris@16: 
Chris@16: template<typename Iterator1
Chris@16:        , typename Iterator2
Chris@16:        , typename Reference
Chris@16: >
Chris@16: class join_iterator_union
Chris@16: {
Chris@16: public:
Chris@16:     typedef Iterator1 iterator1_t;
Chris@16:     typedef Iterator2 iterator2_t;
Chris@16: 
Chris@16:     join_iterator_union() {}
Chris@16:     join_iterator_union(unsigned int /*selected*/, const iterator1_t& it1, const iterator2_t& it2) : m_it1(it1), m_it2(it2) {}
Chris@16: 
Chris@16:     iterator1_t& it1() { return m_it1; }
Chris@16:     const iterator1_t& it1() const { return m_it1; }
Chris@16: 
Chris@16:     iterator2_t& it2() { return m_it2; }
Chris@16:     const iterator2_t& it2() const { return m_it2; }
Chris@16: 
Chris@16:     Reference dereference(unsigned int selected) const
Chris@16:     {
Chris@101:         if (selected)
Chris@101:             return *m_it2;
Chris@101:         return *m_it1;
Chris@16:     }
Chris@16: 
Chris@16:     bool equal(const join_iterator_union& other, unsigned int selected) const
Chris@16:     {
Chris@16:         return selected
Chris@16:             ? m_it2 == other.m_it2
Chris@16:             : m_it1 == other.m_it1;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     iterator1_t m_it1;
Chris@16:     iterator2_t m_it2;
Chris@16: };
Chris@16: 
Chris@16: template<class Iterator, class Reference>
Chris@16: class join_iterator_union<Iterator, Iterator, Reference>
Chris@16: {
Chris@16: public:
Chris@16:     typedef Iterator iterator1_t;
Chris@16:     typedef Iterator iterator2_t;
Chris@16: 
Chris@16:     join_iterator_union() {}
Chris@16: 
Chris@16:     join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
Chris@16:         : m_it(selected ? it2 : it1)
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     iterator1_t& it1() { return m_it; }
Chris@16:     const iterator1_t& it1() const { return m_it; }
Chris@16: 
Chris@16:     iterator2_t& it2() { return m_it; }
Chris@16:     const iterator2_t& it2() const { return m_it; }
Chris@16: 
Chris@16:     Reference dereference(unsigned int) const
Chris@16:     {
Chris@16:         return *m_it;
Chris@16:     }
Chris@16: 
Chris@101:     bool equal(const join_iterator_union& other,
Chris@101:                unsigned int /*selected*/) const
Chris@16:     {
Chris@16:         return m_it == other.m_it;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     iterator1_t m_it;
Chris@16: };
Chris@16: 
Chris@16: template<typename Iterator1
Chris@16:        , typename Iterator2
Chris@16:        , typename ValueType = typename iterator_value<Iterator1>::type
Chris@16:        // find least demanding, commonly supported reference type, in the order &, const&, and by-value:
Chris@16:        , typename Reference = typename mpl::if_c<
Chris@16:                 !is_reference<typename iterator_reference<Iterator1>::type>::value
Chris@16:              || !is_reference<typename iterator_reference<Iterator2>::type>::value,
Chris@16:                         typename remove_const<
Chris@16:                             typename remove_reference<
Chris@16:                                 typename iterator_reference<Iterator1>::type
Chris@16:                             >::type
Chris@16:                         >::type,
Chris@16:                         typename mpl::if_c<
Chris@16:                             is_const<
Chris@16:                                 typename remove_reference<
Chris@16:                                     typename iterator_reference<Iterator1>::type
Chris@16:                                 >::type
Chris@16:                             >::value
Chris@16:                             || is_const<
Chris@16:                                 typename remove_reference<
Chris@16:                                     typename iterator_reference<Iterator2>::type
Chris@16:                                 >::type
Chris@16:                             >::value,
Chris@16:                             typename add_const<
Chris@101:                                 typename iterator_reference<Iterator1>::type
Chris@16:                             >::type,
Chris@16:                             typename iterator_reference<Iterator1>::type
Chris@16:                         >::type
Chris@16:                     >::type
Chris@16:        , typename Traversal = typename demote_iterator_traversal_tag<
Chris@16:                                   typename iterator_traversal<Iterator1>::type
Chris@16:                                 , typename iterator_traversal<Iterator2>::type>::type
Chris@16: >
Chris@16: class join_iterator
Chris@16:     : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
Chris@16: {
Chris@16:     typedef join_iterator_link<Iterator1, Iterator2> link_t;
Chris@16:     typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
Chris@16: public:
Chris@16:     typedef Iterator1 iterator1_t;
Chris@16:     typedef Iterator2 iterator2_t;
Chris@16: 
Chris@16:     join_iterator()
Chris@16:         : m_section(0u)
Chris@16:         , m_it(0u, iterator1_t(), iterator2_t())
Chris@16:         , m_link(link_t(iterator1_t(), iterator2_t()))
Chris@16:     {}
Chris@16: 
Chris@16:     join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
Chris@16:         : m_section(section)
Chris@16:         , m_it(section, current1, current2)
Chris@16:         , m_link(link_t(last1, first2))
Chris@16:         {
Chris@16:         }
Chris@16: 
Chris@16:     template<typename Range1, typename Range2>
Chris@16:     join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag)
Chris@16:         : m_section(boost::empty(r1) ? 1u : 0u)
Chris@16:         , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2))
Chris@16:         , m_link(link_t(boost::end(r1), boost::begin(r2)))
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Range1, typename Range2>
Chris@16:     join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag)
Chris@16:         : m_section(boost::empty(r1) ? 1u : 0u)
Chris@16:         , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2))
Chris@16:         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Range1, typename Range2>
Chris@16:     join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
Chris@16:         : m_section(1u)
Chris@16:         , m_it(1u, boost::end(r1), boost::end(r2))
Chris@16:         , m_link(link_t(boost::end(r1), boost::begin(r2)))
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Range1, typename Range2>
Chris@16:     join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
Chris@16:         : m_section(1u)
Chris@16:         , m_it(1u, boost::const_end(r1), boost::const_end(r2))
Chris@16:         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     void increment()
Chris@16:     {
Chris@16:         if (m_section)
Chris@16:             ++m_it.it2();
Chris@16:         else
Chris@16:         {
Chris@16:             ++m_it.it1();
Chris@16:             if (m_it.it1() == m_link.last1)
Chris@16:             {
Chris@16:                 m_it.it2() = m_link.first2;
Chris@16:                 m_section = 1u;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void decrement()
Chris@16:     {
Chris@16:         if (m_section)
Chris@16:         {
Chris@16:             if (m_it.it2() == m_link.first2)
Chris@16:             {
Chris@16:                 m_it.it1() = boost::prior(m_link.last1);
Chris@16:                 m_section = 0u;
Chris@16:             }
Chris@16:             else
Chris@16:                 --m_it.it2();
Chris@16:         }
Chris@16:         else
Chris@16:             --m_it.it1();
Chris@16:     }
Chris@16: 
Chris@16:     typename join_iterator::reference dereference() const
Chris@16:     {
Chris@16:         return m_it.dereference(m_section);
Chris@16:     }
Chris@16: 
Chris@16:     bool equal(const join_iterator& other) const
Chris@16:     {
Chris@16:         return m_section == other.m_section
Chris@16:             && m_it.equal(other.m_it, m_section);
Chris@16:     }
Chris@16: 
Chris@16:     void advance(typename join_iterator::difference_type offset)
Chris@16:     {
Chris@16:         if (m_section)
Chris@16:             advance_from_range2(offset);
Chris@16:         else
Chris@16:             advance_from_range1(offset);
Chris@16:     }
Chris@16: 
Chris@16:     typename join_iterator::difference_type distance_to(const join_iterator& other) const
Chris@16:     {
Chris@16:         typename join_iterator::difference_type result;
Chris@16:         if (m_section)
Chris@16:         {
Chris@16:             if (other.m_section)
Chris@16:                 result = other.m_it.it2() - m_it.it2();
Chris@16:             else
Chris@16:             {
Chris@16:                 result = (m_link.first2 - m_it.it2())
Chris@16:                        + (other.m_it.it1() - m_link.last1);
Chris@16: 
Chris@16:                 BOOST_ASSERT( result <= 0 );
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             if (other.m_section)
Chris@16:             {
Chris@16:                 result = (m_link.last1 - m_it.it1())
Chris@16:                        + (other.m_it.it2() - m_link.first2);
Chris@16:             }
Chris@16:             else
Chris@16:                 result = other.m_it.it1() - m_it.it1();
Chris@16:         }
Chris@16:         return result;
Chris@16:     }
Chris@16: 
Chris@16:     void advance_from_range2(typename join_iterator::difference_type offset)
Chris@16:     {
Chris@16:         typedef typename join_iterator::difference_type difference_t;
Chris@16:         BOOST_ASSERT( m_section == 1u );
Chris@16:         if (offset < 0)
Chris@16:         {
Chris@16:             difference_t r2_dist = m_link.first2 - m_it.it2();
Chris@16:             BOOST_ASSERT( r2_dist <= 0 );
Chris@16:             if (offset >= r2_dist)
Chris@16:                 std::advance(m_it.it2(), offset);
Chris@16:             else
Chris@16:             {
Chris@16:                 difference_t r1_dist = offset - r2_dist;
Chris@16:                 BOOST_ASSERT( r1_dist <= 0 );
Chris@16:                 m_it.it1() = m_link.last1 + r1_dist;
Chris@16:                 m_section = 0u;
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:             std::advance(m_it.it2(), offset);
Chris@16:     }
Chris@16: 
Chris@16:     void advance_from_range1(typename join_iterator::difference_type offset)
Chris@16:     {
Chris@16:         typedef typename join_iterator::difference_type difference_t;
Chris@16:         BOOST_ASSERT( m_section == 0u );
Chris@16:         if (offset > 0)
Chris@16:         {
Chris@16:             difference_t r1_dist = m_link.last1 - m_it.it1();
Chris@16:             BOOST_ASSERT( r1_dist >= 0 );
Chris@16:             if (offset < r1_dist)
Chris@16:                 std::advance(m_it.it1(), offset);
Chris@16:             else
Chris@16:             {
Chris@16:                 difference_t r2_dist = offset - r1_dist;
Chris@16:                 BOOST_ASSERT( r2_dist >= 0 );
Chris@16:                 m_it.it2() = m_link.first2 + r2_dist;
Chris@16:                 m_section = 1u;
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:             std::advance(m_it.it1(), offset);
Chris@16:     }
Chris@16: 
Chris@16:     unsigned int m_section;
Chris@16:     iterator_union m_it;
Chris@16:     link_t m_link;
Chris@16: 
Chris@16:     friend class ::boost::iterator_core_access;
Chris@16: };
Chris@16: 
Chris@16:     } // namespace range_detail
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // include guard