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