]>
Commit | Line | Data |
---|---|---|
2c1bc4eb PC |
1 | // Algorithm extensions -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2001 Free Software Foundation, Inc. | |
4 | // | |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
30 | /* | |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
56 | #ifndef _EXT_ALGORITHM | |
57 | #define _EXT_ALGORITHM | |
58 | ||
59 | #include <bits/std_algorithm.h> | |
60 | ||
61 | namespace __gnu_cxx | |
62 | { | |
63 | // count and count_if: this version, whose return type is void, was present | |
64 | // in the HP STL, and is retained as an extension for backward compatibility. | |
65 | ||
66 | template<typename _InputIter, typename _Tp, typename _Size> | |
67 | void | |
68 | count(_InputIter __first, _InputIter __last, | |
69 | const _Tp& __value, | |
70 | _Size& __n) | |
71 | { | |
72 | // concept requirements | |
73 | __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) | |
74 | __glibcpp_function_requires(_EqualityComparableConcept< | |
75 | typename std::iterator_traits<_InputIter>::value_type >) | |
76 | __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) | |
77 | for ( ; __first != __last; ++__first) | |
78 | if (*__first == __value) | |
79 | ++__n; | |
80 | } | |
81 | ||
82 | template<typename _InputIter, typename _Predicate, typename _Size> | |
83 | void | |
84 | count_if(_InputIter __first, _InputIter __last, | |
85 | _Predicate __pred, | |
86 | _Size& __n) | |
87 | { | |
88 | // concept requirements | |
89 | __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) | |
90 | __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, | |
91 | typename std::iterator_traits<_InputIter>::value_type>) | |
92 | for ( ; __first != __last; ++__first) | |
93 | if (__pred(*__first)) | |
94 | ++__n; | |
95 | } | |
96 | ||
97 | // random_sample and random_sample_n (extensions, not part of the standard). | |
98 | ||
99 | template<typename _ForwardIter, typename _OutputIter, typename _Distance> | |
100 | _OutputIter | |
101 | random_sample_n(_ForwardIter __first, _ForwardIter __last, | |
102 | _OutputIter __out, const _Distance __n) | |
103 | { | |
104 | // concept requirements | |
105 | __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) | |
106 | __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, | |
107 | typename std::iterator_traits<_ForwardIter>::value_type>) | |
108 | ||
109 | _Distance __remaining = std::distance(__first, __last); | |
110 | _Distance __m = std::min(__n, __remaining); | |
111 | ||
112 | while (__m > 0) { | |
113 | if (std::__random_number(__remaining) < __m) { | |
114 | *__out = *__first; | |
115 | ++__out; | |
116 | --__m; | |
117 | } | |
118 | ||
119 | --__remaining; | |
120 | ++__first; | |
121 | } | |
122 | return __out; | |
123 | } | |
124 | ||
125 | template<typename _ForwardIter, typename _OutputIter, typename _Distance, | |
126 | typename _RandomNumberGenerator> | |
127 | _OutputIter | |
128 | random_sample_n(_ForwardIter __first, _ForwardIter __last, | |
129 | _OutputIter __out, const _Distance __n, | |
130 | _RandomNumberGenerator& __rand) | |
131 | { | |
132 | // concept requirements | |
133 | __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) | |
134 | __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, | |
135 | typename std::iterator_traits<_ForwardIter>::value_type>) | |
136 | __glibcpp_function_requires(_UnaryFunctionConcept< | |
137 | _RandomNumberGenerator, _Distance, _Distance>) | |
138 | ||
139 | _Distance __remaining = std::distance(__first, __last); | |
140 | _Distance __m = std::min(__n, __remaining); | |
141 | ||
142 | while (__m > 0) { | |
143 | if (__rand(__remaining) < __m) { | |
144 | *__out = *__first; | |
145 | ++__out; | |
146 | --__m; | |
147 | } | |
148 | ||
149 | --__remaining; | |
150 | ++__first; | |
151 | } | |
152 | return __out; | |
153 | } | |
154 | ||
155 | template<typename _InputIter, typename _RandomAccessIter, typename _Distance> | |
156 | _RandomAccessIter | |
157 | __random_sample(_InputIter __first, _InputIter __last, | |
158 | _RandomAccessIter __out, | |
159 | const _Distance __n) | |
160 | { | |
161 | _Distance __m = 0; | |
162 | _Distance __t = __n; | |
163 | for ( ; __first != __last && __m < __n; ++__m, ++__first) | |
164 | __out[__m] = *__first; | |
165 | ||
166 | while (__first != __last) { | |
167 | ++__t; | |
168 | _Distance __M = std::__random_number(__t); | |
169 | if (__M < __n) | |
170 | __out[__M] = *__first; | |
171 | ++__first; | |
172 | } | |
173 | ||
174 | return __out + __m; | |
175 | } | |
176 | ||
177 | template<typename _InputIter, typename _RandomAccessIter, | |
178 | typename _RandomNumberGenerator, typename _Distance> | |
179 | _RandomAccessIter | |
180 | __random_sample(_InputIter __first, _InputIter __last, | |
181 | _RandomAccessIter __out, | |
182 | _RandomNumberGenerator& __rand, | |
183 | const _Distance __n) | |
184 | { | |
185 | // concept requirements | |
186 | __glibcpp_function_requires(_UnaryFunctionConcept< | |
187 | _RandomNumberGenerator, _Distance, _Distance>) | |
188 | ||
189 | _Distance __m = 0; | |
190 | _Distance __t = __n; | |
191 | for ( ; __first != __last && __m < __n; ++__m, ++__first) | |
192 | __out[__m] = *__first; | |
193 | ||
194 | while (__first != __last) { | |
195 | ++__t; | |
196 | _Distance __M = __rand(__t); | |
197 | if (__M < __n) | |
198 | __out[__M] = *__first; | |
199 | ++__first; | |
200 | } | |
201 | ||
202 | return __out + __m; | |
203 | } | |
204 | ||
205 | template<typename _InputIter, typename _RandomAccessIter> | |
206 | inline _RandomAccessIter | |
207 | random_sample(_InputIter __first, _InputIter __last, | |
208 | _RandomAccessIter __out_first, _RandomAccessIter __out_last) | |
209 | { | |
210 | // concept requirements | |
211 | __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) | |
212 | __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< | |
213 | _RandomAccessIter>) | |
214 | ||
215 | return __random_sample(__first, __last, | |
216 | __out_first, __out_last - __out_first); | |
217 | } | |
218 | ||
219 | template<typename _InputIter, typename _RandomAccessIter, | |
220 | typename _RandomNumberGenerator> | |
221 | inline _RandomAccessIter | |
222 | random_sample(_InputIter __first, _InputIter __last, | |
223 | _RandomAccessIter __out_first, _RandomAccessIter __out_last, | |
224 | _RandomNumberGenerator& __rand) | |
225 | { | |
226 | // concept requirements | |
227 | __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) | |
228 | __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< | |
229 | _RandomAccessIter>) | |
230 | ||
231 | return __random_sample(__first, __last, | |
232 | __out_first, __rand, | |
233 | __out_last - __out_first); | |
234 | } | |
235 | ||
236 | // is_heap, a predicate testing whether or not a range is | |
237 | // a heap. This function is an extension, not part of the C++ | |
238 | // standard. | |
239 | ||
240 | template<typename _RandomAccessIter, typename _Distance> | |
241 | bool | |
242 | __is_heap(_RandomAccessIter __first, _Distance __n) | |
243 | { | |
244 | _Distance __parent = 0; | |
245 | for (_Distance __child = 1; __child < __n; ++__child) { | |
246 | if (__first[__parent] < __first[__child]) | |
247 | return false; | |
248 | if ((__child & 1) == 0) | |
249 | ++__parent; | |
250 | } | |
251 | return true; | |
252 | } | |
253 | ||
254 | template<typename _RandomAccessIter, typename _Distance, | |
255 | typename _StrictWeakOrdering> | |
256 | bool | |
257 | __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, | |
258 | _Distance __n) | |
259 | { | |
260 | _Distance __parent = 0; | |
261 | for (_Distance __child = 1; __child < __n; ++__child) { | |
262 | if (__comp(__first[__parent], __first[__child])) | |
263 | return false; | |
264 | if ((__child & 1) == 0) | |
265 | ++__parent; | |
266 | } | |
267 | return true; | |
268 | } | |
269 | ||
270 | template<typename _RandomAccessIter> | |
271 | inline bool | |
272 | is_heap(_RandomAccessIter __first, _RandomAccessIter __last) | |
273 | { | |
274 | // concept requirements | |
275 | __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) | |
276 | __glibcpp_function_requires(_LessThanComparableConcept< | |
277 | typename std::iterator_traits<_RandomAccessIter>::value_type>) | |
278 | ||
279 | return __is_heap(__first, __last - __first); | |
280 | } | |
281 | ||
282 | template<typename _RandomAccessIter, typename _StrictWeakOrdering> | |
283 | inline bool | |
284 | is_heap(_RandomAccessIter __first, _RandomAccessIter __last, | |
285 | _StrictWeakOrdering __comp) | |
286 | { | |
287 | // concept requirements | |
288 | __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) | |
289 | __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, | |
290 | typename std::iterator_traits<_RandomAccessIter>::value_type, | |
291 | typename std::iterator_traits<_RandomAccessIter>::value_type>) | |
292 | ||
293 | return __is_heap(__first, __comp, __last - __first); | |
294 | } | |
295 | ||
296 | // is_sorted, a predicated testing whether a range is sorted in | |
297 | // nondescending order. This is an extension, not part of the C++ | |
298 | // standard. | |
299 | ||
300 | template<typename _ForwardIter> | |
301 | bool | |
302 | is_sorted(_ForwardIter __first, _ForwardIter __last) | |
303 | { | |
304 | // concept requirements | |
305 | __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) | |
306 | __glibcpp_function_requires(_LessThanComparableConcept< | |
307 | typename std::iterator_traits<_ForwardIter>::value_type>) | |
308 | ||
309 | if (__first == __last) | |
310 | return true; | |
311 | ||
312 | _ForwardIter __next = __first; | |
313 | for (++__next; __next != __last; __first = __next, ++__next) { | |
314 | if (*__next < *__first) | |
315 | return false; | |
316 | } | |
317 | ||
318 | return true; | |
319 | } | |
320 | ||
321 | template<typename _ForwardIter, typename _StrictWeakOrdering> | |
322 | bool | |
323 | is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) | |
324 | { | |
325 | // concept requirements | |
326 | __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) | |
327 | __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, | |
328 | typename std::iterator_traits<_ForwardIter>::value_type, | |
329 | typename std::iterator_traits<_ForwardIter>::value_type>) | |
330 | ||
331 | if (__first == __last) | |
332 | return true; | |
333 | ||
334 | _ForwardIter __next = __first; | |
335 | for (++__next; __next != __last; __first = __next, ++__next) { | |
336 | if (__comp(*__next, *__first)) | |
337 | return false; | |
338 | } | |
339 | ||
340 | return true; | |
341 | } | |
342 | ||
343 | } // namespace __gnu_cxx | |
344 | ||
345 | #endif /* _EXT_ALGORITHM */ |