]>
Commit | Line | Data |
---|---|---|
2c1bc4eb PC |
1 | // Algorithm extensions -*- C++ -*- |
2 | ||
8d9254fc | 3 | // Copyright (C) 2001-2020 Free Software Foundation, Inc. |
2c1bc4eb PC |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
2c1bc4eb PC |
9 | // any later version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
2c1bc4eb | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
2c1bc4eb PC |
24 | |
25 | /* | |
26 | * | |
27 | * Copyright (c) 1994 | |
28 | * Hewlett-Packard Company | |
29 | * | |
30 | * Permission to use, copy, modify, distribute and sell this software | |
31 | * and its documentation for any purpose is hereby granted without fee, | |
32 | * provided that the above copyright notice appear in all copies and | |
33 | * that both that copyright notice and this permission notice appear | |
34 | * in supporting documentation. Hewlett-Packard Company makes no | |
35 | * representations about the suitability of this software for any | |
36 | * purpose. It is provided "as is" without express or implied warranty. | |
37 | * | |
38 | * | |
39 | * Copyright (c) 1996 | |
40 | * Silicon Graphics Computer Systems, Inc. | |
41 | * | |
42 | * Permission to use, copy, modify, distribute and sell this software | |
43 | * and its documentation for any purpose is hereby granted without fee, | |
44 | * provided that the above copyright notice appear in all copies and | |
45 | * that both that copyright notice and this permission notice appear | |
46 | * in supporting documentation. Silicon Graphics makes no | |
47 | * representations about the suitability of this software for any | |
48 | * purpose. It is provided "as is" without express or implied warranty. | |
49 | */ | |
50 | ||
ffe94f83 PE |
51 | /** @file ext/algorithm |
52 | * This file is a GNU extension to the Standard C++ Library (possibly | |
0aa06b18 | 53 | * containing extensions from the HP/SGI STL subset). |
ffe94f83 PE |
54 | */ |
55 | ||
2c1bc4eb | 56 | #ifndef _EXT_ALGORITHM |
3d7c150e | 57 | #define _EXT_ALGORITHM 1 |
2c1bc4eb | 58 | |
36955a95 | 59 | #pragma GCC system_header |
3d7c150e | 60 | |
54c1bf78 | 61 | #include <algorithm> |
2c1bc4eb | 62 | |
12ffa228 BK |
63 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
64 | { | |
65 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
3cbc7af0 | 66 | |
f53d0ff1 PC |
67 | //-------------------------------------------------- |
68 | // copy_n (not part of the C++ standard) | |
69 | ||
08addde6 | 70 | template<typename _InputIterator, typename _Size, typename _OutputIterator> |
d03eca30 | 71 | std::pair<_InputIterator, _OutputIterator> |
08addde6 PE |
72 | __copy_n(_InputIterator __first, _Size __count, |
73 | _OutputIterator __result, | |
d03eca30 | 74 | std::input_iterator_tag) |
f53d0ff1 | 75 | { |
4a787fa8 PC |
76 | for ( ; __count > 0; --__count) |
77 | { | |
78 | *__result = *__first; | |
79 | ++__first; | |
80 | ++__result; | |
81 | } | |
d03eca30 | 82 | return std::pair<_InputIterator, _OutputIterator>(__first, __result); |
f53d0ff1 PC |
83 | } |
84 | ||
08addde6 | 85 | template<typename _RAIterator, typename _Size, typename _OutputIterator> |
d03eca30 | 86 | inline std::pair<_RAIterator, _OutputIterator> |
08addde6 PE |
87 | __copy_n(_RAIterator __first, _Size __count, |
88 | _OutputIterator __result, | |
d03eca30 | 89 | std::random_access_iterator_tag) |
f53d0ff1 | 90 | { |
08addde6 | 91 | _RAIterator __last = __first + __count; |
d03eca30 | 92 | return std::pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, |
4a787fa8 PC |
93 | __last, |
94 | __result)); | |
f53d0ff1 PC |
95 | } |
96 | ||
97 | /** | |
98 | * @brief Copies the range [first,first+count) into [result,result+count). | |
93c66bc6 BK |
99 | * @param __first An input iterator. |
100 | * @param __count The number of elements to copy. | |
101 | * @param __result An output iterator. | |
f53d0ff1 PC |
102 | * @return A std::pair composed of first+count and result+count. |
103 | * | |
104 | * This is an SGI extension. | |
105 | * This inline function will boil down to a call to @c memmove whenever | |
106 | * possible. Failing that, if random access iterators are passed, then the | |
107 | * loop count will be known (and therefore a candidate for compiler | |
108 | * optimizations such as unrolling). | |
109 | * @ingroup SGIextensions | |
110 | */ | |
08addde6 | 111 | template<typename _InputIterator, typename _Size, typename _OutputIterator> |
d03eca30 | 112 | inline std::pair<_InputIterator, _OutputIterator> |
08addde6 | 113 | copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) |
f53d0ff1 PC |
114 | { |
115 | // concept requirements | |
3d7c150e BK |
116 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
117 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, | |
d03eca30 | 118 | typename std::iterator_traits<_InputIterator>::value_type>) |
f53d0ff1 | 119 | |
6ff7e964 PC |
120 | return __gnu_cxx::__copy_n(__first, __count, __result, |
121 | std::__iterator_category(__first)); | |
f53d0ff1 PC |
122 | } |
123 | ||
08addde6 | 124 | template<typename _InputIterator1, typename _InputIterator2> |
f53d0ff1 | 125 | int |
4a787fa8 PC |
126 | __lexicographical_compare_3way(_InputIterator1 __first1, |
127 | _InputIterator1 __last1, | |
128 | _InputIterator2 __first2, | |
129 | _InputIterator2 __last2) | |
f53d0ff1 | 130 | { |
4a787fa8 PC |
131 | while (__first1 != __last1 && __first2 != __last2) |
132 | { | |
133 | if (*__first1 < *__first2) | |
134 | return -1; | |
135 | if (*__first2 < *__first1) | |
136 | return 1; | |
137 | ++__first1; | |
138 | ++__first2; | |
139 | } | |
140 | if (__first2 == __last2) | |
f53d0ff1 | 141 | return !(__first1 == __last1); |
4a787fa8 | 142 | else |
f53d0ff1 | 143 | return -1; |
f53d0ff1 PC |
144 | } |
145 | ||
146 | inline int | |
147 | __lexicographical_compare_3way(const unsigned char* __first1, | |
148 | const unsigned char* __last1, | |
149 | const unsigned char* __first2, | |
150 | const unsigned char* __last2) | |
151 | { | |
d03eca30 JW |
152 | const std::ptrdiff_t __len1 = __last1 - __first1; |
153 | const std::ptrdiff_t __len2 = __last2 - __first2; | |
360721e3 | 154 | const int __result = __builtin_memcmp(__first1, __first2, |
d03eca30 | 155 | (std::min)(__len1, __len2)); |
fa30fe72 | 156 | return __result != 0 ? __result |
f53d0ff1 PC |
157 | : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); |
158 | } | |
159 | ||
fa30fe72 | 160 | inline int |
f53d0ff1 PC |
161 | __lexicographical_compare_3way(const char* __first1, const char* __last1, |
162 | const char* __first2, const char* __last2) | |
163 | { | |
164 | #if CHAR_MAX == SCHAR_MAX | |
4a787fa8 PC |
165 | return __lexicographical_compare_3way((const signed char*) __first1, |
166 | (const signed char*) __last1, | |
167 | (const signed char*) __first2, | |
168 | (const signed char*) __last2); | |
f53d0ff1 PC |
169 | #else |
170 | return __lexicographical_compare_3way((const unsigned char*) __first1, | |
171 | (const unsigned char*) __last1, | |
172 | (const unsigned char*) __first2, | |
173 | (const unsigned char*) __last2); | |
174 | #endif | |
175 | } | |
176 | ||
177 | /** | |
178 | * @brief @c memcmp on steroids. | |
93c66bc6 BK |
179 | * @param __first1 An input iterator. |
180 | * @param __last1 An input iterator. | |
181 | * @param __first2 An input iterator. | |
182 | * @param __last2 An input iterator. | |
f53d0ff1 PC |
183 | * @return An int, as with @c memcmp. |
184 | * | |
185 | * The return value will be less than zero if the first range is | |
2a60a9f6 BK |
186 | * <em>lexigraphically less than</em> the second, greater than zero |
187 | * if the second range is <em>lexigraphically less than</em> the | |
188 | * first, and zero otherwise. | |
f53d0ff1 PC |
189 | * This is an SGI extension. |
190 | * @ingroup SGIextensions | |
191 | */ | |
08addde6 | 192 | template<typename _InputIterator1, typename _InputIterator2> |
f53d0ff1 | 193 | int |
4a787fa8 PC |
194 | lexicographical_compare_3way(_InputIterator1 __first1, |
195 | _InputIterator1 __last1, | |
196 | _InputIterator2 __first2, | |
197 | _InputIterator2 __last2) | |
f53d0ff1 PC |
198 | { |
199 | // concept requirements | |
3d7c150e BK |
200 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
201 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
202 | __glibcxx_function_requires(_LessThanComparableConcept< | |
d03eca30 | 203 | typename std::iterator_traits<_InputIterator1>::value_type>) |
3d7c150e | 204 | __glibcxx_function_requires(_LessThanComparableConcept< |
d03eca30 | 205 | typename std::iterator_traits<_InputIterator2>::value_type>) |
285b36d6 BK |
206 | __glibcxx_requires_valid_range(__first1, __last1); |
207 | __glibcxx_requires_valid_range(__first2, __last2); | |
f53d0ff1 | 208 | |
4a787fa8 PC |
209 | return __lexicographical_compare_3way(__first1, __last1, __first2, |
210 | __last2); | |
f53d0ff1 PC |
211 | } |
212 | ||
2c1bc4eb PC |
213 | // count and count_if: this version, whose return type is void, was present |
214 | // in the HP STL, and is retained as an extension for backward compatibility. | |
08addde6 | 215 | template<typename _InputIterator, typename _Tp, typename _Size> |
2c1bc4eb | 216 | void |
08addde6 | 217 | count(_InputIterator __first, _InputIterator __last, |
2c1bc4eb PC |
218 | const _Tp& __value, |
219 | _Size& __n) | |
220 | { | |
221 | // concept requirements | |
3d7c150e BK |
222 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
223 | __glibcxx_function_requires(_EqualityComparableConcept< | |
d03eca30 | 224 | typename std::iterator_traits<_InputIterator>::value_type >) |
3d7c150e | 225 | __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) |
285b36d6 BK |
226 | __glibcxx_requires_valid_range(__first, __last); |
227 | ||
2c1bc4eb PC |
228 | for ( ; __first != __last; ++__first) |
229 | if (*__first == __value) | |
230 | ++__n; | |
231 | } | |
232 | ||
08addde6 | 233 | template<typename _InputIterator, typename _Predicate, typename _Size> |
2c1bc4eb | 234 | void |
08addde6 | 235 | count_if(_InputIterator __first, _InputIterator __last, |
2c1bc4eb PC |
236 | _Predicate __pred, |
237 | _Size& __n) | |
238 | { | |
239 | // concept requirements | |
3d7c150e BK |
240 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
241 | __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, | |
d03eca30 | 242 | typename std::iterator_traits<_InputIterator>::value_type>) |
285b36d6 BK |
243 | __glibcxx_requires_valid_range(__first, __last); |
244 | ||
2c1bc4eb PC |
245 | for ( ; __first != __last; ++__first) |
246 | if (__pred(*__first)) | |
247 | ++__n; | |
248 | } | |
249 | ||
250 | // random_sample and random_sample_n (extensions, not part of the standard). | |
251 | ||
fc7f0a80 PE |
252 | /** |
253 | * This is an SGI extension. | |
254 | * @ingroup SGIextensions | |
255 | * @doctodo | |
256 | */ | |
4a787fa8 PC |
257 | template<typename _ForwardIterator, typename _OutputIterator, |
258 | typename _Distance> | |
08addde6 PE |
259 | _OutputIterator |
260 | random_sample_n(_ForwardIterator __first, _ForwardIterator __last, | |
261 | _OutputIterator __out, const _Distance __n) | |
2c1bc4eb PC |
262 | { |
263 | // concept requirements | |
3d7c150e BK |
264 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
265 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, | |
d03eca30 | 266 | typename std::iterator_traits<_ForwardIterator>::value_type>) |
285b36d6 | 267 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb PC |
268 | |
269 | _Distance __remaining = std::distance(__first, __last); | |
d03eca30 | 270 | _Distance __m = (std::min)(__n, __remaining); |
2c1bc4eb | 271 | |
4a787fa8 PC |
272 | while (__m > 0) |
273 | { | |
274 | if ((std::rand() % __remaining) < __m) | |
275 | { | |
2c1bc4eb PC |
276 | *__out = *__first; |
277 | ++__out; | |
278 | --__m; | |
4a787fa8 PC |
279 | } |
280 | --__remaining; | |
281 | ++__first; | |
2c1bc4eb | 282 | } |
2c1bc4eb PC |
283 | return __out; |
284 | } | |
285 | ||
fc7f0a80 PE |
286 | /** |
287 | * This is an SGI extension. | |
288 | * @ingroup SGIextensions | |
289 | * @doctodo | |
290 | */ | |
4a787fa8 PC |
291 | template<typename _ForwardIterator, typename _OutputIterator, |
292 | typename _Distance, typename _RandomNumberGenerator> | |
08addde6 PE |
293 | _OutputIterator |
294 | random_sample_n(_ForwardIterator __first, _ForwardIterator __last, | |
fa30fe72 | 295 | _OutputIterator __out, const _Distance __n, |
2c1bc4eb PC |
296 | _RandomNumberGenerator& __rand) |
297 | { | |
298 | // concept requirements | |
3d7c150e BK |
299 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
300 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, | |
d03eca30 | 301 | typename std::iterator_traits<_ForwardIterator>::value_type>) |
3d7c150e | 302 | __glibcxx_function_requires(_UnaryFunctionConcept< |
2c1bc4eb | 303 | _RandomNumberGenerator, _Distance, _Distance>) |
285b36d6 | 304 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb PC |
305 | |
306 | _Distance __remaining = std::distance(__first, __last); | |
d03eca30 | 307 | _Distance __m = (std::min)(__n, __remaining); |
2c1bc4eb | 308 | |
4a787fa8 PC |
309 | while (__m > 0) |
310 | { | |
311 | if (__rand(__remaining) < __m) | |
312 | { | |
2c1bc4eb PC |
313 | *__out = *__first; |
314 | ++__out; | |
315 | --__m; | |
4a787fa8 PC |
316 | } |
317 | --__remaining; | |
318 | ++__first; | |
2c1bc4eb | 319 | } |
2c1bc4eb PC |
320 | return __out; |
321 | } | |
322 | ||
4a787fa8 PC |
323 | template<typename _InputIterator, typename _RandomAccessIterator, |
324 | typename _Distance> | |
08addde6 PE |
325 | _RandomAccessIterator |
326 | __random_sample(_InputIterator __first, _InputIterator __last, | |
327 | _RandomAccessIterator __out, | |
2c1bc4eb PC |
328 | const _Distance __n) |
329 | { | |
330 | _Distance __m = 0; | |
331 | _Distance __t = __n; | |
fa30fe72 | 332 | for ( ; __first != __last && __m < __n; ++__m, ++__first) |
2c1bc4eb PC |
333 | __out[__m] = *__first; |
334 | ||
4a787fa8 PC |
335 | while (__first != __last) |
336 | { | |
337 | ++__t; | |
338 | _Distance __M = std::rand() % (__t); | |
339 | if (__M < __n) | |
340 | __out[__M] = *__first; | |
341 | ++__first; | |
342 | } | |
2c1bc4eb PC |
343 | return __out + __m; |
344 | } | |
345 | ||
08addde6 | 346 | template<typename _InputIterator, typename _RandomAccessIterator, |
2c1bc4eb | 347 | typename _RandomNumberGenerator, typename _Distance> |
08addde6 PE |
348 | _RandomAccessIterator |
349 | __random_sample(_InputIterator __first, _InputIterator __last, | |
350 | _RandomAccessIterator __out, | |
2c1bc4eb PC |
351 | _RandomNumberGenerator& __rand, |
352 | const _Distance __n) | |
353 | { | |
354 | // concept requirements | |
3d7c150e | 355 | __glibcxx_function_requires(_UnaryFunctionConcept< |
2c1bc4eb PC |
356 | _RandomNumberGenerator, _Distance, _Distance>) |
357 | ||
358 | _Distance __m = 0; | |
359 | _Distance __t = __n; | |
360 | for ( ; __first != __last && __m < __n; ++__m, ++__first) | |
361 | __out[__m] = *__first; | |
362 | ||
4a787fa8 PC |
363 | while (__first != __last) |
364 | { | |
365 | ++__t; | |
366 | _Distance __M = __rand(__t); | |
367 | if (__M < __n) | |
368 | __out[__M] = *__first; | |
369 | ++__first; | |
370 | } | |
2c1bc4eb PC |
371 | return __out + __m; |
372 | } | |
373 | ||
fc7f0a80 PE |
374 | /** |
375 | * This is an SGI extension. | |
376 | * @ingroup SGIextensions | |
377 | * @doctodo | |
378 | */ | |
08addde6 PE |
379 | template<typename _InputIterator, typename _RandomAccessIterator> |
380 | inline _RandomAccessIterator | |
381 | random_sample(_InputIterator __first, _InputIterator __last, | |
4a787fa8 PC |
382 | _RandomAccessIterator __out_first, |
383 | _RandomAccessIterator __out_last) | |
2c1bc4eb PC |
384 | { |
385 | // concept requirements | |
3d7c150e BK |
386 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
387 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< | |
08addde6 | 388 | _RandomAccessIterator>) |
285b36d6 BK |
389 | __glibcxx_requires_valid_range(__first, __last); |
390 | __glibcxx_requires_valid_range(__out_first, __out_last); | |
2c1bc4eb PC |
391 | |
392 | return __random_sample(__first, __last, | |
393 | __out_first, __out_last - __out_first); | |
394 | } | |
395 | ||
fc7f0a80 PE |
396 | /** |
397 | * This is an SGI extension. | |
398 | * @ingroup SGIextensions | |
399 | * @doctodo | |
400 | */ | |
fa30fe72 | 401 | template<typename _InputIterator, typename _RandomAccessIterator, |
2c1bc4eb | 402 | typename _RandomNumberGenerator> |
08addde6 PE |
403 | inline _RandomAccessIterator |
404 | random_sample(_InputIterator __first, _InputIterator __last, | |
4a787fa8 PC |
405 | _RandomAccessIterator __out_first, |
406 | _RandomAccessIterator __out_last, | |
fa30fe72 | 407 | _RandomNumberGenerator& __rand) |
2c1bc4eb PC |
408 | { |
409 | // concept requirements | |
3d7c150e BK |
410 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
411 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< | |
08addde6 | 412 | _RandomAccessIterator>) |
285b36d6 BK |
413 | __glibcxx_requires_valid_range(__first, __last); |
414 | __glibcxx_requires_valid_range(__out_first, __out_last); | |
2c1bc4eb PC |
415 | |
416 | return __random_sample(__first, __last, | |
417 | __out_first, __rand, | |
418 | __out_last - __out_first); | |
419 | } | |
fa30fe72 | 420 | |
734f5023 | 421 | #if __cplusplus >= 201103L |
60a40f62 PC |
422 | using std::is_heap; |
423 | #else | |
fc7f0a80 PE |
424 | /** |
425 | * This is an SGI extension. | |
426 | * @ingroup SGIextensions | |
427 | * @doctodo | |
428 | */ | |
08addde6 | 429 | template<typename _RandomAccessIterator> |
2c1bc4eb | 430 | inline bool |
08addde6 | 431 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
2c1bc4eb PC |
432 | { |
433 | // concept requirements | |
4a787fa8 PC |
434 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
435 | _RandomAccessIterator>) | |
3d7c150e | 436 | __glibcxx_function_requires(_LessThanComparableConcept< |
d03eca30 | 437 | typename std::iterator_traits<_RandomAccessIterator>::value_type>) |
285b36d6 | 438 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb | 439 | |
285b36d6 | 440 | return std::__is_heap(__first, __last - __first); |
2c1bc4eb PC |
441 | } |
442 | ||
fc7f0a80 PE |
443 | /** |
444 | * This is an SGI extension. | |
445 | * @ingroup SGIextensions | |
446 | * @doctodo | |
447 | */ | |
08addde6 | 448 | template<typename _RandomAccessIterator, typename _StrictWeakOrdering> |
2c1bc4eb | 449 | inline bool |
08addde6 | 450 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
2c1bc4eb PC |
451 | _StrictWeakOrdering __comp) |
452 | { | |
453 | // concept requirements | |
4a787fa8 PC |
454 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
455 | _RandomAccessIterator>) | |
3d7c150e | 456 | __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, |
d03eca30 JW |
457 | typename std::iterator_traits<_RandomAccessIterator>::value_type, |
458 | typename std::iterator_traits<_RandomAccessIterator>::value_type>) | |
285b36d6 | 459 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb | 460 | |
285b36d6 | 461 | return std::__is_heap(__first, __comp, __last - __first); |
2c1bc4eb | 462 | } |
60a40f62 | 463 | #endif |
2c1bc4eb | 464 | |
734f5023 | 465 | #if __cplusplus >= 201103L |
7c16382a JY |
466 | using std::is_sorted; |
467 | #else | |
2c1bc4eb PC |
468 | // is_sorted, a predicated testing whether a range is sorted in |
469 | // nondescending order. This is an extension, not part of the C++ | |
470 | // standard. | |
471 | ||
fc7f0a80 PE |
472 | /** |
473 | * This is an SGI extension. | |
474 | * @ingroup SGIextensions | |
475 | * @doctodo | |
476 | */ | |
08addde6 | 477 | template<typename _ForwardIterator> |
2c1bc4eb | 478 | bool |
08addde6 | 479 | is_sorted(_ForwardIterator __first, _ForwardIterator __last) |
2c1bc4eb PC |
480 | { |
481 | // concept requirements | |
3d7c150e BK |
482 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
483 | __glibcxx_function_requires(_LessThanComparableConcept< | |
d03eca30 | 484 | typename std::iterator_traits<_ForwardIterator>::value_type>) |
285b36d6 | 485 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb PC |
486 | |
487 | if (__first == __last) | |
488 | return true; | |
489 | ||
08addde6 | 490 | _ForwardIterator __next = __first; |
4a787fa8 | 491 | for (++__next; __next != __last; __first = __next, ++__next) |
2c1bc4eb PC |
492 | if (*__next < *__first) |
493 | return false; | |
2c1bc4eb PC |
494 | return true; |
495 | } | |
496 | ||
fc7f0a80 PE |
497 | /** |
498 | * This is an SGI extension. | |
499 | * @ingroup SGIextensions | |
500 | * @doctodo | |
501 | */ | |
08addde6 | 502 | template<typename _ForwardIterator, typename _StrictWeakOrdering> |
2c1bc4eb | 503 | bool |
4a787fa8 PC |
504 | is_sorted(_ForwardIterator __first, _ForwardIterator __last, |
505 | _StrictWeakOrdering __comp) | |
2c1bc4eb PC |
506 | { |
507 | // concept requirements | |
3d7c150e BK |
508 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
509 | __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, | |
d03eca30 JW |
510 | typename std::iterator_traits<_ForwardIterator>::value_type, |
511 | typename std::iterator_traits<_ForwardIterator>::value_type>) | |
285b36d6 | 512 | __glibcxx_requires_valid_range(__first, __last); |
2c1bc4eb PC |
513 | |
514 | if (__first == __last) | |
515 | return true; | |
516 | ||
08addde6 | 517 | _ForwardIterator __next = __first; |
4a787fa8 | 518 | for (++__next; __next != __last; __first = __next, ++__next) |
2c1bc4eb PC |
519 | if (__comp(*__next, *__first)) |
520 | return false; | |
2c1bc4eb PC |
521 | return true; |
522 | } | |
734f5023 | 523 | #endif // C++11 |
3cbc7af0 | 524 | |
d5c59224 PC |
525 | /** |
526 | * @brief Find the median of three values. | |
93c66bc6 BK |
527 | * @param __a A value. |
528 | * @param __b A value. | |
529 | * @param __c A value. | |
d5c59224 PC |
530 | * @return One of @p a, @p b or @p c. |
531 | * | |
532 | * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n | |
533 | * then the value returned will be @c m. | |
534 | * This is an SGI extension. | |
535 | * @ingroup SGIextensions | |
536 | */ | |
537 | template<typename _Tp> | |
538 | const _Tp& | |
539 | __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) | |
540 | { | |
541 | // concept requirements | |
542 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) | |
543 | if (__a < __b) | |
544 | if (__b < __c) | |
545 | return __b; | |
546 | else if (__a < __c) | |
547 | return __c; | |
548 | else | |
549 | return __a; | |
550 | else if (__a < __c) | |
551 | return __a; | |
552 | else if (__b < __c) | |
553 | return __c; | |
554 | else | |
555 | return __b; | |
556 | } | |
557 | ||
558 | /** | |
559 | * @brief Find the median of three values using a predicate for comparison. | |
93c66bc6 BK |
560 | * @param __a A value. |
561 | * @param __b A value. | |
562 | * @param __c A value. | |
563 | * @param __comp A binary predicate. | |
d5c59224 PC |
564 | * @return One of @p a, @p b or @p c. |
565 | * | |
566 | * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) | |
567 | * and @p comp(m,n) are both true then the value returned will be @c m. | |
568 | * This is an SGI extension. | |
569 | * @ingroup SGIextensions | |
570 | */ | |
571 | template<typename _Tp, typename _Compare> | |
572 | const _Tp& | |
573 | __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) | |
574 | { | |
575 | // concept requirements | |
576 | __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, | |
577 | _Tp, _Tp>) | |
578 | if (__comp(__a, __b)) | |
579 | if (__comp(__b, __c)) | |
580 | return __b; | |
581 | else if (__comp(__a, __c)) | |
582 | return __c; | |
583 | else | |
584 | return __a; | |
585 | else if (__comp(__a, __c)) | |
586 | return __a; | |
587 | else if (__comp(__b, __c)) | |
588 | return __c; | |
589 | else | |
590 | return __b; | |
591 | } | |
592 | ||
12ffa228 BK |
593 | _GLIBCXX_END_NAMESPACE_VERSION |
594 | } // namespace | |
2c1bc4eb PC |
595 | |
596 | #endif /* _EXT_ALGORITHM */ |