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 | |
31 | namespace boost { namespace geometry { namespace range { |
32 | |
33 | namespace detail { |
34 | |
35 | // NOTE: For SinglePassRanges pos could iterate over all elements until the i-th element was met. |
36 | |
37 | template <typename RandomAccessRange> |
38 | struct 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 | */ |
57 | template <typename RandomAccessRange> |
58 | inline typename boost::range_iterator<RandomAccessRange const>::type |
59 | pos(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 | */ |
70 | template <typename RandomAccessRange> |
71 | inline typename boost::range_iterator<RandomAccessRange>::type |
72 | pos(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 | */ |
83 | template <typename RandomAccessRange> |
84 | inline typename boost::range_reference<RandomAccessRange const>::type |
85 | at(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 | */ |
96 | template <typename RandomAccessRange> |
97 | inline typename boost::range_reference<RandomAccessRange>::type |
98 | at(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 | */ |
109 | template <typename Range> |
110 | inline typename boost::range_reference<Range const>::type |
111 | front(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 | */ |
121 | template <typename Range> |
122 | inline typename boost::range_reference<Range>::type |
123 | front(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 | */ |
135 | template <typename BidirectionalRange> |
136 | inline typename boost::range_reference<BidirectionalRange const>::type |
137 | back(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 | */ |
148 | template <typename BidirectionalRange> |
149 | inline typename boost::range_reference<BidirectionalRange>::type |
150 | back(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 | */ |
163 | template <typename Range> |
164 | inline 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 | */ |
175 | template <typename Range> |
176 | inline 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 | */ |
187 | template <typename Range> |
188 | inline 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 | */ |
200 | template <typename Range> |
201 | inline void pop_back(Range & rng) |
202 | { |
203 | BOOST_GEOMETRY_ASSERT(!boost::empty(rng)); |
204 | range::resize(rng, boost::size(rng) - 1); |
205 | } |
206 | |
207 | namespace detail { |
208 | |
209 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
210 | |
211 | template <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> |
218 | struct 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 | |
226 | template <typename It, typename OutIt> |
227 | struct 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 | |
235 | template <typename It, typename OutIt> |
236 | inline 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 | |
243 | template <typename It, typename OutIt> |
244 | inline 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 | */ |
258 | template <typename Range> |
259 | inline typename boost::range_iterator<Range>::type |
260 | erase(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 | */ |
290 | template <typename Range> |
291 | inline typename boost::range_iterator<Range>::type |
292 | erase(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 | */ |
309 | template <typename Range> |
310 | inline typename boost::range_iterator<Range>::type |
311 | erase(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 | */ |
347 | template <typename Range> |
348 | inline typename boost::range_iterator<Range>::type |
349 | erase(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 | |