// Algorithm extensions -*- C++ -*-
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
+// 2009, 2010, 2011
+// 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)
+// 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,
// 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.
+// 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.
-// 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.
+// 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/>.
/*
*
* 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
+#define _EXT_ALGORITHM 1
#pragma GCC system_header
-#include <bits/std_algorithm.h>
-namespace __gnu_cxx
+#include <algorithm>
+
+namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
using std::ptrdiff_t;
using std::min;
using std::pair;
//--------------------------------------------------
// 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,
+ 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<_InputIter, _OutputIter>(__first, __result);
+ for ( ; __count > 0; --__count)
+ {
+ *__result = *__first;
+ ++__first;
+ ++__result;
+ }
+ return pair<_InputIterator, _OutputIterator>(__first, __result);
}
- template<typename _RAIter, typename _Size, typename _OutputIter>
- inline pair<_RAIter, _OutputIter>
- __copy_n(_RAIter __first, _Size __count,
- _OutputIter __result,
+ template<typename _RAIterator, typename _Size, typename _OutputIterator>
+ inline pair<_RAIterator, _OutputIterator>
+ __copy_n(_RAIterator __first, _Size __count,
+ _OutputIterator __result,
random_access_iterator_tag)
{
- _RAIter __last = __first + __count;
- return pair<_RAIter, _OutputIter>(__last,
- std::copy(__first, __last, __result));
+ _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.
+ * @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.
* 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)
+ template<typename _InputIterator, typename _Size, typename _OutputIterator>
+ inline pair<_InputIterator, _OutputIterator>
+ copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
{
// concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_InputIter>::value_type>)
+ __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));
+ return __gnu_cxx::__copy_n(__first, __count, __result,
+ std::__iterator_category(__first));
}
- template<typename _InputIter1, typename _InputIter2>
+ template<typename _InputIterator1, typename _InputIterator2>
int
- __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
- _InputIter2 __first2, _InputIter2 __last2)
+ __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) {
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (*__first1 < *__first2)
+ return -1;
+ if (*__first2 < *__first1)
+ return 1;
+ ++__first1;
+ ++__first2;
+ }
+ if (__first2 == __last2)
return !(__first1 == __last1);
- }
- else {
+ else
return -1;
- }
}
inline int
{
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
+ const int __result = __builtin_memcmp(__first1, __first2,
+ min(__len1, __len2));
+ return __result != 0 ? __result
: (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
}
- inline int
+ 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);
+ 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,
/**
* @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.
+ * @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.
+ * <em>lexigraphically less than</em> the second, greater than zero
+ * if the second range is <em>lexigraphically less than</em> the
+ * first, and zero otherwise.
* This is an SGI extension.
* @ingroup SGIextensions
*/
- template<typename _InputIter1, typename _InputIter2>
+ template<typename _InputIterator1, typename _InputIterator2>
int
- lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
- _InputIter2 __first2, _InputIter2 __last2)
+ lexicographical_compare_3way(_InputIterator1 __first1,
+ _InputIterator1 __last1,
+ _InputIterator2 __first2,
+ _InputIterator2 __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);
+ __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 _InputIter, typename _Tp, typename _Size>
+ template<typename _InputIterator, typename _Tp, typename _Size>
void
- count(_InputIter __first, _InputIter __last,
+ count(_InputIterator __first, _InputIterator __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>)
+ __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 _InputIter, typename _Predicate, typename _Size>
+ template<typename _InputIterator, typename _Predicate, typename _Size>
void
- count_if(_InputIter __first, _InputIter __last,
+ count_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred,
_Size& __n)
{
// concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
- typename iterator_traits<_InputIter>::value_type>)
+ __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).
- template<typename _ForwardIter, typename _OutputIter, typename _Distance>
- _OutputIter
- random_sample_n(_ForwardIter __first, _ForwardIter __last,
- _OutputIter __out, const _Distance __n)
+ /**
+ * 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
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
+ __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::__random_number(__remaining) < __m) {
+ while (__m > 0)
+ {
+ if ((std::rand() % __remaining) < __m)
+ {
*__out = *__first;
++__out;
--__m;
+ }
+ --__remaining;
+ ++__first;
}
-
- --__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,
+ /**
+ * 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
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
- __glibcpp_function_requires(_UnaryFunctionConcept<
+ __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) {
+ while (__m > 0)
+ {
+ if (__rand(__remaining) < __m)
+ {
*__out = *__first;
++__out;
--__m;
+ }
+ --__remaining;
+ ++__first;
}
-
- --__remaining;
- ++__first;
- }
return __out;
}
- template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __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)
+ 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;
- }
-
+ while (__first != __last)
+ {
+ ++__t;
+ _Distance __M = std::rand() % (__t);
+ if (__M < __n)
+ __out[__M] = *__first;
+ ++__first;
+ }
return __out + __m;
}
- template<typename _InputIter, typename _RandomAccessIter,
+ template<typename _InputIterator, typename _RandomAccessIterator,
typename _RandomNumberGenerator, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out,
+ _RandomAccessIterator
+ __random_sample(_InputIterator __first, _InputIterator __last,
+ _RandomAccessIterator __out,
_RandomNumberGenerator& __rand,
const _Distance __n)
{
// concept requirements
- __glibcpp_function_requires(_UnaryFunctionConcept<
+ __glibcxx_function_requires(_UnaryFunctionConcept<
_RandomNumberGenerator, _Distance, _Distance>)
_Distance __m = 0;
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;
- }
-
+ 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)
+ /**
+ * 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
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
+ __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);
}
- template<typename _InputIter, typename _RandomAccessIter,
+ /**
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ * @doctodo
+ */
+ template<typename _InputIterator, typename _RandomAccessIterator,
typename _RandomNumberGenerator>
- inline _RandomAccessIter
- random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out_first, _RandomAccessIter __out_last,
- _RandomNumberGenerator& __rand)
+ inline _RandomAccessIterator
+ random_sample(_InputIterator __first, _InputIterator __last,
+ _RandomAccessIterator __out_first,
+ _RandomAccessIterator __out_last,
+ _RandomNumberGenerator& __rand)
{
// concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
+ __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);
}
-
- // 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>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::is_heap;
+#else
+ /**
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ * @doctodo
+ */
+ template<typename _RandomAccessIterator>
inline bool
- is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
+ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
- __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
- __glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIter>::value_type>)
+ __glibcxx_function_requires(_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
+ __glibcxx_requires_valid_range(__first, __last);
- return __is_heap(__first, __last - __first);
+ return std::__is_heap(__first, __last - __first);
}
- template<typename _RandomAccessIter, typename _StrictWeakOrdering>
+ /**
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ * @doctodo
+ */
+ template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
inline bool
- is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
+ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __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);
+ __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
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using std::is_sorted;
+#else
// 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>
+ /**
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ * @doctodo
+ */
+ template<typename _ForwardIterator>
bool
- is_sorted(_ForwardIter __first, _ForwardIter __last)
+ is_sorted(_ForwardIterator __first, _ForwardIterator __last)
{
// concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIter>::value_type>)
+ __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;
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
+ _ForwardIterator __next = __first;
+ for (++__next; __next != __last; __first = __next, ++__next)
if (*__next < *__first)
return false;
- }
-
return true;
}
- template<typename _ForwardIter, typename _StrictWeakOrdering>
+ /**
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ * @doctodo
+ */
+ template<typename _ForwardIterator, typename _StrictWeakOrdering>
bool
- is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
+ is_sorted(_ForwardIterator __first, _ForwardIterator __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>)
+ __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;
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
+ _ForwardIterator __next = __first;
+ for (++__next; __next != __last; __first = __next, ++__next)
if (__comp(*__next, *__first))
return false;
- }
-
return true;
}
+#endif // __GXX_EXPERIMENTAL_CXX0X__
+
+ /**
+ * @brief Find the median of three values.
+ * @param __a A value.
+ * @param __b A value.
+ * @param __c A value.
+ * @return One of @p a, @p b or @p c.
+ *
+ * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
+ * then the value returned will be @c m.
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ */
+ template<typename _Tp>
+ const _Tp&
+ __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ if (__a < __b)
+ if (__b < __c)
+ return __b;
+ else if (__a < __c)
+ return __c;
+ else
+ return __a;
+ else if (__a < __c)
+ return __a;
+ else if (__b < __c)
+ return __c;
+ else
+ return __b;
+ }
+
+ /**
+ * @brief Find the median of three values using a predicate for comparison.
+ * @param __a A value.
+ * @param __b A value.
+ * @param __c A value.
+ * @param __comp A binary predicate.
+ * @return One of @p a, @p b or @p c.
+ *
+ * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
+ * and @p comp(m,n) are both true then the value returned will be @c m.
+ * This is an SGI extension.
+ * @ingroup SGIextensions
+ */
+ template<typename _Tp, typename _Compare>
+ const _Tp&
+ __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
+ _Tp, _Tp>)
+ if (__comp(__a, __b))
+ if (__comp(__b, __c))
+ return __b;
+ else if (__comp(__a, __c))
+ return __c;
+ else
+ return __a;
+ else if (__comp(__a, __c))
+ return __a;
+ else if (__comp(__b, __c))
+ return __c;
+ else
+ return __b;
+ }
-} // namespace __gnu_cxx
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
#endif /* _EXT_ALGORITHM */
OSDN Git Service
