1*e4b17023SJohn Marino// Algorithm extensions -*- C++ -*- 2*e4b17023SJohn Marino 3*e4b17023SJohn Marino// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 4*e4b17023SJohn Marino// 2009, 2010, 2011 5*e4b17023SJohn Marino// Free Software Foundation, Inc. 6*e4b17023SJohn Marino// 7*e4b17023SJohn Marino// This file is part of the GNU ISO C++ Library. This library is free 8*e4b17023SJohn Marino// software; you can redistribute it and/or modify it under the 9*e4b17023SJohn Marino// terms of the GNU General Public License as published by the 10*e4b17023SJohn Marino// Free Software Foundation; either version 3, or (at your option) 11*e4b17023SJohn Marino// any later version. 12*e4b17023SJohn Marino 13*e4b17023SJohn Marino// This library is distributed in the hope that it will be useful, 14*e4b17023SJohn Marino// but WITHOUT ANY WARRANTY; without even the implied warranty of 15*e4b17023SJohn Marino// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16*e4b17023SJohn Marino// GNU General Public License for more details. 17*e4b17023SJohn Marino 18*e4b17023SJohn Marino// Under Section 7 of GPL version 3, you are granted additional 19*e4b17023SJohn Marino// permissions described in the GCC Runtime Library Exception, version 20*e4b17023SJohn Marino// 3.1, as published by the Free Software Foundation. 21*e4b17023SJohn Marino 22*e4b17023SJohn Marino// You should have received a copy of the GNU General Public License and 23*e4b17023SJohn Marino// a copy of the GCC Runtime Library Exception along with this program; 24*e4b17023SJohn Marino// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 25*e4b17023SJohn Marino// <http://www.gnu.org/licenses/>. 26*e4b17023SJohn Marino 27*e4b17023SJohn Marino/* 28*e4b17023SJohn Marino * 29*e4b17023SJohn Marino * Copyright (c) 1994 30*e4b17023SJohn Marino * Hewlett-Packard Company 31*e4b17023SJohn Marino * 32*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 33*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 34*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 35*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 36*e4b17023SJohn Marino * in supporting documentation. Hewlett-Packard Company makes no 37*e4b17023SJohn Marino * representations about the suitability of this software for any 38*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 39*e4b17023SJohn Marino * 40*e4b17023SJohn Marino * 41*e4b17023SJohn Marino * Copyright (c) 1996 42*e4b17023SJohn Marino * Silicon Graphics Computer Systems, Inc. 43*e4b17023SJohn Marino * 44*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 45*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 46*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 47*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 48*e4b17023SJohn Marino * in supporting documentation. Silicon Graphics makes no 49*e4b17023SJohn Marino * representations about the suitability of this software for any 50*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 51*e4b17023SJohn Marino */ 52*e4b17023SJohn Marino 53*e4b17023SJohn Marino/** @file ext/algorithm 54*e4b17023SJohn Marino * This file is a GNU extension to the Standard C++ Library (possibly 55*e4b17023SJohn Marino * containing extensions from the HP/SGI STL subset). 56*e4b17023SJohn Marino */ 57*e4b17023SJohn Marino 58*e4b17023SJohn Marino#ifndef _EXT_ALGORITHM 59*e4b17023SJohn Marino#define _EXT_ALGORITHM 1 60*e4b17023SJohn Marino 61*e4b17023SJohn Marino#pragma GCC system_header 62*e4b17023SJohn Marino 63*e4b17023SJohn Marino#include <algorithm> 64*e4b17023SJohn Marino 65*e4b17023SJohn Marinonamespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 66*e4b17023SJohn Marino{ 67*e4b17023SJohn Marino_GLIBCXX_BEGIN_NAMESPACE_VERSION 68*e4b17023SJohn Marino 69*e4b17023SJohn Marino using std::ptrdiff_t; 70*e4b17023SJohn Marino using std::min; 71*e4b17023SJohn Marino using std::pair; 72*e4b17023SJohn Marino using std::input_iterator_tag; 73*e4b17023SJohn Marino using std::random_access_iterator_tag; 74*e4b17023SJohn Marino using std::iterator_traits; 75*e4b17023SJohn Marino 76*e4b17023SJohn Marino //-------------------------------------------------- 77*e4b17023SJohn Marino // copy_n (not part of the C++ standard) 78*e4b17023SJohn Marino 79*e4b17023SJohn Marino template<typename _InputIterator, typename _Size, typename _OutputIterator> 80*e4b17023SJohn Marino pair<_InputIterator, _OutputIterator> 81*e4b17023SJohn Marino __copy_n(_InputIterator __first, _Size __count, 82*e4b17023SJohn Marino _OutputIterator __result, 83*e4b17023SJohn Marino input_iterator_tag) 84*e4b17023SJohn Marino { 85*e4b17023SJohn Marino for ( ; __count > 0; --__count) 86*e4b17023SJohn Marino { 87*e4b17023SJohn Marino *__result = *__first; 88*e4b17023SJohn Marino ++__first; 89*e4b17023SJohn Marino ++__result; 90*e4b17023SJohn Marino } 91*e4b17023SJohn Marino return pair<_InputIterator, _OutputIterator>(__first, __result); 92*e4b17023SJohn Marino } 93*e4b17023SJohn Marino 94*e4b17023SJohn Marino template<typename _RAIterator, typename _Size, typename _OutputIterator> 95*e4b17023SJohn Marino inline pair<_RAIterator, _OutputIterator> 96*e4b17023SJohn Marino __copy_n(_RAIterator __first, _Size __count, 97*e4b17023SJohn Marino _OutputIterator __result, 98*e4b17023SJohn Marino random_access_iterator_tag) 99*e4b17023SJohn Marino { 100*e4b17023SJohn Marino _RAIterator __last = __first + __count; 101*e4b17023SJohn Marino return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 102*e4b17023SJohn Marino __last, 103*e4b17023SJohn Marino __result)); 104*e4b17023SJohn Marino } 105*e4b17023SJohn Marino 106*e4b17023SJohn Marino /** 107*e4b17023SJohn Marino * @brief Copies the range [first,first+count) into [result,result+count). 108*e4b17023SJohn Marino * @param __first An input iterator. 109*e4b17023SJohn Marino * @param __count The number of elements to copy. 110*e4b17023SJohn Marino * @param __result An output iterator. 111*e4b17023SJohn Marino * @return A std::pair composed of first+count and result+count. 112*e4b17023SJohn Marino * 113*e4b17023SJohn Marino * This is an SGI extension. 114*e4b17023SJohn Marino * This inline function will boil down to a call to @c memmove whenever 115*e4b17023SJohn Marino * possible. Failing that, if random access iterators are passed, then the 116*e4b17023SJohn Marino * loop count will be known (and therefore a candidate for compiler 117*e4b17023SJohn Marino * optimizations such as unrolling). 118*e4b17023SJohn Marino * @ingroup SGIextensions 119*e4b17023SJohn Marino */ 120*e4b17023SJohn Marino template<typename _InputIterator, typename _Size, typename _OutputIterator> 121*e4b17023SJohn Marino inline pair<_InputIterator, _OutputIterator> 122*e4b17023SJohn Marino copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 123*e4b17023SJohn Marino { 124*e4b17023SJohn Marino // concept requirements 125*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 126*e4b17023SJohn Marino __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 127*e4b17023SJohn Marino typename iterator_traits<_InputIterator>::value_type>) 128*e4b17023SJohn Marino 129*e4b17023SJohn Marino return __gnu_cxx::__copy_n(__first, __count, __result, 130*e4b17023SJohn Marino std::__iterator_category(__first)); 131*e4b17023SJohn Marino } 132*e4b17023SJohn Marino 133*e4b17023SJohn Marino template<typename _InputIterator1, typename _InputIterator2> 134*e4b17023SJohn Marino int 135*e4b17023SJohn Marino __lexicographical_compare_3way(_InputIterator1 __first1, 136*e4b17023SJohn Marino _InputIterator1 __last1, 137*e4b17023SJohn Marino _InputIterator2 __first2, 138*e4b17023SJohn Marino _InputIterator2 __last2) 139*e4b17023SJohn Marino { 140*e4b17023SJohn Marino while (__first1 != __last1 && __first2 != __last2) 141*e4b17023SJohn Marino { 142*e4b17023SJohn Marino if (*__first1 < *__first2) 143*e4b17023SJohn Marino return -1; 144*e4b17023SJohn Marino if (*__first2 < *__first1) 145*e4b17023SJohn Marino return 1; 146*e4b17023SJohn Marino ++__first1; 147*e4b17023SJohn Marino ++__first2; 148*e4b17023SJohn Marino } 149*e4b17023SJohn Marino if (__first2 == __last2) 150*e4b17023SJohn Marino return !(__first1 == __last1); 151*e4b17023SJohn Marino else 152*e4b17023SJohn Marino return -1; 153*e4b17023SJohn Marino } 154*e4b17023SJohn Marino 155*e4b17023SJohn Marino inline int 156*e4b17023SJohn Marino __lexicographical_compare_3way(const unsigned char* __first1, 157*e4b17023SJohn Marino const unsigned char* __last1, 158*e4b17023SJohn Marino const unsigned char* __first2, 159*e4b17023SJohn Marino const unsigned char* __last2) 160*e4b17023SJohn Marino { 161*e4b17023SJohn Marino const ptrdiff_t __len1 = __last1 - __first1; 162*e4b17023SJohn Marino const ptrdiff_t __len2 = __last2 - __first2; 163*e4b17023SJohn Marino const int __result = __builtin_memcmp(__first1, __first2, 164*e4b17023SJohn Marino min(__len1, __len2)); 165*e4b17023SJohn Marino return __result != 0 ? __result 166*e4b17023SJohn Marino : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 167*e4b17023SJohn Marino } 168*e4b17023SJohn Marino 169*e4b17023SJohn Marino inline int 170*e4b17023SJohn Marino __lexicographical_compare_3way(const char* __first1, const char* __last1, 171*e4b17023SJohn Marino const char* __first2, const char* __last2) 172*e4b17023SJohn Marino { 173*e4b17023SJohn Marino#if CHAR_MAX == SCHAR_MAX 174*e4b17023SJohn Marino return __lexicographical_compare_3way((const signed char*) __first1, 175*e4b17023SJohn Marino (const signed char*) __last1, 176*e4b17023SJohn Marino (const signed char*) __first2, 177*e4b17023SJohn Marino (const signed char*) __last2); 178*e4b17023SJohn Marino#else 179*e4b17023SJohn Marino return __lexicographical_compare_3way((const unsigned char*) __first1, 180*e4b17023SJohn Marino (const unsigned char*) __last1, 181*e4b17023SJohn Marino (const unsigned char*) __first2, 182*e4b17023SJohn Marino (const unsigned char*) __last2); 183*e4b17023SJohn Marino#endif 184*e4b17023SJohn Marino } 185*e4b17023SJohn Marino 186*e4b17023SJohn Marino /** 187*e4b17023SJohn Marino * @brief @c memcmp on steroids. 188*e4b17023SJohn Marino * @param __first1 An input iterator. 189*e4b17023SJohn Marino * @param __last1 An input iterator. 190*e4b17023SJohn Marino * @param __first2 An input iterator. 191*e4b17023SJohn Marino * @param __last2 An input iterator. 192*e4b17023SJohn Marino * @return An int, as with @c memcmp. 193*e4b17023SJohn Marino * 194*e4b17023SJohn Marino * The return value will be less than zero if the first range is 195*e4b17023SJohn Marino * <em>lexigraphically less than</em> the second, greater than zero 196*e4b17023SJohn Marino * if the second range is <em>lexigraphically less than</em> the 197*e4b17023SJohn Marino * first, and zero otherwise. 198*e4b17023SJohn Marino * This is an SGI extension. 199*e4b17023SJohn Marino * @ingroup SGIextensions 200*e4b17023SJohn Marino */ 201*e4b17023SJohn Marino template<typename _InputIterator1, typename _InputIterator2> 202*e4b17023SJohn Marino int 203*e4b17023SJohn Marino lexicographical_compare_3way(_InputIterator1 __first1, 204*e4b17023SJohn Marino _InputIterator1 __last1, 205*e4b17023SJohn Marino _InputIterator2 __first2, 206*e4b17023SJohn Marino _InputIterator2 __last2) 207*e4b17023SJohn Marino { 208*e4b17023SJohn Marino // concept requirements 209*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 210*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 211*e4b17023SJohn Marino __glibcxx_function_requires(_LessThanComparableConcept< 212*e4b17023SJohn Marino typename iterator_traits<_InputIterator1>::value_type>) 213*e4b17023SJohn Marino __glibcxx_function_requires(_LessThanComparableConcept< 214*e4b17023SJohn Marino typename iterator_traits<_InputIterator2>::value_type>) 215*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first1, __last1); 216*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first2, __last2); 217*e4b17023SJohn Marino 218*e4b17023SJohn Marino return __lexicographical_compare_3way(__first1, __last1, __first2, 219*e4b17023SJohn Marino __last2); 220*e4b17023SJohn Marino } 221*e4b17023SJohn Marino 222*e4b17023SJohn Marino // count and count_if: this version, whose return type is void, was present 223*e4b17023SJohn Marino // in the HP STL, and is retained as an extension for backward compatibility. 224*e4b17023SJohn Marino template<typename _InputIterator, typename _Tp, typename _Size> 225*e4b17023SJohn Marino void 226*e4b17023SJohn Marino count(_InputIterator __first, _InputIterator __last, 227*e4b17023SJohn Marino const _Tp& __value, 228*e4b17023SJohn Marino _Size& __n) 229*e4b17023SJohn Marino { 230*e4b17023SJohn Marino // concept requirements 231*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 232*e4b17023SJohn Marino __glibcxx_function_requires(_EqualityComparableConcept< 233*e4b17023SJohn Marino typename iterator_traits<_InputIterator>::value_type >) 234*e4b17023SJohn Marino __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 235*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 236*e4b17023SJohn Marino 237*e4b17023SJohn Marino for ( ; __first != __last; ++__first) 238*e4b17023SJohn Marino if (*__first == __value) 239*e4b17023SJohn Marino ++__n; 240*e4b17023SJohn Marino } 241*e4b17023SJohn Marino 242*e4b17023SJohn Marino template<typename _InputIterator, typename _Predicate, typename _Size> 243*e4b17023SJohn Marino void 244*e4b17023SJohn Marino count_if(_InputIterator __first, _InputIterator __last, 245*e4b17023SJohn Marino _Predicate __pred, 246*e4b17023SJohn Marino _Size& __n) 247*e4b17023SJohn Marino { 248*e4b17023SJohn Marino // concept requirements 249*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 250*e4b17023SJohn Marino __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 251*e4b17023SJohn Marino typename iterator_traits<_InputIterator>::value_type>) 252*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 253*e4b17023SJohn Marino 254*e4b17023SJohn Marino for ( ; __first != __last; ++__first) 255*e4b17023SJohn Marino if (__pred(*__first)) 256*e4b17023SJohn Marino ++__n; 257*e4b17023SJohn Marino } 258*e4b17023SJohn Marino 259*e4b17023SJohn Marino // random_sample and random_sample_n (extensions, not part of the standard). 260*e4b17023SJohn Marino 261*e4b17023SJohn Marino /** 262*e4b17023SJohn Marino * This is an SGI extension. 263*e4b17023SJohn Marino * @ingroup SGIextensions 264*e4b17023SJohn Marino * @doctodo 265*e4b17023SJohn Marino */ 266*e4b17023SJohn Marino template<typename _ForwardIterator, typename _OutputIterator, 267*e4b17023SJohn Marino typename _Distance> 268*e4b17023SJohn Marino _OutputIterator 269*e4b17023SJohn Marino random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 270*e4b17023SJohn Marino _OutputIterator __out, const _Distance __n) 271*e4b17023SJohn Marino { 272*e4b17023SJohn Marino // concept requirements 273*e4b17023SJohn Marino __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 274*e4b17023SJohn Marino __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 275*e4b17023SJohn Marino typename iterator_traits<_ForwardIterator>::value_type>) 276*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 277*e4b17023SJohn Marino 278*e4b17023SJohn Marino _Distance __remaining = std::distance(__first, __last); 279*e4b17023SJohn Marino _Distance __m = min(__n, __remaining); 280*e4b17023SJohn Marino 281*e4b17023SJohn Marino while (__m > 0) 282*e4b17023SJohn Marino { 283*e4b17023SJohn Marino if ((std::rand() % __remaining) < __m) 284*e4b17023SJohn Marino { 285*e4b17023SJohn Marino *__out = *__first; 286*e4b17023SJohn Marino ++__out; 287*e4b17023SJohn Marino --__m; 288*e4b17023SJohn Marino } 289*e4b17023SJohn Marino --__remaining; 290*e4b17023SJohn Marino ++__first; 291*e4b17023SJohn Marino } 292*e4b17023SJohn Marino return __out; 293*e4b17023SJohn Marino } 294*e4b17023SJohn Marino 295*e4b17023SJohn Marino /** 296*e4b17023SJohn Marino * This is an SGI extension. 297*e4b17023SJohn Marino * @ingroup SGIextensions 298*e4b17023SJohn Marino * @doctodo 299*e4b17023SJohn Marino */ 300*e4b17023SJohn Marino template<typename _ForwardIterator, typename _OutputIterator, 301*e4b17023SJohn Marino typename _Distance, typename _RandomNumberGenerator> 302*e4b17023SJohn Marino _OutputIterator 303*e4b17023SJohn Marino random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 304*e4b17023SJohn Marino _OutputIterator __out, const _Distance __n, 305*e4b17023SJohn Marino _RandomNumberGenerator& __rand) 306*e4b17023SJohn Marino { 307*e4b17023SJohn Marino // concept requirements 308*e4b17023SJohn Marino __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 309*e4b17023SJohn Marino __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 310*e4b17023SJohn Marino typename iterator_traits<_ForwardIterator>::value_type>) 311*e4b17023SJohn Marino __glibcxx_function_requires(_UnaryFunctionConcept< 312*e4b17023SJohn Marino _RandomNumberGenerator, _Distance, _Distance>) 313*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 314*e4b17023SJohn Marino 315*e4b17023SJohn Marino _Distance __remaining = std::distance(__first, __last); 316*e4b17023SJohn Marino _Distance __m = min(__n, __remaining); 317*e4b17023SJohn Marino 318*e4b17023SJohn Marino while (__m > 0) 319*e4b17023SJohn Marino { 320*e4b17023SJohn Marino if (__rand(__remaining) < __m) 321*e4b17023SJohn Marino { 322*e4b17023SJohn Marino *__out = *__first; 323*e4b17023SJohn Marino ++__out; 324*e4b17023SJohn Marino --__m; 325*e4b17023SJohn Marino } 326*e4b17023SJohn Marino --__remaining; 327*e4b17023SJohn Marino ++__first; 328*e4b17023SJohn Marino } 329*e4b17023SJohn Marino return __out; 330*e4b17023SJohn Marino } 331*e4b17023SJohn Marino 332*e4b17023SJohn Marino template<typename _InputIterator, typename _RandomAccessIterator, 333*e4b17023SJohn Marino typename _Distance> 334*e4b17023SJohn Marino _RandomAccessIterator 335*e4b17023SJohn Marino __random_sample(_InputIterator __first, _InputIterator __last, 336*e4b17023SJohn Marino _RandomAccessIterator __out, 337*e4b17023SJohn Marino const _Distance __n) 338*e4b17023SJohn Marino { 339*e4b17023SJohn Marino _Distance __m = 0; 340*e4b17023SJohn Marino _Distance __t = __n; 341*e4b17023SJohn Marino for ( ; __first != __last && __m < __n; ++__m, ++__first) 342*e4b17023SJohn Marino __out[__m] = *__first; 343*e4b17023SJohn Marino 344*e4b17023SJohn Marino while (__first != __last) 345*e4b17023SJohn Marino { 346*e4b17023SJohn Marino ++__t; 347*e4b17023SJohn Marino _Distance __M = std::rand() % (__t); 348*e4b17023SJohn Marino if (__M < __n) 349*e4b17023SJohn Marino __out[__M] = *__first; 350*e4b17023SJohn Marino ++__first; 351*e4b17023SJohn Marino } 352*e4b17023SJohn Marino return __out + __m; 353*e4b17023SJohn Marino } 354*e4b17023SJohn Marino 355*e4b17023SJohn Marino template<typename _InputIterator, typename _RandomAccessIterator, 356*e4b17023SJohn Marino typename _RandomNumberGenerator, typename _Distance> 357*e4b17023SJohn Marino _RandomAccessIterator 358*e4b17023SJohn Marino __random_sample(_InputIterator __first, _InputIterator __last, 359*e4b17023SJohn Marino _RandomAccessIterator __out, 360*e4b17023SJohn Marino _RandomNumberGenerator& __rand, 361*e4b17023SJohn Marino const _Distance __n) 362*e4b17023SJohn Marino { 363*e4b17023SJohn Marino // concept requirements 364*e4b17023SJohn Marino __glibcxx_function_requires(_UnaryFunctionConcept< 365*e4b17023SJohn Marino _RandomNumberGenerator, _Distance, _Distance>) 366*e4b17023SJohn Marino 367*e4b17023SJohn Marino _Distance __m = 0; 368*e4b17023SJohn Marino _Distance __t = __n; 369*e4b17023SJohn Marino for ( ; __first != __last && __m < __n; ++__m, ++__first) 370*e4b17023SJohn Marino __out[__m] = *__first; 371*e4b17023SJohn Marino 372*e4b17023SJohn Marino while (__first != __last) 373*e4b17023SJohn Marino { 374*e4b17023SJohn Marino ++__t; 375*e4b17023SJohn Marino _Distance __M = __rand(__t); 376*e4b17023SJohn Marino if (__M < __n) 377*e4b17023SJohn Marino __out[__M] = *__first; 378*e4b17023SJohn Marino ++__first; 379*e4b17023SJohn Marino } 380*e4b17023SJohn Marino return __out + __m; 381*e4b17023SJohn Marino } 382*e4b17023SJohn Marino 383*e4b17023SJohn Marino /** 384*e4b17023SJohn Marino * This is an SGI extension. 385*e4b17023SJohn Marino * @ingroup SGIextensions 386*e4b17023SJohn Marino * @doctodo 387*e4b17023SJohn Marino */ 388*e4b17023SJohn Marino template<typename _InputIterator, typename _RandomAccessIterator> 389*e4b17023SJohn Marino inline _RandomAccessIterator 390*e4b17023SJohn Marino random_sample(_InputIterator __first, _InputIterator __last, 391*e4b17023SJohn Marino _RandomAccessIterator __out_first, 392*e4b17023SJohn Marino _RandomAccessIterator __out_last) 393*e4b17023SJohn Marino { 394*e4b17023SJohn Marino // concept requirements 395*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 396*e4b17023SJohn Marino __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 397*e4b17023SJohn Marino _RandomAccessIterator>) 398*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 399*e4b17023SJohn Marino __glibcxx_requires_valid_range(__out_first, __out_last); 400*e4b17023SJohn Marino 401*e4b17023SJohn Marino return __random_sample(__first, __last, 402*e4b17023SJohn Marino __out_first, __out_last - __out_first); 403*e4b17023SJohn Marino } 404*e4b17023SJohn Marino 405*e4b17023SJohn Marino /** 406*e4b17023SJohn Marino * This is an SGI extension. 407*e4b17023SJohn Marino * @ingroup SGIextensions 408*e4b17023SJohn Marino * @doctodo 409*e4b17023SJohn Marino */ 410*e4b17023SJohn Marino template<typename _InputIterator, typename _RandomAccessIterator, 411*e4b17023SJohn Marino typename _RandomNumberGenerator> 412*e4b17023SJohn Marino inline _RandomAccessIterator 413*e4b17023SJohn Marino random_sample(_InputIterator __first, _InputIterator __last, 414*e4b17023SJohn Marino _RandomAccessIterator __out_first, 415*e4b17023SJohn Marino _RandomAccessIterator __out_last, 416*e4b17023SJohn Marino _RandomNumberGenerator& __rand) 417*e4b17023SJohn Marino { 418*e4b17023SJohn Marino // concept requirements 419*e4b17023SJohn Marino __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 420*e4b17023SJohn Marino __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 421*e4b17023SJohn Marino _RandomAccessIterator>) 422*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 423*e4b17023SJohn Marino __glibcxx_requires_valid_range(__out_first, __out_last); 424*e4b17023SJohn Marino 425*e4b17023SJohn Marino return __random_sample(__first, __last, 426*e4b17023SJohn Marino __out_first, __rand, 427*e4b17023SJohn Marino __out_last - __out_first); 428*e4b17023SJohn Marino } 429*e4b17023SJohn Marino 430*e4b17023SJohn Marino#ifdef __GXX_EXPERIMENTAL_CXX0X__ 431*e4b17023SJohn Marino using std::is_heap; 432*e4b17023SJohn Marino#else 433*e4b17023SJohn Marino /** 434*e4b17023SJohn Marino * This is an SGI extension. 435*e4b17023SJohn Marino * @ingroup SGIextensions 436*e4b17023SJohn Marino * @doctodo 437*e4b17023SJohn Marino */ 438*e4b17023SJohn Marino template<typename _RandomAccessIterator> 439*e4b17023SJohn Marino inline bool 440*e4b17023SJohn Marino is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 441*e4b17023SJohn Marino { 442*e4b17023SJohn Marino // concept requirements 443*e4b17023SJohn Marino __glibcxx_function_requires(_RandomAccessIteratorConcept< 444*e4b17023SJohn Marino _RandomAccessIterator>) 445*e4b17023SJohn Marino __glibcxx_function_requires(_LessThanComparableConcept< 446*e4b17023SJohn Marino typename iterator_traits<_RandomAccessIterator>::value_type>) 447*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 448*e4b17023SJohn Marino 449*e4b17023SJohn Marino return std::__is_heap(__first, __last - __first); 450*e4b17023SJohn Marino } 451*e4b17023SJohn Marino 452*e4b17023SJohn Marino /** 453*e4b17023SJohn Marino * This is an SGI extension. 454*e4b17023SJohn Marino * @ingroup SGIextensions 455*e4b17023SJohn Marino * @doctodo 456*e4b17023SJohn Marino */ 457*e4b17023SJohn Marino template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 458*e4b17023SJohn Marino inline bool 459*e4b17023SJohn Marino is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 460*e4b17023SJohn Marino _StrictWeakOrdering __comp) 461*e4b17023SJohn Marino { 462*e4b17023SJohn Marino // concept requirements 463*e4b17023SJohn Marino __glibcxx_function_requires(_RandomAccessIteratorConcept< 464*e4b17023SJohn Marino _RandomAccessIterator>) 465*e4b17023SJohn Marino __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 466*e4b17023SJohn Marino typename iterator_traits<_RandomAccessIterator>::value_type, 467*e4b17023SJohn Marino typename iterator_traits<_RandomAccessIterator>::value_type>) 468*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 469*e4b17023SJohn Marino 470*e4b17023SJohn Marino return std::__is_heap(__first, __comp, __last - __first); 471*e4b17023SJohn Marino } 472*e4b17023SJohn Marino#endif 473*e4b17023SJohn Marino 474*e4b17023SJohn Marino#ifdef __GXX_EXPERIMENTAL_CXX0X__ 475*e4b17023SJohn Marino using std::is_sorted; 476*e4b17023SJohn Marino#else 477*e4b17023SJohn Marino // is_sorted, a predicated testing whether a range is sorted in 478*e4b17023SJohn Marino // nondescending order. This is an extension, not part of the C++ 479*e4b17023SJohn Marino // standard. 480*e4b17023SJohn Marino 481*e4b17023SJohn Marino /** 482*e4b17023SJohn Marino * This is an SGI extension. 483*e4b17023SJohn Marino * @ingroup SGIextensions 484*e4b17023SJohn Marino * @doctodo 485*e4b17023SJohn Marino */ 486*e4b17023SJohn Marino template<typename _ForwardIterator> 487*e4b17023SJohn Marino bool 488*e4b17023SJohn Marino is_sorted(_ForwardIterator __first, _ForwardIterator __last) 489*e4b17023SJohn Marino { 490*e4b17023SJohn Marino // concept requirements 491*e4b17023SJohn Marino __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 492*e4b17023SJohn Marino __glibcxx_function_requires(_LessThanComparableConcept< 493*e4b17023SJohn Marino typename iterator_traits<_ForwardIterator>::value_type>) 494*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 495*e4b17023SJohn Marino 496*e4b17023SJohn Marino if (__first == __last) 497*e4b17023SJohn Marino return true; 498*e4b17023SJohn Marino 499*e4b17023SJohn Marino _ForwardIterator __next = __first; 500*e4b17023SJohn Marino for (++__next; __next != __last; __first = __next, ++__next) 501*e4b17023SJohn Marino if (*__next < *__first) 502*e4b17023SJohn Marino return false; 503*e4b17023SJohn Marino return true; 504*e4b17023SJohn Marino } 505*e4b17023SJohn Marino 506*e4b17023SJohn Marino /** 507*e4b17023SJohn Marino * This is an SGI extension. 508*e4b17023SJohn Marino * @ingroup SGIextensions 509*e4b17023SJohn Marino * @doctodo 510*e4b17023SJohn Marino */ 511*e4b17023SJohn Marino template<typename _ForwardIterator, typename _StrictWeakOrdering> 512*e4b17023SJohn Marino bool 513*e4b17023SJohn Marino is_sorted(_ForwardIterator __first, _ForwardIterator __last, 514*e4b17023SJohn Marino _StrictWeakOrdering __comp) 515*e4b17023SJohn Marino { 516*e4b17023SJohn Marino // concept requirements 517*e4b17023SJohn Marino __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 518*e4b17023SJohn Marino __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 519*e4b17023SJohn Marino typename iterator_traits<_ForwardIterator>::value_type, 520*e4b17023SJohn Marino typename iterator_traits<_ForwardIterator>::value_type>) 521*e4b17023SJohn Marino __glibcxx_requires_valid_range(__first, __last); 522*e4b17023SJohn Marino 523*e4b17023SJohn Marino if (__first == __last) 524*e4b17023SJohn Marino return true; 525*e4b17023SJohn Marino 526*e4b17023SJohn Marino _ForwardIterator __next = __first; 527*e4b17023SJohn Marino for (++__next; __next != __last; __first = __next, ++__next) 528*e4b17023SJohn Marino if (__comp(*__next, *__first)) 529*e4b17023SJohn Marino return false; 530*e4b17023SJohn Marino return true; 531*e4b17023SJohn Marino } 532*e4b17023SJohn Marino#endif // __GXX_EXPERIMENTAL_CXX0X__ 533*e4b17023SJohn Marino 534*e4b17023SJohn Marino /** 535*e4b17023SJohn Marino * @brief Find the median of three values. 536*e4b17023SJohn Marino * @param __a A value. 537*e4b17023SJohn Marino * @param __b A value. 538*e4b17023SJohn Marino * @param __c A value. 539*e4b17023SJohn Marino * @return One of @p a, @p b or @p c. 540*e4b17023SJohn Marino * 541*e4b17023SJohn Marino * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 542*e4b17023SJohn Marino * then the value returned will be @c m. 543*e4b17023SJohn Marino * This is an SGI extension. 544*e4b17023SJohn Marino * @ingroup SGIextensions 545*e4b17023SJohn Marino */ 546*e4b17023SJohn Marino template<typename _Tp> 547*e4b17023SJohn Marino const _Tp& 548*e4b17023SJohn Marino __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 549*e4b17023SJohn Marino { 550*e4b17023SJohn Marino // concept requirements 551*e4b17023SJohn Marino __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 552*e4b17023SJohn Marino if (__a < __b) 553*e4b17023SJohn Marino if (__b < __c) 554*e4b17023SJohn Marino return __b; 555*e4b17023SJohn Marino else if (__a < __c) 556*e4b17023SJohn Marino return __c; 557*e4b17023SJohn Marino else 558*e4b17023SJohn Marino return __a; 559*e4b17023SJohn Marino else if (__a < __c) 560*e4b17023SJohn Marino return __a; 561*e4b17023SJohn Marino else if (__b < __c) 562*e4b17023SJohn Marino return __c; 563*e4b17023SJohn Marino else 564*e4b17023SJohn Marino return __b; 565*e4b17023SJohn Marino } 566*e4b17023SJohn Marino 567*e4b17023SJohn Marino /** 568*e4b17023SJohn Marino * @brief Find the median of three values using a predicate for comparison. 569*e4b17023SJohn Marino * @param __a A value. 570*e4b17023SJohn Marino * @param __b A value. 571*e4b17023SJohn Marino * @param __c A value. 572*e4b17023SJohn Marino * @param __comp A binary predicate. 573*e4b17023SJohn Marino * @return One of @p a, @p b or @p c. 574*e4b17023SJohn Marino * 575*e4b17023SJohn Marino * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 576*e4b17023SJohn Marino * and @p comp(m,n) are both true then the value returned will be @c m. 577*e4b17023SJohn Marino * This is an SGI extension. 578*e4b17023SJohn Marino * @ingroup SGIextensions 579*e4b17023SJohn Marino */ 580*e4b17023SJohn Marino template<typename _Tp, typename _Compare> 581*e4b17023SJohn Marino const _Tp& 582*e4b17023SJohn Marino __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 583*e4b17023SJohn Marino { 584*e4b17023SJohn Marino // concept requirements 585*e4b17023SJohn Marino __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, 586*e4b17023SJohn Marino _Tp, _Tp>) 587*e4b17023SJohn Marino if (__comp(__a, __b)) 588*e4b17023SJohn Marino if (__comp(__b, __c)) 589*e4b17023SJohn Marino return __b; 590*e4b17023SJohn Marino else if (__comp(__a, __c)) 591*e4b17023SJohn Marino return __c; 592*e4b17023SJohn Marino else 593*e4b17023SJohn Marino return __a; 594*e4b17023SJohn Marino else if (__comp(__a, __c)) 595*e4b17023SJohn Marino return __a; 596*e4b17023SJohn Marino else if (__comp(__b, __c)) 597*e4b17023SJohn Marino return __c; 598*e4b17023SJohn Marino else 599*e4b17023SJohn Marino return __b; 600*e4b17023SJohn Marino } 601*e4b17023SJohn Marino 602*e4b17023SJohn Marino_GLIBCXX_END_NAMESPACE_VERSION 603*e4b17023SJohn Marino} // namespace 604*e4b17023SJohn Marino 605*e4b17023SJohn Marino#endif /* _EXT_ALGORITHM */ 606