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

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