197403Sobrien// Algorithm extensions -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file ext/algorithm 5797403Sobrien * This file is a GNU extension to the Standard C++ Library (possibly 58169691Skan * containing extensions from the HP/SGI STL subset). 5997403Sobrien */ 6097403Sobrien 6197403Sobrien#ifndef _EXT_ALGORITHM 62132720Skan#define _EXT_ALGORITHM 1 6397403Sobrien 6497403Sobrien#pragma GCC system_header 65132720Skan 6697403Sobrien#include <algorithm> 6797403Sobrien 68169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 69169691Skan 7097403Sobrien using std::ptrdiff_t; 7197403Sobrien using std::min; 7297403Sobrien using std::pair; 7397403Sobrien using std::input_iterator_tag; 7497403Sobrien using std::random_access_iterator_tag; 7597403Sobrien using std::iterator_traits; 7697403Sobrien 7797403Sobrien //-------------------------------------------------- 7897403Sobrien // copy_n (not part of the C++ standard) 7997403Sobrien 80132720Skan template<typename _InputIterator, typename _Size, typename _OutputIterator> 81132720Skan pair<_InputIterator, _OutputIterator> 82132720Skan __copy_n(_InputIterator __first, _Size __count, 83132720Skan _OutputIterator __result, 8497403Sobrien input_iterator_tag) 8597403Sobrien { 86169691Skan for ( ; __count > 0; --__count) 87169691Skan { 88169691Skan *__result = *__first; 89169691Skan ++__first; 90169691Skan ++__result; 91169691Skan } 92132720Skan return pair<_InputIterator, _OutputIterator>(__first, __result); 9397403Sobrien } 9497403Sobrien 95132720Skan template<typename _RAIterator, typename _Size, typename _OutputIterator> 96132720Skan inline pair<_RAIterator, _OutputIterator> 97132720Skan __copy_n(_RAIterator __first, _Size __count, 98132720Skan _OutputIterator __result, 9997403Sobrien random_access_iterator_tag) 10097403Sobrien { 101132720Skan _RAIterator __last = __first + __count; 102169691Skan return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 103169691Skan __last, 104169691Skan __result)); 10597403Sobrien } 10697403Sobrien 10797403Sobrien /** 10897403Sobrien * @brief Copies the range [first,first+count) into [result,result+count). 10997403Sobrien * @param first An input iterator. 11097403Sobrien * @param count The number of elements to copy. 11197403Sobrien * @param result An output iterator. 11297403Sobrien * @return A std::pair composed of first+count and result+count. 11397403Sobrien * 11497403Sobrien * This is an SGI extension. 11597403Sobrien * This inline function will boil down to a call to @c memmove whenever 11697403Sobrien * possible. Failing that, if random access iterators are passed, then the 11797403Sobrien * loop count will be known (and therefore a candidate for compiler 11897403Sobrien * optimizations such as unrolling). 11997403Sobrien * @ingroup SGIextensions 12097403Sobrien */ 121132720Skan template<typename _InputIterator, typename _Size, typename _OutputIterator> 122132720Skan inline pair<_InputIterator, _OutputIterator> 123132720Skan copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 12497403Sobrien { 12597403Sobrien // concept requirements 126132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 127132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 128132720Skan typename iterator_traits<_InputIterator>::value_type>) 12997403Sobrien 13097403Sobrien return __copy_n(__first, __count, __result, 13197403Sobrien std::__iterator_category(__first)); 13297403Sobrien } 13397403Sobrien 134132720Skan template<typename _InputIterator1, typename _InputIterator2> 13597403Sobrien int 136169691Skan __lexicographical_compare_3way(_InputIterator1 __first1, 137169691Skan _InputIterator1 __last1, 138169691Skan _InputIterator2 __first2, 139169691Skan _InputIterator2 __last2) 14097403Sobrien { 141169691Skan while (__first1 != __last1 && __first2 != __last2) 142169691Skan { 143169691Skan if (*__first1 < *__first2) 144169691Skan return -1; 145169691Skan if (*__first2 < *__first1) 146169691Skan return 1; 147169691Skan ++__first1; 148169691Skan ++__first2; 149169691Skan } 150169691Skan if (__first2 == __last2) 15197403Sobrien return !(__first1 == __last1); 152169691Skan else 15397403Sobrien return -1; 15497403Sobrien } 15597403Sobrien 15697403Sobrien inline int 15797403Sobrien __lexicographical_compare_3way(const unsigned char* __first1, 15897403Sobrien const unsigned char* __last1, 15997403Sobrien const unsigned char* __first2, 16097403Sobrien const unsigned char* __last2) 16197403Sobrien { 16297403Sobrien const ptrdiff_t __len1 = __last1 - __first1; 16397403Sobrien const ptrdiff_t __len2 = __last2 - __first2; 16497403Sobrien const int __result = std::memcmp(__first1, __first2, min(__len1, __len2)); 165132720Skan return __result != 0 ? __result 16697403Sobrien : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 16797403Sobrien } 16897403Sobrien 169132720Skan inline int 17097403Sobrien __lexicographical_compare_3way(const char* __first1, const char* __last1, 17197403Sobrien const char* __first2, const char* __last2) 17297403Sobrien { 17397403Sobrien#if CHAR_MAX == SCHAR_MAX 174169691Skan return __lexicographical_compare_3way((const signed char*) __first1, 175169691Skan (const signed char*) __last1, 176169691Skan (const signed char*) __first2, 177169691Skan (const signed char*) __last2); 17897403Sobrien#else 17997403Sobrien return __lexicographical_compare_3way((const unsigned char*) __first1, 18097403Sobrien (const unsigned char*) __last1, 18197403Sobrien (const unsigned char*) __first2, 18297403Sobrien (const unsigned char*) __last2); 18397403Sobrien#endif 18497403Sobrien } 18597403Sobrien 18697403Sobrien /** 18797403Sobrien * @brief @c memcmp on steroids. 18897403Sobrien * @param first1 An input iterator. 18997403Sobrien * @param last1 An input iterator. 19097403Sobrien * @param first2 An input iterator. 19197403Sobrien * @param last2 An input iterator. 19297403Sobrien * @return An int, as with @c memcmp. 19397403Sobrien * 19497403Sobrien * The return value will be less than zero if the first range is 19597403Sobrien * "lexigraphically less than" the second, greater than zero if the second 19697403Sobrien * range is "lexigraphically less than" the first, and zero otherwise. 19797403Sobrien * This is an SGI extension. 19897403Sobrien * @ingroup SGIextensions 19997403Sobrien */ 200132720Skan template<typename _InputIterator1, typename _InputIterator2> 20197403Sobrien int 202169691Skan lexicographical_compare_3way(_InputIterator1 __first1, 203169691Skan _InputIterator1 __last1, 204169691Skan _InputIterator2 __first2, 205169691Skan _InputIterator2 __last2) 20697403Sobrien { 20797403Sobrien // concept requirements 208132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 209132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 210132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 211132720Skan typename iterator_traits<_InputIterator1>::value_type>) 212132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 213132720Skan typename iterator_traits<_InputIterator2>::value_type>) 214132720Skan __glibcxx_requires_valid_range(__first1, __last1); 215132720Skan __glibcxx_requires_valid_range(__first2, __last2); 21697403Sobrien 217169691Skan return __lexicographical_compare_3way(__first1, __last1, __first2, 218169691Skan __last2); 21997403Sobrien } 22097403Sobrien 22197403Sobrien // count and count_if: this version, whose return type is void, was present 22297403Sobrien // in the HP STL, and is retained as an extension for backward compatibility. 223132720Skan template<typename _InputIterator, typename _Tp, typename _Size> 22497403Sobrien void 225132720Skan count(_InputIterator __first, _InputIterator __last, 22697403Sobrien const _Tp& __value, 22797403Sobrien _Size& __n) 22897403Sobrien { 22997403Sobrien // concept requirements 230132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 231132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 232132720Skan typename iterator_traits<_InputIterator>::value_type >) 233132720Skan __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 234132720Skan __glibcxx_requires_valid_range(__first, __last); 235132720Skan 23697403Sobrien for ( ; __first != __last; ++__first) 23797403Sobrien if (*__first == __value) 23897403Sobrien ++__n; 23997403Sobrien } 24097403Sobrien 241132720Skan template<typename _InputIterator, typename _Predicate, typename _Size> 24297403Sobrien void 243132720Skan count_if(_InputIterator __first, _InputIterator __last, 24497403Sobrien _Predicate __pred, 24597403Sobrien _Size& __n) 24697403Sobrien { 24797403Sobrien // concept requirements 248132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 249132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 250132720Skan typename iterator_traits<_InputIterator>::value_type>) 251132720Skan __glibcxx_requires_valid_range(__first, __last); 252132720Skan 25397403Sobrien for ( ; __first != __last; ++__first) 25497403Sobrien if (__pred(*__first)) 25597403Sobrien ++__n; 25697403Sobrien } 25797403Sobrien 25897403Sobrien // random_sample and random_sample_n (extensions, not part of the standard). 25997403Sobrien 260102782Skan /** 261102782Skan * This is an SGI extension. 262102782Skan * @ingroup SGIextensions 263102782Skan * @doctodo 264102782Skan */ 265169691Skan template<typename _ForwardIterator, typename _OutputIterator, 266169691Skan typename _Distance> 267132720Skan _OutputIterator 268132720Skan random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 269132720Skan _OutputIterator __out, const _Distance __n) 27097403Sobrien { 27197403Sobrien // concept requirements 272132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 273132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 274132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 275132720Skan __glibcxx_requires_valid_range(__first, __last); 27697403Sobrien 27797403Sobrien _Distance __remaining = std::distance(__first, __last); 27897403Sobrien _Distance __m = min(__n, __remaining); 27997403Sobrien 280169691Skan while (__m > 0) 281169691Skan { 282169691Skan if ((std::rand() % __remaining) < __m) 283169691Skan { 28497403Sobrien *__out = *__first; 28597403Sobrien ++__out; 28697403Sobrien --__m; 287169691Skan } 288169691Skan --__remaining; 289169691Skan ++__first; 29097403Sobrien } 29197403Sobrien return __out; 29297403Sobrien } 29397403Sobrien 294102782Skan /** 295102782Skan * This is an SGI extension. 296102782Skan * @ingroup SGIextensions 297102782Skan * @doctodo 298102782Skan */ 299169691Skan template<typename _ForwardIterator, typename _OutputIterator, 300169691Skan typename _Distance, typename _RandomNumberGenerator> 301132720Skan _OutputIterator 302132720Skan random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 303132720Skan _OutputIterator __out, const _Distance __n, 30497403Sobrien _RandomNumberGenerator& __rand) 30597403Sobrien { 30697403Sobrien // concept requirements 307132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 308132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 309132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 310132720Skan __glibcxx_function_requires(_UnaryFunctionConcept< 31197403Sobrien _RandomNumberGenerator, _Distance, _Distance>) 312132720Skan __glibcxx_requires_valid_range(__first, __last); 31397403Sobrien 31497403Sobrien _Distance __remaining = std::distance(__first, __last); 31597403Sobrien _Distance __m = min(__n, __remaining); 31697403Sobrien 317169691Skan while (__m > 0) 318169691Skan { 319169691Skan if (__rand(__remaining) < __m) 320169691Skan { 32197403Sobrien *__out = *__first; 32297403Sobrien ++__out; 32397403Sobrien --__m; 324169691Skan } 325169691Skan --__remaining; 326169691Skan ++__first; 32797403Sobrien } 32897403Sobrien return __out; 32997403Sobrien } 33097403Sobrien 331169691Skan template<typename _InputIterator, typename _RandomAccessIterator, 332169691Skan typename _Distance> 333132720Skan _RandomAccessIterator 334132720Skan __random_sample(_InputIterator __first, _InputIterator __last, 335132720Skan _RandomAccessIterator __out, 33697403Sobrien const _Distance __n) 33797403Sobrien { 33897403Sobrien _Distance __m = 0; 33997403Sobrien _Distance __t = __n; 340132720Skan for ( ; __first != __last && __m < __n; ++__m, ++__first) 34197403Sobrien __out[__m] = *__first; 34297403Sobrien 343169691Skan while (__first != __last) 344169691Skan { 345169691Skan ++__t; 346169691Skan _Distance __M = std::rand() % (__t); 347169691Skan if (__M < __n) 348169691Skan __out[__M] = *__first; 349169691Skan ++__first; 350169691Skan } 35197403Sobrien return __out + __m; 35297403Sobrien } 35397403Sobrien 354132720Skan template<typename _InputIterator, typename _RandomAccessIterator, 35597403Sobrien typename _RandomNumberGenerator, typename _Distance> 356132720Skan _RandomAccessIterator 357132720Skan __random_sample(_InputIterator __first, _InputIterator __last, 358132720Skan _RandomAccessIterator __out, 35997403Sobrien _RandomNumberGenerator& __rand, 36097403Sobrien const _Distance __n) 36197403Sobrien { 36297403Sobrien // concept requirements 363132720Skan __glibcxx_function_requires(_UnaryFunctionConcept< 36497403Sobrien _RandomNumberGenerator, _Distance, _Distance>) 36597403Sobrien 36697403Sobrien _Distance __m = 0; 36797403Sobrien _Distance __t = __n; 36897403Sobrien for ( ; __first != __last && __m < __n; ++__m, ++__first) 36997403Sobrien __out[__m] = *__first; 37097403Sobrien 371169691Skan while (__first != __last) 372169691Skan { 373169691Skan ++__t; 374169691Skan _Distance __M = __rand(__t); 375169691Skan if (__M < __n) 376169691Skan __out[__M] = *__first; 377169691Skan ++__first; 378169691Skan } 37997403Sobrien return __out + __m; 38097403Sobrien } 38197403Sobrien 382102782Skan /** 383102782Skan * This is an SGI extension. 384102782Skan * @ingroup SGIextensions 385102782Skan * @doctodo 386102782Skan */ 387132720Skan template<typename _InputIterator, typename _RandomAccessIterator> 388132720Skan inline _RandomAccessIterator 389132720Skan random_sample(_InputIterator __first, _InputIterator __last, 390169691Skan _RandomAccessIterator __out_first, 391169691Skan _RandomAccessIterator __out_last) 39297403Sobrien { 39397403Sobrien // concept requirements 394132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 395132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 396132720Skan _RandomAccessIterator>) 397132720Skan __glibcxx_requires_valid_range(__first, __last); 398132720Skan __glibcxx_requires_valid_range(__out_first, __out_last); 39997403Sobrien 40097403Sobrien return __random_sample(__first, __last, 40197403Sobrien __out_first, __out_last - __out_first); 40297403Sobrien } 40397403Sobrien 404102782Skan /** 405102782Skan * This is an SGI extension. 406102782Skan * @ingroup SGIextensions 407102782Skan * @doctodo 408102782Skan */ 409132720Skan template<typename _InputIterator, typename _RandomAccessIterator, 41097403Sobrien typename _RandomNumberGenerator> 411132720Skan inline _RandomAccessIterator 412132720Skan random_sample(_InputIterator __first, _InputIterator __last, 413169691Skan _RandomAccessIterator __out_first, 414169691Skan _RandomAccessIterator __out_last, 415132720Skan _RandomNumberGenerator& __rand) 41697403Sobrien { 41797403Sobrien // concept requirements 418132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 419132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 420132720Skan _RandomAccessIterator>) 421132720Skan __glibcxx_requires_valid_range(__first, __last); 422132720Skan __glibcxx_requires_valid_range(__out_first, __out_last); 42397403Sobrien 42497403Sobrien return __random_sample(__first, __last, 42597403Sobrien __out_first, __rand, 42697403Sobrien __out_last - __out_first); 42797403Sobrien } 42897403Sobrien 429102782Skan /** 430102782Skan * This is an SGI extension. 431102782Skan * @ingroup SGIextensions 432102782Skan * @doctodo 433102782Skan */ 434132720Skan template<typename _RandomAccessIterator> 43597403Sobrien inline bool 436132720Skan is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 43797403Sobrien { 43897403Sobrien // concept requirements 439169691Skan __glibcxx_function_requires(_RandomAccessIteratorConcept< 440169691Skan _RandomAccessIterator>) 441132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 442132720Skan typename iterator_traits<_RandomAccessIterator>::value_type>) 443132720Skan __glibcxx_requires_valid_range(__first, __last); 44497403Sobrien 445132720Skan return std::__is_heap(__first, __last - __first); 44697403Sobrien } 44797403Sobrien 448102782Skan /** 449102782Skan * This is an SGI extension. 450102782Skan * @ingroup SGIextensions 451102782Skan * @doctodo 452102782Skan */ 453132720Skan template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 45497403Sobrien inline bool 455132720Skan is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 45697403Sobrien _StrictWeakOrdering __comp) 45797403Sobrien { 45897403Sobrien // concept requirements 459169691Skan __glibcxx_function_requires(_RandomAccessIteratorConcept< 460169691Skan _RandomAccessIterator>) 461132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 462132720Skan typename iterator_traits<_RandomAccessIterator>::value_type, 463132720Skan typename iterator_traits<_RandomAccessIterator>::value_type>) 464132720Skan __glibcxx_requires_valid_range(__first, __last); 46597403Sobrien 466132720Skan return std::__is_heap(__first, __comp, __last - __first); 46797403Sobrien } 46897403Sobrien 46997403Sobrien // is_sorted, a predicated testing whether a range is sorted in 47097403Sobrien // nondescending order. This is an extension, not part of the C++ 47197403Sobrien // standard. 47297403Sobrien 473102782Skan /** 474102782Skan * This is an SGI extension. 475102782Skan * @ingroup SGIextensions 476102782Skan * @doctodo 477102782Skan */ 478132720Skan template<typename _ForwardIterator> 47997403Sobrien bool 480132720Skan is_sorted(_ForwardIterator __first, _ForwardIterator __last) 48197403Sobrien { 48297403Sobrien // concept requirements 483132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 484132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 485132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 486132720Skan __glibcxx_requires_valid_range(__first, __last); 48797403Sobrien 48897403Sobrien if (__first == __last) 48997403Sobrien return true; 49097403Sobrien 491132720Skan _ForwardIterator __next = __first; 492169691Skan for (++__next; __next != __last; __first = __next, ++__next) 49397403Sobrien if (*__next < *__first) 49497403Sobrien return false; 49597403Sobrien return true; 49697403Sobrien } 49797403Sobrien 498102782Skan /** 499102782Skan * This is an SGI extension. 500102782Skan * @ingroup SGIextensions 501102782Skan * @doctodo 502102782Skan */ 503132720Skan template<typename _ForwardIterator, typename _StrictWeakOrdering> 50497403Sobrien bool 505169691Skan is_sorted(_ForwardIterator __first, _ForwardIterator __last, 506169691Skan _StrictWeakOrdering __comp) 50797403Sobrien { 50897403Sobrien // concept requirements 509132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 510132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 511132720Skan typename iterator_traits<_ForwardIterator>::value_type, 512132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 513132720Skan __glibcxx_requires_valid_range(__first, __last); 51497403Sobrien 51597403Sobrien if (__first == __last) 51697403Sobrien return true; 51797403Sobrien 518132720Skan _ForwardIterator __next = __first; 519169691Skan for (++__next; __next != __last; __first = __next, ++__next) 52097403Sobrien if (__comp(*__next, *__first)) 52197403Sobrien return false; 52297403Sobrien return true; 52397403Sobrien } 52497403Sobrien 525169691Skan_GLIBCXX_END_NAMESPACE 526169691Skan 52797403Sobrien#endif /* _EXT_ALGORITHM */ 528