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, 2019.
6 // Modifications copyright (c) 2013-2019 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
applyboost::geometry::range::detail::pos51 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
pos(RandomAccessRange const & rng,typename boost::range_size<RandomAccessRange const>::type i)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
pos(RandomAccessRange & rng,typename boost::range_size<RandomAccessRange>::type i)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
at(RandomAccessRange const & rng,typename boost::range_size<RandomAccessRange const>::type i)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
at(RandomAccessRange & rng,typename boost::range_size<RandomAccessRange>::type i)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
front(Range const & rng)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
front(Range & rng)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
back(BidirectionalRange const & rng)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
back(BidirectionalRange & rng)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>
clear(Range & rng)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>
push_back(Range & rng,typename boost::range_value<Range>::type const & value)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>
resize(Range & rng,typename boost::range_size<Range>::type new_size)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>
pop_back(Range & rng)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 {
applyboost::geometry::range::detail::copy_or_move_impl227 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 {
applyboost::geometry::range::detail::copy_or_move_impl236 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>
copy_or_move(It first,It last,OutIt out)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
erase(Range & rng,typename boost::range_iterator<Range>::type it)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
erase(Range & rng,typename boost::range_iterator<Range const>::type cit)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 range::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
erase(Range & rng,typename boost::range_iterator<Range>::type first,typename boost::range_iterator<Range>::type last)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
erase(Range & rng,typename boost::range_iterator<Range const>::type cfirst,typename boost::range_iterator<Range const>::type clast)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 range::erase(rng, first, last);
370 }
371
372 // back_inserter
373
374 template <class Container>
375 class back_insert_iterator
376 {
377 public:
378 typedef std::output_iterator_tag iterator_category;
379 typedef void value_type;
380 typedef void difference_type;
381 typedef void pointer;
382 typedef void reference;
383
384 typedef Container container_type;
385
back_insert_iterator(Container & c)386 explicit back_insert_iterator(Container & c)
387 : container(boost::addressof(c))
388 {}
389
operator =(typename Container::value_type const & value)390 back_insert_iterator & operator=(typename Container::value_type const& value)
391 {
392 range::push_back(*container, value);
393 return *this;
394 }
395
operator *()396 back_insert_iterator & operator* ()
397 {
398 return *this;
399 }
400
operator ++()401 back_insert_iterator & operator++ ()
402 {
403 return *this;
404 }
405
operator ++(int)406 back_insert_iterator operator++(int)
407 {
408 return *this;
409 }
410
411 private:
412 Container * container;
413 };
414
415 template <typename Range>
back_inserter(Range & rng)416 inline back_insert_iterator<Range> back_inserter(Range & rng)
417 {
418 return back_insert_iterator<Range>(rng);
419 }
420
421 }}} // namespace boost::geometry::range
422
423 #endif // BOOST_GEOMETRY_UTIL_RANGE_HPP
424