1f2ced752SOliver Tappe/*
2f2ced752SOliver Tappe *
3f2ced752SOliver Tappe * Copyright (c) 1994
4f2ced752SOliver Tappe * Hewlett-Packard Company
5f2ced752SOliver Tappe *
6f2ced752SOliver Tappe * Permission to use, copy, modify, distribute and sell this software
7f2ced752SOliver Tappe * and its documentation for any purpose is hereby granted without fee,
8f2ced752SOliver Tappe * provided that the above copyright notice appear in all copies and
9f2ced752SOliver Tappe * that both that copyright notice and this permission notice appear
10f2ced752SOliver Tappe * in supporting documentation.  Hewlett-Packard Company makes no
11f2ced752SOliver Tappe * representations about the suitability of this software for any
12f2ced752SOliver Tappe * purpose.  It is provided "as is" without express or implied warranty.
13f2ced752SOliver Tappe *
14f2ced752SOliver Tappe *
15f2ced752SOliver Tappe * Copyright (c) 1996
16f2ced752SOliver Tappe * Silicon Graphics Computer Systems, Inc.
17f2ced752SOliver Tappe *
18f2ced752SOliver Tappe * Permission to use, copy, modify, distribute and sell this software
19f2ced752SOliver Tappe * and its documentation for any purpose is hereby granted without fee,
20f2ced752SOliver Tappe * provided that the above copyright notice appear in all copies and
21f2ced752SOliver Tappe * that both that copyright notice and this permission notice appear
22f2ced752SOliver Tappe * in supporting documentation.  Silicon Graphics makes no
23f2ced752SOliver Tappe * representations about the suitability of this software for any
24f2ced752SOliver Tappe * purpose.  It is provided "as is" without express or implied warranty.
25f2ced752SOliver Tappe */
26f2ced752SOliver Tappe
27f2ced752SOliver Tappe/* NOTE: This is an internal header file, included by other STL headers.
28f2ced752SOliver Tappe *   You should not attempt to use it directly.
29f2ced752SOliver Tappe */
30f2ced752SOliver Tappe
31f2ced752SOliver Tappe#ifndef __SGI_STL_INTERNAL_ALGO_H
32f2ced752SOliver Tappe#define __SGI_STL_INTERNAL_ALGO_H
33f2ced752SOliver Tappe
34f2ced752SOliver Tappe#include <stl_heap.h>
35f2ced752SOliver Tappe
36f2ced752SOliver Tappe__STL_BEGIN_NAMESPACE
37f2ced752SOliver Tappe
38f2ced752SOliver Tappe#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
39f2ced752SOliver Tappe#pragma set woff 1209
40f2ced752SOliver Tappe#endif
41f2ced752SOliver Tappe
42f2ced752SOliver Tappe// __median (an extension, not present in the C++ standard).
43f2ced752SOliver Tappe
44f2ced752SOliver Tappetemplate <class _Tp>
45f2ced752SOliver Tappeinline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
46f2ced752SOliver Tappe  if (__a < __b)
47f2ced752SOliver Tappe    if (__b < __c)
48f2ced752SOliver Tappe      return __b;
49f2ced752SOliver Tappe    else if (__a < __c)
50f2ced752SOliver Tappe      return __c;
51f2ced752SOliver Tappe    else
52f2ced752SOliver Tappe      return __a;
53f2ced752SOliver Tappe  else if (__a < __c)
54f2ced752SOliver Tappe    return __a;
55f2ced752SOliver Tappe  else if (__b < __c)
56f2ced752SOliver Tappe    return __c;
57f2ced752SOliver Tappe  else
58f2ced752SOliver Tappe    return __b;
59f2ced752SOliver Tappe}
60f2ced752SOliver Tappe
61f2ced752SOliver Tappetemplate <class _Tp, class _Compare>
62f2ced752SOliver Tappeinline const _Tp&
63f2ced752SOliver Tappe__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
64f2ced752SOliver Tappe  if (__comp(__a, __b))
65f2ced752SOliver Tappe    if (__comp(__b, __c))
66f2ced752SOliver Tappe      return __b;
67f2ced752SOliver Tappe    else if (__comp(__a, __c))
68f2ced752SOliver Tappe      return __c;
69f2ced752SOliver Tappe    else
70f2ced752SOliver Tappe      return __a;
71f2ced752SOliver Tappe  else if (__comp(__a, __c))
72f2ced752SOliver Tappe    return __a;
73f2ced752SOliver Tappe  else if (__comp(__b, __c))
74f2ced752SOliver Tappe    return __c;
75f2ced752SOliver Tappe  else
76f2ced752SOliver Tappe    return __b;
77f2ced752SOliver Tappe}
78f2ced752SOliver Tappe
79f2ced752SOliver Tappe// for_each.  Apply a function to every element of a range.
80f2ced752SOliver Tappetemplate <class _InputIter, class _Function>
81f2ced752SOliver Tappe_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
82f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
83f2ced752SOliver Tappe    __f(*__first);
84f2ced752SOliver Tappe  return __f;
85f2ced752SOliver Tappe}
86f2ced752SOliver Tappe
87f2ced752SOliver Tappe// find and find_if.
88f2ced752SOliver Tappe
89f2ced752SOliver Tappetemplate <class _InputIter, class _Tp>
90f2ced752SOliver Tappeinline _InputIter find(_InputIter __first, _InputIter __last,
91f2ced752SOliver Tappe                       const _Tp& __val,
92f2ced752SOliver Tappe                       input_iterator_tag)
93f2ced752SOliver Tappe{
94f2ced752SOliver Tappe  while (__first != __last && *__first != __val)
95f2ced752SOliver Tappe    ++__first;
96f2ced752SOliver Tappe  return __first;
97f2ced752SOliver Tappe}
98f2ced752SOliver Tappe
99f2ced752SOliver Tappetemplate <class _InputIter, class _Predicate>
100f2ced752SOliver Tappeinline _InputIter find_if(_InputIter __first, _InputIter __last,
101f2ced752SOliver Tappe                          _Predicate __pred,
102f2ced752SOliver Tappe                          input_iterator_tag)
103f2ced752SOliver Tappe{
104f2ced752SOliver Tappe  while (__first != __last && !__pred(*__first))
105f2ced752SOliver Tappe    ++__first;
106f2ced752SOliver Tappe  return __first;
107f2ced752SOliver Tappe}
108f2ced752SOliver Tappe
109f2ced752SOliver Tappe#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
110f2ced752SOliver Tappe
111f2ced752SOliver Tappetemplate <class _RandomAccessIter, class _Tp>
112f2ced752SOliver Tappe_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
113f2ced752SOliver Tappe                       const _Tp& __val,
114f2ced752SOliver Tappe                       random_access_iterator_tag)
115f2ced752SOliver Tappe{
116f2ced752SOliver Tappe  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
117f2ced752SOliver Tappe    = (__last - __first) >> 2;
118f2ced752SOliver Tappe
119f2ced752SOliver Tappe  for ( ; __trip_count > 0 ; --__trip_count) {
120f2ced752SOliver Tappe    if (*__first == __val) return __first;
121f2ced752SOliver Tappe    ++__first;
122f2ced752SOliver Tappe
123f2ced752SOliver Tappe    if (*__first == __val) return __first;
124f2ced752SOliver Tappe    ++__first;
125f2ced752SOliver Tappe
126f2ced752SOliver Tappe    if (*__first == __val) return __first;
127f2ced752SOliver Tappe    ++__first;
128f2ced752SOliver Tappe
129f2ced752SOliver Tappe    if (*__first == __val) return __first;
130f2ced752SOliver Tappe    ++__first;
131f2ced752SOliver Tappe  }
132f2ced752SOliver Tappe
133f2ced752SOliver Tappe  switch(__last - __first) {
134f2ced752SOliver Tappe  case 3:
135f2ced752SOliver Tappe    if (*__first == __val) return __first;
136f2ced752SOliver Tappe    ++__first;
137f2ced752SOliver Tappe  case 2:
138f2ced752SOliver Tappe    if (*__first == __val) return __first;
139f2ced752SOliver Tappe    ++__first;
140f2ced752SOliver Tappe  case 1:
141f2ced752SOliver Tappe    if (*__first == __val) return __first;
142f2ced752SOliver Tappe    ++__first;
143f2ced752SOliver Tappe  case 0:
144f2ced752SOliver Tappe  default:
145f2ced752SOliver Tappe    return __last;
146f2ced752SOliver Tappe  }
147f2ced752SOliver Tappe}
148f2ced752SOliver Tappe
149f2ced752SOliver Tappetemplate <class _RandomAccessIter, class _Predicate>
150f2ced752SOliver Tappe_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
151f2ced752SOliver Tappe                          _Predicate __pred,
152f2ced752SOliver Tappe                          random_access_iterator_tag)
153f2ced752SOliver Tappe{
154f2ced752SOliver Tappe  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
155f2ced752SOliver Tappe    = (__last - __first) >> 2;
156f2ced752SOliver Tappe
157f2ced752SOliver Tappe  for ( ; __trip_count > 0 ; --__trip_count) {
158f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
159f2ced752SOliver Tappe    ++__first;
160f2ced752SOliver Tappe
161f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
162f2ced752SOliver Tappe    ++__first;
163f2ced752SOliver Tappe
164f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
165f2ced752SOliver Tappe    ++__first;
166f2ced752SOliver Tappe
167f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
168f2ced752SOliver Tappe    ++__first;
169f2ced752SOliver Tappe  }
170f2ced752SOliver Tappe
171f2ced752SOliver Tappe  switch(__last - __first) {
172f2ced752SOliver Tappe  case 3:
173f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
174f2ced752SOliver Tappe    ++__first;
175f2ced752SOliver Tappe  case 2:
176f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
177f2ced752SOliver Tappe    ++__first;
178f2ced752SOliver Tappe  case 1:
179f2ced752SOliver Tappe    if (__pred(*__first)) return __first;
180f2ced752SOliver Tappe    ++__first;
181f2ced752SOliver Tappe  case 0:
182f2ced752SOliver Tappe  default:
183f2ced752SOliver Tappe    return __last;
184f2ced752SOliver Tappe  }
185f2ced752SOliver Tappe}
186f2ced752SOliver Tappe
187f2ced752SOliver Tappe#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
188f2ced752SOliver Tappe
189f2ced752SOliver Tappetemplate <class _InputIter, class _Tp>
190f2ced752SOliver Tappeinline _InputIter find(_InputIter __first, _InputIter __last,
191f2ced752SOliver Tappe                       const _Tp& __val)
192f2ced752SOliver Tappe{
193f2ced752SOliver Tappe  return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
194f2ced752SOliver Tappe}
195f2ced752SOliver Tappe
196f2ced752SOliver Tappetemplate <class _InputIter, class _Predicate>
197f2ced752SOliver Tappeinline _InputIter find_if(_InputIter __first, _InputIter __last,
198f2ced752SOliver Tappe                          _Predicate __pred) {
199f2ced752SOliver Tappe  return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
200f2ced752SOliver Tappe}
201f2ced752SOliver Tappe
202f2ced752SOliver Tappe// adjacent_find.
203f2ced752SOliver Tappe
204f2ced752SOliver Tappetemplate <class _ForwardIter>
205f2ced752SOliver Tappe_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
206f2ced752SOliver Tappe  if (__first == __last)
207f2ced752SOliver Tappe    return __last;
208f2ced752SOliver Tappe  _ForwardIter __next = __first;
209f2ced752SOliver Tappe  while(++__next != __last) {
210f2ced752SOliver Tappe    if (*__first == *__next)
211f2ced752SOliver Tappe      return __first;
212f2ced752SOliver Tappe    __first = __next;
213f2ced752SOliver Tappe  }
214f2ced752SOliver Tappe  return __last;
215f2ced752SOliver Tappe}
216f2ced752SOliver Tappe
217f2ced752SOliver Tappetemplate <class _ForwardIter, class _BinaryPredicate>
218f2ced752SOliver Tappe_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
219f2ced752SOliver Tappe                           _BinaryPredicate __binary_pred) {
220f2ced752SOliver Tappe  if (__first == __last)
221f2ced752SOliver Tappe    return __last;
222f2ced752SOliver Tappe  _ForwardIter __next = __first;
223f2ced752SOliver Tappe  while(++__next != __last) {
224f2ced752SOliver Tappe    if (__binary_pred(*__first, *__next))
225f2ced752SOliver Tappe      return __first;
226f2ced752SOliver Tappe    __first = __next;
227f2ced752SOliver Tappe  }
228f2ced752SOliver Tappe  return __last;
229f2ced752SOliver Tappe}
230f2ced752SOliver Tappe
231f2ced752SOliver Tappe// count and count_if.  There are two version of each, one whose return type
232f2ced752SOliver Tappe// type is void and one (present only if we have partial specialization)
233f2ced752SOliver Tappe// whose return type is iterator_traits<_InputIter>::difference_type.  The
234f2ced752SOliver Tappe// C++ standard only has the latter version, but the former, which was present
235f2ced752SOliver Tappe// in the HP STL, is retained for backward compatibility.
236f2ced752SOliver Tappe
237f2ced752SOliver Tappetemplate <class _InputIter, class _Tp, class _Size>
238f2ced752SOliver Tappevoid count(_InputIter __first, _InputIter __last, const _Tp& __value,
239f2ced752SOliver Tappe           _Size& __n) {
240f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
241f2ced752SOliver Tappe    if (*__first == __value)
242f2ced752SOliver Tappe      ++__n;
243f2ced752SOliver Tappe}
244f2ced752SOliver Tappe
245f2ced752SOliver Tappetemplate <class _InputIter, class _Predicate, class _Size>
246f2ced752SOliver Tappevoid count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
247f2ced752SOliver Tappe              _Size& __n) {
248f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
249f2ced752SOliver Tappe    if (__pred(*__first))
250f2ced752SOliver Tappe      ++__n;
251f2ced752SOliver Tappe}
252f2ced752SOliver Tappe
253f2ced752SOliver Tappe#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
254f2ced752SOliver Tappe
255f2ced752SOliver Tappetemplate <class _InputIter, class _Tp>
256f2ced752SOliver Tappetypename iterator_traits<_InputIter>::difference_type
257f2ced752SOliver Tappecount(_InputIter __first, _InputIter __last, const _Tp& __value) {
258f2ced752SOliver Tappe  typename iterator_traits<_InputIter>::difference_type __n = 0;
259f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
260f2ced752SOliver Tappe    if (*__first == __value)
261f2ced752SOliver Tappe      ++__n;
262f2ced752SOliver Tappe  return __n;
263f2ced752SOliver Tappe}
264f2ced752SOliver Tappe
265f2ced752SOliver Tappetemplate <class _InputIter, class _Predicate>
266f2ced752SOliver Tappetypename iterator_traits<_InputIter>::difference_type
267f2ced752SOliver Tappecount_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
268f2ced752SOliver Tappe  typename iterator_traits<_InputIter>::difference_type __n = 0;
269f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
270f2ced752SOliver Tappe    if (__pred(*__first))
271f2ced752SOliver Tappe      ++__n;
272f2ced752SOliver Tappe  return __n;
273f2ced752SOliver Tappe}
274f2ced752SOliver Tappe
275f2ced752SOliver Tappe
276f2ced752SOliver Tappe#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
277f2ced752SOliver Tappe
278f2ced752SOliver Tappe// search.
279f2ced752SOliver Tappe
280f2ced752SOliver Tappetemplate <class _ForwardIter1, class _ForwardIter2>
281f2ced752SOliver Tappe_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
282f2ced752SOliver Tappe                     _ForwardIter2 __first2, _ForwardIter2 __last2)
283f2ced752SOliver Tappe{
284f2ced752SOliver Tappe  // Test for empty ranges
285f2ced752SOliver Tappe  if (__first1 == __last1 || __first2 == __last2)
286f2ced752SOliver Tappe    return __first1;
287f2ced752SOliver Tappe
288f2ced752SOliver Tappe  // Test for a pattern of length 1.
289f2ced752SOliver Tappe  _ForwardIter2 __tmp(__first2);
290f2ced752SOliver Tappe  ++__tmp;
291f2ced752SOliver Tappe  if (__tmp == __last2)
292f2ced752SOliver Tappe    return find(__first1, __last1, *__first2);
293f2ced752SOliver Tappe
294f2ced752SOliver Tappe  // General case.
295f2ced752SOliver Tappe
296f2ced752SOliver Tappe  _ForwardIter2 __p1, __p;
297f2ced752SOliver Tappe
298f2ced752SOliver Tappe  __p1 = __first2; ++__p1;
299f2ced752SOliver Tappe
300f2ced752SOliver Tappe  _ForwardIter1 __current = __first1;
301f2ced752SOliver Tappe
302f2ced752SOliver Tappe  while (__first1 != __last1) {
303f2ced752SOliver Tappe    __first1 = find(__first1, __last1, *__first2);
304f2ced752SOliver Tappe    if (__first1 == __last1)
305f2ced752SOliver Tappe      return __last1;
306f2ced752SOliver Tappe
307f2ced752SOliver Tappe    __p = __p1;
308f2ced752SOliver Tappe    __current = __first1;
309f2ced752SOliver Tappe    if (++__current == __last1)
310f2ced752SOliver Tappe      return __last1;
311f2ced752SOliver Tappe
312f2ced752SOliver Tappe    while (*__current == *__p) {
313f2ced752SOliver Tappe      if (++__p == __last2)
314f2ced752SOliver Tappe        return __first1;
315f2ced752SOliver Tappe      if (++__current == __last1)
316f2ced752SOliver Tappe        return __last1;
317f2ced752SOliver Tappe    }
318f2ced752SOliver Tappe
319f2ced752SOliver Tappe    ++__first1;
320f2ced752SOliver Tappe  }
321f2ced752SOliver Tappe  return __first1;
322f2ced752SOliver Tappe}
323f2ced752SOliver Tappe
324f2ced752SOliver Tappetemplate <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
325f2ced752SOliver Tappe_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
326f2ced752SOliver Tappe                     _ForwardIter2 __first2, _ForwardIter2 __last2,
327f2ced752SOliver Tappe                     _BinaryPred  __predicate)
328f2ced752SOliver Tappe{
329f2ced752SOliver Tappe  // Test for empty ranges
330f2ced752SOliver Tappe  if (__first1 == __last1 || __first2 == __last2)
331f2ced752SOliver Tappe    return __first1;
332f2ced752SOliver Tappe
333f2ced752SOliver Tappe  // Test for a pattern of length 1.
334f2ced752SOliver Tappe  _ForwardIter2 __tmp(__first2);
335f2ced752SOliver Tappe  ++__tmp;
336f2ced752SOliver Tappe  if (__tmp == __last2)
337f2ced752SOliver Tappe    return find(__first1, __last1, *__first2);
338f2ced752SOliver Tappe
339f2ced752SOliver Tappe  // General case.
340f2ced752SOliver Tappe
341f2ced752SOliver Tappe  _ForwardIter2 __p1, __p;
342f2ced752SOliver Tappe
343f2ced752SOliver Tappe  __p1 = __first2; ++__p1;
344f2ced752SOliver Tappe
345f2ced752SOliver Tappe  _ForwardIter1 __current = __first1;
346f2ced752SOliver Tappe
347f2ced752SOliver Tappe  while (__first1 != __last1) {
348f2ced752SOliver Tappe    while (__first1 != __last1) {
349f2ced752SOliver Tappe      if (__predicate(*__first1, *__first2))
350f2ced752SOliver Tappe        break;
351f2ced752SOliver Tappe      ++__first1;
352f2ced752SOliver Tappe    }
353f2ced752SOliver Tappe    while (__first1 != __last1 && !__predicate(*__first1, *__first2))
354f2ced752SOliver Tappe      ++__first1;
355f2ced752SOliver Tappe    if (__first1 == __last1)
356f2ced752SOliver Tappe      return __last1;
357f2ced752SOliver Tappe
358f2ced752SOliver Tappe    __p = __p1;
359f2ced752SOliver Tappe    __current = __first1;
360f2ced752SOliver Tappe    if (++__current == __last1) return __last1;
361f2ced752SOliver Tappe
362f2ced752SOliver Tappe    while (__predicate(*__current, *__p)) {
363f2ced752SOliver Tappe      if (++__p == __last2)
364f2ced752SOliver Tappe        return __first1;
365f2ced752SOliver Tappe      if (++__current == __last1)
366f2ced752SOliver Tappe        return __last1;
367f2ced752SOliver Tappe    }
368f2ced752SOliver Tappe
369f2ced752SOliver Tappe    ++__first1;
370f2ced752SOliver Tappe  }
371f2ced752SOliver Tappe  return __first1;
372f2ced752SOliver Tappe}
373f2ced752SOliver Tappe
374f2ced752SOliver Tappe// search_n.  Search for __count consecutive copies of __val.
375f2ced752SOliver Tappe
376f2ced752SOliver Tappetemplate <class _ForwardIter, class _Integer, class _Tp>
377f2ced752SOliver Tappe_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
378f2ced752SOliver Tappe                      _Integer __count, const _Tp& __val) {
379f2ced752SOliver Tappe  if (__count <= 0)
380f2ced752SOliver Tappe    return __first;
381f2ced752SOliver Tappe  else {
382f2ced752SOliver Tappe    __first = find(__first, __last, __val);
383f2ced752SOliver Tappe    while (__first != __last) {
384f2ced752SOliver Tappe      _Integer __n = __count - 1;
385f2ced752SOliver Tappe      _ForwardIter __i = __first;
386f2ced752SOliver Tappe      ++__i;
387f2ced752SOliver Tappe      while (__i != __last && __n != 0 && *__i == __val) {
388f2ced752SOliver Tappe        ++__i;
389f2ced752SOliver Tappe        --__n;
390f2ced752SOliver Tappe      }
391f2ced752SOliver Tappe      if (__n == 0)
392f2ced752SOliver Tappe        return __first;
393f2ced752SOliver Tappe      else
394f2ced752SOliver Tappe        __first = find(__i, __last, __val);
395f2ced752SOliver Tappe    }
396f2ced752SOliver Tappe    return __last;
397f2ced752SOliver Tappe  }
398f2ced752SOliver Tappe}
399f2ced752SOliver Tappe
400f2ced752SOliver Tappetemplate <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
401f2ced752SOliver Tappe_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
402f2ced752SOliver Tappe                      _Integer __count, const _Tp& __val,
403f2ced752SOliver Tappe                      _BinaryPred __binary_pred) {
404f2ced752SOliver Tappe  if (__count <= 0)
405f2ced752SOliver Tappe    return __first;
406f2ced752SOliver Tappe  else {
407f2ced752SOliver Tappe    while (__first != __last) {
408f2ced752SOliver Tappe      if (__binary_pred(*__first, __val))
409f2ced752SOliver Tappe        break;
410f2ced752SOliver Tappe      ++__first;
411f2ced752SOliver Tappe    }
412f2ced752SOliver Tappe    while (__first != __last) {
413f2ced752SOliver Tappe      _Integer __n = __count - 1;
414f2ced752SOliver Tappe      _ForwardIter __i = __first;
415f2ced752SOliver Tappe      ++__i;
416f2ced752SOliver Tappe      while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
417f2ced752SOliver Tappe        ++__i;
418f2ced752SOliver Tappe        --__n;
419f2ced752SOliver Tappe      }
420f2ced752SOliver Tappe      if (__n == 0)
421f2ced752SOliver Tappe        return __first;
422f2ced752SOliver Tappe      else {
423f2ced752SOliver Tappe        while (__i != __last) {
424f2ced752SOliver Tappe          if (__binary_pred(*__i, __val))
425f2ced752SOliver Tappe            break;
426f2ced752SOliver Tappe          ++__i;
427f2ced752SOliver Tappe        }
428f2ced752SOliver Tappe        __first = __i;
429f2ced752SOliver Tappe      }
430f2ced752SOliver Tappe    }
431f2ced752SOliver Tappe    return __last;
432f2ced752SOliver Tappe  }
433f2ced752SOliver Tappe}
434f2ced752SOliver Tappe
435f2ced752SOliver Tappe// swap_ranges
436f2ced752SOliver Tappe
437f2ced752SOliver Tappetemplate <class _ForwardIter1, class _ForwardIter2>
438f2ced752SOliver Tappe_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
439f2ced752SOliver Tappe                          _ForwardIter2 __first2) {
440f2ced752SOliver Tappe  for ( ; __first1 != __last1; ++__first1, ++__first2)
441f2ced752SOliver Tappe    iter_swap(__first1, __first2);
442f2ced752SOliver Tappe  return __first2;
443f2ced752SOliver Tappe}
444f2ced752SOliver Tappe
445f2ced752SOliver Tappe// transform
446f2ced752SOliver Tappe
447f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _UnaryOperation>
448f2ced752SOliver Tappe_OutputIter transform(_InputIter __first, _InputIter __last,
449f2ced752SOliver Tappe                      _OutputIter __result, _UnaryOperation __oper) {
450f2ced752SOliver Tappe  for ( ; __first != __last; ++__first, ++__result)
451f2ced752SOliver Tappe    *__result = __oper(*__first);
452f2ced752SOliver Tappe  return __result;
453f2ced752SOliver Tappe}
454f2ced752SOliver Tappe
455f2ced752SOliver Tappetemplate <class _InputIter1, class _InputIter2, class _OutputIter,
456f2ced752SOliver Tappe          class _BinaryOperation>
457f2ced752SOliver Tappe_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
458f2ced752SOliver Tappe                      _InputIter2 __first2, _OutputIter __result,
459f2ced752SOliver Tappe                      _BinaryOperation __binary_op) {
460f2ced752SOliver Tappe  for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
461f2ced752SOliver Tappe    *__result = __binary_op(*__first1, *__first2);
462f2ced752SOliver Tappe  return __result;
463f2ced752SOliver Tappe}
464f2ced752SOliver Tappe
465f2ced752SOliver Tappe// replace, replace_if, replace_copy, replace_copy_if
466f2ced752SOliver Tappe
467f2ced752SOliver Tappetemplate <class _ForwardIter, class _Tp>
468f2ced752SOliver Tappevoid replace(_ForwardIter __first, _ForwardIter __last,
469f2ced752SOliver Tappe             const _Tp& __old_value, const _Tp& __new_value) {
470f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
471f2ced752SOliver Tappe    if (*__first == __old_value)
472f2ced752SOliver Tappe      *__first = __new_value;
473f2ced752SOliver Tappe}
474f2ced752SOliver Tappe
475f2ced752SOliver Tappetemplate <class _ForwardIter, class _Predicate, class _Tp>
476f2ced752SOliver Tappevoid replace_if(_ForwardIter __first, _ForwardIter __last,
477f2ced752SOliver Tappe                _Predicate __pred, const _Tp& __new_value) {
478f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
479f2ced752SOliver Tappe    if (__pred(*__first))
480f2ced752SOliver Tappe      *__first = __new_value;
481f2ced752SOliver Tappe}
482f2ced752SOliver Tappe
483f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _Tp>
484f2ced752SOliver Tappe_OutputIter replace_copy(_InputIter __first, _InputIter __last,
485f2ced752SOliver Tappe                         _OutputIter __result,
486f2ced752SOliver Tappe                         const _Tp& __old_value, const _Tp& __new_value) {
487f2ced752SOliver Tappe  for ( ; __first != __last; ++__first, ++__result)
488f2ced752SOliver Tappe    *__result = *__first == __old_value ? __new_value : *__first;
489f2ced752SOliver Tappe  return __result;
490f2ced752SOliver Tappe}
491f2ced752SOliver Tappe
492f2ced752SOliver Tappetemplate <class Iterator, class _OutputIter, class _Predicate, class _Tp>
493f2ced752SOliver Tappe_OutputIter replace_copy_if(Iterator __first, Iterator __last,
494f2ced752SOliver Tappe                            _OutputIter __result,
495f2ced752SOliver Tappe                            _Predicate __pred, const _Tp& __new_value) {
496f2ced752SOliver Tappe  for ( ; __first != __last; ++__first, ++__result)
497f2ced752SOliver Tappe    *__result = __pred(*__first) ? __new_value : *__first;
498f2ced752SOliver Tappe  return __result;
499f2ced752SOliver Tappe}
500f2ced752SOliver Tappe
501f2ced752SOliver Tappe// generate and generate_n
502f2ced752SOliver Tappe
503f2ced752SOliver Tappetemplate <class _ForwardIter, class _Generator>
504f2ced752SOliver Tappevoid generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
505f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
506f2ced752SOliver Tappe    *__first = __gen();
507f2ced752SOliver Tappe}
508f2ced752SOliver Tappe
509f2ced752SOliver Tappetemplate <class _OutputIter, class _Size, class _Generator>
510f2ced752SOliver Tappe_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
511f2ced752SOliver Tappe  for ( ; __n > 0; --__n, ++__first)
512f2ced752SOliver Tappe    *__first = __gen();
513f2ced752SOliver Tappe  return __first;
514f2ced752SOliver Tappe}
515f2ced752SOliver Tappe
516f2ced752SOliver Tappe// remove, remove_if, remove_copy, remove_copy_if
517f2ced752SOliver Tappe
518f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _Tp>
519f2ced752SOliver Tappe_OutputIter remove_copy(_InputIter __first, _InputIter __last,
520f2ced752SOliver Tappe                        _OutputIter __result, const _Tp& __value) {
521f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
522f2ced752SOliver Tappe    if (*__first != __value) {
523f2ced752SOliver Tappe      *__result = *__first;
524f2ced752SOliver Tappe      ++__result;
525f2ced752SOliver Tappe    }
526f2ced752SOliver Tappe  return __result;
527f2ced752SOliver Tappe}
528f2ced752SOliver Tappe
529f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _Predicate>
530f2ced752SOliver Tappe_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
531f2ced752SOliver Tappe                           _OutputIter __result, _Predicate __pred) {
532f2ced752SOliver Tappe  for ( ; __first != __last; ++__first)
533f2ced752SOliver Tappe    if (!__pred(*__first)) {
534f2ced752SOliver Tappe      *__result = *__first;
535f2ced752SOliver Tappe      ++__result;
536f2ced752SOliver Tappe    }
537f2ced752SOliver Tappe  return __result;
538f2ced752SOliver Tappe}
539f2ced752SOliver Tappe
540f2ced752SOliver Tappetemplate <class _ForwardIter, class _Tp>
541f2ced752SOliver Tappe_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
542f2ced752SOliver Tappe                    const _Tp& __value) {
543f2ced752SOliver Tappe  __first = find(__first, __last, __value);
544f2ced752SOliver Tappe  _ForwardIter __i = __first;
545f2ced752SOliver Tappe  return __first == __last ? __first
546f2ced752SOliver Tappe                           : remove_copy(++__i, __last, __first, __value);
547f2ced752SOliver Tappe}
548f2ced752SOliver Tappe
549f2ced752SOliver Tappetemplate <class _ForwardIter, class _Predicate>
550f2ced752SOliver Tappe_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
551f2ced752SOliver Tappe                       _Predicate __pred) {
552f2ced752SOliver Tappe  __first = find_if(__first, __last, __pred);
553f2ced752SOliver Tappe  _ForwardIter __i = __first;
554f2ced752SOliver Tappe  return __first == __last ? __first
555f2ced752SOliver Tappe                           : remove_copy_if(++__i, __last, __first, __pred);
556f2ced752SOliver Tappe}
557f2ced752SOliver Tappe
558f2ced752SOliver Tappe// unique and unique_copy
559f2ced752SOliver Tappe
560f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _Tp>
561f2ced752SOliver Tappe_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
562f2ced752SOliver Tappe                          _OutputIter __result, _Tp*) {
563f2ced752SOliver Tappe  _Tp __value = *__first;
564f2ced752SOliver Tappe  *__result = __value;
565f2ced752SOliver Tappe  while (++__first != __last)
566f2ced752SOliver Tappe    if (__value != *__first) {
567f2ced752SOliver Tappe      __value = *__first;
568f2ced752SOliver Tappe      *++__result = __value;
569f2ced752SOliver Tappe    }
570f2ced752SOliver Tappe  return ++__result;
571f2ced752SOliver Tappe}
572f2ced752SOliver Tappe
573f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter>
574f2ced752SOliver Tappeinline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
575f2ced752SOliver Tappe                                 _OutputIter __result,
576f2ced752SOliver Tappe                                 output_iterator_tag) {
577f2ced752SOliver Tappe  return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
578f2ced752SOliver Tappe}
579f2ced752SOliver Tappe
580f2ced752SOliver Tappetemplate <class _InputIter, class _ForwardIter>
581f2ced752SOliver Tappe_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
582f2ced752SOliver Tappe                           _ForwardIter __result, forward_iterator_tag) {
583f2ced752SOliver Tappe  *__result = *__first;
584f2ced752SOliver Tappe  while (++__first != __last)
585f2ced752SOliver Tappe    if (*__result != *__first) *++__result = *__first;
586f2ced752SOliver Tappe  return ++__result;
587f2ced752SOliver Tappe}
588f2ced752SOliver Tappe
589f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter>
590f2ced752SOliver Tappeinline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
591f2ced752SOliver Tappe                               _OutputIter __result) {
592f2ced752SOliver Tappe  if (__first == __last) return __result;
593f2ced752SOliver Tappe  return __unique_copy(__first, __last, __result,
594f2ced752SOliver Tappe                       __ITERATOR_CATEGORY(__result));
595f2ced752SOliver Tappe}
596f2ced752SOliver Tappe
597f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _BinaryPredicate,
598f2ced752SOliver Tappe          class _Tp>
599f2ced752SOliver Tappe_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
600f2ced752SOliver Tappe                          _OutputIter __result,
601f2ced752SOliver Tappe                          _BinaryPredicate __binary_pred, _Tp*) {
602f2ced752SOliver Tappe  _Tp __value = *__first;
603f2ced752SOliver Tappe  *__result = __value;
604f2ced752SOliver Tappe  while (++__first != __last)
605f2ced752SOliver Tappe    if (!__binary_pred(__value, *__first)) {
606f2ced752SOliver Tappe      __value = *__first;
607f2ced752SOliver Tappe      *++__result = __value;
608f2ced752SOliver Tappe    }
609f2ced752SOliver Tappe  return ++__result;
610f2ced752SOliver Tappe}
611f2ced752SOliver Tappe
612f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _BinaryPredicate>
613f2ced752SOliver Tappeinline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
614f2ced752SOliver Tappe                                 _OutputIter __result,
615f2ced752SOliver Tappe                                 _BinaryPredicate __binary_pred,
616f2ced752SOliver Tappe                                 output_iterator_tag) {
617f2ced752SOliver Tappe  return __unique_copy(__first, __last, __result, __binary_pred,
618f2ced752SOliver Tappe                       __VALUE_TYPE(__first));
619f2ced752SOliver Tappe}
620f2ced752SOliver Tappe
621f2ced752SOliver Tappetemplate <class _InputIter, class _ForwardIter, class _BinaryPredicate>
622f2ced752SOliver Tappe_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
623f2ced752SOliver Tappe                           _ForwardIter __result,
624f2ced752SOliver Tappe                           _BinaryPredicate __binary_pred,
625f2ced752SOliver Tappe                           forward_iterator_tag) {
626f2ced752SOliver Tappe  *__result = *__first;
627f2ced752SOliver Tappe  while (++__first != __last)
628f2ced752SOliver Tappe    if (!__binary_pred(*__result, *__first)) *++__result = *__first;
629f2ced752SOliver Tappe  return ++__result;
630f2ced752SOliver Tappe}
631f2ced752SOliver Tappe
632f2ced752SOliver Tappetemplate <class _InputIter, class _OutputIter, class _BinaryPredicate>
633f2ced752SOliver Tappeinline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
634f2ced752SOliver Tappe                               _OutputIter __result,
635f2ced752SOliver Tappe                               _BinaryPredicate __binary_pred) {
636f2ced752SOliver Tappe  if (__first == __last) return __result;
637f2ced752SOliver Tappe  return __unique_copy(__first, __last, __result, __binary_pred,
638f2ced752SOliver Tappe                       __ITERATOR_CATEGORY(__result));
639f2ced752SOliver Tappe}
640f2ced752SOliver Tappe
641f2ced752SOliver Tappetemplate <class _ForwardIter>
642f2ced752SOliver Tappe_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
643f2ced752SOliver Tappe  __first = adjacent_find(__first, __last);
644f2ced752SOliver Tappe  return unique_copy(__first, __last, __first);
645f2ced752SOliver Tappe}
646f2ced752SOliver Tappe
647f2ced752SOliver Tappetemplate <class _ForwardIter, class _BinaryPredicate>
648f2ced752SOliver Tappe_ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
649f2ced752SOliver Tappe                    _BinaryPredicate __binary_pred) {
650f2ced752SOliver Tappe  __first = adjacent_find(__first, __last, __binary_pred);
651f2ced752SOliver Tappe  return unique_copy(__first, __last, __first, __binary_pred);
652f2ced752SOliver Tappe}
653f2ced752SOliver Tappe
654f2ced752SOliver Tappe// reverse and reverse_copy, and their auxiliary functions
655f2ced752SOliver Tappe
656f2ced752SOliver Tappetemplate <class _BidirectionalIter>
657f2ced752SOliver Tappevoid __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
658f2ced752SOliver Tappe               bidirectional_iterator_tag) {
659f2ced752SOliver Tappe  while (true)
660f2ced752SOliver Tappe    if (__first == __last || __first == --__last)
661f2ced752SOliver Tappe      return;
662f2ced752SOliver Tappe    else
663f2ced752SOliver Tappe      iter_swap(__first++, __last);
664f2ced752SOliver Tappe}
665f2ced752SOliver Tappe
666f2ced752SOliver Tappetemplate <class _RandomAccessIter>
667f2ced752SOliver Tappevoid __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
668f2ced752SOliver Tappe               random_access_iterator_tag) {
669f2ced752SOliver Tappe  while (__first < __last)
670f2ced752SOliver Tappe    iter_swap(__first++, --__last);
671f2ced752SOliver Tappe}
672f2ced752SOliver Tappe
673f2ced752SOliver Tappetemplate <class _BidirectionalIter>
674f2ced752SOliver Tappeinline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
675f2ced752SOliver Tappe  __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
676f2ced752SOliver Tappe}
677f2ced752SOliver Tappe
678f2ced752SOliver Tappetemplate <class _BidirectionalIter, class _OutputIter>
679f2ced752SOliver Tappe_OutputIter reverse_copy(_BidirectionalIter __first,
680f2ced752SOliver Tappe                            _BidirectionalIter __last,
681f2ced752SOliver Tappe                            _OutputIter __result) {
682f2ced752SOliver Tappe  while (__first != __last) {
683f2ced752SOliver Tappe    --__last;
684f2ced752SOliver Tappe    *__result = *__last;
685f2ced752SOliver Tappe    ++__result;
686f2ced752SOliver Tappe  }
687f2ced752SOliver Tappe  return __result;
688f2ced752SOliver Tappe}
689f2ced752SOliver Tappe
690f2ced752SOliver Tappe// rotate and rotate_copy, and their auxiliary functions
691f2ced752SOliver Tappe
692f2ced752SOliver Tappetemplate <class _EuclideanRingElement>
693f2ced752SOliver Tappe_EuclideanRingElement __gcd(_EuclideanRingElement __m,
694f2ced752SOliver Tappe                            _EuclideanRingElement __n)
695f2ced752SOliver Tappe{
696f2ced752SOliver Tappe  while (__n != 0) {
697f2ced752SOliver Tappe    _EuclideanRingElement __t = __m % __n;
698f2ced752SOliver Tappe    __m = __n;
699f2ced752SOliver Tappe    __n = __t;
700f2ced752SOliver Tappe  }
701f2ced752SOliver Tappe  return __m;
702f2ced752SOliver Tappe}
703f2ced752SOliver Tappe
704f2ced752SOliver Tappetemplate <class _ForwardIter, class _Distance>
705f2ced752SOliver Tappe_ForwardIter __rotate(_ForwardIter __first,
706f2ced752SOliver Tappe                      _ForwardIter __middle,
707f2ced752SOliver Tappe                      _ForwardIter __last,
708f2ced752SOliver Tappe                      _Distance*,
709f2ced752SOliver Tappe                      forward_iterator_tag) {
710f2ced752SOliver Tappe  if (__first == __middle)
711f2ced752SOliver Tappe    return __last;
712f2ced752SOliver Tappe  if (__last  == __middle)
713f2ced752SOliver Tappe    return __first;
714f2ced752SOliver Tappe
715f2ced752SOliver Tappe  _ForwardIter __first2 = __middle;
716f2ced752SOliver Tappe  do {
717f2ced752SOliver Tappe    swap(*__first++, *__first2++);
718f2ced752SOliver Tappe    if (__first == __middle)
719f2ced752SOliver Tappe      __middle = __first2;
720f2ced752SOliver Tappe  } while (__first2 != __last);
721f2ced752SOliver Tappe
722f2ced752SOliver Tappe  _ForwardIter __new_middle = __first;
723f2ced752SOliver Tappe
724f2ced752SOliver Tappe  __first2 = __middle;
725f2ced752SOliver Tappe
726f2ced752SOliver Tappe  while (__first2 != __last) {
727f2ced752SOliver Tappe    swap (*__first++, *__first2++);
728f2ced752SOliver Tappe    if (__first == __middle)
729f2ced752SOliver Tappe      __middle = __first2;
730f2ced752SOliver Tappe    else if (__first2 == __last)
731f2ced752SOliver Tappe      __first2 = __middle;
732f2ced752SOliver Tappe  }
733f2ced752SOliver Tappe
734f2ced752SOliver Tappe  return __new_middle;
735f2ced752SOliver Tappe}
736f2ced752SOliver Tappe