// Algorithm extensions -*- C++ -*-
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
-// Free Software Foundation, Inc.
+// Copyright (C) 2001-2020 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
-// 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/>.
/*
*
#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;
+namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
//--------------------------------------------------
// copy_n (not part of the C++ standard)
template<typename _InputIterator, typename _Size, typename _OutputIterator>
- pair<_InputIterator, _OutputIterator>
+ std::pair<_InputIterator, _OutputIterator>
__copy_n(_InputIterator __first, _Size __count,
_OutputIterator __result,
- input_iterator_tag)
+ std::input_iterator_tag)
{
for ( ; __count > 0; --__count)
{
++__first;
++__result;
}
- return pair<_InputIterator, _OutputIterator>(__first, __result);
+ return std::pair<_InputIterator, _OutputIterator>(__first, __result);
}
template<typename _RAIterator, typename _Size, typename _OutputIterator>
- inline pair<_RAIterator, _OutputIterator>
+ inline std::pair<_RAIterator, _OutputIterator>
__copy_n(_RAIterator __first, _Size __count,
_OutputIterator __result,
- random_access_iterator_tag)
+ std::random_access_iterator_tag)
{
_RAIterator __last = __first + __count;
- return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
+ return std::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.
* @ingroup SGIextensions
*/
template<typename _InputIterator, typename _Size, typename _OutputIterator>
- inline pair<_InputIterator, _OutputIterator>
+ inline std::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>)
+ typename std::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 _InputIterator1, typename _InputIterator2>
const unsigned char* __first2,
const unsigned char* __last2)
{
- const ptrdiff_t __len1 = __last1 - __first1;
- const ptrdiff_t __len2 = __last2 - __first2;
+ const std::ptrdiff_t __len1 = __last1 - __first1;
+ const std::ptrdiff_t __len2 = __last2 - __first2;
const int __result = __builtin_memcmp(__first1, __first2,
- min(__len1, __len2));
+ (std::min)(__len1, __len2));
return __result != 0 ? __result
: (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
}
/**
* @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
*/
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
+ typename std::iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator2>::value_type>)
+ typename std::iterator_traits<_InputIterator2>::value_type>)
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_InputIterator>::value_type >)
+ typename std::iterator_traits<_InputIterator>::value_type >)
__glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
__glibcxx_requires_valid_range(__first, __last);
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
- typename iterator_traits<_InputIterator>::value_type>)
+ typename std::iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
for ( ; __first != __last; ++__first)
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- typename iterator_traits<_ForwardIterator>::value_type>)
+ typename std::iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
_Distance __remaining = std::distance(__first, __last);
- _Distance __m = min(__n, __remaining);
+ _Distance __m = (std::min)(__n, __remaining);
while (__m > 0)
{
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
- typename iterator_traits<_ForwardIterator>::value_type>)
+ typename std::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);
+ _Distance __m = (std::min)(__n, __remaining);
while (__m > 0)
{
__out_last - __out_first);
}
+#if __cplusplus >= 201103L
+ using std::is_heap;
+#else
/**
* This is an SGI extension.
* @ingroup SGIextensions
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ typename std::iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__is_heap(__first, __last - __first);
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_RandomAccessIterator>::value_type,
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ typename std::iterator_traits<_RandomAccessIterator>::value_type,
+ typename std::iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__is_heap(__first, __comp, __last - __first);
}
+#endif
+#if __cplusplus >= 201103L
+ 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.
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
+ typename std::iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_ForwardIterator>::value_type,
- typename iterator_traits<_ForwardIterator>::value_type>)
+ typename std::iterator_traits<_ForwardIterator>::value_type,
+ typename std::iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
return false;
return true;
}
+#endif // C++11
+
+ /**
+ * @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;
+ }
-_GLIBCXX_END_NAMESPACE
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
#endif /* _EXT_ALGORITHM */
projects / thirdparty / gcc.git / blobdiff