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