xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/ext/algorithm (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
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