libstdc++
ext/algorithm
Go to the documentation of this file.
1// Algorithm extensions -*- C++ -*-
2
3// Copyright (C) 2001-2021 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 <algorithm>
62
63namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
64{
65_GLIBCXX_BEGIN_NAMESPACE_VERSION
66
67 //--------------------------------------------------
68 // copy_n (not part of the C++ standard)
69
70 template<typename _InputIterator, typename _Size, typename _OutputIterator>
71 std::pair<_InputIterator, _OutputIterator>
72 __copy_n(_InputIterator __first, _Size __count,
73 _OutputIterator __result,
74 std::input_iterator_tag)
75 {
76 for ( ; __count > 0; --__count)
77 {
78 *__result = *__first;
79 ++__first;
80 ++__result;
81 }
82 return std::pair<_InputIterator, _OutputIterator>(__first, __result);
83 }
84
85 template<typename _RAIterator, typename _Size, typename _OutputIterator>
86 inline std::pair<_RAIterator, _OutputIterator>
87 __copy_n(_RAIterator __first, _Size __count,
88 _OutputIterator __result,
89 std::random_access_iterator_tag)
90 {
91 _RAIterator __last = __first + __count;
92 return std::pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
93 __last,
94 __result));
95 }
96
97 /**
98 * @brief Copies the range [first,first+count) into [result,result+count).
99 * @param __first An input iterator.
100 * @param __count The number of elements to copy.
101 * @param __result An output iterator.
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 */
111 template<typename _InputIterator, typename _Size, typename _OutputIterator>
112 inline std::pair<_InputIterator, _OutputIterator>
113 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
114 {
115 // concept requirements
116 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
117 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
118 typename std::iterator_traits<_InputIterator>::value_type>)
119
120 return __gnu_cxx::__copy_n(__first, __count, __result,
121 std::__iterator_category(__first));
122 }
123
124 template<typename _InputIterator1, typename _InputIterator2>
125 int
126 __lexicographical_compare_3way(_InputIterator1 __first1,
127 _InputIterator1 __last1,
128 _InputIterator2 __first2,
129 _InputIterator2 __last2)
130 {
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)
141 return !(__first1 == __last1);
142 else
143 return -1;
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 {
152 const std::ptrdiff_t __len1 = __last1 - __first1;
153 const std::ptrdiff_t __len2 = __last2 - __first2;
154 const int __result = __builtin_memcmp(__first1, __first2,
155 (std::min)(__len1, __len2));
156 return __result != 0 ? __result
157 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
158 }
159
160 inline int
161 __lexicographical_compare_3way(const char* __first1, const char* __last1,
162 const char* __first2, const char* __last2)
163 {
164#if CHAR_MAX == SCHAR_MAX
165 return __lexicographical_compare_3way((const signed char*) __first1,
166 (const signed char*) __last1,
167 (const signed char*) __first2,
168 (const signed char*) __last2);
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.
179 * @param __first1 An input iterator.
180 * @param __last1 An input iterator.
181 * @param __first2 An input iterator.
182 * @param __last2 An input iterator.
183 * @return An int, as with @c memcmp.
184 *
185 * The return value will be less than zero if the first range is
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.
189 * This is an SGI extension.
190 * @ingroup SGIextensions
191 */
192 template<typename _InputIterator1, typename _InputIterator2>
193 int
194 lexicographical_compare_3way(_InputIterator1 __first1,
195 _InputIterator1 __last1,
196 _InputIterator2 __first2,
197 _InputIterator2 __last2)
198 {
199 // concept requirements
200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
201 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
202 __glibcxx_function_requires(_LessThanComparableConcept<
203 typename std::iterator_traits<_InputIterator1>::value_type>)
204 __glibcxx_function_requires(_LessThanComparableConcept<
205 typename std::iterator_traits<_InputIterator2>::value_type>)
206 __glibcxx_requires_valid_range(__first1, __last1);
207 __glibcxx_requires_valid_range(__first2, __last2);
208
209 return __lexicographical_compare_3way(__first1, __last1, __first2,
210 __last2);
211 }
212
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.
215 template<typename _InputIterator, typename _Tp, typename _Size>
216 void
217 count(_InputIterator __first, _InputIterator __last,
218 const _Tp& __value,
219 _Size& __n)
220 {
221 // concept requirements
222 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
223 __glibcxx_function_requires(_EqualityComparableConcept<
224 typename std::iterator_traits<_InputIterator>::value_type >)
225 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
226 __glibcxx_requires_valid_range(__first, __last);
227
228 for ( ; __first != __last; ++__first)
229 if (*__first == __value)
230 ++__n;
231 }
232
233 template<typename _InputIterator, typename _Predicate, typename _Size>
234 void
235 count_if(_InputIterator __first, _InputIterator __last,
236 _Predicate __pred,
237 _Size& __n)
238 {
239 // concept requirements
240 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
241 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
242 typename std::iterator_traits<_InputIterator>::value_type>)
243 __glibcxx_requires_valid_range(__first, __last);
244
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
252 /**
253 * This is an SGI extension.
254 * @ingroup SGIextensions
255 * @doctodo
256 */
257 template<typename _ForwardIterator, typename _OutputIterator,
258 typename _Distance>
259 _OutputIterator
260 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
261 _OutputIterator __out, const _Distance __n)
262 {
263 // concept requirements
264 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
265 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
266 typename std::iterator_traits<_ForwardIterator>::value_type>)
267 __glibcxx_requires_valid_range(__first, __last);
268
269 _Distance __remaining = std::distance(__first, __last);
270 _Distance __m = (std::min)(__n, __remaining);
271
272 while (__m > 0)
273 {
274 if ((std::rand() % __remaining) < __m)
275 {
276 *__out = *__first;
277 ++__out;
278 --__m;
279 }
280 --__remaining;
281 ++__first;
282 }
283 return __out;
284 }
285
286 /**
287 * This is an SGI extension.
288 * @ingroup SGIextensions
289 * @doctodo
290 */
291 template<typename _ForwardIterator, typename _OutputIterator,
292 typename _Distance, typename _RandomNumberGenerator>
293 _OutputIterator
294 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
295 _OutputIterator __out, const _Distance __n,
296 _RandomNumberGenerator& __rand)
297 {
298 // concept requirements
299 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
301 typename std::iterator_traits<_ForwardIterator>::value_type>)
302 __glibcxx_function_requires(_UnaryFunctionConcept<
303 _RandomNumberGenerator, _Distance, _Distance>)
304 __glibcxx_requires_valid_range(__first, __last);
305
306 _Distance __remaining = std::distance(__first, __last);
307 _Distance __m = (std::min)(__n, __remaining);
308
309 while (__m > 0)
310 {
311 if (__rand(__remaining) < __m)
312 {
313 *__out = *__first;
314 ++__out;
315 --__m;
316 }
317 --__remaining;
318 ++__first;
319 }
320 return __out;
321 }
322
323 template<typename _InputIterator, typename _RandomAccessIterator,
324 typename _Distance>
325 _RandomAccessIterator
326 __random_sample(_InputIterator __first, _InputIterator __last,
327 _RandomAccessIterator __out,
328 const _Distance __n)
329 {
330 _Distance __m = 0;
331 _Distance __t = __n;
332 for ( ; __first != __last && __m < __n; ++__m, ++__first)
333 __out[__m] = *__first;
334
335 while (__first != __last)
336 {
337 ++__t;
338 _Distance __M = std::rand() % (__t);
339 if (__M < __n)
340 __out[__M] = *__first;
341 ++__first;
342 }
343 return __out + __m;
344 }
345
346 template<typename _InputIterator, typename _RandomAccessIterator,
347 typename _RandomNumberGenerator, typename _Distance>
348 _RandomAccessIterator
349 __random_sample(_InputIterator __first, _InputIterator __last,
350 _RandomAccessIterator __out,
351 _RandomNumberGenerator& __rand,
352 const _Distance __n)
353 {
354 // concept requirements
355 __glibcxx_function_requires(_UnaryFunctionConcept<
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
363 while (__first != __last)
364 {
365 ++__t;
366 _Distance __M = __rand(__t);
367 if (__M < __n)
368 __out[__M] = *__first;
369 ++__first;
370 }
371 return __out + __m;
372 }
373
374 /**
375 * This is an SGI extension.
376 * @ingroup SGIextensions
377 * @doctodo
378 */
379 template<typename _InputIterator, typename _RandomAccessIterator>
380 inline _RandomAccessIterator
381 random_sample(_InputIterator __first, _InputIterator __last,
382 _RandomAccessIterator __out_first,
383 _RandomAccessIterator __out_last)
384 {
385 // concept requirements
386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
387 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
388 _RandomAccessIterator>)
389 __glibcxx_requires_valid_range(__first, __last);
390 __glibcxx_requires_valid_range(__out_first, __out_last);
391
392 return __random_sample(__first, __last,
393 __out_first, __out_last - __out_first);
394 }
395
396 /**
397 * This is an SGI extension.
398 * @ingroup SGIextensions
399 * @doctodo
400 */
401 template<typename _InputIterator, typename _RandomAccessIterator,
402 typename _RandomNumberGenerator>
403 inline _RandomAccessIterator
404 random_sample(_InputIterator __first, _InputIterator __last,
405 _RandomAccessIterator __out_first,
406 _RandomAccessIterator __out_last,
407 _RandomNumberGenerator& __rand)
408 {
409 // concept requirements
410 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
411 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
412 _RandomAccessIterator>)
413 __glibcxx_requires_valid_range(__first, __last);
414 __glibcxx_requires_valid_range(__out_first, __out_last);
415
416 return __random_sample(__first, __last,
417 __out_first, __rand,
418 __out_last - __out_first);
419 }
420
421#if __cplusplus >= 201103L
422 using std::is_heap;
423#else
424 /**
425 * This is an SGI extension.
426 * @ingroup SGIextensions
427 * @doctodo
428 */
429 template<typename _RandomAccessIterator>
430 inline bool
431 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
432 {
433 // concept requirements
434 __glibcxx_function_requires(_RandomAccessIteratorConcept<
435 _RandomAccessIterator>)
436 __glibcxx_function_requires(_LessThanComparableConcept<
437 typename std::iterator_traits<_RandomAccessIterator>::value_type>)
438 __glibcxx_requires_valid_range(__first, __last);
439
440 return std::__is_heap(__first, __last - __first);
441 }
442
443 /**
444 * This is an SGI extension.
445 * @ingroup SGIextensions
446 * @doctodo
447 */
448 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
449 inline bool
450 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
451 _StrictWeakOrdering __comp)
452 {
453 // concept requirements
454 __glibcxx_function_requires(_RandomAccessIteratorConcept<
455 _RandomAccessIterator>)
456 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
457 typename std::iterator_traits<_RandomAccessIterator>::value_type,
458 typename std::iterator_traits<_RandomAccessIterator>::value_type>)
459 __glibcxx_requires_valid_range(__first, __last);
460
461 return std::__is_heap(__first, __comp, __last - __first);
462 }
463#endif
464
465#if __cplusplus >= 201103L
466 using std::is_sorted;
467#else
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
472 /**
473 * This is an SGI extension.
474 * @ingroup SGIextensions
475 * @doctodo
476 */
477 template<typename _ForwardIterator>
478 bool
479 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
480 {
481 // concept requirements
482 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
483 __glibcxx_function_requires(_LessThanComparableConcept<
484 typename std::iterator_traits<_ForwardIterator>::value_type>)
485 __glibcxx_requires_valid_range(__first, __last);
486
487 if (__first == __last)
488 return true;
489
490 _ForwardIterator __next = __first;
491 for (++__next; __next != __last; __first = __next, ++__next)
492 if (*__next < *__first)
493 return false;
494 return true;
495 }
496
497 /**
498 * This is an SGI extension.
499 * @ingroup SGIextensions
500 * @doctodo
501 */
502 template<typename _ForwardIterator, typename _StrictWeakOrdering>
503 bool
504 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
505 _StrictWeakOrdering __comp)
506 {
507 // concept requirements
508 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
509 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
510 typename std::iterator_traits<_ForwardIterator>::value_type,
511 typename std::iterator_traits<_ForwardIterator>::value_type>)
512 __glibcxx_requires_valid_range(__first, __last);
513
514 if (__first == __last)
515 return true;
516
517 _ForwardIterator __next = __first;
518 for (++__next; __next != __last; __first = __next, ++__next)
519 if (__comp(*__next, *__first))
520 return false;
521 return true;
522 }
523#endif // C++11
524
525 /**
526 * @brief Find the median of three values.
527 * @param __a A value.
528 * @param __b A value.
529 * @param __c A value.
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.
560 * @param __a A value.
561 * @param __b A value.
562 * @param __c A value.
563 * @param __comp A binary predicate.
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
593_GLIBCXX_END_NAMESPACE_VERSION
594} // namespace
595
596#endif /* _EXT_ALGORITHM */