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