diff options
Diffstat (limited to 'contrib/libstdc++/include/ext/algorithm')
| -rw-r--r-- | contrib/libstdc++/include/ext/algorithm | 496 |
1 files changed, 496 insertions, 0 deletions
diff --git a/contrib/libstdc++/include/ext/algorithm b/contrib/libstdc++/include/ext/algorithm new file mode 100644 index 0000000..bf72765 --- /dev/null +++ b/contrib/libstdc++/include/ext/algorithm @@ -0,0 +1,496 @@ +// Algorithm extensions -*- C++ -*- + +// Copyright (C) 2001, 2002 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 2, 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. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/* + * + * 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). You should only + * include this header if you are using GCC 3 or later. + */ + +#ifndef _EXT_ALGORITHM +#define _EXT_ALGORITHM + +#pragma GCC system_header +#include <algorithm> + +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 _InputIter, typename _Size, typename _OutputIter> + pair<_InputIter, _OutputIter> + __copy_n(_InputIter __first, _Size __count, + _OutputIter __result, + input_iterator_tag) + { + for ( ; __count > 0; --__count) { + *__result = *__first; + ++__first; + ++__result; + } + return pair<_InputIter, _OutputIter>(__first, __result); + } + + template<typename _RAIter, typename _Size, typename _OutputIter> + inline pair<_RAIter, _OutputIter> + __copy_n(_RAIter __first, _Size __count, + _OutputIter __result, + random_access_iterator_tag) + { + _RAIter __last = __first + __count; + return pair<_RAIter, _OutputIter>(__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 _InputIter, typename _Size, typename _OutputIter> + inline pair<_InputIter, _OutputIter> + copy_n(_InputIter __first, _Size __count, _OutputIter __result) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) + __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>) + + return __copy_n(__first, __count, __result, + std::__iterator_category(__first)); + } + + template<typename _InputIter1, typename _InputIter2> + int + __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __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 = std::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 _InputIter1, typename _InputIter2> + int + lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __last2) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) + __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) + __glibcpp_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>) + __glibcpp_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIter2>::value_type>) + + 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 _InputIter, typename _Tp, typename _Size> + void + count(_InputIter __first, _InputIter __last, + const _Tp& __value, + _Size& __n) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) + __glibcpp_function_requires(_EqualityComparableConcept< + typename iterator_traits<_InputIter>::value_type >) + __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) + for ( ; __first != __last; ++__first) + if (*__first == __value) + ++__n; + } + + template<typename _InputIter, typename _Predicate, typename _Size> + void + count_if(_InputIter __first, _InputIter __last, + _Predicate __pred, + _Size& __n) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) + __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>) + for ( ; __first != __last; ++__first) + if (__pred(*__first)) + ++__n; + } + + // random_sample and random_sample_n (extensions, not part of the standard). + + template<typename _ForwardIter, typename _OutputIter, typename _Distance> + _OutputIter + random_sample_n(_ForwardIter __first, _ForwardIter __last, + _OutputIter __out, const _Distance __n) + { + // concept requirements + __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) + __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, + typename iterator_traits<_ForwardIter>::value_type>) + + _Distance __remaining = std::distance(__first, __last); + _Distance __m = min(__n, __remaining); + + while (__m > 0) { + if (std::__random_number(__remaining) < __m) { + *__out = *__first; + ++__out; + --__m; + } + + --__remaining; + ++__first; + } + return __out; + } + + template<typename _ForwardIter, typename _OutputIter, typename _Distance, + typename _RandomNumberGenerator> + _OutputIter + random_sample_n(_ForwardIter __first, _ForwardIter __last, + _OutputIter __out, const _Distance __n, + _RandomNumberGenerator& __rand) + { + // concept requirements + __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) + __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, + typename iterator_traits<_ForwardIter>::value_type>) + __glibcpp_function_requires(_UnaryFunctionConcept< + _RandomNumberGenerator, _Distance, _Distance>) + + _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 _InputIter, typename _RandomAccessIter, typename _Distance> + _RandomAccessIter + __random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __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::__random_number(__t); + if (__M < __n) + __out[__M] = *__first; + ++__first; + } + + return __out + __m; + } + + template<typename _InputIter, typename _RandomAccessIter, + typename _RandomNumberGenerator, typename _Distance> + _RandomAccessIter + __random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out, + _RandomNumberGenerator& __rand, + const _Distance __n) + { + // concept requirements + __glibcpp_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; + } + + template<typename _InputIter, typename _RandomAccessIter> + inline _RandomAccessIter + random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_first, _RandomAccessIter __out_last) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) + __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>) + + return __random_sample(__first, __last, + __out_first, __out_last - __out_first); + } + + template<typename _InputIter, typename _RandomAccessIter, + typename _RandomNumberGenerator> + inline _RandomAccessIter + random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_first, _RandomAccessIter __out_last, + _RandomNumberGenerator& __rand) + { + // concept requirements + __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) + __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>) + + return __random_sample(__first, __last, + __out_first, __rand, + __out_last - __out_first); + } + + // is_heap, a predicate testing whether or not a range is + // a heap. This function is an extension, not part of the C++ + // standard. + + template<typename _RandomAccessIter, typename _Distance> + bool + __is_heap(_RandomAccessIter __first, _Distance __n) + { + _Distance __parent = 0; + for (_Distance __child = 1; __child < __n; ++__child) { + if (__first[__parent] < __first[__child]) + return false; + if ((__child & 1) == 0) + ++__parent; + } + return true; + } + + template<typename _RandomAccessIter, typename _Distance, + typename _StrictWeakOrdering> + bool + __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, + _Distance __n) + { + _Distance __parent = 0; + for (_Distance __child = 1; __child < __n; ++__child) { + if (__comp(__first[__parent], __first[__child])) + return false; + if ((__child & 1) == 0) + ++__parent; + } + return true; + } + + template<typename _RandomAccessIter> + inline bool + is_heap(_RandomAccessIter __first, _RandomAccessIter __last) + { + // concept requirements + __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) + __glibcpp_function_requires(_LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>) + + return __is_heap(__first, __last - __first); + } + + template<typename _RandomAccessIter, typename _StrictWeakOrdering> + inline bool + is_heap(_RandomAccessIter __first, _RandomAccessIter __last, + _StrictWeakOrdering __comp) + { + // concept requirements + __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) + __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>) + + return __is_heap(__first, __comp, __last - __first); + } + + // is_sorted, a predicated testing whether a range is sorted in + // nondescending order. This is an extension, not part of the C++ + // standard. + + template<typename _ForwardIter> + bool + is_sorted(_ForwardIter __first, _ForwardIter __last) + { + // concept requirements + __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) + __glibcpp_function_requires(_LessThanComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>) + + if (__first == __last) + return true; + + _ForwardIter __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) { + if (*__next < *__first) + return false; + } + + return true; + } + + template<typename _ForwardIter, typename _StrictWeakOrdering> + bool + is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) + { + // concept requirements + __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) + __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>) + + if (__first == __last) + return true; + + _ForwardIter __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) { + if (__comp(*__next, *__first)) + return false; + } + + return true; + } + +} // namespace __gnu_cxx + +#endif /* _EXT_ALGORITHM */ |
