join_iterator.hpp 10.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
// Boost.Range library
//
//  Copyright Neil Groves 2009. Use, modification and
//  distribution is subject to the Boost Software License, Version
//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//
// Acknowledgements:
// aschoedl contributed an improvement to the determination
// of the Reference type parameter.
//
// For more information, see http://www.boost.org/libs/range/
//
#ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
#define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED

#include <iterator>
#include <boost/assert.hpp>
#include <boost/iterator/iterator_traits.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/empty.hpp>
#include <boost/range/detail/demote_iterator_traversal_tag.hpp>
#include <boost/range/value_type.hpp>
#include <boost/next_prior.hpp>

namespace boost
{
    namespace range_detail
    {

template<typename Iterator1, typename Iterator2>
struct join_iterator_link
{
public:
    join_iterator_link(Iterator1 last1, Iterator2 first2)
        :    last1(last1)
        ,    first2(first2)
    {
    }

    Iterator1 last1;
    Iterator2 first2;

private:
    join_iterator_link() /* = delete */ ;
};

class join_iterator_begin_tag {};
class join_iterator_end_tag {};

template<typename Iterator1
       , typename Iterator2
       , typename Reference
>
class join_iterator_union
{
public:
    typedef Iterator1 iterator1_t;
    typedef Iterator2 iterator2_t;

    join_iterator_union() {}
    join_iterator_union(unsigned int /*selected*/, const iterator1_t& it1, const iterator2_t& it2) : m_it1(it1), m_it2(it2) {}

    iterator1_t& it1() { return m_it1; }
    const iterator1_t& it1() const { return m_it1; }

    iterator2_t& it2() { return m_it2; }
    const iterator2_t& it2() const { return m_it2; }

    Reference dereference(unsigned int selected) const
    {
        return selected ? *m_it2 : *m_it1;
    }

    bool equal(const join_iterator_union& other, unsigned int selected) const
    {
        return selected
            ? m_it2 == other.m_it2
            : m_it1 == other.m_it1;
    }

private:
    iterator1_t m_it1;
    iterator2_t m_it2;
};

template<class Iterator, class Reference>
class join_iterator_union<Iterator, Iterator, Reference>
{
public:
    typedef Iterator iterator1_t;
    typedef Iterator iterator2_t;

    join_iterator_union() {}

    join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
        : m_it(selected ? it2 : it1)
    {
    }

    iterator1_t& it1() { return m_it; }
    const iterator1_t& it1() const { return m_it; }

    iterator2_t& it2() { return m_it; }
    const iterator2_t& it2() const { return m_it; }

    Reference dereference(unsigned int) const
    {
        return *m_it;
    }

    bool equal(const join_iterator_union& other, unsigned int selected) const
    {
        return m_it == other.m_it;
    }

private:
    iterator1_t m_it;
};

template<typename Iterator1
       , typename Iterator2
       , typename ValueType = typename iterator_value<Iterator1>::type
       // find least demanding, commonly supported reference type, in the order &, const&, and by-value:
       , typename Reference = typename mpl::if_c<
                !is_reference<typename iterator_reference<Iterator1>::type>::value
             || !is_reference<typename iterator_reference<Iterator2>::type>::value,
                        typename remove_const<
                            typename remove_reference<
                                typename iterator_reference<Iterator1>::type
                            >::type
                        >::type,
                        typename mpl::if_c<
                            is_const<
                                typename remove_reference<
                                    typename iterator_reference<Iterator1>::type
                                >::type
                            >::value
                            || is_const<
                                typename remove_reference<
                                    typename iterator_reference<Iterator2>::type
                                >::type
                            >::value,
                            typename add_const<
                                typename iterator_reference<Iterator2>::type
                            >::type,
                            typename iterator_reference<Iterator1>::type
                        >::type
                    >::type
       , typename Traversal = typename demote_iterator_traversal_tag<
                                  typename iterator_traversal<Iterator1>::type
                                , typename iterator_traversal<Iterator2>::type>::type
>
class join_iterator
    : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
{
    typedef join_iterator_link<Iterator1, Iterator2> link_t;
    typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
public:
    typedef Iterator1 iterator1_t;
    typedef Iterator2 iterator2_t;

    join_iterator()
        : m_section(0u)
        , m_it(0u, iterator1_t(), iterator2_t())
        , m_link(link_t(iterator1_t(), iterator2_t()))
    {}

    join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
        : m_section(section)
        , m_it(section, current1, current2)
        , m_link(link_t(last1, first2))
        {
        }

    template<typename Range1, typename Range2>
    join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag)
        : m_section(boost::empty(r1) ? 1u : 0u)
        , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2))
        , m_link(link_t(boost::end(r1), boost::begin(r2)))
    {
    }

    template<typename Range1, typename Range2>
    join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag)
        : m_section(boost::empty(r1) ? 1u : 0u)
        , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2))
        , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
    {
    }

    template<typename Range1, typename Range2>
    join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
        : m_section(1u)
        , m_it(1u, boost::end(r1), boost::end(r2))
        , m_link(link_t(boost::end(r1), boost::begin(r2)))
    {
    }

    template<typename Range1, typename Range2>
    join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
        : m_section(1u)
        , m_it(1u, boost::const_end(r1), boost::const_end(r2))
        , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
    {
    }

