1 : // Bits and pieces used in algorithms -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 : // Free Software Foundation, Inc.
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
19 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 :
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 :
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.
60 : */
61 :
62 : #ifndef _ALGOBASE_H
63 : #define _ALGOBASE_H 1
64 :
65 : #include <bits/c++config.h>
66 : #include <cstring>
67 : #include <climits>
68 : #include <cstdlib>
69 : #include <cstddef>
70 : #include <iosfwd>
71 : #include <bits/stl_pair.h>
72 : #include <bits/cpp_type_traits.h>
73 : #include <ext/type_traits.h>
74 : #include <bits/stl_iterator_base_types.h>
75 : #include <bits/stl_iterator_base_funcs.h>
76 : #include <bits/stl_iterator.h>
77 : #include <bits/concept_check.h>
78 : #include <debug/debug.h>
79 :
80 : _GLIBCXX_BEGIN_NAMESPACE(std)
81 :
82 : /**
83 : * @brief Swaps two values.
84 : * @param a A thing of arbitrary type.
85 : * @param b Another thing of arbitrary type.
86 : * @return Nothing.
87 : *
88 : * This is the simple classic generic implementation. It will work on
89 : * any type which has a copy constructor and an assignment operator.
90 : */
91 : template<typename _Tp>
92 : inline void
93 : swap(_Tp& __a, _Tp& __b)
94 : {
95 : // concept requirements
96 : __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
97 :
98 : _Tp __tmp = __a;
99 : __a = __b;
100 : __b = __tmp;
101 : }
102 :
103 : // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
104 : // nutshell, we are partially implementing the resolution of DR 187,
105 : // when it's safe, i.e., the value_types are equal.
106 : template<bool _BoolType>
107 : struct __iter_swap
108 : {
109 : template<typename _ForwardIterator1, typename _ForwardIterator2>
110 : static void
111 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
112 : {
113 : typedef typename iterator_traits<_ForwardIterator1>::value_type
114 : _ValueType1;
115 : _ValueType1 __tmp = *__a;
116 : *__a = *__b;
117 : *__b = __tmp;
118 : }
119 : };
120 :
121 : template<>
122 : struct __iter_swap<true>
123 : {
124 : template<typename _ForwardIterator1, typename _ForwardIterator2>
125 : static void
126 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
127 : {
128 : swap(*__a, *__b);
129 : }
130 : };
131 :
132 : /**
133 : * @brief Swaps the contents of two iterators.
134 : * @param a An iterator.
135 : * @param b Another iterator.
136 : * @return Nothing.
137 : *
138 : * This function swaps the values pointed to by two iterators, not the
139 : * iterators themselves.
140 : */
141 : template<typename _ForwardIterator1, typename _ForwardIterator2>
142 : inline void
143 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
144 : {
145 : typedef typename iterator_traits<_ForwardIterator1>::value_type
146 : _ValueType1;
147 : typedef typename iterator_traits<_ForwardIterator2>::value_type
148 : _ValueType2;
149 :
150 : // concept requirements
151 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
152 : _ForwardIterator1>)
153 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
154 : _ForwardIterator2>)
155 : __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
156 : _ValueType2>)
157 : __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
158 : _ValueType1>)
159 :
160 : typedef typename iterator_traits<_ForwardIterator1>::reference
161 : _ReferenceType1;
162 : typedef typename iterator_traits<_ForwardIterator2>::reference
163 : _ReferenceType2;
164 : std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value &&
165 : __are_same<_ValueType1 &, _ReferenceType1>::__value &&
166 : __are_same<_ValueType2 &, _ReferenceType2>::__value>::
167 : iter_swap(__a, __b);
168 : }
169 :
170 : /**
171 : * @brief This does what you think it does.
172 : * @param a A thing of arbitrary type.
173 : * @param b Another thing of arbitrary type.
174 : * @return The lesser of the parameters.
175 : *
176 : * This is the simple classic generic implementation. It will work on
177 : * temporary expressions, since they are only evaluated once, unlike a
178 : * preprocessor macro.
179 : */
180 : template<typename _Tp>
181 : inline const _Tp&
182 23936 : min(const _Tp& __a, const _Tp& __b)
183 : {
184 : // concept requirements
185 : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
186 : //return __b < __a ? __b : __a;
187 23936 : if (__b < __a)
188 127 : return __b;
189 23809 : return __a;
190 23936 : }
191 :
192 : /**
193 : * @brief This does what you think it does.
194 : * @param a A thing of arbitrary type.
195 : * @param b Another thing of arbitrary type.
196 : * @return The greater of the parameters.
197 : *
198 : * This is the simple classic generic implementation. It will work on
199 : * temporary expressions, since they are only evaluated once, unlike a
200 : * preprocessor macro.
201 : */
202 : template<typename _Tp>
203 : inline const _Tp&
204 6502 : max(const _Tp& __a, const _Tp& __b)
205 : {
206 : // concept requirements
207 : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
208 : //return __a < __b ? __b : __a;
209 6502 : if (__a < __b)
210 5857 : return __b;
211 645 : return __a;
212 6502 : }
213 :
214 : /**
215 : * @brief This does what you think it does.
216 : * @param a A thing of arbitrary type.
217 : * @param b Another thing of arbitrary type.
218 : * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
219 : * @return The lesser of the parameters.
220 : *
221 : * This will work on temporary expressions, since they are only evaluated
222 : * once, unlike a preprocessor macro.
223 : */
224 : template<typename _Tp, typename _Compare>
225 : inline const _Tp&
226 : min(const _Tp& __a, const _Tp& __b, _Compare __comp)
227 : {
228 : //return __comp(__b, __a) ? __b : __a;
229 : if (__comp(__b, __a))
230 : return __b;
231 : return __a;
232 : }
233 :
234 : /**
235 : * @brief This does what you think it does.
236 : * @param a A thing of arbitrary type.
237 : * @param b Another thing of arbitrary type.
238 : * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
239 : * @return The greater of the parameters.
240 : *
241 : * This will work on temporary expressions, since they are only evaluated
242 : * once, unlike a preprocessor macro.
243 : */
244 : template<typename _Tp, typename _Compare>
245 : inline const _Tp&
246 : max(const _Tp& __a, const _Tp& __b, _Compare __comp)
247 : {
248 : //return __comp(__a, __b) ? __b : __a;
249 : if (__comp(__a, __b))
250 : return __b;
251 : return __a;
252 : }
253 :
254 : // All of these auxiliary structs serve two purposes. (1) Replace
255 : // calls to copy with memmove whenever possible. (Memmove, not memcpy,
256 : // because the input and output ranges are permitted to overlap.)
257 : // (2) If we're using random access iterators, then write the loop as
258 : // a for loop with an explicit count.
259 :
260 : template<bool, typename>
261 : struct __copy
262 : {
263 : template<typename _II, typename _OI>
264 : static _OI
265 : copy(_II __first, _II __last, _OI __result)
266 : {
267 : for (; __first != __last; ++__result, ++__first)
268 : *__result = *__first;
269 : return __result;
270 : }
271 : };
272 :
273 : template<bool _BoolType>
274 : struct __copy<_BoolType, random_access_iterator_tag>
275 : {
276 : template<typename _II, typename _OI>
277 : static _OI
278 0 : copy(_II __first, _II __last, _OI __result)
279 : {
280 : typedef typename iterator_traits<_II>::difference_type _Distance;
281 0 : for(_Distance __n = __last - __first; __n > 0; --__n)
282 : {
283 0 : *__result = *__first;
284 0 : ++__first;
285 0 : ++__result;
286 0 : }
287 0 : return __result;
288 : }
289 : };
290 :
291 : template<>
292 : struct __copy<true, random_access_iterator_tag>
293 : {
294 : template<typename _Tp>
295 : static _Tp*
296 20033 : copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
297 : {
298 20033 : std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
299 20033 : return __result + (__last - __first);
300 : }
301 : };
302 :
303 : template<typename _II, typename _OI>
304 : inline _OI
305 20033 : __copy_aux(_II __first, _II __last, _OI __result)
306 : {
307 : typedef typename iterator_traits<_II>::value_type _ValueTypeI;
308 : typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
309 : typedef typename iterator_traits<_II>::iterator_category _Category;
310 20033 : const bool __simple = (__is_scalar<_ValueTypeI>::__value
311 : && __is_pointer<_II>::__value
312 : && __is_pointer<_OI>::__value
313 : && __are_same<_ValueTypeI, _ValueTypeO>::__value);
314 :
315 20033 : return std::__copy<__simple, _Category>::copy(__first, __last, __result);
316 : }
317 :
318 : // Helpers for streambuf iterators (either istream or ostream).
319 : template<typename _CharT>
320 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
321 : ostreambuf_iterator<_CharT> >::__type
322 : __copy_aux(_CharT*, _CharT*, ostreambuf_iterator<_CharT>);
323 :
324 : template<typename _CharT>
325 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
326 : ostreambuf_iterator<_CharT> >::__type
327 : __copy_aux(const _CharT*, const _CharT*, ostreambuf_iterator<_CharT>);
328 :
329 : template<typename _CharT>
330 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type
331 : __copy_aux(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
332 : _CharT*);
333 :
334 : template<bool, bool>
335 : struct __copy_normal
336 : {
337 : template<typename _II, typename _OI>
338 : static _OI
339 20027 : __copy_n(_II __first, _II __last, _OI __result)
340 20027 : { return std::__copy_aux(__first, __last, __result); }
341 : };
342 :
343 : template<>
344 : struct __copy_normal<true, false>
345 : {
346 : template<typename _II, typename _OI>
347 : static _OI
348 6 : __copy_n(_II __first, _II __last, _OI __result)
349 6 : { return std::__copy_aux(__first.base(), __last.base(), __result); }
350 : };
351 :
352 : template<>
353 : struct __copy_normal<false, true>
354 : {
355 : template<typename _II, typename _OI>
356 : static _OI
357 : __copy_n(_II __first, _II __last, _OI __result)
358 : { return _OI(std::__copy_aux(__first, __last, __result.base())); }
359 : };
360 :
361 : template<>
362 : struct __copy_normal<true, true>
363 : {
364 : template<typename _II, typename _OI>
365 : static _OI
366 0 : __copy_n(_II __first, _II __last, _OI __result)
367 0 : { return _OI(std::__copy_aux(__first.base(), __last.base(),
368 0 : __result.base())); }
369 : };
370 :
371 : /**
372 : * @brief Copies the range [first,last) into result.
373 : * @param first An input iterator.
374 : * @param last An input iterator.
375 : * @param result An output iterator.
376 : * @return result + (last - first)
377 : *
378 : * This inline function will boil down to a call to @c memmove whenever
379 : * possible. Failing that, if random access iterators are passed, then the
380 : * loop count will be known (and therefore a candidate for compiler
381 : * optimizations such as unrolling). Result may not be contained within
382 : * [first,last); the copy_backward function should be used instead.
383 : *
384 : * Note that the end of the output range is permitted to be contained
385 : * within [first,last).
386 : */
387 : template<typename _InputIterator, typename _OutputIterator>
388 : inline _OutputIterator
389 20033 : copy(_InputIterator __first, _InputIterator __last,
390 20033 : _OutputIterator __result)
391 : {
392 : // concept requirements
393 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
394 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
395 : typename iterator_traits<_InputIterator>::value_type>)
396 : __glibcxx_requires_valid_range(__first, __last);
397 :
398 20033 : const bool __in = __is_normal_iterator<_InputIterator>::__value;
399 20033 : const bool __out = __is_normal_iterator<_OutputIterator>::__value;
400 20033 : return std::__copy_normal<__in, __out>::__copy_n(__first, __last,
401 : __result);
402 : }
403 :
404 : // Overload for streambuf iterators.
405 : template<typename _CharT>
406 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
407 : ostreambuf_iterator<_CharT> >::__type
408 : copy(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
409 : ostreambuf_iterator<_CharT>);
410 :
411 : template<bool, typename>
412 : struct __copy_backward
413 : {
414 : template<typename _BI1, typename _BI2>
415 : static _BI2
416 : __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
417 : {
418 : while (__first != __last)
419 : *--__result = *--__last;
420 : return __result;
421 : }
422 : };
423 :
424 : template<bool _BoolType>
425 : struct __copy_backward<_BoolType, random_access_iterator_tag>
426 : {
427 : template<typename _BI1, typename _BI2>
428 : static _BI2
429 0 : __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
430 : {
431 0 : typename iterator_traits<_BI1>::difference_type __n;
432 0 : for (__n = __last - __first; __n > 0; --__n)
433 0 : *--__result = *--__last;
434 0 : return __result;
435 : }
436 : };
437 :
438 : template<>
439 : struct __copy_backward<true, random_access_iterator_tag>
440 : {
441 : template<typename _Tp>
442 : static _Tp*
443 0 : __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
444 : {
445 0 : const ptrdiff_t _Num = __last - __first;
446 0 : std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
447 0 : return __result - _Num;
448 : }
449 : };
450 :
451 : template<typename _BI1, typename _BI2>
452 : inline _BI2
453 0 : __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
454 : {
455 : typedef typename iterator_traits<_BI1>::value_type _ValueType1;
456 : typedef typename iterator_traits<_BI2>::value_type _ValueType2;
457 : typedef typename iterator_traits<_BI1>::iterator_category _Category;
458 0 : const bool __simple = (__is_scalar<_ValueType1>::__value
459 : && __is_pointer<_BI1>::__value
460 : && __is_pointer<_BI2>::__value
461 : && __are_same<_ValueType1, _ValueType2>::__value);
462 :
463 0 : return std::__copy_backward<__simple, _Category>::__copy_b(__first,
464 : __last,
465 : __result);
466 : }
467 :
468 : template<bool, bool>
469 : struct __copy_backward_normal
470 : {
471 : template<typename _BI1, typename _BI2>
472 : static _BI2
473 0 : __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
474 0 : { return std::__copy_backward_aux(__first, __last, __result); }
475 : };
476 :
477 : template<>
478 : struct __copy_backward_normal<true, false>
479 : {
480 : template<typename _BI1, typename _BI2>
481 : static _BI2
482 : __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
483 : { return std::__copy_backward_aux(__first.base(), __last.base(),
484 : __result); }
485 : };
486 :
487 : template<>
488 : struct __copy_backward_normal<false, true>
489 : {
490 : template<typename _BI1, typename _BI2>
491 : static _BI2
492 : __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
493 : { return _BI2(std::__copy_backward_aux(__first, __last,
494 : __result.base())); }
495 : };
496 :
497 : template<>
498 : struct __copy_backward_normal<true, true>
499 : {
500 : template<typename _BI1, typename _BI2>
501 : static _BI2
502 : __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
503 : { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(),
504 : __result.base())); }
505 : };
506 :
507 : /**
508 : * @brief Copies the range [first,last) into result.
509 : * @param first A bidirectional iterator.
510 : * @param last A bidirectional iterator.
511 : * @param result A bidirectional iterator.
512 : * @return result - (first - last)
513 : *
514 : * The function has the same effect as copy, but starts at the end of the
515 : * range and works its way to the start, returning the start of the result.
516 : * This inline function will boil down to a call to @c memmove whenever
517 : * possible. Failing that, if random access iterators are passed, then the
518 : * loop count will be known (and therefore a candidate for compiler
519 : * optimizations such as unrolling).
520 : *
521 : * Result may not be in the range [first,last). Use copy instead. Note
522 : * that the start of the output range may overlap [first,last).
523 : */
524 : template <typename _BI1, typename _BI2>
525 : inline _BI2
526 0 : copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
527 : {
528 : // concept requirements
529 : __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
530 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
531 : __glibcxx_function_requires(_ConvertibleConcept<
532 : typename iterator_traits<_BI1>::value_type,
533 : typename iterator_traits<_BI2>::value_type>)
534 : __glibcxx_requires_valid_range(__first, __last);
535 :
536 0 : const bool __bi1 = __is_normal_iterator<_BI1>::__value;
537 0 : const bool __bi2 = __is_normal_iterator<_BI2>::__value;
538 0 : return std::__copy_backward_normal<__bi1, __bi2>::__copy_b_n(__first,
539 : __last,
540 : __result);
541 : }
542 :
543 : template<bool>
544 : struct __fill
545 : {
546 : template<typename _ForwardIterator, typename _Tp>
547 : static void
548 58 : fill(_ForwardIterator __first, _ForwardIterator __last,
549 58 : const _Tp& __value)
550 : {
551 116 : for (; __first != __last; ++__first)
552 0 : *__first = __value;
553 58 : }
554 : };
555 :
556 : template<>
557 : struct __fill<true>
558 : {
559 : template<typename _ForwardIterator, typename _Tp>
560 : static void
561 : fill(_ForwardIterator __first, _ForwardIterator __last,
562 : const _Tp& __value)
563 : {
564 : const _Tp __tmp = __value;
565 : for (; __first != __last; ++__first)
566 : *__first = __tmp;
567 : }
568 : };
569 :
570 : /**
571 : * @brief Fills the range [first,last) with copies of value.
572 : * @param first A forward iterator.
573 : * @param last A forward iterator.
574 : * @param value A reference-to-const of arbitrary type.
575 : * @return Nothing.
576 : *
577 : * This function fills a range with copies of the same value. For one-byte
578 : * types filling contiguous areas of memory, this becomes an inline call to
579 : * @c memset.
580 : */
581 : template<typename _ForwardIterator, typename _Tp>
582 : void
583 58 : fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
584 : {
585 : // concept requirements
586 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
587 : _ForwardIterator>)
588 : __glibcxx_requires_valid_range(__first, __last);
589 :
590 58 : const bool __scalar = __is_scalar<_Tp>::__value;
591 58 : std::__fill<__scalar>::fill(__first, __last, __value);
592 58 : }
593 :
594 : // Specialization: for one-byte types we can use memset.
595 : inline void
596 5212 : fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
597 : {
598 : __glibcxx_requires_valid_range(__first, __last);
599 5212 : const unsigned char __tmp = __c;
600 5212 : std::memset(__first, __tmp, __last - __first);
601 5212 : }
602 :
603 : inline void
604 : fill(signed char* __first, signed char* __last, const signed char& __c)
605 : {
606 : __glibcxx_requires_valid_range(__first, __last);
607 : const signed char __tmp = __c;
608 : std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
609 : }
610 :
611 : inline void
612 16681 : fill(char* __first, char* __last, const char& __c)
613 : {
614 : __glibcxx_requires_valid_range(__first, __last);
615 16681 : const char __tmp = __c;
616 16681 : std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
617 16681 : }
618 :
619 : template<bool>
620 : struct __fill_n
621 : {
622 : template<typename _OutputIterator, typename _Size, typename _Tp>
623 : static _OutputIterator
624 : fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
625 : {
626 : for (; __n > 0; --__n, ++__first)
627 : *__first = __value;
628 : return __first;
629 : }
630 : };
631 :
632 : template<>
633 : struct __fill_n<true>
634 : {
635 : template<typename _OutputIterator, typename _Size, typename _Tp>
636 : static _OutputIterator
637 : fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
638 : {
639 : const _Tp __tmp = __value;
640 : for (; __n > 0; --__n, ++__first)
641 : *__first = __tmp;
642 : return __first;
643 : }
644 : };
645 :
646 : /**
647 : * @brief Fills the range [first,first+n) with copies of value.
648 : * @param first An output iterator.
649 : * @param n The count of copies to perform.
650 : * @param value A reference-to-const of arbitrary type.
651 : * @return The iterator at first+n.
652 : *
653 : * This function fills a range with copies of the same value. For one-byte
654 : * types filling contiguous areas of memory, this becomes an inline call to
655 : * @c memset.
656 : */
657 : template<typename _OutputIterator, typename _Size, typename _Tp>
658 : _OutputIterator
659 : fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
660 : {
661 : // concept requirements
662 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
663 :
664 : const bool __scalar = __is_scalar<_Tp>::__value;
665 : return std::__fill_n<__scalar>::fill_n(__first, __n, __value);
666 : }
667 :
668 : template<typename _Size>
669 : inline unsigned char*
670 5206 : fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
671 : {
672 5206 : std::fill(__first, __first + __n, __c);
673 5206 : return __first + __n;
674 : }
675 :
676 : template<typename _Size>
677 : inline signed char*
678 : fill_n(signed char* __first, _Size __n, const signed char& __c)
679 : {
680 : std::fill(__first, __first + __n, __c);
681 : return __first + __n;
682 : }
683 :
684 : template<typename _Size>
685 : inline char*
686 8626 : fill_n(char* __first, _Size __n, const char& __c)
687 : {
688 8626 : std::fill(__first, __first + __n, __c);
689 8626 : return __first + __n;
690 : }
691 :
692 : /**
693 : * @brief Finds the places in ranges which don't match.
694 : * @param first1 An input iterator.
695 : * @param last1 An input iterator.
696 : * @param first2 An input iterator.
697 : * @return A pair of iterators pointing to the first mismatch.
698 : *
699 : * This compares the elements of two ranges using @c == and returns a pair
700 : * of iterators. The first iterator points into the first range, the
701 : * second iterator points into the second range, and the elements pointed
702 : * to by the iterators are not equal.
703 : */
704 : template<typename _InputIterator1, typename _InputIterator2>
705 : pair<_InputIterator1, _InputIterator2>
706 : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
707 : _InputIterator2 __first2)
708 : {
709 : // concept requirements
710 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
711 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
712 : __glibcxx_function_requires(_EqualOpConcept<
713 : typename iterator_traits<_InputIterator1>::value_type,
714 : typename iterator_traits<_InputIterator2>::value_type>)
715 : __glibcxx_requires_valid_range(__first1, __last1);
716 :
717 : while (__first1 != __last1 && *__first1 == *__first2)
718 : {
719 : ++__first1;
720 : ++__first2;
721 : }
722 : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
723 : }
724 :
725 : /**
726 : * @brief Finds the places in ranges which don't match.
727 : * @param first1 An input iterator.
728 : * @param last1 An input iterator.
729 : * @param first2 An input iterator.
730 : * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
731 : * @return A pair of iterators pointing to the first mismatch.
732 : *
733 : * This compares the elements of two ranges using the binary_pred
734 : * parameter, and returns a pair
735 : * of iterators. The first iterator points into the first range, the
736 : * second iterator points into the second range, and the elements pointed
737 : * to by the iterators are not equal.
738 : */
739 : template<typename _InputIterator1, typename _InputIterator2,
740 : typename _BinaryPredicate>
741 : pair<_InputIterator1, _InputIterator2>
742 : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
743 : _InputIterator2 __first2, _BinaryPredicate __binary_pred)
744 : {
745 : // concept requirements
746 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
747 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
748 : __glibcxx_requires_valid_range(__first1, __last1);
749 :
750 : while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
751 : {
752 : ++__first1;
753 : ++__first2;
754 : }
755 : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
756 : }
757 :
758 : /**
759 : * @brief Tests a range for element-wise equality.
760 : * @param first1 An input iterator.
761 : * @param last1 An input iterator.
762 : * @param first2 An input iterator.
763 : * @return A boolean true or false.
764 : *
765 : * This compares the elements of two ranges using @c == and returns true or
766 : * false depending on whether all of the corresponding elements of the
767 : * ranges are equal.
768 : */
769 : template<typename _InputIterator1, typename _InputIterator2>
770 : inline bool
771 : equal(_InputIterator1 __first1, _InputIterator1 __last1,
772 : _InputIterator2 __first2)
773 : {
774 : // concept requirements
775 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
776 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
777 : __glibcxx_function_requires(_EqualOpConcept<
778 : typename iterator_traits<_InputIterator1>::value_type,
779 : typename iterator_traits<_InputIterator2>::value_type>)
780 : __glibcxx_requires_valid_range(__first1, __last1);
781 :
782 : for (; __first1 != __last1; ++__first1, ++__first2)
783 : if (!(*__first1 == *__first2))
784 : return false;
785 : return true;
786 : }
787 :
788 : /**
789 : * @brief Tests a range for element-wise equality.
790 : * @param first1 An input iterator.
791 : * @param last1 An input iterator.
792 : * @param first2 An input iterator.
793 : * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
794 : * @return A boolean true or false.
795 : *
796 : * This compares the elements of two ranges using the binary_pred
797 : * parameter, and returns true or
798 : * false depending on whether all of the corresponding elements of the
799 : * ranges are equal.
800 : */
801 : template<typename _InputIterator1, typename _InputIterator2,
802 : typename _BinaryPredicate>
803 : inline bool
804 : equal(_InputIterator1 __first1, _InputIterator1 __last1,
805 : _InputIterator2 __first2,
806 : _BinaryPredicate __binary_pred)
807 : {
808 : // concept requirements
809 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
810 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
811 : __glibcxx_requires_valid_range(__first1, __last1);
812 :
813 : for (; __first1 != __last1; ++__first1, ++__first2)
814 : if (!__binary_pred(*__first1, *__first2))
815 : return false;
816 : return true;
817 : }
818 :
819 : /**
820 : * @brief Performs "dictionary" comparison on ranges.
821 : * @param first1 An input iterator.
822 : * @param last1 An input iterator.
823 : * @param first2 An input iterator.
824 : * @param last2 An input iterator.
825 : * @return A boolean true or false.
826 : *
827 : * "Returns true if the sequence of elements defined by the range
828 : * [first1,last1) is lexicographically less than the sequence of elements
829 : * defined by the range [first2,last2). Returns false otherwise."
830 : * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
831 : * then this is an inline call to @c memcmp.
832 : */
833 : template<typename _InputIterator1, typename _InputIterator2>
834 : bool
835 : lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
836 : _InputIterator2 __first2, _InputIterator2 __last2)
837 : {
838 : // concept requirements
839 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
840 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
841 : __glibcxx_function_requires(_LessThanOpConcept<
842 : typename iterator_traits<_InputIterator1>::value_type,
843 : typename iterator_traits<_InputIterator2>::value_type>)
844 : __glibcxx_function_requires(_LessThanOpConcept<
845 : typename iterator_traits<_InputIterator2>::value_type,
846 : typename iterator_traits<_InputIterator1>::value_type>)
847 : __glibcxx_requires_valid_range(__first1, __last1);
848 : __glibcxx_requires_valid_range(__first2, __last2);
849 :
850 : for (; __first1 != __last1 && __first2 != __last2;
851 : ++__first1, ++__first2)
852 : {
853 : if (*__first1 < *__first2)
854 : return true;
855 : if (*__first2 < *__first1)
856 : return false;
857 : }
858 : return __first1 == __last1 && __first2 != __last2;
859 : }
860 :
861 : /**
862 : * @brief Performs "dictionary" comparison on ranges.
863 : * @param first1 An input iterator.
864 : * @param last1 An input iterator.
865 : * @param first2 An input iterator.
866 : * @param last2 An input iterator.
867 : * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
868 : * @return A boolean true or false.
869 : *
870 : * The same as the four-parameter @c lexigraphical_compare, but uses the
871 : * comp parameter instead of @c <.
872 : */
873 : template<typename _InputIterator1, typename _InputIterator2,
874 : typename _Compare>
875 : bool
876 : lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
877 : _InputIterator2 __first2, _InputIterator2 __last2,
878 : _Compare __comp)
879 : {
880 : // concept requirements
881 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
882 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
883 : __glibcxx_requires_valid_range(__first1, __last1);
884 : __glibcxx_requires_valid_range(__first2, __last2);
885 :
886 : for (; __first1 != __last1 && __first2 != __last2;
887 : ++__first1, ++__first2)
888 : {
889 : if (__comp(*__first1, *__first2))
890 : return true;
891 : if (__comp(*__first2, *__first1))
892 : return false;
893 : }
894 : return __first1 == __last1 && __first2 != __last2;
895 : }
896 :
897 : inline bool
898 : lexicographical_compare(const unsigned char* __first1,
899 : const unsigned char* __last1,
900 : const unsigned char* __first2,
901 : const unsigned char* __last2)
902 : {
903 : __glibcxx_requires_valid_range(__first1, __last1);
904 : __glibcxx_requires_valid_range(__first2, __last2);
905 :
906 : const size_t __len1 = __last1 - __first1;
907 : const size_t __len2 = __last2 - __first2;
908 : const int __result = std::memcmp(__first1, __first2,
909 : std::min(__len1, __len2));
910 : return __result != 0 ? __result < 0 : __len1 < __len2;
911 : }
912 :
913 : inline bool
914 : lexicographical_compare(const char* __first1, const char* __last1,
915 : const char* __first2, const char* __last2)
916 : {
917 : __glibcxx_requires_valid_range(__first1, __last1);
918 : __glibcxx_requires_valid_range(__first2, __last2);
919 :
920 : #if CHAR_MAX == SCHAR_MAX
921 : return std::lexicographical_compare((const signed char*) __first1,
922 : (const signed char*) __last1,
923 : (const signed char*) __first2,
924 : (const signed char*) __last2);
925 : #else /* CHAR_MAX == SCHAR_MAX */
926 : return std::lexicographical_compare((const unsigned char*) __first1,
927 : (const unsigned char*) __last1,
928 : (const unsigned char*) __first2,
929 : (const unsigned char*) __last2);
930 : #endif /* CHAR_MAX == SCHAR_MAX */
931 : }
932 :
933 : _GLIBCXX_END_NAMESPACE
934 :
935 : #endif
|
