diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/algorithm')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/ext/algorithm | 528 |
1 files changed, 0 insertions, 528 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/algorithm b/gcc-4.4.3/libstdc++-v3/include/ext/algorithm deleted file mode 100644 index 4cd1dae80..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/algorithm +++ /dev/null @@ -1,528 +0,0 @@ -// Algorithm extensions -*- C++ -*- - -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 -// Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 3, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -/* - * - * Copyright (c) 1994 - * Hewlett-Packard Company - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Hewlett-Packard Company makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - * - * Copyright (c) 1996 - * Silicon Graphics Computer Systems, Inc. - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Silicon Graphics makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - */ - -/** @file ext/algorithm - * This file is a GNU extension to the Standard C++ Library (possibly - * containing extensions from the HP/SGI STL subset). - */ - -#ifndef _EXT_ALGORITHM -#define _EXT_ALGORITHM 1 - -#pragma GCC system_header - -#include <algorithm> - -_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) - - using std::ptrdiff_t; - using std::min; - using std::pair; - using std::input_iterator_tag; - using std::random_access_iterator_tag; - using std::iterator_traits; - - //-------------------------------------------------- - // copy_n (not part of the C++ standard) - - template<typename _InputIterator, typename _Size, typename _OutputIterator> - pair<_InputIterator, _OutputIterator> - __copy_n(_InputIterator __first, _Size __count, - _OutputIterator __result, - input_iterator_tag) - { - for ( ; __count > 0; --__count) - { - *__result = *__first; - ++__first; - ++__result; - } - return pair<_InputIterator, _OutputIterator>(__first, __result); - } - - template<typename _RAIterator, typename _Size, typename _OutputIterator> - inline pair<_RAIterator, _OutputIterator> - __copy_n(_RAIterator __first, _Size __count, - _OutputIterator __result, - random_access_iterator_tag) - { - _RAIterator __last = __first + __count; - return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, - __last, - __result)); - } - - /** - * @brief Copies the range [first,first+count) into [result,result+count). - * @param first An input iterator. - * @param count The number of elements to copy. - * @param result An output iterator. - * @return A std::pair composed of first+count and result+count. - * - * This is an SGI extension. - * This inline function will boil down to a call to @c memmove whenever - * possible. Failing that, if random access iterators are passed, then the - * loop count will be known (and therefore a candidate for compiler - * optimizations such as unrolling). - * @ingroup SGIextensions - */ - template<typename _InputIterator, typename _Size, typename _OutputIterator> - inline pair<_InputIterator, _OutputIterator> - copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator>::value_type>) - - return __copy_n(__first, __count, __result, - std::__iterator_category(__first)); - } - - template<typename _InputIterator1, typename _InputIterator2> - int - __lexicographical_compare_3way(_InputIterator1 __first1, - _InputIterator1 __last1, - _InputIterator2 __first2, - _InputIterator2 __last2) - { - while (__first1 != __last1 && __first2 != __last2) - { - if (*__first1 < *__first2) - return -1; - if (*__first2 < *__first1) - return 1; - ++__first1; - ++__first2; - } - if (__first2 == __last2) - return !(__first1 == __last1); - else - return -1; - } - - inline int - __lexicographical_compare_3way(const unsigned char* __first1, - const unsigned char* __last1, - const unsigned char* __first2, - const unsigned char* __last2) - { - const ptrdiff_t __len1 = __last1 - __first1; - const ptrdiff_t __len2 = __last2 - __first2; - const int __result = __builtin_memcmp(__first1, __first2, - min(__len1, __len2)); - return __result != 0 ? __result - : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); - } - - inline int - __lexicographical_compare_3way(const char* __first1, const char* __last1, - const char* __first2, const char* __last2) - { -#if CHAR_MAX == SCHAR_MAX - return __lexicographical_compare_3way((const signed char*) __first1, - (const signed char*) __last1, - (const signed char*) __first2, - (const signed char*) __last2); -#else - return __lexicographical_compare_3way((const unsigned char*) __first1, - (const unsigned char*) __last1, - (const unsigned char*) __first2, - (const unsigned char*) __last2); -#endif - } - - /** - * @brief @c memcmp on steroids. - * @param first1 An input iterator. - * @param last1 An input iterator. - * @param first2 An input iterator. - * @param last2 An input iterator. - * @return An int, as with @c memcmp. - * - * The return value will be less than zero if the first range is - * "lexigraphically less than" the second, greater than zero if the second - * range is "lexigraphically less than" the first, and zero otherwise. - * This is an SGI extension. - * @ingroup SGIextensions - */ - template<typename _InputIterator1, typename _InputIterator2> - int - lexicographical_compare_3way(_InputIterator1 __first1, - _InputIterator1 __last1, - _InputIterator2 __first2, - _InputIterator2 __last2) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - return __lexicographical_compare_3way(__first1, __last1, __first2, - __last2); - } - - // count and count_if: this version, whose return type is void, was present - // in the HP STL, and is retained as an extension for backward compatibility. - template<typename _InputIterator, typename _Tp, typename _Size> - void - count(_InputIterator __first, _InputIterator __last, - const _Tp& __value, - _Size& __n) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_InputIterator>::value_type >) - __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) - __glibcxx_requires_valid_range(__first, __last); - - for ( ; __first != __last; ++__first) - if (*__first == __value) - ++__n; - } - - template<typename _InputIterator, typename _Predicate, typename _Size> - void - count_if(_InputIterator __first, _InputIterator __last, - _Predicate __pred, - _Size& __n) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - for ( ; __first != __last; ++__first) - if (__pred(*__first)) - ++__n; - } - - // random_sample and random_sample_n (extensions, not part of the standard). - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _ForwardIterator, typename _OutputIterator, - typename _Distance> - _OutputIterator - random_sample_n(_ForwardIterator __first, _ForwardIterator __last, - _OutputIterator __out, const _Distance __n) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - _Distance __remaining = std::distance(__first, __last); - _Distance __m = min(__n, __remaining); - - while (__m > 0) - { - if ((std::rand() % __remaining) < __m) - { - *__out = *__first; - ++__out; - --__m; - } - --__remaining; - ++__first; - } - return __out; - } - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _ForwardIterator, typename _OutputIterator, - typename _Distance, typename _RandomNumberGenerator> - _OutputIterator - random_sample_n(_ForwardIterator __first, _ForwardIterator __last, - _OutputIterator __out, const _Distance __n, - _RandomNumberGenerator& __rand) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_function_requires(_UnaryFunctionConcept< - _RandomNumberGenerator, _Distance, _Distance>) - __glibcxx_requires_valid_range(__first, __last); - - _Distance __remaining = std::distance(__first, __last); - _Distance __m = min(__n, __remaining); - - while (__m > 0) - { - if (__rand(__remaining) < __m) - { - *__out = *__first; - ++__out; - --__m; - } - --__remaining; - ++__first; - } - return __out; - } - - template<typename _InputIterator, typename _RandomAccessIterator, - typename _Distance> - _RandomAccessIterator - __random_sample(_InputIterator __first, _InputIterator __last, - _RandomAccessIterator __out, - const _Distance __n) - { - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __out[__m] = *__first; - - while (__first != __last) - { - ++__t; - _Distance __M = std::rand() % (__t); - if (__M < __n) - __out[__M] = *__first; - ++__first; - } - return __out + __m; - } - - template<typename _InputIterator, typename _RandomAccessIterator, - typename _RandomNumberGenerator, typename _Distance> - _RandomAccessIterator - __random_sample(_InputIterator __first, _InputIterator __last, - _RandomAccessIterator __out, - _RandomNumberGenerator& __rand, - const _Distance __n) - { - // concept requirements - __glibcxx_function_requires(_UnaryFunctionConcept< - _RandomNumberGenerator, _Distance, _Distance>) - - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __out[__m] = *__first; - - while (__first != __last) - { - ++__t; - _Distance __M = __rand(__t); - if (__M < __n) - __out[__M] = *__first; - ++__first; - } - return __out + __m; - } - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _InputIterator, typename _RandomAccessIterator> - inline _RandomAccessIterator - random_sample(_InputIterator __first, _InputIterator __last, - _RandomAccessIterator __out_first, - _RandomAccessIterator __out_last) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_requires_valid_range(__first, __last); - __glibcxx_requires_valid_range(__out_first, __out_last); - - return __random_sample(__first, __last, - __out_first, __out_last - __out_first); - } - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _InputIterator, typename _RandomAccessIterator, - typename _RandomNumberGenerator> - inline _RandomAccessIterator - random_sample(_InputIterator __first, _InputIterator __last, - _RandomAccessIterator __out_first, - _RandomAccessIterator __out_last, - _RandomNumberGenerator& __rand) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_requires_valid_range(__first, __last); - __glibcxx_requires_valid_range(__out_first, __out_last); - - return __random_sample(__first, __last, - __out_first, __rand, - __out_last - __out_first); - } - -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - using std::is_heap; -#else - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _RandomAccessIterator> - inline bool - is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) - { - // concept requirements - __glibcxx_function_requires(_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_RandomAccessIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - return std::__is_heap(__first, __last - __first); - } - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _RandomAccessIterator, typename _StrictWeakOrdering> - inline bool - is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _StrictWeakOrdering __comp) - { - // concept requirements - __glibcxx_function_requires(_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, - typename iterator_traits<_RandomAccessIterator>::value_type, - typename iterator_traits<_RandomAccessIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - return std::__is_heap(__first, __comp, __last - __first); - } -#endif - - // is_sorted, a predicated testing whether a range is sorted in - // nondescending order. This is an extension, not part of the C++ - // standard. - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _ForwardIterator> - bool - is_sorted(_ForwardIterator __first, _ForwardIterator __last) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return true; - - _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) - if (*__next < *__first) - return false; - return true; - } - - /** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo - */ - template<typename _ForwardIterator, typename _StrictWeakOrdering> - bool - is_sorted(_ForwardIterator __first, _ForwardIterator __last, - _StrictWeakOrdering __comp) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, - typename iterator_traits<_ForwardIterator>::value_type, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return true; - - _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) - if (__comp(*__next, *__first)) - return false; - return true; - } - -_GLIBCXX_END_NAMESPACE - -#endif /* _EXT_ALGORITHM */ |