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.
6// Modifications copyright (c) 2013-2015 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
19#include <boost/concept_check.hpp>
20#include <boost/config.hpp>
21#include <boost/range/concepts.hpp>
22#include <boost/range/begin.hpp>
23#include <boost/range/end.hpp>
24#include <boost/range/empty.hpp>
25#include <boost/range/size.hpp>
26#include <boost/type_traits/is_convertible.hpp>
27
28#include <boost/geometry/core/assert.hpp>
29#include <boost/geometry/core/mutable_range.hpp>
30
31namespace boost { namespace geometry { namespace range {
32
33namespace detail {
34
35// NOTE: For SinglePassRanges pos could iterate over all elements until the i-th element was met.
36
37template <typename RandomAccessRange>
38struct pos
39{
40 typedef typename boost::range_iterator<RandomAccessRange>::type iterator;
41 typedef typename boost::range_size<RandomAccessRange>::type size_type;
42 typedef typename boost::range_difference<RandomAccessRange>::type difference_type;
43
44 static inline iterator apply(RandomAccessRange & rng, size_type i)
45 {
46 BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<RandomAccessRange> ));
47 return boost::begin(rng) + static_cast<difference_type>(i);
48 }
49};
50
51} // namespace detail
52
53/*!
54\brief Short utility to conveniently return an iterator of a RandomAccessRange.
55\ingroup utility
56*/
57template <typename RandomAccessRange>
58inline typename boost::range_iterator<RandomAccessRange const>::type
59pos(RandomAccessRange const& rng,
60 typename boost::range_size<RandomAccessRange const>::type i)
61{
62 BOOST_GEOMETRY_ASSERT(i <= boost::size(rng));
63 return detail::pos<RandomAccessRange const>::apply(rng, i);
64}
65
66/*!
67\brief Short utility to conveniently return an iterator of a RandomAccessRange.
68\ingroup utility
69*/
70template <typename RandomAccessRange>
71inline typename boost::range_iterator<RandomAccessRange>::type
72pos(RandomAccessRange & rng,
73 typename boost::range_size<RandomAccessRange>::type i)
74{
75 BOOST_GEOMETRY_ASSERT(i <= boost::size(rng));
76 return detail::pos<RandomAccessRange>::apply(rng, i);
77}
78
79/*!
80\brief Short utility to conveniently return an element of a RandomAccessRange.
81\ingroup utility
82*/
83template <typename RandomAccessRange>
84inline typename boost::range_reference<RandomAccessRange const>::type
85at(RandomAccessRange const& rng,
86 typename boost::range_size<RandomAccessRange const>::type i)
87{
88 BOOST_GEOMETRY_ASSERT(i < boost::size(rng));
89 return * detail::pos<RandomAccessRange const>::apply(rng, i);
90}
91
92/*!
93\brief Short utility to conveniently return an element of a RandomAccessRange.
94\ingroup utility
95*/
96template <typename RandomAccessRange>
97inline typename boost::range_reference<RandomAccessRange>::type
98at(RandomAccessRange & rng,
99 typename boost::range_size<RandomAccessRange>::type i)
100{
101 BOOST_GEOMETRY_ASSERT(i < boost::size(rng));
102 return * detail::pos<RandomAccessRange>::apply(rng, i);
103}
104
105/*!
106\brief Short utility to conveniently return the front element of a Range.
107\ingroup utility
108*/
109template <typename Range>
110inline typename boost::range_reference<Range const>::type
111front(Range const& rng)
112{
113 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
114 return *boost::begin(rng);
115}
116
117/*!
118\brief Short utility to conveniently return the front element of a Range.
119\ingroup utility
120*/
121template <typename Range>
122inline typename boost::range_reference<Range>::type
123front(Range & rng)
124{
125 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
126 return *boost::begin(rng);
127}
128
129// NOTE: For SinglePassRanges back() could iterate over all elements until the last element is met.
130
131/*!
132\brief Short utility to conveniently return the back element of a BidirectionalRange.
133\ingroup utility
134*/
135template <typename BidirectionalRange>
136inline typename boost::range_reference<BidirectionalRange const>::type
137back(BidirectionalRange const& rng)
138{
139 BOOST_RANGE_CONCEPT_ASSERT(( boost::BidirectionalRangeConcept<BidirectionalRange const> ));
140 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
141 return *(boost::rbegin(rng));
142}
143
144/*!
145\brief Short utility to conveniently return the back element of a BidirectionalRange.
146\ingroup utility
147*/
148template <typename BidirectionalRange>
149inline typename boost::range_reference<BidirectionalRange>::type
150back(BidirectionalRange & rng)
151{
152 BOOST_RANGE_CONCEPT_ASSERT((boost::BidirectionalRangeConcept<BidirectionalRange>));
153 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
154 return *(boost::rbegin(rng));
155}
156
157
158/*!
159\brief Short utility to conveniently clear a mutable range.
160 It uses traits::clear<>.
161\ingroup utility
162*/
163template <typename Range>
164inline void clear(Range & rng)
165{
166 // NOTE: this trait is probably not needed since it could be implemented using resize()
167 geometry::traits::clear<Range>::apply(rng);
168}
169
170/*!
171\brief Short utility to conveniently insert a new element at the end of a mutable range.
172 It uses boost::geometry::traits::push_back<>.
173\ingroup utility
174*/
175template <typename Range>
176inline void push_back(Range & rng,
177 typename boost::range_value<Range>::type const& value)
178{
179 geometry::traits::push_back<Range>::apply(rng, value);
180}
181
182/*!
183\brief Short utility to conveniently resize a mutable range.
184 It uses boost::geometry::traits::resize<>.
185\ingroup utility
186*/
187template <typename Range>
188inline void resize(Range & rng,
189 typename boost::range_size<Range>::type new_size)
190{
191 geometry::traits::resize<Range>::apply(rng, new_size);
192}
193
194
195/*!
196\brief Short utility to conveniently remove an element from the back of a mutable range.
197 It uses resize().
198\ingroup utility
199*/
200template <typename Range>
201inline void pop_back(Range & rng)
202{
203 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
204 range::resize(rng, boost::size(rng) - 1);
205}
206
207namespace detail {
208
209#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
210
211template <typename It,
212 typename OutIt,
213 bool UseMove = boost::is_convertible
214 <
215 typename std::iterator_traits<It>::value_type &&,
216 typename std::iterator_traits<OutIt>::value_type
217 >::value>
218struct copy_or_move_impl
219{
220 static inline OutIt apply(It first, It last, OutIt out)
221 {
222 return std::move(first, last, out);
223 }
224};
225
226template <typename It, typename OutIt>
227struct copy_or_move_impl<It, OutIt, false>
228{
229 static inline OutIt apply(It first, It last, OutIt out)
230 {
231 return std::copy(first, last, out);
232 }
233};
234
235template <typename It, typename OutIt>
236inline OutIt copy_or_move(It first, It last, OutIt out)
237{
238 return copy_or_move_impl<It, OutIt>::apply(first, last, out);
239}
240
241#else
242
243template <typename It, typename OutIt>
244inline OutIt copy_or_move(It first, It last, OutIt out)
245{
246 return std::copy(first, last, out);
247}
248
249#endif
250
251} // namespace detail
252
253/*!
254\brief Short utility to conveniently remove an element from a mutable range.
255 It uses std::copy() and resize(). Version taking mutable iterators.
256\ingroup utility
257*/
258template <typename Range>
259inline typename boost::range_iterator<Range>::type
260erase(Range & rng,
261 typename boost::range_iterator<Range>::type it)
262{
263 BOOST_GEOMETRY_ASSERT(!boost::empty(rng));
264 BOOST_GEOMETRY_ASSERT(it != boost::end(rng));
265
266 typename boost::range_difference<Range>::type const
267 d = std::distance(boost::begin(rng), it);
268
269 typename boost::range_iterator<Range>::type
270 next = it;
271 ++next;
272
273 detail::copy_or_move(next, boost::end(rng), it);
274 range::resize(rng, boost::size(rng) - 1);
275
276 // NOTE: In general this should be sufficient:
277 // return it;
278 // But in MSVC using the returned iterator causes
279 // assertion failures when iterator debugging is enabled
280 // Furthermore the code below should work in the case if resize()
281 // invalidates iterators when the container is resized down.
282 return boost::begin(rng) + d;
283}
284
285/*!
286\brief Short utility to conveniently remove an element from a mutable range.
287 It uses std::copy() and resize(). Version taking non-mutable iterators.
288\ingroup utility
289*/
290template <typename Range>
291inline typename boost::range_iterator<Range>::type
292erase(Range & rng,
293 typename boost::range_iterator<Range const>::type cit)
294{
295 BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
296
297 typename boost::range_iterator<Range>::type
298 it = boost::begin(rng)
299 + std::distance(boost::const_begin(rng), cit);
300
301 return erase(rng, it);
302}
303
304/*!
305\brief Short utility to conveniently remove a range of elements from a mutable range.
306 It uses std::copy() and resize(). Version taking mutable iterators.
307\ingroup utility
308*/
309template <typename Range>
310inline typename boost::range_iterator<Range>::type
311erase(Range & rng,
312 typename boost::range_iterator<Range>::type first,
313 typename boost::range_iterator<Range>::type last)
314{
315 typename boost::range_difference<Range>::type const
316 diff = std::distance(first, last);
317 BOOST_GEOMETRY_ASSERT(diff >= 0);
318
319 std::size_t const count = static_cast<std::size_t>(diff);
320 BOOST_GEOMETRY_ASSERT(count <= boost::size(rng));
321
322 if ( count > 0 )
323 {
324 typename boost::range_difference<Range>::type const
325 d = std::distance(boost::begin(rng), first);
326
327 detail::copy_or_move(last, boost::end(rng), first);
328 range::resize(rng, boost::size(rng) - count);
329
330 // NOTE: In general this should be sufficient:
331 // return first;
332 // But in MSVC using the returned iterator causes
333 // assertion failures when iterator debugging is enabled
334 // Furthermore the code below should work in the case if resize()
335 // invalidates iterators when the container is resized down.
336 return boost::begin(rng) + d;
337 }
338
339 return first;
340}
341
342/*!
343\brief Short utility to conveniently remove a range of elements from a mutable range.
344 It uses std::copy() and resize(). Version taking non-mutable iterators.
345\ingroup utility
346*/
347template <typename Range>
348inline typename boost::range_iterator<Range>::type
349erase(Range & rng,
350 typename boost::range_iterator<Range const>::type cfirst,
351 typename boost::range_iterator<Range const>::type clast)
352{
353 BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
354
355 typename boost::range_iterator<Range>::type
356 first = boost::begin(rng)
357 + std::distance(boost::const_begin(rng), cfirst);
358 typename boost::range_iterator<Range>::type
359 last = boost::begin(rng)
360 + std::distance(boost::const_begin(rng), clast);
361
362 return erase(rng, first, last);
363}
364
365}}} // namespace boost::geometry::range
366
367#endif // BOOST_GEOMETRY_UTIL_RANGE_HPP
368

source code of boost/boost/geometry/util/range.hpp