ceph/src/boost/boost/range/detail/join_iterator.hpp

   1 // Boost.Range library
   2 //
   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)
   7 //
   8 // Acknowledgements:
   9 // aschoedl contributed an improvement to the determination
  10 // of the Reference type parameter.
  11 //
  12 // Leonid Gershanovich reported Trac ticket 7376 about the dereference operator
  13 // requiring identical reference types due to using the ternary if.
  14 //
  15 // For more information, see http://www.boost.org/libs/range/
  16 //
  17 #ifndef BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
  18 #define BOOST_RANGE_DETAIL_JOIN_ITERATOR_HPP_INCLUDED
  19
  20 #include <iterator>
  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>
  34
  35 namespace boost
  36 {
  37     namespace range_detail
  38     {
  39
  40 template<typename Iterator1, typename Iterator2>
  41 struct join_iterator_link
  42 {
  43 public:
  44     join_iterator_link(Iterator1 last1, Iterator2 first2)
  45         :    last1(last1)
  46         ,    first2(first2)
  47     {
  48     }
  49
  50     Iterator1 last1;
  51     Iterator2 first2;
  52
  53 private:
  54     join_iterator_link() /* = delete */ ;
  55 };
  56
  57 class join_iterator_begin_tag {};
  58 class join_iterator_end_tag {};
  59
  60 template<typename Iterator1
  61        , typename Iterator2
  62        , typename Reference
  63 >
  64 class join_iterator_union
  65 {
  66 public:
  67     typedef Iterator1 iterator1_t;
  68     typedef Iterator2 iterator2_t;
  69
  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) {}
  72
  73     iterator1_t& it1() { return m_it1; }
  74     const iterator1_t& it1() const { return m_it1; }
  75
  76     iterator2_t& it2() { return m_it2; }
  77     const iterator2_t& it2() const { return m_it2; }
  78
  79     Reference dereference(unsigned int selected) const
  80     {
  81         if (selected)
  82             return *m_it2;
  83         return *m_it1;
  84     }
  85
  86     bool equal(const join_iterator_union& other, unsigned int selected) const
  87     {
  88         return selected
  89             ? m_it2 == other.m_it2
  90             : m_it1 == other.m_it1;
  91     }
  92
  93 private:
  94     iterator1_t m_it1;
  95     iterator2_t m_it2;
  96 };
  97
  98 template<class Iterator, class Reference>
  99 class join_iterator_union<Iterator, Iterator, Reference>
 100 {
 101 public:
 102     typedef Iterator iterator1_t;
 103     typedef Iterator iterator2_t;
 104
 105     join_iterator_union() {}
 106
 107     join_iterator_union(unsigned int selected, const iterator1_t& it1, const iterator2_t& it2)
 108         : m_it(selected ? it2 : it1)
 109     {
 110     }
 111
 112     iterator1_t& it1() { return m_it; }
 113     const iterator1_t& it1() const { return m_it; }
 114
 115     iterator2_t& it2() { return m_it; }
 116     const iterator2_t& it2() const { return m_it; }
 117
 118     Reference dereference(unsigned int) const
 119     {
 120         return *m_it;
 121     }
 122
 123     bool equal(const join_iterator_union& other,
 124                unsigned int /*selected*/) const
 125     {
 126         return m_it == other.m_it;
 127     }
 128
 129 private:
 130     iterator1_t m_it;
 131 };
 132
 133 template<typename Iterator1
 134        , typename Iterator2
 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
 143                             >::type
 144                         >::type,
 145                         typename mpl::if_c<
 146                             is_const<
 147                                 typename remove_reference<
 148                                     typename iterator_reference<Iterator1>::type
 149                                 >::type
 150                             >::value
 151                             || is_const<
 152                                 typename remove_reference<
 153                                     typename iterator_reference<Iterator2>::type
 154                                 >::type
 155                             >::value,
 156                             typename add_reference<
 157                                 typename add_const<
 158                                     typename remove_reference<
 159                                         typename iterator_reference<Iterator1>::type
 160                                     >::type
 161                                 >::type
 162                             >::type,
 163                             typename iterator_reference<Iterator1>::type
 164                         >::type
 165                     >::type
 166        , typename Traversal = typename demote_iterator_traversal_tag<
 167                                   typename iterator_traversal<Iterator1>::type
 168                                 , typename iterator_traversal<Iterator2>::type>::type
 169 >
 170 class join_iterator
 171     : public iterator_facade<join_iterator<Iterator1,Iterator2,ValueType,Reference,Traversal>, ValueType, Traversal, Reference>
 172 {
 173     typedef join_iterator_link<Iterator1, Iterator2> link_t;
 174     typedef join_iterator_union<Iterator1, Iterator2, Reference> iterator_union;
 175 public:
 176     typedef Iterator1 iterator1_t;
 177     typedef Iterator2 iterator2_t;
 178
 179     join_iterator()
 180         : m_section(0u)
 181         , m_it(0u, iterator1_t(), iterator2_t())
 182         , m_link(link_t(iterator1_t(), iterator2_t()))
 183     {}
 184
 185     join_iterator(unsigned int section, Iterator1 current1, Iterator1 last1, Iterator2 first2, Iterator2 current2)
 186         : m_section(section)
 187         , m_it(section, current1, current2)
 188         , m_link(link_t(last1, first2))
 189         {
 190         }
 191
 192     template<typename Range1, typename Range2>
 193     join_iterator(Range1& r1, Range2& r2, join_iterator_begin_tag)
 194         : m_section(boost::empty(r1) ? 1u : 0u)
 195         , m_it(boost::empty(r1) ? 1u : 0u, boost::begin(r1), boost::begin(r2))
 196         , m_link(link_t(boost::end(r1), boost::begin(r2)))
 197     {
 198     }
 199
 200     template<typename Range1, typename Range2>
 201     join_iterator(const Range1& r1, const Range2& r2, join_iterator_begin_tag)
 202         : m_section(boost::empty(r1) ? 1u : 0u)
 203         , m_it(boost::empty(r1) ? 1u : 0u, boost::const_begin(r1), boost::const_begin(r2))
 204         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
 205     {
 206     }
 207
 208     template<typename Range1, typename Range2>
 209     join_iterator(Range1& r1, Range2& r2, join_iterator_end_tag)
 210         : m_section(1u)
 211         , m_it(1u, boost::end(r1), boost::end(r2))
 212         , m_link(link_t(boost::end(r1), boost::begin(r2)))
 213     {
 214     }
 215
 216     template<typename Range1, typename Range2>
 217     join_iterator(const Range1& r1, const Range2& r2, join_iterator_end_tag)
 218         : m_section(1u)
 219         , m_it(1u, boost::const_end(r1), boost::const_end(r2))
 220         , m_link(link_t(boost::const_end(r1), boost::const_begin(r2)))
 221     {
 222     }
 223
 224 private:
 225     void increment()
 226     {
 227         if (m_section)
 228             ++m_it.it2();
 229         else
 230         {
 231             ++m_it.it1();
 232             if (m_it.it1() == m_link.last1)
 233             {
 234                 m_it.it2() = m_link.first2;
 235                 m_section = 1u;
 236             }
 237         }
 238     }
 239
 240     void decrement()
 241     {
 242         if (m_section)
 243         {
 244             if (m_it.it2() == m_link.first2)
 245             {
 246                 m_it.it1() = boost::prior(m_link.last1);
 247                 m_section = 0u;
 248             }
 249             else
 250                 --m_it.it2();
 251         }
 252         else
 253             --m_it.it1();
 254     }
 255
 256     typename join_iterator::reference dereference() const
 257     {
 258         return m_it.dereference(m_section);
 259     }
 260
 261     bool equal(const join_iterator& other) const
 262     {
 263         return m_section == other.m_section
 264             && m_it.equal(other.m_it, m_section);
 265     }
 266
 267     void advance(typename join_iterator::difference_type offset)
 268     {
 269         if (m_section)
 270             advance_from_range2(offset);
 271         else
 272             advance_from_range1(offset);
 273     }
 274
 275     typename join_iterator::difference_type distance_to(const join_iterator& other) const
 276     {
 277         typename join_iterator::difference_type result;
 278         if (m_section)
 279         {
 280             if (other.m_section)
 281                 result = other.m_it.it2() - m_it.it2();
 282             else
 283             {
 284                 result = (m_link.first2 - m_it.it2())
 285                        + (other.m_it.it1() - m_link.last1);
 286
 287                 BOOST_ASSERT( result <= 0 );
 288             }
 289         }
 290         else
 291         {
 292             if (other.m_section)
 293             {
 294                 result = (m_link.last1 - m_it.it1())
 295                        + (other.m_it.it2() - m_link.first2);
 296             }
 297             else
 298                 result = other.m_it.it1() - m_it.it1();
 299         }
 300         return result;
 301     }
 302
 303     void advance_from_range2(typename join_iterator::difference_type offset)
 304     {
 305         typedef typename join_iterator::difference_type difference_t;
 306         BOOST_ASSERT( m_section == 1u );
 307         if (offset < 0)
 308         {
 309             difference_t r2_dist = m_link.first2 - m_it.it2();
 310             BOOST_ASSERT( r2_dist <= 0 );
 311             if (offset >= r2_dist)
 312                 std::advance(m_it.it2(), offset);
 313             else
 314             {
 315                 difference_t r1_dist = offset - r2_dist;
 316                 BOOST_ASSERT( r1_dist <= 0 );
 317                 m_it.it1() = m_link.last1 + r1_dist;
 318                 m_section = 0u;
 319             }
 320         }
 321         else
 322             std::advance(m_it.it2(), offset);
 323     }
 324
 325     void advance_from_range1(typename join_iterator::difference_type offset)
 326     {
 327         typedef typename join_iterator::difference_type difference_t;
 328         BOOST_ASSERT( m_section == 0u );
 329         if (offset > 0)
 330         {
 331             difference_t r1_dist = m_link.last1 - m_it.it1();
 332             BOOST_ASSERT( r1_dist >= 0 );
 333             if (offset < r1_dist)
 334                 std::advance(m_it.it1(), offset);
 335             else
 336             {
 337                 difference_t r2_dist = offset - r1_dist;
 338                 BOOST_ASSERT( r2_dist >= 0 );
 339                 m_it.it2() = m_link.first2 + r2_dist;
 340                 m_section = 1u;
 341             }
 342         }
 343         else
 344             std::advance(m_it.it1(), offset);
 345     }
 346
 347     unsigned int m_section;
 348     iterator_union m_it;
 349     link_t m_link;
 350
 351     friend class ::boost::iterator_core_access;
 352 };
 353
 354     } // namespace range_detail
 355
 356 } // namespace boost
 357
 358 #endif // include guard