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