]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Bits and pieces used in algorithms -*- C++ -*- |
2 | ||
e9e90c1f | 3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 |
0002d5d2 | 4 | // Free Software Foundation, Inc. |
42526146 PE |
5 | // |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
9 | // Free Software Foundation; either version 2, or (at your option) | |
10 | // any later version. | |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
17 | // You should have received a copy of the GNU General Public License along | |
18 | // with this library; see the file COPYING. If not, write to the Free | |
83f51799 | 19 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, |
42526146 PE |
20 | // USA. |
21 | ||
22 | // As a special exception, you may use this file as part of a free software | |
23 | // library without restriction. Specifically, if other files instantiate | |
24 | // templates or use macros or inline functions from this file, or you compile | |
25 | // this file and link it with other files to produce an executable, this | |
26 | // file does not by itself cause the resulting executable to be covered by | |
27 | // the GNU General Public License. This exception does not however | |
28 | // invalidate any other reasons why the executable file might be covered by | |
29 | // the GNU General Public License. | |
30 | ||
725dc051 BK |
31 | /* |
32 | * | |
33 | * Copyright (c) 1994 | |
34 | * Hewlett-Packard Company | |
35 | * | |
36 | * Permission to use, copy, modify, distribute and sell this software | |
37 | * and its documentation for any purpose is hereby granted without fee, | |
38 | * provided that the above copyright notice appear in all copies and | |
39 | * that both that copyright notice and this permission notice appear | |
40 | * in supporting documentation. Hewlett-Packard Company makes no | |
41 | * representations about the suitability of this software for any | |
42 | * purpose. It is provided "as is" without express or implied warranty. | |
43 | * | |
44 | * | |
45 | * Copyright (c) 1996-1998 | |
46 | * Silicon Graphics Computer Systems, Inc. | |
47 | * | |
48 | * Permission to use, copy, modify, distribute and sell this software | |
49 | * and its documentation for any purpose is hereby granted without fee, | |
50 | * provided that the above copyright notice appear in all copies and | |
51 | * that both that copyright notice and this permission notice appear | |
52 | * in supporting documentation. Silicon Graphics makes no | |
53 | * representations about the suitability of this software for any | |
54 | * purpose. It is provided "as is" without express or implied warranty. | |
55 | */ | |
56 | ||
729e3d3f PE |
57 | /** @file stl_algobase.h |
58 | * This is an internal header file, included by other library headers. | |
59 | * You should not attempt to use it directly. | |
725dc051 BK |
60 | */ |
61 | ||
046d30f4 PC |
62 | #ifndef _STL_ALGOBASE_H |
63 | #define _STL_ALGOBASE_H 1 | |
725dc051 | 64 | |
9cfeea6e | 65 | #include <bits/c++config.h> |
54c1bf78 | 66 | #include <cstddef> |
39b8cd70 | 67 | #include <bits/functexcept.h> |
badd64ad | 68 | #include <bits/cpp_type_traits.h> |
105c6331 | 69 | #include <ext/type_traits.h> |
6725add5 | 70 | #include <ext/numeric_traits.h> |
c2ba9709 | 71 | #include <bits/algorithmfwd.h> |
30a20a1e | 72 | #include <bits/stl_iterator_base_funcs.h> |
725dc051 | 73 | #include <bits/stl_iterator.h> |
30a20a1e | 74 | #include <bits/concept_check.h> |
285b36d6 | 75 | #include <debug/debug.h> |
e14e932b | 76 | #include <bits/stl_move.h> // For std::swap and _GLIBCXX_MOVE |
3a6b0f54 | 77 | |
3cbc7af0 | 78 | _GLIBCXX_BEGIN_NAMESPACE(std) |
575665ff | 79 | |
575665ff CJ |
80 | // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a |
81 | // nutshell, we are partially implementing the resolution of DR 187, | |
82 | // when it's safe, i.e., the value_types are equal. | |
83 | template<bool _BoolType> | |
84 | struct __iter_swap | |
85 | { | |
86 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
87 | static void | |
88 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) | |
89 | { | |
90 | typedef typename iterator_traits<_ForwardIterator1>::value_type | |
91 | _ValueType1; | |
3a6b0f54 PC |
92 | _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); |
93 | *__a = _GLIBCXX_MOVE(*__b); | |
94 | *__b = _GLIBCXX_MOVE(__tmp); | |
575665ff CJ |
95 | } |
96 | }; | |
97 | ||
98 | template<> | |
99 | struct __iter_swap<true> | |
100 | { | |
101 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
102 | static void | |
103 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) | |
104 | { | |
105 | swap(*__a, *__b); | |
106 | } | |
107 | }; | |
108 | ||
729e3d3f PE |
109 | /** |
110 | * @brief Swaps the contents of two iterators. | |
111 | * @param a An iterator. | |
112 | * @param b Another iterator. | |
113 | * @return Nothing. | |
114 | * | |
115 | * This function swaps the values pointed to by two iterators, not the | |
116 | * iterators themselves. | |
117 | */ | |
08addde6 | 118 | template<typename _ForwardIterator1, typename _ForwardIterator2> |
02d92e3b | 119 | inline void |
08addde6 | 120 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
02d92e3b | 121 | { |
ffa67767 PC |
122 | typedef typename iterator_traits<_ForwardIterator1>::value_type |
123 | _ValueType1; | |
124 | typedef typename iterator_traits<_ForwardIterator2>::value_type | |
125 | _ValueType2; | |
02d92e3b SW |
126 | |
127 | // concept requirements | |
ffa67767 PC |
128 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
129 | _ForwardIterator1>) | |
130 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
131 | _ForwardIterator2>) | |
132 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, | |
133 | _ValueType2>) | |
134 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, | |
135 | _ValueType1>) | |
aed63147 CJ |
136 | |
137 | typedef typename iterator_traits<_ForwardIterator1>::reference | |
138 | _ReferenceType1; | |
139 | typedef typename iterator_traits<_ForwardIterator2>::reference | |
140 | _ReferenceType2; | |
d22a3166 PC |
141 | std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value |
142 | && __are_same<_ValueType1&, _ReferenceType1>::__value | |
143 | && __are_same<_ValueType2&, _ReferenceType2>::__value>:: | |
575665ff | 144 | iter_swap(__a, __b); |
02d92e3b SW |
145 | } |
146 | ||
91b0b94a PC |
147 | /** |
148 | * @brief Swap the elements of two sequences. | |
149 | * @param first1 A forward iterator. | |
150 | * @param last1 A forward iterator. | |
151 | * @param first2 A forward iterator. | |
152 | * @return An iterator equal to @p first2+(last1-first1). | |
153 | * | |
154 | * Swaps each element in the range @p [first1,last1) with the | |
155 | * corresponding element in the range @p [first2,(last1-first1)). | |
156 | * The ranges must not overlap. | |
157 | */ | |
158 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
159 | _ForwardIterator2 | |
160 | swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
161 | _ForwardIterator2 __first2) | |
162 | { | |
163 | // concept requirements | |
164 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
165 | _ForwardIterator1>) | |
166 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
167 | _ForwardIterator2>) | |
168 | __glibcxx_function_requires(_ConvertibleConcept< | |
169 | typename iterator_traits<_ForwardIterator1>::value_type, | |
170 | typename iterator_traits<_ForwardIterator2>::value_type>) | |
171 | __glibcxx_function_requires(_ConvertibleConcept< | |
172 | typename iterator_traits<_ForwardIterator2>::value_type, | |
173 | typename iterator_traits<_ForwardIterator1>::value_type>) | |
174 | __glibcxx_requires_valid_range(__first1, __last1); | |
175 | ||
176 | for (; __first1 != __last1; ++__first1, ++__first2) | |
177 | std::iter_swap(__first1, __first2); | |
178 | return __first2; | |
179 | } | |
180 | ||
729e3d3f PE |
181 | /** |
182 | * @brief This does what you think it does. | |
183 | * @param a A thing of arbitrary type. | |
184 | * @param b Another thing of arbitrary type. | |
185 | * @return The lesser of the parameters. | |
186 | * | |
187 | * This is the simple classic generic implementation. It will work on | |
188 | * temporary expressions, since they are only evaluated once, unlike a | |
189 | * preprocessor macro. | |
190 | */ | |
02d92e3b SW |
191 | template<typename _Tp> |
192 | inline const _Tp& | |
193 | min(const _Tp& __a, const _Tp& __b) | |
194 | { | |
195 | // concept requirements | |
3d7c150e | 196 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
02d92e3b | 197 | //return __b < __a ? __b : __a; |
ffa67767 PC |
198 | if (__b < __a) |
199 | return __b; | |
200 | return __a; | |
02d92e3b SW |
201 | } |
202 | ||
1b4a6975 PE |
203 | /** |
204 | * @brief This does what you think it does. | |
205 | * @param a A thing of arbitrary type. | |
206 | * @param b Another thing of arbitrary type. | |
207 | * @return The greater of the parameters. | |
208 | * | |
209 | * This is the simple classic generic implementation. It will work on | |
210 | * temporary expressions, since they are only evaluated once, unlike a | |
211 | * preprocessor macro. | |
212 | */ | |
02d92e3b SW |
213 | template<typename _Tp> |
214 | inline const _Tp& | |
ed6814f7 | 215 | max(const _Tp& __a, const _Tp& __b) |
02d92e3b SW |
216 | { |
217 | // concept requirements | |
3d7c150e | 218 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
02d92e3b | 219 | //return __a < __b ? __b : __a; |
ffa67767 PC |
220 | if (__a < __b) |
221 | return __b; | |
222 | return __a; | |
02d92e3b SW |
223 | } |
224 | ||
1b4a6975 PE |
225 | /** |
226 | * @brief This does what you think it does. | |
227 | * @param a A thing of arbitrary type. | |
228 | * @param b Another thing of arbitrary type. | |
229 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
230 | * @return The lesser of the parameters. | |
231 | * | |
232 | * This will work on temporary expressions, since they are only evaluated | |
233 | * once, unlike a preprocessor macro. | |
234 | */ | |
02d92e3b SW |
235 | template<typename _Tp, typename _Compare> |
236 | inline const _Tp& | |
237 | min(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
238 | { | |
239 | //return __comp(__b, __a) ? __b : __a; | |
ffa67767 PC |
240 | if (__comp(__b, __a)) |
241 | return __b; | |
242 | return __a; | |
02d92e3b SW |
243 | } |
244 | ||
1b4a6975 PE |
245 | /** |
246 | * @brief This does what you think it does. | |
247 | * @param a A thing of arbitrary type. | |
248 | * @param b Another thing of arbitrary type. | |
249 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
250 | * @return The greater of the parameters. | |
251 | * | |
252 | * This will work on temporary expressions, since they are only evaluated | |
253 | * once, unlike a preprocessor macro. | |
254 | */ | |
02d92e3b SW |
255 | template<typename _Tp, typename _Compare> |
256 | inline const _Tp& | |
257 | max(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
258 | { | |
259 | //return __comp(__a, __b) ? __b : __a; | |
ffa67767 PC |
260 | if (__comp(__a, __b)) |
261 | return __b; | |
262 | return __a; | |
02d92e3b SW |
263 | } |
264 | ||
d22a3166 PC |
265 | |
266 | // If _Iterator is a __normal_iterator return its base (a plain pointer, | |
267 | // normally) otherwise return it untouched. See copy, fill, ... | |
268 | template<typename _Iterator, | |
269 | bool _BoolType = __is_normal_iterator<_Iterator>::__value> | |
270 | struct __niter_base | |
271 | { | |
272 | static const _Iterator& | |
273 | __b(const _Iterator& __it) | |
274 | { return __it; } | |
275 | }; | |
276 | ||
277 | template<typename _Iterator> | |
278 | struct __niter_base<_Iterator, true> | |
279 | { | |
280 | static const typename _Iterator::_Iterator_type& | |
281 | __b(const _Iterator& __it) | |
282 | { return __it.base(); } | |
283 | }; | |
284 | ||
5e91e92e | 285 | // All of these auxiliary structs serve two purposes. (1) Replace |
02d92e3b SW |
286 | // calls to copy with memmove whenever possible. (Memmove, not memcpy, |
287 | // because the input and output ranges are permitted to overlap.) | |
288 | // (2) If we're using random access iterators, then write the loop as | |
289 | // a for loop with an explicit count. | |
290 | ||
695e0fbf PC |
291 | template<bool, typename> |
292 | struct __copy | |
02d92e3b | 293 | { |
695e0fbf PC |
294 | template<typename _II, typename _OI> |
295 | static _OI | |
296 | copy(_II __first, _II __last, _OI __result) | |
297 | { | |
298 | for (; __first != __last; ++__result, ++__first) | |
299 | *__result = *__first; | |
300 | return __result; | |
301 | } | |
302 | }; | |
02d92e3b | 303 | |
695e0fbf PC |
304 | template<bool _BoolType> |
305 | struct __copy<_BoolType, random_access_iterator_tag> | |
02d92e3b | 306 | { |
695e0fbf PC |
307 | template<typename _II, typename _OI> |
308 | static _OI | |
309 | copy(_II __first, _II __last, _OI __result) | |
310 | { | |
311 | typedef typename iterator_traits<_II>::difference_type _Distance; | |
312 | for(_Distance __n = __last - __first; __n > 0; --__n) | |
313 | { | |
314 | *__result = *__first; | |
315 | ++__first; | |
316 | ++__result; | |
317 | } | |
318 | return __result; | |
46c4e5d6 | 319 | } |
695e0fbf | 320 | }; |
02d92e3b | 321 | |
695e0fbf PC |
322 | template<> |
323 | struct __copy<true, random_access_iterator_tag> | |
02d92e3b | 324 | { |
695e0fbf PC |
325 | template<typename _Tp> |
326 | static _Tp* | |
327 | copy(const _Tp* __first, const _Tp* __last, _Tp* __result) | |
328 | { | |
360721e3 PC |
329 | __builtin_memmove(__result, __first, |
330 | sizeof(_Tp) * (__last - __first)); | |
695e0fbf PC |
331 | return __result + (__last - __first); |
332 | } | |
333 | }; | |
02d92e3b | 334 | |
695e0fbf PC |
335 | template<typename _II, typename _OI> |
336 | inline _OI | |
337 | __copy_aux(_II __first, _II __last, _OI __result) | |
338 | { | |
339 | typedef typename iterator_traits<_II>::value_type _ValueTypeI; | |
340 | typedef typename iterator_traits<_OI>::value_type _ValueTypeO; | |
341 | typedef typename iterator_traits<_II>::iterator_category _Category; | |
ff2ea587 | 342 | const bool __simple = (__is_pod(_ValueTypeI) |
4d73fac9 PC |
343 | && __is_pointer<_II>::__value |
344 | && __is_pointer<_OI>::__value | |
345 | && __are_same<_ValueTypeI, _ValueTypeO>::__value); | |
695e0fbf PC |
346 | |
347 | return std::__copy<__simple, _Category>::copy(__first, __last, __result); | |
348 | } | |
02d92e3b | 349 | |
0002d5d2 | 350 | // Helpers for streambuf iterators (either istream or ostream). |
39b8cd70 PC |
351 | // NB: avoid including <iosfwd>, relatively large. |
352 | template<typename _CharT> | |
353 | struct char_traits; | |
354 | ||
355 | template<typename _CharT, typename _Traits> | |
356 | class istreambuf_iterator; | |
357 | ||
358 | template<typename _CharT, typename _Traits> | |
359 | class ostreambuf_iterator; | |
360 | ||
0002d5d2 | 361 | template<typename _CharT> |
f56fe8ff | 362 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
39b8cd70 PC |
363 | ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
364 | __copy_aux(_CharT*, _CharT*, | |
365 | ostreambuf_iterator<_CharT, char_traits<_CharT> >); | |
0002d5d2 PC |
366 | |
367 | template<typename _CharT> | |
105c6331 | 368 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
39b8cd70 PC |
369 | ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
370 | __copy_aux(const _CharT*, const _CharT*, | |
371 | ostreambuf_iterator<_CharT, char_traits<_CharT> >); | |
0002d5d2 PC |
372 | |
373 | template<typename _CharT> | |
f56fe8ff PC |
374 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
375 | _CharT*>::__type | |
39b8cd70 PC |
376 | __copy_aux(istreambuf_iterator<_CharT, char_traits<_CharT> >, |
377 | istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); | |
0002d5d2 | 378 | |
1b4a6975 PE |
379 | /** |
380 | * @brief Copies the range [first,last) into result. | |
381 | * @param first An input iterator. | |
382 | * @param last An input iterator. | |
383 | * @param result An output iterator. | |
384 | * @return result + (first - last) | |
385 | * | |
386 | * This inline function will boil down to a call to @c memmove whenever | |
387 | * possible. Failing that, if random access iterators are passed, then the | |
388 | * loop count will be known (and therefore a candidate for compiler | |
119dbb1f JQ |
389 | * optimizations such as unrolling). Result may not be contained within |
390 | * [first,last); the copy_backward function should be used instead. | |
391 | * | |
392 | * Note that the end of the output range is permitted to be contained | |
393 | * within [first,last). | |
1b4a6975 | 394 | */ |
d22a3166 PC |
395 | template<typename _II, typename _OI> |
396 | inline _OI | |
397 | copy(_II __first, _II __last, _OI __result) | |
02d92e3b SW |
398 | { |
399 | // concept requirements | |
d22a3166 PC |
400 | __glibcxx_function_requires(_InputIteratorConcept<_II>) |
401 | __glibcxx_function_requires(_OutputIteratorConcept<_OI, | |
402 | typename iterator_traits<_II>::value_type>) | |
285b36d6 | 403 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 404 | |
d22a3166 PC |
405 | return _OI(std::__copy_aux(__niter_base<_II>::__b(__first), |
406 | __niter_base<_II>::__b(__last), | |
407 | __niter_base<_OI>::__b(__result))); | |
02d92e3b | 408 | } |
0002d5d2 | 409 | |
d22a3166 | 410 | |
badd64ad PC |
411 | template<bool, typename> |
412 | struct __copy_backward | |
413 | { | |
414 | template<typename _BI1, typename _BI2> | |
415 | static _BI2 | |
e75ea710 | 416 | __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) |
badd64ad PC |
417 | { |
418 | while (__first != __last) | |
419 | *--__result = *--__last; | |
420 | return __result; | |
421 | } | |
02d92e3b SW |
422 | }; |
423 | ||
badd64ad PC |
424 | template<bool _BoolType> |
425 | struct __copy_backward<_BoolType, random_access_iterator_tag> | |
426 | { | |
427 | template<typename _BI1, typename _BI2> | |
428 | static _BI2 | |
e75ea710 | 429 | __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) |
badd64ad PC |
430 | { |
431 | typename iterator_traits<_BI1>::difference_type __n; | |
432 | for (__n = __last - __first; __n > 0; --__n) | |
433 | *--__result = *--__last; | |
434 | return __result; | |
435 | } | |
02d92e3b SW |
436 | }; |
437 | ||
badd64ad PC |
438 | template<> |
439 | struct __copy_backward<true, random_access_iterator_tag> | |
440 | { | |
441 | template<typename _Tp> | |
442 | static _Tp* | |
e75ea710 | 443 | __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result) |
badd64ad PC |
444 | { |
445 | const ptrdiff_t _Num = __last - __first; | |
360721e3 | 446 | __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); |
badd64ad PC |
447 | return __result - _Num; |
448 | } | |
02d92e3b SW |
449 | }; |
450 | ||
451 | template<typename _BI1, typename _BI2> | |
452 | inline _BI2 | |
453 | __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) | |
454 | { | |
695e0fbf PC |
455 | typedef typename iterator_traits<_BI1>::value_type _ValueType1; |
456 | typedef typename iterator_traits<_BI2>::value_type _ValueType2; | |
badd64ad | 457 | typedef typename iterator_traits<_BI1>::iterator_category _Category; |
ff2ea587 | 458 | const bool __simple = (__is_pod(_ValueType1) |
4d73fac9 PC |
459 | && __is_pointer<_BI1>::__value |
460 | && __is_pointer<_BI2>::__value | |
461 | && __are_same<_ValueType1, _ValueType2>::__value); | |
badd64ad | 462 | |
e75ea710 PC |
463 | return std::__copy_backward<__simple, _Category>::__copy_b(__first, |
464 | __last, | |
465 | __result); | |
02d92e3b SW |
466 | } |
467 | ||
1b4a6975 PE |
468 | /** |
469 | * @brief Copies the range [first,last) into result. | |
119dbb1f JQ |
470 | * @param first A bidirectional iterator. |
471 | * @param last A bidirectional iterator. | |
472 | * @param result A bidirectional iterator. | |
1b4a6975 PE |
473 | * @return result - (first - last) |
474 | * | |
475 | * The function has the same effect as copy, but starts at the end of the | |
476 | * range and works its way to the start, returning the start of the result. | |
477 | * This inline function will boil down to a call to @c memmove whenever | |
478 | * possible. Failing that, if random access iterators are passed, then the | |
479 | * loop count will be known (and therefore a candidate for compiler | |
480 | * optimizations such as unrolling). | |
119dbb1f JQ |
481 | * |
482 | * Result may not be in the range [first,last). Use copy instead. Note | |
483 | * that the start of the output range may overlap [first,last). | |
1b4a6975 | 484 | */ |
02d92e3b SW |
485 | template <typename _BI1, typename _BI2> |
486 | inline _BI2 | |
487 | copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) | |
488 | { | |
489 | // concept requirements | |
3d7c150e BK |
490 | __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) |
491 | __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) | |
492 | __glibcxx_function_requires(_ConvertibleConcept< | |
02d92e3b | 493 | typename iterator_traits<_BI1>::value_type, |
4d16bdbb | 494 | typename iterator_traits<_BI2>::value_type>) |
285b36d6 | 495 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 496 | |
d22a3166 PC |
497 | return _BI2(std::__copy_backward_aux(__niter_base<_BI1>::__b(__first), |
498 | __niter_base<_BI1>::__b(__last), | |
499 | __niter_base<_BI2>::__b(__result))); | |
02d92e3b SW |
500 | } |
501 | ||
e9e90c1f | 502 | |
394033f8 PC |
503 | template<typename _ForwardIterator, typename _Tp> |
504 | inline typename | |
505 | __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type | |
506 | __fill_a(_ForwardIterator __first, _ForwardIterator __last, | |
507 | const _Tp& __value) | |
6e539e23 | 508 | { |
394033f8 PC |
509 | for (; __first != __last; ++__first) |
510 | *__first = __value; | |
511 | } | |
512 | ||
08addde6 | 513 | template<typename _ForwardIterator, typename _Tp> |
394033f8 PC |
514 | inline typename |
515 | __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type | |
516 | __fill_a(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) | |
02d92e3b | 517 | { |
394033f8 PC |
518 | for (; __first != __last; ++__first) |
519 | *__first = __value; | |
02d92e3b SW |
520 | } |
521 | ||
d22a3166 | 522 | // Specialization: for char types we can use memset. |
394033f8 PC |
523 | template<typename _Tp> |
524 | inline typename | |
525 | __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type | |
526 | __fill_a(_Tp* __first, _Tp* __last, _Tp __c) | |
527 | { __builtin_memset(__first, static_cast<unsigned char>(__c), | |
528 | __last - __first); } | |
725dc051 | 529 | |
e9e90c1f PC |
530 | /** |
531 | * @brief Fills the range [first,last) with copies of value. | |
532 | * @param first A forward iterator. | |
533 | * @param last A forward iterator. | |
534 | * @param value A reference-to-const of arbitrary type. | |
535 | * @return Nothing. | |
536 | * | |
537 | * This function fills a range with copies of the same value. For char | |
538 | * types filling contiguous areas of memory, this becomes an inline call | |
539 | * to @c memset or @c wmemset. | |
540 | */ | |
541 | template<typename _ForwardIterator, typename _Tp> | |
542 | inline void | |
543 | fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) | |
544 | { | |
545 | // concept requirements | |
546 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
547 | _ForwardIterator>) | |
548 | __glibcxx_requires_valid_range(__first, __last); | |
549 | ||
394033f8 PC |
550 | std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first), |
551 | std::__niter_base<_ForwardIterator>::__b(__last), __value); | |
e9e90c1f PC |
552 | } |
553 | ||
6e539e23 | 554 | template<typename _OutputIterator, typename _Size, typename _Tp> |
394033f8 PC |
555 | inline typename |
556 | __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type | |
557 | __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) | |
02d92e3b | 558 | { |
394033f8 PC |
559 | for (; __n > 0; --__n, ++__first) |
560 | *__first = __value; | |
561 | return __first; | |
02d92e3b SW |
562 | } |
563 | ||
394033f8 PC |
564 | template<typename _OutputIterator, typename _Size, typename _Tp> |
565 | inline typename | |
566 | __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type | |
567 | __fill_n_a(_OutputIterator __first, _Size __n, _Tp __value) | |
02d92e3b | 568 | { |
394033f8 PC |
569 | for (; __n > 0; --__n, ++__first) |
570 | *__first = __value; | |
571 | return __first; | |
02d92e3b SW |
572 | } |
573 | ||
394033f8 PC |
574 | template<typename _Size, typename _Tp> |
575 | inline typename | |
576 | __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type | |
577 | __fill_n_a(_Tp* __first, _Size __n, _Tp __c) | |
e9e90c1f | 578 | { |
394033f8 | 579 | std::__fill_a(__first, __first + __n, __c); |
e9e90c1f PC |
580 | return __first + __n; |
581 | } | |
582 | ||
e9e90c1f PC |
583 | /** |
584 | * @brief Fills the range [first,first+n) with copies of value. | |
585 | * @param first An output iterator. | |
586 | * @param n The count of copies to perform. | |
587 | * @param value A reference-to-const of arbitrary type. | |
588 | * @return The iterator at first+n. | |
589 | * | |
590 | * This function fills a range with copies of the same value. For char | |
591 | * types filling contiguous areas of memory, this becomes an inline call | |
592 | * to @c memset or @ wmemset. | |
593 | */ | |
d22a3166 PC |
594 | template<typename _OI, typename _Size, typename _Tp> |
595 | inline _OI | |
596 | fill_n(_OI __first, _Size __n, const _Tp& __value) | |
e9e90c1f PC |
597 | { |
598 | // concept requirements | |
d22a3166 | 599 | __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) |
e9e90c1f | 600 | |
394033f8 PC |
601 | return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first), |
602 | __n, __value)); | |
e9e90c1f | 603 | } |
02d92e3b | 604 | |
d22a3166 PC |
605 | template<bool _BoolType> |
606 | struct __equal | |
607 | { | |
608 | template<typename _II1, typename _II2> | |
609 | static bool | |
610 | equal(_II1 __first1, _II1 __last1, _II2 __first2) | |
611 | { | |
612 | for (; __first1 != __last1; ++__first1, ++__first2) | |
613 | if (!(*__first1 == *__first2)) | |
614 | return false; | |
615 | return true; | |
616 | } | |
617 | }; | |
618 | ||
619 | template<> | |
620 | struct __equal<true> | |
621 | { | |
622 | template<typename _Tp> | |
623 | static bool | |
624 | equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) | |
625 | { | |
360721e3 PC |
626 | return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) |
627 | * (__last1 - __first1)); | |
d22a3166 PC |
628 | } |
629 | }; | |
630 | ||
631 | template<typename _II1, typename _II2> | |
632 | inline bool | |
633 | __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) | |
634 | { | |
635 | typedef typename iterator_traits<_II1>::value_type _ValueType1; | |
636 | typedef typename iterator_traits<_II2>::value_type _ValueType2; | |
637 | const bool __simple = (__is_integer<_ValueType1>::__value | |
638 | && __is_pointer<_II1>::__value | |
639 | && __is_pointer<_II2>::__value | |
640 | && __are_same<_ValueType1, _ValueType2>::__value); | |
641 | ||
642 | return std::__equal<__simple>::equal(__first1, __last1, __first2); | |
643 | } | |
644 | ||
c2ba9709 JS |
645 | |
646 | template<typename, typename> | |
647 | struct __lc_rai | |
648 | { | |
649 | template<typename _II1, typename _II2> | |
650 | static _II1 | |
651 | __newlast1(_II1, _II1 __last1, _II2, _II2) | |
652 | { return __last1; } | |
653 | ||
654 | template<typename _II> | |
655 | static bool | |
656 | __cnd2(_II __first, _II __last) | |
657 | { return __first != __last; } | |
658 | }; | |
659 | ||
660 | template<> | |
661 | struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> | |
662 | { | |
663 | template<typename _RAI1, typename _RAI2> | |
664 | static _RAI1 | |
665 | __newlast1(_RAI1 __first1, _RAI1 __last1, | |
666 | _RAI2 __first2, _RAI2 __last2) | |
667 | { | |
668 | const typename iterator_traits<_RAI1>::difference_type | |
669 | __diff1 = __last1 - __first1; | |
670 | const typename iterator_traits<_RAI2>::difference_type | |
671 | __diff2 = __last2 - __first2; | |
672 | return __diff2 < __diff1 ? __first1 + __diff2 : __last1; | |
673 | } | |
674 | ||
675 | template<typename _RAI> | |
676 | static bool | |
677 | __cnd2(_RAI, _RAI) | |
678 | { return true; } | |
679 | }; | |
680 | ||
681 | // XXX should these be enabled-if'd for signed/unsigned types instead? | |
682 | inline bool | |
683 | lexicographical_compare(const unsigned char* __first1, | |
684 | const unsigned char* __last1, | |
685 | const unsigned char* __first2, | |
686 | const unsigned char* __last2) | |
687 | { | |
688 | __glibcxx_requires_valid_range(__first1, __last1); | |
689 | __glibcxx_requires_valid_range(__first2, __last2); | |
690 | ||
691 | const size_t __len1 = __last1 - __first1; | |
692 | const size_t __len2 = __last2 - __first2; | |
693 | const int __result = __builtin_memcmp(__first1, __first2, | |
694 | std::min(__len1, __len2)); | |
695 | return __result != 0 ? __result < 0 : __len1 < __len2; | |
696 | } | |
697 | ||
698 | inline bool | |
699 | lexicographical_compare(const char* __first1, const char* __last1, | |
700 | const char* __first2, const char* __last2) | |
701 | { | |
702 | __glibcxx_requires_valid_range(__first1, __last1); | |
703 | __glibcxx_requires_valid_range(__first2, __last2); | |
704 | ||
705 | if (__gnu_cxx::__numeric_traits<char>::__is_signed) | |
706 | { | |
707 | typedef const signed char* value_type; | |
708 | value_type __f1 = reinterpret_cast<value_type>(__first1); | |
709 | value_type __l1 = reinterpret_cast<value_type>(__last1); | |
710 | value_type __f2 = reinterpret_cast<value_type>(__first2); | |
711 | value_type __l2 = reinterpret_cast<value_type>(__last2); | |
712 | return _GLIBCXX_STD_P::lexicographical_compare(__f1, __l1, __f2, __l2); | |
713 | } | |
714 | else | |
715 | { | |
716 | typedef const unsigned char* value_type; | |
717 | value_type __f1 = reinterpret_cast<value_type>(__first1); | |
718 | value_type __l1 = reinterpret_cast<value_type>(__last1); | |
719 | value_type __f2 = reinterpret_cast<value_type>(__first2); | |
720 | value_type __l2 = reinterpret_cast<value_type>(__last2); | |
721 | return _GLIBCXX_STD_P::lexicographical_compare(__f1, __l1, __f2, __l2); | |
722 | } | |
723 | } | |
724 | ||
725 | _GLIBCXX_END_NAMESPACE | |
726 | ||
727 | _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) | |
728 | ||
1b4a6975 PE |
729 | /** |
730 | * @brief Tests a range for element-wise equality. | |
731 | * @param first1 An input iterator. | |
732 | * @param last1 An input iterator. | |
733 | * @param first2 An input iterator. | |
734 | * @return A boolean true or false. | |
735 | * | |
736 | * This compares the elements of two ranges using @c == and returns true or | |
737 | * false depending on whether all of the corresponding elements of the | |
738 | * ranges are equal. | |
739 | */ | |
d22a3166 | 740 | template<typename _II1, typename _II2> |
02d92e3b | 741 | inline bool |
d22a3166 | 742 | equal(_II1 __first1, _II1 __last1, _II2 __first2) |
02d92e3b SW |
743 | { |
744 | // concept requirements | |
d22a3166 PC |
745 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
746 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
3d7c150e | 747 | __glibcxx_function_requires(_EqualOpConcept< |
d22a3166 PC |
748 | typename iterator_traits<_II1>::value_type, |
749 | typename iterator_traits<_II2>::value_type>) | |
285b36d6 | 750 | __glibcxx_requires_valid_range(__first1, __last1); |
d22a3166 | 751 | |
394033f8 PC |
752 | return std::__equal_aux(std::__niter_base<_II1>::__b(__first1), |
753 | std::__niter_base<_II1>::__b(__last1), | |
754 | std::__niter_base<_II2>::__b(__first2)); | |
02d92e3b SW |
755 | } |
756 | ||
1b4a6975 PE |
757 | /** |
758 | * @brief Tests a range for element-wise equality. | |
759 | * @param first1 An input iterator. | |
760 | * @param last1 An input iterator. | |
761 | * @param first2 An input iterator. | |
c2ba9709 JS |
762 | * @param binary_pred A binary predicate @link s20_3_1_base |
763 | * functor@endlink. | |
764 | * @return A boolean true or false. | |
1b4a6975 PE |
765 | * |
766 | * This compares the elements of two ranges using the binary_pred | |
767 | * parameter, and returns true or | |
768 | * false depending on whether all of the corresponding elements of the | |
769 | * ranges are equal. | |
770 | */ | |
c2ba9709 | 771 | template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> |
02d92e3b | 772 | inline bool |
c2ba9709 JS |
773 | equal(_IIter1 __first1, _IIter1 __last1, |
774 | _IIter2 __first2, _BinaryPredicate __binary_pred) | |
02d92e3b SW |
775 | { |
776 | // concept requirements | |
c2ba9709 JS |
777 | __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) |
778 | __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) | |
285b36d6 | 779 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 780 | |
43da93a7 | 781 | for (; __first1 != __last1; ++__first1, ++__first2) |
dded9d2c | 782 | if (!bool(__binary_pred(*__first1, *__first2))) |
02d92e3b | 783 | return false; |
725dc051 | 784 | return true; |
02d92e3b SW |
785 | } |
786 | ||
1b4a6975 PE |
787 | /** |
788 | * @brief Performs "dictionary" comparison on ranges. | |
789 | * @param first1 An input iterator. | |
790 | * @param last1 An input iterator. | |
791 | * @param first2 An input iterator. | |
792 | * @param last2 An input iterator. | |
793 | * @return A boolean true or false. | |
794 | * | |
795 | * "Returns true if the sequence of elements defined by the range | |
796 | * [first1,last1) is lexicographically less than the sequence of elements | |
797 | * defined by the range [first2,last2). Returns false otherwise." | |
798 | * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, | |
799 | * then this is an inline call to @c memcmp. | |
800 | */ | |
c2fe93f7 | 801 | template<typename _II1, typename _II2> |
02d92e3b | 802 | bool |
c2ba9709 | 803 | lexicographical_compare(_II1 __first1, _II1 __last1, |
c2fe93f7 | 804 | _II2 __first2, _II2 __last2) |
02d92e3b | 805 | { |
c2fe93f7 PC |
806 | typedef typename iterator_traits<_II1>::iterator_category _Category1; |
807 | typedef typename iterator_traits<_II2>::iterator_category _Category2; | |
3a6b0f54 | 808 | typedef __lc_rai<_Category1, _Category2> __rai_type; |
c2fe93f7 | 809 | |
02d92e3b | 810 | // concept requirements |
c2fe93f7 PC |
811 | typedef typename iterator_traits<_II1>::value_type _ValueType1; |
812 | typedef typename iterator_traits<_II2>::value_type _ValueType2; | |
813 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) | |
814 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
815 | __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) | |
816 | __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) | |
285b36d6 BK |
817 | __glibcxx_requires_valid_range(__first1, __last1); |
818 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b | 819 | |
3a6b0f54 PC |
820 | __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); |
821 | for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); | |
43da93a7 | 822 | ++__first1, ++__first2) |
46c4e5d6 BK |
823 | { |
824 | if (*__first1 < *__first2) | |
825 | return true; | |
826 | if (*__first2 < *__first1) | |
827 | return false; | |
828 | } | |
02d92e3b SW |
829 | return __first1 == __last1 && __first2 != __last2; |
830 | } | |
831 | ||
1b4a6975 PE |
832 | /** |
833 | * @brief Performs "dictionary" comparison on ranges. | |
834 | * @param first1 An input iterator. | |
835 | * @param last1 An input iterator. | |
836 | * @param first2 An input iterator. | |
837 | * @param last2 An input iterator. | |
838 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
839 | * @return A boolean true or false. | |
840 | * | |
c2fe93f7 | 841 | * The same as the four-parameter @c lexicographical_compare, but uses the |
1b4a6975 PE |
842 | * comp parameter instead of @c <. |
843 | */ | |
c2fe93f7 | 844 | template<typename _II1, typename _II2, typename _Compare> |
02d92e3b | 845 | bool |
c2fe93f7 PC |
846 | lexicographical_compare(_II1 __first1, _II1 __last1, |
847 | _II2 __first2, _II2 __last2, _Compare __comp) | |
02d92e3b | 848 | { |
c2fe93f7 PC |
849 | typedef typename iterator_traits<_II1>::iterator_category _Category1; |
850 | typedef typename iterator_traits<_II2>::iterator_category _Category2; | |
c2ba9709 | 851 | typedef __lc_rai<_Category1, _Category2> __rai_type; |
c2fe93f7 | 852 | |
02d92e3b | 853 | // concept requirements |
c2fe93f7 PC |
854 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
855 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
285b36d6 BK |
856 | __glibcxx_requires_valid_range(__first1, __last1); |
857 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b | 858 | |
c2ba9709 JS |
859 | __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); |
860 | for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); | |
43da93a7 | 861 | ++__first1, ++__first2) |
46c4e5d6 BK |
862 | { |
863 | if (__comp(*__first1, *__first2)) | |
864 | return true; | |
865 | if (__comp(*__first2, *__first1)) | |
866 | return false; | |
867 | } | |
02d92e3b SW |
868 | return __first1 == __last1 && __first2 != __last2; |
869 | } | |
870 | ||
285b36d6 | 871 | |
c2ba9709 JS |
872 | /** |
873 | * @brief Finds the places in ranges which don't match. | |
874 | * @param first1 An input iterator. | |
875 | * @param last1 An input iterator. | |
876 | * @param first2 An input iterator. | |
877 | * @return A pair of iterators pointing to the first mismatch. | |
878 | * | |
879 | * This compares the elements of two ranges using @c == and returns a pair | |
880 | * of iterators. The first iterator points into the first range, the | |
881 | * second iterator points into the second range, and the elements pointed | |
882 | * to by the iterators are not equal. | |
883 | */ | |
884 | template<typename _InputIterator1, typename _InputIterator2> | |
885 | pair<_InputIterator1, _InputIterator2> | |
886 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
887 | _InputIterator2 __first2) | |
888 | { | |
889 | // concept requirements | |
890 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
891 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
892 | __glibcxx_function_requires(_EqualOpConcept< | |
893 | typename iterator_traits<_InputIterator1>::value_type, | |
894 | typename iterator_traits<_InputIterator2>::value_type>) | |
895 | __glibcxx_requires_valid_range(__first1, __last1); | |
02d92e3b | 896 | |
c2ba9709 JS |
897 | while (__first1 != __last1 && *__first1 == *__first2) |
898 | { | |
899 | ++__first1; | |
900 | ++__first2; | |
901 | } | |
902 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); | |
903 | } | |
285b36d6 | 904 | |
c2ba9709 JS |
905 | /** |
906 | * @brief Finds the places in ranges which don't match. | |
907 | * @param first1 An input iterator. | |
908 | * @param last1 An input iterator. | |
909 | * @param first2 An input iterator. | |
910 | * @param binary_pred A binary predicate @link s20_3_1_base | |
911 | * functor@endlink. | |
912 | * @return A pair of iterators pointing to the first mismatch. | |
913 | * | |
914 | * This compares the elements of two ranges using the binary_pred | |
915 | * parameter, and returns a pair | |
916 | * of iterators. The first iterator points into the first range, the | |
917 | * second iterator points into the second range, and the elements pointed | |
918 | * to by the iterators are not equal. | |
919 | */ | |
920 | template<typename _InputIterator1, typename _InputIterator2, | |
921 | typename _BinaryPredicate> | |
922 | pair<_InputIterator1, _InputIterator2> | |
923 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
924 | _InputIterator2 __first2, _BinaryPredicate __binary_pred) | |
925 | { | |
926 | // concept requirements | |
927 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
928 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
929 | __glibcxx_requires_valid_range(__first1, __last1); | |
02d92e3b | 930 | |
c2ba9709 JS |
931 | while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) |
932 | { | |
933 | ++__first1; | |
934 | ++__first2; | |
935 | } | |
936 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); | |
937 | } | |
938 | ||
939 | _GLIBCXX_END_NESTED_NAMESPACE | |
940 | ||
941 | // NB: This file is included within many other C++ includes, as a way | |
942 | // of getting the base algorithms. So, make sure that parallel bits | |
943 | // come in too if requested. | |
944 | #ifdef _GLIBCXX_PARALLEL | |
945 | //# include <parallel/algorithm> | |
946 | # include <parallel/algobase.h> | |
947 | #endif | |
725dc051 | 948 | |
ed6814f7 | 949 | #endif |