ceph/src/boost/boost/geometry/util/range.hpp

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013-2021.
   6 // Modifications copyright (c) 2013-2021 Oracle and/or its affiliates.
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Licensed under the Boost Software License version 1.0.
  10 // http://www.boost.org/users/license.html
  11
  12 #ifndef BOOST_GEOMETRY_UTIL_RANGE_HPP
  13 #define BOOST_GEOMETRY_UTIL_RANGE_HPP
  14
  15 #include <algorithm>
  16 #include <iterator>
  17 #include <type_traits>
  18
  19 #include <boost/concept_check.hpp>
  20 #include <boost/config.hpp>
  21 #include <boost/core/addressof.hpp>
  22 #include <boost/mpl/has_xxx.hpp>
  23 #include <boost/range/concepts.hpp>
  24 #include <boost/range/begin.hpp>
  25 #include <boost/range/end.hpp>
  26 #include <boost/range/empty.hpp>
  27 #include <boost/range/difference_type.hpp>
  28 #include <boost/range/has_range_iterator.hpp>
  29 #include <boost/range/iterator.hpp>
  30 #include <boost/range/reference.hpp>
  31 #include <boost/range/size.hpp>
  32 #include <boost/range/value_type.hpp>
  33
  34 #include <boost/geometry/core/assert.hpp>
  35 #include <boost/geometry/core/mutable_range.hpp>
  36
  37 namespace boost { namespace geometry { namespace range
  38 {
  39
  40 namespace detail
  41 {
  42
  43 BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
  44
  45 template <typename T>
  46 struct is_iterator
  47     : std::integral_constant
  48         <
  49             bool,
  50             has_iterator_category
  51                 <
  52                     std::iterator_traits<T>
  53                 >::value
  54         >
  55 {};
  56
  57
  58 template <typename T, bool HasIterator = boost::has_range_iterator<T>::value>
  59 struct is_range_impl
  60     : is_iterator
  61         <
  62             typename boost::range_iterator<T>::type
  63         >
  64 {};
  65 template <typename T>
  66 struct is_range_impl<T, false>
  67     : std::false_type
  68 {};
  69
  70 template <typename T>
  71 struct is_range
  72     : is_range_impl<T>
  73 {};
  74
  75 template <typename Range, typename T = void>
  76 using enable_if_mutable_t = std::enable_if_t
  77     <
  78         (! std::is_const<std::remove_reference_t<Range>>::value),
  79         T
  80     >;
  81
  82
  83 } // namespace detail
  84
  85
  86 /*!
  87 \brief Short utility to conveniently return an iterator of a RandomAccessRange.
  88 \ingroup utility
  89 */
  90 template <typename RandomAccessRange>
  91 inline typename boost::range_iterator<RandomAccessRange>::type
  92 pos(RandomAccessRange && rng,
  93     typename boost::range_size<RandomAccessRange>::type i)
  94 {
  95     BOOST_RANGE_CONCEPT_ASSERT((boost::RandomAccessRangeConcept<RandomAccessRange>));
  96     BOOST_GEOMETRY_ASSERT(i <= boost::size(rng));
  97     return boost::begin(rng)
  98          + static_cast<typename boost::range_difference<RandomAccessRange>::type>(i);
  99 }
 100
 101 /*!
 102 \brief Short utility to conveniently return an element of a RandomAccessRange.
 103 \ingroup utility
 104 */
 105 template <typename RandomAccessRange>
 106 inline typename boost::range_reference<RandomAccessRange>::type
 107 at(RandomAccessRange && rng,
 108    typename boost::range_size<RandomAccessRange>::type i)
 109 {
 110     return *pos(rng, i);
 111 }
 112
 113 /*!
 114 \brief Short utility to conveniently return the front element of a Range.
 115 \ingroup utility
 116 */
 117 template <typename Range>
 118 inline typename boost::range_reference<Range>::type
 119 front(Range && rng)
 120 {
 121     BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
 122     return *boost::begin(rng);
 123 }
 124
 125 /*!
 126 \brief Short utility to conveniently return the back element of a BidirectionalRange.
 127 \ingroup utility
 128 */
 129 template <typename BidirectionalRange>
 130 inline typename boost::range_reference<BidirectionalRange>::type
 131 back(BidirectionalRange && rng)
 132 {
 133     BOOST_RANGE_CONCEPT_ASSERT((boost::BidirectionalRangeConcept<BidirectionalRange>));
 134     BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
 135     auto it = boost::end(rng);
 136     return *(--it);
 137 }
 138
 139
 140 /*!
 141 \brief Short utility to conveniently clear a mutable range.
 142        It uses traits::clear<>.
 143 \ingroup utility
 144 */
 145 template
 146 <
 147     typename Range,
 148     detail::enable_if_mutable_t<Range, int> = 0
 149 >
 150 inline void clear(Range && rng)
 151 {
 152     geometry::traits::clear
 153         <
 154             std::remove_reference_t<Range>
 155         >::apply(rng);
 156 }
 157
 158 /*!
 159 \brief Short utility to conveniently insert a new element at the end of a mutable range.
 160        It uses boost::geometry::traits::push_back<>.
 161 \ingroup utility
 162 */
 163 template
 164 <
 165     typename Range,
 166     detail::enable_if_mutable_t<Range, int> = 0
 167 >
 168 inline void push_back(Range && rng,
 169                       typename boost::range_value<Range>::type const& value)
 170 {
 171     geometry::traits::push_back
 172         <
 173             std::remove_reference_t<Range>
 174         >::apply(rng, value);
 175 }
 176
 177 /*!
 178 \brief Short utility to conveniently insert a new element at the end of a mutable range.
 179        It uses boost::geometry::traits::push_back<>.
 180 \ingroup utility
 181 */
 182 template
 183 <
 184     typename Range,
 185     detail::enable_if_mutable_t<Range, int> = 0
 186 >
 187 inline void push_back(Range && rng,
 188                       typename boost::range_value<Range>::type && value)
 189 {
 190     geometry::traits::push_back
 191         <
 192             std::remove_reference_t<Range>
 193         >::apply(rng, std::move(value));
 194 }
 195
 196 /*!
 197 \brief Short utility to conveniently insert a new element at the end of a mutable range.
 198        It uses boost::geometry::traits::emplace_back<>.
 199 \ingroup utility
 200 */
 201 template
 202 <
 203     typename Range,
 204     typename ...Args,
 205     detail::enable_if_mutable_t<Range, int> = 0
 206 >
 207 inline void emplace_back(Range && rng, Args &&... args)
 208 {
 209     geometry::traits::emplace_back
 210         <
 211             std::remove_reference_t<Range>
 212         >::apply(rng, std::forward<Args>(args)...);
 213 }
 214
 215 /*!
 216 \brief Short utility to conveniently resize a mutable range.
 217        It uses boost::geometry::traits::resize<>.
 218 \ingroup utility
 219 */
 220 template
 221 <
 222     typename Range,
 223     detail::enable_if_mutable_t<Range, int> = 0
 224 >
 225 inline void resize(Range && rng,
 226                    typename boost::range_size<Range>::type new_size)
 227 {
 228     geometry::traits::resize
 229         <
 230             std::remove_reference_t<Range>
 231         >::apply(rng, new_size);
 232 }
 233
 234 /*!
 235 \brief Short utility to conveniently remove an element from the back of a mutable range.
 236        It uses resize().
 237 \ingroup utility
 238 */
 239 template
 240 <
 241     typename Range,
 242     detail::enable_if_mutable_t<Range, int> = 0
 243 >
 244 inline void pop_back(Range && rng)
 245 {
 246     BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
 247     range::resize(rng, boost::size(rng) - 1);
 248 }
 249
 250 /*!
 251 \brief Short utility to conveniently remove an element from a mutable range.
 252        It uses std::move() and resize(). Version taking mutable iterators.
 253 \ingroup utility
 254 */
 255 template
 256 <
 257     typename Range,
 258     detail::enable_if_mutable_t<Range, int> = 0
 259 >
 260 inline typename boost::range_iterator<Range>::type
 261 erase(Range && rng,
 262       typename boost::range_iterator<Range>::type it)
 263 {
 264     BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
 265     BOOST_GEOMETRY_ASSERT(it != boost::end(rng));
 266
 267     typename boost::range_difference<Range>::type const
 268         d = std::distance(boost::begin(rng), it);
 269
 270     typename boost::range_iterator<Range>::type
 271         next = it;
 272     ++next;
 273
 274     std::move(next, boost::end(rng), it);
 275     range::resize(rng, boost::size(rng) - 1);
 276
 277     // NOTE: In general this should be sufficient:
 278     //    return it;
 279     // But in MSVC using the returned iterator causes
 280     // assertion failures when iterator debugging is enabled
 281     // Furthermore the code below should work in the case if resize()
 282     // invalidates iterators when the container is resized down.
 283     return boost::begin(rng) + d;
 284 }
 285
 286 /*!
 287 \brief Short utility to conveniently remove an element from a mutable range.
 288        It uses std::move() and resize(). Version taking non-mutable iterators.
 289 \ingroup utility
 290 */
 291 template
 292 <
 293     typename Range,
 294     detail::enable_if_mutable_t<Range, int> = 0
 295 >
 296 inline typename boost::range_iterator<Range>::type
 297 erase(Range && rng,
 298       typename boost::range_iterator<std::remove_reference_t<Range> const>::type cit)
 299 {
 300     BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
 301
 302     typename boost::range_iterator<Range>::type
 303         it = boost::begin(rng)
 304                 + std::distance(boost::const_begin(rng), cit);
 305
 306     return range::erase(rng, it);
 307 }
 308
 309 /*!
 310 \brief Short utility to conveniently remove a range of elements from a mutable range.
 311        It uses std::move() and resize(). Version taking mutable iterators.
 312 \ingroup utility
 313 */
 314 template
 315 <
 316     typename Range,
 317     detail::enable_if_mutable_t<Range, int> = 0
 318 >
 319 inline typename boost::range_iterator<Range>::type
 320 erase(Range && rng,
 321       typename boost::range_iterator<Range>::type first,
 322       typename boost::range_iterator<Range>::type last)
 323 {
 324     typename boost::range_difference<Range>::type const
 325         diff = std::distance(first, last);
 326     BOOST_GEOMETRY_ASSERT(diff >= 0);
 327
 328     std::size_t const count = static_cast<std::size_t>(diff);
 329     BOOST_GEOMETRY_ASSERT(count <= boost::size(rng));
 330
 331     if ( count > 0 )
 332     {
 333         typename boost::range_difference<Range>::type const
 334             d = std::distance(boost::begin(rng), first);
 335
 336         std::move(last, boost::end(rng), first);
 337         range::resize(rng, boost::size(rng) - count);
 338
 339         // NOTE: In general this should be sufficient:
 340         //    return first;
 341         // But in MSVC using the returned iterator causes
 342         // assertion failures when iterator debugging is enabled
 343         // Furthermore the code below should work in the case if resize()
 344         // invalidates iterators when the container is resized down.
 345         return boost::begin(rng) + d;
 346     }
 347
 348     return first;
 349 }
 350
 351 /*!
 352 \brief Short utility to conveniently remove a range of elements from a mutable range.
 353        It uses std::move() and resize(). Version taking non-mutable iterators.
 354 \ingroup utility
 355 */
 356 template
 357 <
 358     typename Range,
 359     detail::enable_if_mutable_t<Range, int> = 0
 360 >
 361 inline typename boost::range_iterator<Range>::type
 362 erase(Range && rng,
 363       typename boost::range_iterator<std::remove_reference_t<Range> const>::type cfirst,
 364       typename boost::range_iterator<std::remove_reference_t<Range> const>::type clast)
 365 {
 366     BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
 367
 368     typename boost::range_iterator<Range>::type
 369         first = boost::begin(rng)
 370                     + std::distance(boost::const_begin(rng), cfirst);
 371     typename boost::range_iterator<Range>::type
 372         last = boost::begin(rng)
 373                     + std::distance(boost::const_begin(rng), clast);
 374
 375     return range::erase(rng, first, last);
 376 }
 377
 378 // back_inserter
 379
 380 template <class Container>
 381 class back_insert_iterator
 382 {
 383 public:
 384     typedef std::output_iterator_tag iterator_category;
 385     typedef void value_type;
 386     typedef void difference_type;
 387     typedef void pointer;
 388     typedef void reference;
 389
 390     typedef Container container_type;
 391
 392     explicit back_insert_iterator(Container & c)
 393         : container(boost::addressof(c))
 394     {}
 395
 396     back_insert_iterator & operator=(typename Container::value_type const& value)
 397     {
 398         range::push_back(*container, value);
 399         return *this;
 400     }
 401
 402     back_insert_iterator & operator=(typename Container::value_type && value)
 403     {
 404         range::push_back(*container, std::move(value));
 405         return *this;
 406     }
 407
 408     back_insert_iterator & operator* ()
 409     {
 410         return *this;
 411     }
 412
 413     back_insert_iterator & operator++ ()
 414     {
 415         return *this;
 416     }
 417
 418     back_insert_iterator operator++(int)
 419     {
 420         return *this;
 421     }
 422
 423 private:
 424     Container * container;
 425 };
 426
 427 template <typename Range>
 428 inline back_insert_iterator<Range> back_inserter(Range & rng)
 429 {
 430     return back_insert_iterator<Range>(rng);
 431 }
 432
 433 }}} // namespace boost::geometry::range
 434
 435 #endif // BOOST_GEOMETRY_UTIL_RANGE_HPP