private:
    void increment()
    {
        if (m_section)
            ++m_it.it2();
        else
        {
            ++m_it.it1();
            if (m_it.it1() == m_link.last1)
            {
                m_it.it2() = m_link.first2;
                m_section = 1u;
            }
        }
    }

    void decrement()
    {
        if (m_section)
        {
            if (m_it.it2() == m_link.first2)
            {
                m_it.it1() = boost::prior(m_link.last1);
                m_section = 0u;
            }
            else
                --m_it.it2();
        }
        else
            --m_it.it1();
    }

    typename join_iterator::reference dereference() const
    {
        return m_it.dereference(m_section);
    }

    bool equal(const join_iterator& other) const
    {
        return m_section == other.m_section
            && m_it.equal(other.m_it, m_section);
    }

    void advance(typename join_iterator::difference_type offset)
    {
        if (m_section)
            advance_from_range2(offset);
        else
            advance_from_range1(offset);
    }

    typename join_iterator::difference_type distance_to(const join_iterator& other) const
    {
        typename join_iterator::difference_type result;
        if (m_section)
        {
            if (other.m_section)
                result = other.m_it.it2() - m_it.it2();
            else
            {
                result = (m_link.first2 - m_it.it2())
                       + (other.m_it.it1() - m_link.last1);

                BOOST_ASSERT( result <= 0 );
            }
        }
        else
        {
            if (other.m_section)
            {
                result = (m_link.last1 - m_it.it1())
                       + (other.m_it.it2() - m_link.first2);
            }
            else
                result = other.m_it.it1() - m_it.it1();
        }
        return result;
    }

    void advance_from_range2(typename join_iterator::difference_type offset)
    {
        typedef typename join_iterator::difference_type difference_t;
        BOOST_ASSERT( m_section == 1u );
        if (offset < 0)
        {
            difference_t r2_dist = m_link.first2 - m_it.it2();
            BOOST_ASSERT( r2_dist <= 0 );
            if (offset >= r2_dist)
                std::advance(m_it.it2(), offset);
            else
            {
                difference_t r1_dist = offset - r2_dist;
                BOOST_ASSERT( r1_dist <= 0 );
                m_it.it1() = m_link.last1 + r1_dist;
                m_section = 0u;
            }
        }
        else
            std::advance(m_it.it2(), offset);
    }

    void advance_from_range1(typename join_iterator::difference_type offset)
    {
        typedef typename join_iterator::difference_type difference_t;
        BOOST_ASSERT( m_section == 0u );
        if (offset > 0)
        {
            difference_t r1_dist = m_link.last1 - m_it.it1();
            BOOST_ASSERT( r1_dist >= 0 );
            if (offset < r1_dist)
                std::advance(m_it.it1(), offset);
            else
            {
                difference_t r2_dist = offset - r1_dist;
                BOOST_ASSERT( r2_dist >= 0 );
                m_it.it2() = m_link.first2 + r2_dist;
                m_section = 1u;
            }
        }
        else
            std::advance(m_it.it1(), offset);
    }

    unsigned int m_section;
    iterator_union m_it;
    link_t m_link;

    friend class ::boost::iterator_core_access;
};

    } // namespace range_detail

} // namespace boost

#endif // include guard