1 // Algorithm extensions -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
46 * Silicon Graphics Computer Systems, Inc.
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
57 /** @file ext/algorithm
58 * This file is a GNU extension to the Standard C++ Library (possibly
59 * containing extensions from the HP/SGI STL subset).
62 #ifndef _EXT_ALGORITHM
63 #define _EXT_ALGORITHM 1
65 #pragma GCC system_header
69 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
74 using std::input_iterator_tag;
75 using std::random_access_iterator_tag;
76 using std::iterator_traits;
78 //--------------------------------------------------
79 // copy_n (not part of the C++ standard)
81 template<typename _InputIterator, typename _Size, typename _OutputIterator>
82 pair<_InputIterator, _OutputIterator>
83 __copy_n(_InputIterator __first, _Size __count,
84 _OutputIterator __result,
87 for ( ; __count > 0; --__count)
93 return pair<_InputIterator, _OutputIterator>(__first, __result);
96 template<typename _RAIterator, typename _Size, typename _OutputIterator>
97 inline pair<_RAIterator, _OutputIterator>
98 __copy_n(_RAIterator __first, _Size __count,
99 _OutputIterator __result,
100 random_access_iterator_tag)
102 _RAIterator __last = __first + __count;
103 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
109 * @brief Copies the range [first,first+count) into [result,result+count).
110 * @param first An input iterator.
111 * @param count The number of elements to copy.
112 * @param result An output iterator.
113 * @return A std::pair composed of first+count and result+count.
115 * This is an SGI extension.
116 * This inline function will boil down to a call to @c memmove whenever
117 * possible. Failing that, if random access iterators are passed, then the
118 * loop count will be known (and therefore a candidate for compiler
119 * optimizations such as unrolling).
120 * @ingroup SGIextensions
122 template<typename _InputIterator, typename _Size, typename _OutputIterator>
123 inline pair<_InputIterator, _OutputIterator>
124 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
126 // concept requirements
127 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
128 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
129 typename iterator_traits<_InputIterator>::value_type>)
131 return __copy_n(__first, __count, __result,
132 std::__iterator_category(__first));
135 template<typename _InputIterator1, typename _InputIterator2>
137 __lexicographical_compare_3way(_InputIterator1 __first1,
138 _InputIterator1 __last1,
139 _InputIterator2 __first2,
140 _InputIterator2 __last2)
142 while (__first1 != __last1 && __first2 != __last2)
144 if (*__first1 < *__first2)
146 if (*__first2 < *__first1)
151 if (__first2 == __last2)
152 return !(__first1 == __last1);
158 __lexicographical_compare_3way(const unsigned char* __first1,
159 const unsigned char* __last1,
160 const unsigned char* __first2,
161 const unsigned char* __last2)
163 const ptrdiff_t __len1 = __last1 - __first1;
164 const ptrdiff_t __len2 = __last2 - __first2;
165 const int __result = __builtin_memcmp(__first1, __first2,
166 min(__len1, __len2));
167 return __result != 0 ? __result
168 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
172 __lexicographical_compare_3way(const char* __first1, const char* __last1,
173 const char* __first2, const char* __last2)
175 #if CHAR_MAX == SCHAR_MAX
176 return __lexicographical_compare_3way((const signed char*) __first1,
177 (const signed char*) __last1,
178 (const signed char*) __first2,
179 (const signed char*) __last2);
181 return __lexicographical_compare_3way((const unsigned char*) __first1,
182 (const unsigned char*) __last1,
183 (const unsigned char*) __first2,
184 (const unsigned char*) __last2);
189 * @brief @c memcmp on steroids.
190 * @param first1 An input iterator.
191 * @param last1 An input iterator.
192 * @param first2 An input iterator.
193 * @param last2 An input iterator.
194 * @return An int, as with @c memcmp.
196 * The return value will be less than zero if the first range is
197 * "lexigraphically less than" the second, greater than zero if the second
198 * range is "lexigraphically less than" the first, and zero otherwise.
199 * This is an SGI extension.
200 * @ingroup SGIextensions
202 template<typename _InputIterator1, typename _InputIterator2>
204 lexicographical_compare_3way(_InputIterator1 __first1,
205 _InputIterator1 __last1,
206 _InputIterator2 __first2,
207 _InputIterator2 __last2)
209 // concept requirements
210 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
211 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
212 __glibcxx_function_requires(_LessThanComparableConcept<
213 typename iterator_traits<_InputIterator1>::value_type>)
214 __glibcxx_function_requires(_LessThanComparableConcept<
215 typename iterator_traits<_InputIterator2>::value_type>)
216 __glibcxx_requires_valid_range(__first1, __last1);
217 __glibcxx_requires_valid_range(__first2, __last2);
219 return __lexicographical_compare_3way(__first1, __last1, __first2,
223 // count and count_if: this version, whose return type is void, was present
224 // in the HP STL, and is retained as an extension for backward compatibility.
225 template<typename _InputIterator, typename _Tp, typename _Size>
227 count(_InputIterator __first, _InputIterator __last,
231 // concept requirements
232 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
233 __glibcxx_function_requires(_EqualityComparableConcept<
234 typename iterator_traits<_InputIterator>::value_type >)
235 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
236 __glibcxx_requires_valid_range(__first, __last);
238 for ( ; __first != __last; ++__first)
239 if (*__first == __value)
243 template<typename _InputIterator, typename _Predicate, typename _Size>
245 count_if(_InputIterator __first, _InputIterator __last,
249 // concept requirements
250 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
251 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
252 typename iterator_traits<_InputIterator>::value_type>)
253 __glibcxx_requires_valid_range(__first, __last);
255 for ( ; __first != __last; ++__first)
256 if (__pred(*__first))
260 // random_sample and random_sample_n (extensions, not part of the standard).
263 * This is an SGI extension.
264 * @ingroup SGIextensions
267 template<typename _ForwardIterator, typename _OutputIterator,
270 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
271 _OutputIterator __out, const _Distance __n)
273 // concept requirements
274 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
275 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
276 typename iterator_traits<_ForwardIterator>::value_type>)
277 __glibcxx_requires_valid_range(__first, __last);
279 _Distance __remaining = std::distance(__first, __last);
280 _Distance __m = min(__n, __remaining);
284 if ((std::rand() % __remaining) < __m)
297 * This is an SGI extension.
298 * @ingroup SGIextensions
301 template<typename _ForwardIterator, typename _OutputIterator,
302 typename _Distance, typename _RandomNumberGenerator>
304 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
305 _OutputIterator __out, const _Distance __n,
306 _RandomNumberGenerator& __rand)
308 // concept requirements
309 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
310 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
311 typename iterator_traits<_ForwardIterator>::value_type>)
312 __glibcxx_function_requires(_UnaryFunctionConcept<
313 _RandomNumberGenerator, _Distance, _Distance>)
314 __glibcxx_requires_valid_range(__first, __last);
316 _Distance __remaining = std::distance(__first, __last);
317 _Distance __m = min(__n, __remaining);
321 if (__rand(__remaining) < __m)
333 template<typename _InputIterator, typename _RandomAccessIterator,
335 _RandomAccessIterator
336 __random_sample(_InputIterator __first, _InputIterator __last,
337 _RandomAccessIterator __out,
342 for ( ; __first != __last && __m < __n; ++__m, ++__first)
343 __out[__m] = *__first;
345 while (__first != __last)
348 _Distance __M = std::rand() % (__t);
350 __out[__M] = *__first;
356 template<typename _InputIterator, typename _RandomAccessIterator,
357 typename _RandomNumberGenerator, typename _Distance>
358 _RandomAccessIterator
359 __random_sample(_InputIterator __first, _InputIterator __last,
360 _RandomAccessIterator __out,
361 _RandomNumberGenerator& __rand,
364 // concept requirements
365 __glibcxx_function_requires(_UnaryFunctionConcept<
366 _RandomNumberGenerator, _Distance, _Distance>)
370 for ( ; __first != __last && __m < __n; ++__m, ++__first)
371 __out[__m] = *__first;
373 while (__first != __last)
376 _Distance __M = __rand(__t);
378 __out[__M] = *__first;
385 * This is an SGI extension.
386 * @ingroup SGIextensions
389 template<typename _InputIterator, typename _RandomAccessIterator>
390 inline _RandomAccessIterator
391 random_sample(_InputIterator __first, _InputIterator __last,
392 _RandomAccessIterator __out_first,
393 _RandomAccessIterator __out_last)
395 // concept requirements
396 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
397 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
398 _RandomAccessIterator>)
399 __glibcxx_requires_valid_range(__first, __last);
400 __glibcxx_requires_valid_range(__out_first, __out_last);
402 return __random_sample(__first, __last,
403 __out_first, __out_last - __out_first);
407 * This is an SGI extension.
408 * @ingroup SGIextensions
411 template<typename _InputIterator, typename _RandomAccessIterator,
412 typename _RandomNumberGenerator>
413 inline _RandomAccessIterator
414 random_sample(_InputIterator __first, _InputIterator __last,
415 _RandomAccessIterator __out_first,
416 _RandomAccessIterator __out_last,
417 _RandomNumberGenerator& __rand)
419 // concept requirements
420 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
421 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
422 _RandomAccessIterator>)
423 __glibcxx_requires_valid_range(__first, __last);
424 __glibcxx_requires_valid_range(__out_first, __out_last);
426 return __random_sample(__first, __last,
428 __out_last - __out_first);
431 #ifdef __GXX_EXPERIMENTAL_CXX0X__
433 using std::is_sorted;
436 * This is an SGI extension.
437 * @ingroup SGIextensions
440 template<typename _RandomAccessIterator>
442 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
444 // concept requirements
445 __glibcxx_function_requires(_RandomAccessIteratorConcept<
446 _RandomAccessIterator>)
447 __glibcxx_function_requires(_LessThanComparableConcept<
448 typename iterator_traits<_RandomAccessIterator>::value_type>)
449 __glibcxx_requires_valid_range(__first, __last);
451 return std::__is_heap(__first, __last - __first);
455 * This is an SGI extension.
456 * @ingroup SGIextensions
459 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
461 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
462 _StrictWeakOrdering __comp)
464 // concept requirements
465 __glibcxx_function_requires(_RandomAccessIteratorConcept<
466 _RandomAccessIterator>)
467 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
468 typename iterator_traits<_RandomAccessIterator>::value_type,
469 typename iterator_traits<_RandomAccessIterator>::value_type>)
470 __glibcxx_requires_valid_range(__first, __last);
472 return std::__is_heap(__first, __comp, __last - __first);
475 // is_sorted, a predicated testing whether a range is sorted in
476 // nondescending order. This is an extension, not part of the C++
480 * This is an SGI extension.
481 * @ingroup SGIextensions
484 template<typename _ForwardIterator>
486 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
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);
494 if (__first == __last)
497 _ForwardIterator __next = __first;
498 for (++__next; __next != __last; __first = __next, ++__next)
499 if (*__next < *__first)
505 * This is an SGI extension.
506 * @ingroup SGIextensions
509 template<typename _ForwardIterator, typename _StrictWeakOrdering>
511 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
512 _StrictWeakOrdering __comp)
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);
521 if (__first == __last)
524 _ForwardIterator __next = __first;
525 for (++__next; __next != __last; __first = __next, ++__next)
526 if (__comp(*__next, *__first))
532 _GLIBCXX_END_NAMESPACE
534 #endif /* _EXT_ALGORITHM */