?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
btrfs: [] on the end of a struct field is a variable length array.
[haiku.git] / headers / cpp / stl_algo.h
blobe9beaee15f11a5d01f85bdef3032a01265dcb7f1
1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
13 *
14 *
15 * Copyright (c) 1996
16 * Silicon Graphics Computer Systems, Inc.
17 *
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
25 */
26
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
29 */
30
31 #ifndef __SGI_STL_INTERNAL_ALGO_H
32 #define __SGI_STL_INTERNAL_ALGO_H
33
34 #include <stl_heap.h>
35
36 __STL_BEGIN_NAMESPACE
37
38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
39 #pragma set woff 1209
40 #endif
41
42 // __median (an extension, not present in the C++ standard).
43
44 template <class _Tp>
45 inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
46 if (__a < __b)
47 if (__b < __c)
48 return __b;
49 else if (__a < __c)
50 return __c;
51 else
52 return __a;
53 else if (__a < __c)
54 return __a;
55 else if (__b < __c)
56 return __c;
57 else
58 return __b;
59 }
60
61 template <class _Tp, class _Compare>
62 inline const _Tp&
63 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
64 if (__comp(__a, __b))
65 if (__comp(__b, __c))
66 return __b;
67 else if (__comp(__a, __c))
68 return __c;
69 else
70 return __a;
71 else if (__comp(__a, __c))
72 return __a;
73 else if (__comp(__b, __c))
74 return __c;
75 else
76 return __b;
77 }
78
79 // for_each. Apply a function to every element of a range.
80 template <class _InputIter, class _Function>
81 _Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
82 for ( ; __first != __last; ++__first)
83 __f(*__first);
84 return __f;
85 }
86
87 // find and find_if.
88
89 template <class _InputIter, class _Tp>
90 inline _InputIter find(_InputIter __first, _InputIter __last,
91 const _Tp& __val,
92 input_iterator_tag)
93 {
94 while (__first != __last && *__first != __val)
95 ++__first;
96 return __first;
97 }
98
99 template <class _InputIter, class _Predicate>
100 inline _InputIter find_if(_InputIter __first, _InputIter __last,
101 _Predicate __pred,
102 input_iterator_tag)
103 {
104 while (__first != __last && !__pred(*__first))
105 ++__first;
106 return __first;
107 }
108
109 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
110
111 template <class _RandomAccessIter, class _Tp>
112 _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
113 const _Tp& __val,
114 random_access_iterator_tag)
115 {
116 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
117 = (__last - __first) >> 2;
118
119 for ( ; __trip_count > 0 ; --__trip_count) {
120 if (*__first == __val) return __first;
121 ++__first;
122
123 if (*__first == __val) return __first;
124 ++__first;
125
126 if (*__first == __val) return __first;
127 ++__first;
128
129 if (*__first == __val) return __first;
130 ++__first;
131 }
132
133 switch(__last - __first) {
134 case 3:
135 if (*__first == __val) return __first;
136 ++__first;
137 case 2:
138 if (*__first == __val) return __first;
139 ++__first;
140 case 1:
141 if (*__first == __val) return __first;
142 ++__first;
143 case 0:
144 default:
145 return __last;
146 }
147 }
148
149 template <class _RandomAccessIter, class _Predicate>
150 _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
151 _Predicate __pred,
152 random_access_iterator_tag)
153 {
154 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
155 = (__last - __first) >> 2;
156
157 for ( ; __trip_count > 0 ; --__trip_count) {
158 if (__pred(*__first)) return __first;
159 ++__first;
160
161 if (__pred(*__first)) return __first;
162 ++__first;
163
164 if (__pred(*__first)) return __first;
165 ++__first;
166
167 if (__pred(*__first)) return __first;
168 ++__first;
169 }
170
171 switch(__last - __first) {
172 case 3:
173 if (__pred(*__first)) return __first;
174 ++__first;
175 case 2:
176 if (__pred(*__first)) return __first;
177 ++__first;
178 case 1:
179 if (__pred(*__first)) return __first;
180 ++__first;
181 case 0:
182 default:
183 return __last;
184 }
185 }
186
187 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
188
189 template <class _InputIter, class _Tp>
190 inline _InputIter find(_InputIter __first, _InputIter __last,
191 const _Tp& __val)
192 {
193 return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
194 }
195
196 template <class _InputIter, class _Predicate>
197 inline _InputIter find_if(_InputIter __first, _InputIter __last,
198 _Predicate __pred) {
199 return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
200 }
201
202 // adjacent_find.
203
204 template <class _ForwardIter>
205 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
206 if (__first == __last)
207 return __last;
208 _ForwardIter __next = __first;
209 while(++__next != __last) {
210 if (*__first == *__next)
211 return __first;
212 __first = __next;
213 }
214 return __last;
215 }
216
217 template <class _ForwardIter, class _BinaryPredicate>
218 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
219 _BinaryPredicate __binary_pred) {
220 if (__first == __last)
221 return __last;
222 _ForwardIter __next = __first;
223 while(++__next != __last) {
224 if (__binary_pred(*__first, *__next))
225 return __first;
226 __first = __next;
227 }
228 return __last;
229 }
230
231 // count and count_if. There are two version of each, one whose return type
232 // type is void and one (present only if we have partial specialization)
233 // whose return type is iterator_traits<_InputIter>::difference_type. The
234 // C++ standard only has the latter version, but the former, which was present
235 // in the HP STL, is retained for backward compatibility.
236
237 template <class _InputIter, class _Tp, class _Size>
238 void count(_InputIter __first, _InputIter __last, const _Tp& __value,
239 _Size& __n) {
240 for ( ; __first != __last; ++__first)
241 if (*__first == __value)
242 ++__n;
243 }
244
245 template <class _InputIter, class _Predicate, class _Size>
246 void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
247 _Size& __n) {
248 for ( ; __first != __last; ++__first)
249 if (__pred(*__first))
250 ++__n;
251 }
252
253 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
254
255 template <class _InputIter, class _Tp>
256 typename iterator_traits<_InputIter>::difference_type
257 count(_InputIter __first, _InputIter __last, const _Tp& __value) {
258 typename iterator_traits<_InputIter>::difference_type __n = 0;
259 for ( ; __first != __last; ++__first)
260 if (*__first == __value)
261 ++__n;
262 return __n;
263 }
264
265 template <class _InputIter, class _Predicate>
266 typename iterator_traits<_InputIter>::difference_type
267 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
268 typename iterator_traits<_InputIter>::difference_type __n = 0;
269 for ( ; __first != __last; ++__first)
270 if (__pred(*__first))
271 ++__n;
272 return __n;
273 }
274
275
276 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
277
278 // search.
279
280 template <class _ForwardIter1, class _ForwardIter2>
281 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
282 _ForwardIter2 __first2, _ForwardIter2 __last2)
283 {
284 // Test for empty ranges
285 if (__first1 == __last1 || __first2 == __last2)
286 return __first1;
287
288 // Test for a pattern of length 1.
289 _ForwardIter2 __tmp(__first2);
290 ++__tmp;
291 if (__tmp == __last2)
292 return find(__first1, __last1, *__first2);
293
294 // General case.
295
296 _ForwardIter2 __p1, __p;
297
298 __p1 = __first2; ++__p1;
299
300 _ForwardIter1 __current = __first1;
301
302 while (__first1 != __last1) {
303 __first1 = find(__first1, __last1, *__first2);
304 if (__first1 == __last1)
305 return __last1;
306
307 __p = __p1;
308 __current = __first1;
309 if (++__current == __last1)
310 return __last1;
311
312 while (*__current == *__p) {
313 if (++__p == __last2)
314 return __first1;
315 if (++__current == __last1)
316 return __last1;
317 }
318
319 ++__first1;
320 }
321 return __first1;
322 }
323
324 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
325 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
326 _ForwardIter2 __first2, _ForwardIter2 __last2,
327 _BinaryPred __predicate)
328 {
329 // Test for empty ranges
330 if (__first1 == __last1 || __first2 == __last2)
331 return __first1;
332
333 // Test for a pattern of length 1.
334 _ForwardIter2 __tmp(__first2);
335 ++__tmp;
336 if (__tmp == __last2)
337 return find(__first1, __last1, *__first2);
338
339 // General case.
340
341 _ForwardIter2 __p1, __p;
342
343 __p1 = __first2; ++__p1;
344
345 _ForwardIter1 __current = __first1;
346
347 while (__first1 != __last1) {
348 while (__first1 != __last1) {
349 if (__predicate(*__first1, *__first2))
350 break;
351 ++__first1;
352 }
353 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
354 ++__first1;
355 if (__first1 == __last1)
356 return __last1;
357
358 __p = __p1;
359 __current = __first1;
360 if (++__current == __last1) return __last1;
361
362 while (__predicate(*__current, *__p)) {
363 if (++__p == __last2)
364 return __first1;
365 if (++__current == __last1)
366 return __last1;
367 }
368
369 ++__first1;
370 }
371 return __first1;
372 }
373
374 // search_n. Search for __count consecutive copies of __val.
375
376 template <class _ForwardIter, class _Integer, class _Tp>
377 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
378 _Integer __count, const _Tp& __val) {
379 if (__count <= 0)
380 return __first;
381 else {
382 __first = find(__first, __last, __val);
383 while (__first != __last) {
384 _Integer __n = __count - 1;
385 _ForwardIter __i = __first;
386 ++__i;
387 while (__i != __last && __n != 0 && *__i == __val) {
388 ++__i;
389 --__n;
390 }
391 if (__n == 0)
392 return __first;
393 else
394 __first = find(__i, __last, __val);
395 }
396 return __last;
397 }
398 }
399
400 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
401 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
402 _Integer __count, const _Tp& __val,
403 _BinaryPred __binary_pred) {
404 if (__count <= 0)
405 return __first;
406 else {
407 while (__first != __last) {
408 if (__binary_pred(*__first, __val))
409 break;
410 ++__first;
411 }
412 while (__first != __last) {
413 _Integer __n = __count - 1;
414 _ForwardIter __i = __first;
415 ++__i;
416 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
417 ++__i;
418 --__n;
419 }
420 if (__n == 0)
421 return __first;
422 else {
423 while (__i != __last) {
424 if (__binary_pred(*__i, __val))
425 break;
426 ++__i;
427 }
428 __first = __i;
429 }
430 }
431 return __last;
432 }
433 }
434
435 // swap_ranges
436
437 template <class _ForwardIter1, class _ForwardIter2>
438 _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
439 _ForwardIter2 __first2) {
440 for ( ; __first1 != __last1; ++__first1, ++__first2)
441 iter_swap(__first1, __first2);
442 return __first2;
443 }
444
445 // transform
446
447 template <class _InputIter, class _OutputIter, class _UnaryOperation>
448 _OutputIter transform(_InputIter __first, _InputIter __last,
449 _OutputIter __result, _UnaryOperation __oper) {
450 for ( ; __first != __last; ++__first, ++__result)
451 *__result = __oper(*__first);
452 return __result;
453 }
454
455 template <class _InputIter1, class _InputIter2, class _OutputIter,
456 class _BinaryOperation>
457 _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
458 _InputIter2 __first2, _OutputIter __result,
459 _BinaryOperation __binary_op) {
460 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
461 *__result = __binary_op(*__first1, *__first2);
462 return __result;
463 }
464
465 // replace, replace_if, replace_copy, replace_copy_if
466
467 template <class _ForwardIter, class _Tp>
468 void replace(_ForwardIter __first, _ForwardIter __last,
469 const _Tp& __old_value, const _Tp& __new_value) {
470 for ( ; __first != __last; ++__first)
471 if (*__first == __old_value)
472 *__first = __new_value;
473 }
474
475 template <class _ForwardIter, class _Predicate, class _Tp>
476 void replace_if(_ForwardIter __first, _ForwardIter __last,
477 _Predicate __pred, const _Tp& __new_value) {
478 for ( ; __first != __last; ++__first)
479 if (__pred(*__first))
480 *__first = __new_value;
481 }
482
483 template <class _InputIter, class _OutputIter, class _Tp>
484 _OutputIter replace_copy(_InputIter __first, _InputIter __last,
485 _OutputIter __result,
486 const _Tp& __old_value, const _Tp& __new_value) {
487 for ( ; __first != __last; ++__first, ++__result)
488 *__result = *__first == __old_value ? __new_value : *__first;
489 return __result;
490 }
491
492 template <class Iterator, class _OutputIter, class _Predicate, class _Tp>
493 _OutputIter replace_copy_if(Iterator __first, Iterator __last,
494 _OutputIter __result,
495 _Predicate __pred, const _Tp& __new_value) {
496 for ( ; __first != __last; ++__first, ++__result)
497 *__result = __pred(*__first) ? __new_value : *__first;
498 return __result;
499 }
500
501 // generate and generate_n
502
503 template <class _ForwardIter, class _Generator>
504 void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
505 for ( ; __first != __last; ++__first)
506 *__first = __gen();
507 }
508
509 template <class _OutputIter, class _Size, class _Generator>
510 _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
511 for ( ; __n > 0; --__n, ++__first)
512 *__first = __gen();
513 return __first;
514 }
515
516 // remove, remove_if, remove_copy, remove_copy_if
517
518 template <class _InputIter, class _OutputIter, class _Tp>
519 _OutputIter remove_copy(_InputIter __first, _InputIter __last,
520 _OutputIter __result, const _Tp& __value) {
521 for ( ; __first != __last; ++__first)
522 if (*__first != __value) {
523 *__result = *__first;
524 ++__result;
525 }
526 return __result;
527 }
528
529 template <class _InputIter, class _OutputIter, class _Predicate>
530 _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
531 _OutputIter __result, _Predicate __pred) {
532 for ( ; __first != __last; ++__first)
533 if (!__pred(*__first)) {
534 *__result = *__first;
535 ++__result;
536 }
537 return __result;
538 }
539
540 template <class _ForwardIter, class _Tp>
541 _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
542 const _Tp& __value) {
543 __first = find(__first, __last, __value);
544 _ForwardIter __i = __first;
545 return __first == __last ? __first
546 : remove_copy(++__i, __last, __first, __value);
547 }
548
549 template <class _ForwardIter, class _Predicate>
550 _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
551 _Predicate __pred) {
552 __first = find_if(__first, __last, __pred);
553 _ForwardIter __i = __first;
554 return __first == __last ? __first
555 : remove_copy_if(++__i, __last, __first, __pred);
556 }
557
558 // unique and unique_copy
559
560 template <class _InputIter, class _OutputIter, class _Tp>
561 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
562 _OutputIter __result, _Tp*) {
563 _Tp __value = *__first;
564 *__result = __value;
565 while (++__first != __last)
566 if (__value != *__first) {
567 __value = *__first;
568 *++__result = __value;
569 }
570 return ++__result;
571 }
572
573 template <class _InputIter, class _OutputIter>
574 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
575 _OutputIter __result,
576 output_iterator_tag) {
577 return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
578 }
579
580 template <class _InputIter, class _ForwardIter>
581 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
582 _ForwardIter __result, forward_iterator_tag) {
583 *__result = *__first;
584 while (++__first != __last)
585 if (*__result != *__first) *++__result = *__first;
586 return ++__result;
587 }
588
589 template <class _InputIter, class _OutputIter>
590 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
591 _OutputIter __result) {
592 if (__first == __last) return __result;
593 return __unique_copy(__first, __last, __result,
594 __ITERATOR_CATEGORY(__result));
595 }
596
597 template <class _InputIter, class _OutputIter, class _BinaryPredicate,
598 class _Tp>
599 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
600 _OutputIter __result,
601 _BinaryPredicate __binary_pred, _Tp*) {
602 _Tp __value = *__first;
603 *__result = __value;
604 while (++__first != __last)
605 if (!__binary_pred(__value, *__first)) {
606 __value = *__first;
607 *++__result = __value;
608 }
609 return ++__result;
610 }
611
612 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
613 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
614 _OutputIter __result,
615 _BinaryPredicate __binary_pred,
616 output_iterator_tag) {
617 return __unique_copy(__first, __last, __result, __binary_pred,
618 __VALUE_TYPE(__first));
619 }
620
621 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
622 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
623 _ForwardIter __result,
624 _BinaryPredicate __binary_pred,
625 forward_iterator_tag) {
626 *__result = *__first;
627 while (++__first != __last)
628 if (!__binary_pred(*__result, *__first)) *++__result = *__first;
629 return ++__result;
630 }
631
632 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
633 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
634 _OutputIter __result,
635 _BinaryPredicate __binary_pred) {
636 if (__first == __last) return __result;
637 return __unique_copy(__first, __last, __result, __binary_pred,
638 __ITERATOR_CATEGORY(__result));
639 }
640
641 template <class _ForwardIter>
642 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
643 __first = adjacent_find(__first, __last);
644 return unique_copy(__first, __last, __first);
645 }
646
647 template <class _ForwardIter, class _BinaryPredicate>
648 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
649 _BinaryPredicate __binary_pred) {
650 __first = adjacent_find(__first, __last, __binary_pred);
651 return unique_copy(__first, __last, __first, __binary_pred);
652 }
653
654 // reverse and reverse_copy, and their auxiliary functions
655
656 template <class _BidirectionalIter>
657 void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
658 bidirectional_iterator_tag) {
659 while (true)
660 if (__first == __last || __first == --__last)
661 return;
662 else
663 iter_swap(__first++, __last);
664 }
665
666 template <class _RandomAccessIter>
667 void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
668 random_access_iterator_tag) {
669 while (__first < __last)
670 iter_swap(__first++, --__last);
671 }
672
673 template <class _BidirectionalIter>
674 inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
675 __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
676 }
677
678 template <class _BidirectionalIter, class _OutputIter>
679 _OutputIter reverse_copy(_BidirectionalIter __first,
680 _BidirectionalIter __last,
681 _OutputIter __result) {
682 while (__first != __last) {
683 --__last;
684 *__result = *__last;
685 ++__result;
686 }
687 return __result;
688 }
689
690 // rotate and rotate_copy, and their auxiliary functions
691
692 template <class _EuclideanRingElement>
693 _EuclideanRingElement __gcd(_EuclideanRingElement __m,
694 _EuclideanRingElement __n)
695 {
696 while (__n != 0) {
697 _EuclideanRingElement __t = __m % __n;
698 __m = __n;
699 __n = __t;
700 }
701 return __m;
702 }
703
704 template <class _ForwardIter, class _Distance>
705 _ForwardIter __rotate(_ForwardIter __first,
706 _ForwardIter __middle,
707 _ForwardIter __last,
708 _Distance*,
709 forward_iterator_tag) {
710 if (__first == __middle)
711 return __last;
712 if (__last == __middle)
713 return __first;
714
715 _ForwardIter __first2 = __middle;
716 do {
717 swap(*__first++, *__first2++);
718 if (__first == __middle)
719 __middle = __first2;
720 } while (__first2 != __last);
721
722 _ForwardIter __new_middle = __first;
723
724 __first2 = __middle;
725
726 while (__first2 != __last) {
727 swap (*__first++, *__first2++);
728 if (__first == __middle)
729 __middle = __first2;
730 else if (__first2 == __last)
731 __first2 = __middle;
732 }
733
734 return __new_middle;
735 }
736
737
738 template <class _BidirectionalIter, class _Distance>
739 _BidirectionalIter __rotate(_BidirectionalIter __first,
740 _BidirectionalIter __middle,
741 _BidirectionalIter __last,
742 _Distance*,
743 bidirectional_iterator_tag) {
744 if (__first == __middle)
745 return __last;
746 if (__last == __middle)
747 return __first;
748
749 __reverse(__first, __middle, bidirectional_iterator_tag());
750 __reverse(__middle, __last, bidirectional_iterator_tag());
751
752 while (__first != __middle && __middle != __last)
753 swap (*__first++, *--__last);
754
755 if (__first == __middle) {
756 __reverse(__middle, __last, bidirectional_iterator_tag());
757 return __last;
758 }
759 else {
760 __reverse(__first, __middle, bidirectional_iterator_tag());
761 return __first;
762 }
763 }
764
765 template <class _RandomAccessIter, class _Distance, class _Tp>
766 _RandomAccessIter __rotate(_RandomAccessIter __first,
767 _RandomAccessIter __middle,
768 _RandomAccessIter __last,
769 _Distance *, _Tp *) {
770
771 _Distance __n = __last - __first;
772 _Distance __k = __middle - __first;
773 _Distance __l = __n - __k;
774 _RandomAccessIter __result = __first + (__last - __middle);
775
776 if (__k == __l) {
777 swap_ranges(__first, __middle, __middle);
778 return __result;
779 }
780
781 _Distance __d = __gcd(__n, __k);
782
783 for (_Distance __i = 0; __i < __d; __i++) {
784 _Tp __tmp = *__first;
785 _RandomAccessIter __p = __first;
786
787 if (__k < __l) {
788 for (_Distance __j = 0; __j < __l/__d; __j++) {
789 if (__p > __first + __l) {
790 *__p = *(__p - __l);
791 __p -= __l;
792 }
793
794 *__p = *(__p + __k);
795 __p += __k;
796 }
797 }
798
799 else {
800 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
801 if (__p < __last - __k) {
802 *__p = *(__p + __k);
803 __p += __k;
804 }
805
806 *__p = * (__p - __l);
807 __p -= __l;
808 }
809 }
810
811 *__p = __tmp;
812 ++__first;
813 }
814
815 return __result;
816 }
817
818 template <class _ForwardIter>
819 inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
820 _ForwardIter __last) {
821 return __rotate(__first, __middle, __last,
822 __DISTANCE_TYPE(__first),
823 __ITERATOR_CATEGORY(__first));
824 }
825
826 template <class _ForwardIter, class _OutputIter>
827 _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
828 _ForwardIter __last, _OutputIter __result) {
829 return copy(__first, __middle, copy(__middle, __last, __result));
830 }
831
832 // Return a random number in the range [0, __n). This function encapsulates
833 // whether we're using rand (part of the standard C library) or lrand48
834 // (not standard, but a much better choice whenever it's available).
835
836 template <class _Distance>
837 inline _Distance __random_number(_Distance __n) {
838 #ifdef __STL_NO_DRAND48
839 return rand() % __n;
840 #else
841 return lrand48() % __n;
842 #endif
843 }
844
845 // random_shuffle
846
847 template <class _RandomAccessIter>
848 inline void random_shuffle(_RandomAccessIter __first,
849 _RandomAccessIter __last) {
850 if (__first == __last) return;
851 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
852 iter_swap(__i, __first + __random_number((__i - __first) + 1));
853 }
854
855 template <class _RandomAccessIter, class _RandomNumberGenerator>
856 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
857 _RandomNumberGenerator& __rand) {
858 if (__first == __last) return;
859 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
860 iter_swap(__i, __first + __rand((__i - __first) + 1));
861 }
862
863 // random_sample and random_sample_n (extensions, not part of the standard).
864
865 template <class _ForwardIter, class _OutputIter, class _Distance>
866 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
867 _OutputIter __out, const _Distance __n)
868 {
869 _Distance __remaining = 0;
870 distance(__first, __last, __remaining);
871 _Distance __m = min(__n, __remaining);
872
873 while (__m > 0) {
874 if (__random_number(__remaining) < __m) {
875 *__out = *__first;
876 ++__out;
877 --__m;
878 }
879
880 --__remaining;
881 ++__first;
882 }
883 return __out;
884 }
885
886 template <class _ForwardIter, class _OutputIter, class _Distance,
887 class _RandomNumberGenerator>
888 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
889 _OutputIter __out, const _Distance __n,
890 _RandomNumberGenerator& __rand)
891 {
892 _Distance __remaining = 0;
893 distance(__first, __last, __remaining);
894 _Distance __m = min(__n, __remaining);
895
896 while (__m > 0) {
897 if (__rand(__remaining) < __m) {
898 *__out = *__first;
899 ++__out;
900 --__m;
901 }
902
903 --__remaining;
904 ++__first;
905 }
906 return __out;
907 }
908
909 template <class _InputIter, class _RandomAccessIter, class _Distance>
910 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
911 _RandomAccessIter __out,
912 const _Distance __n)
913 {
914 _Distance __m = 0;
915 _Distance __t = __n;
916 for ( ; __first != __last && __m < __n; ++__m, ++__first)
917 __out[__m] = *__first;
918
919 while (__first != __last) {
920 ++__t;
921 _Distance __M = __random_number(__t);
922 if (__M < __n)
923 __out[__M] = *__first;
924 ++__first;
925 }
926
927 return __out + __m;
928 }
929
930 template <class _InputIter, class _RandomAccessIter,
931 class _RandomNumberGenerator, class _Distance>
932 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
933 _RandomAccessIter __out,
934 _RandomNumberGenerator& __rand,
935 const _Distance __n)
936 {
937 _Distance __m = 0;
938 _Distance __t = __n;
939 for ( ; __first != __last && __m < __n; ++__m, ++__first)
940 __out[__m] = *__first;
941
942 while (__first != __last) {
943 ++__t;
944 _Distance __M = __rand(__t);
945 if (__M < __n)
946 __out[__M] = *__first;
947 ++__first;
948 }
949
950 return __out + __m;
951 }
952
953 template <class _InputIter, class _RandomAccessIter>
954 inline _RandomAccessIter
955 random_sample(_InputIter __first, _InputIter __last,
956 _RandomAccessIter __out_first, _RandomAccessIter __out_last)
957 {
958 return __random_sample(__first, __last,
959 __out_first, __out_last - __out_first);
960 }
961
962
963 template <class _InputIter, class _RandomAccessIter,
964 class _RandomNumberGenerator>
965 inline _RandomAccessIter
966 random_sample(_InputIter __first, _InputIter __last,
967 _RandomAccessIter __out_first, _RandomAccessIter __out_last,
968 _RandomNumberGenerator& __rand)
969 {
970 return __random_sample(__first, __last,
971 __out_first, __rand,
972 __out_last - __out_first);
973 }
974
975 // partition, stable_partition, and their auxiliary functions
976
977 template <class _ForwardIter, class _Predicate>
978 _ForwardIter __partition(_ForwardIter __first,
979 _ForwardIter __last,
980 _Predicate __pred,
981 forward_iterator_tag) {
982 if (__first == __last) return __first;
983
984 while (__pred(*__first))
985 if (++__first == __last) return __first;
986
987 _ForwardIter __next = __first;
988
989 while (++__next != __last)
990 if (__pred(*__next)) {
991 swap(*__first, *__next);
992 ++__first;
993 }
994
995 return __first;
996 }
997
998 template <class _BidirectionalIter, class _Predicate>
999 _BidirectionalIter __partition(_BidirectionalIter __first,
1000 _BidirectionalIter __last,
1001 _Predicate __pred,
1002 bidirectional_iterator_tag) {
1003 while (true) {
1004 while (true)
1005 if (__first == __last)
1006 return __first;
1007 else if (__pred(*__first))
1008 ++__first;
1009 else
1010 break;
1011 --__last;
1012 while (true)
1013 if (__first == __last)
1014 return __first;
1015 else if (!__pred(*__last))
1016 --__last;
1017 else
1018 break;
1019 iter_swap(__first, __last);
1020 ++__first;
1021 }
1022 }
1023
1024 template <class _ForwardIter, class _Predicate>
1025 inline _ForwardIter partition(_ForwardIter __first,
1026 _ForwardIter __last,
1027 _Predicate __pred) {
1028 return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
1029 }
1030
1031
1032 template <class _ForwardIter, class _Predicate, class _Distance>
1033 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
1034 _ForwardIter __last,
1035 _Predicate __pred, _Distance __len) {
1036 if (__len == 1)
1037 return __pred(*__first) ? __last : __first;
1038 _ForwardIter __middle = __first;
1039 advance(__middle, __len / 2);
1040 return rotate(__inplace_stable_partition(__first, __middle, __pred,
1041 __len / 2),
1042 __middle,
1043 __inplace_stable_partition(__middle, __last, __pred,
1044 __len - __len / 2));
1045 }
1046
1047 template <class _ForwardIter, class _Pointer, class _Predicate,
1048 class _Distance>
1049 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
1050 _ForwardIter __last,
1051 _Predicate __pred, _Distance __len,
1052 _Pointer __buffer,
1053 _Distance __buffer_size)
1054 {
1055 if (__len <= __buffer_size) {
1056 _ForwardIter __result1 = __first;
1057 _Pointer __result2 = __buffer;
1058 for ( ; __first != __last ; ++__first)
1059 if (__pred(*__first)) {
1060 *__result1 = *__first;
1061 ++__result1;
1062 }
1063 else {
1064 *__result2 = *__first;
1065 ++__result2;
1066 }
1067 copy(__buffer, __result2, __result1);
1068 return __result1;
1069 }
1070 else {
1071 _ForwardIter __middle = __first;
1072 advance(__middle, __len / 2);
1073 return rotate(__stable_partition_adaptive(
1074 __first, __middle, __pred,
1075 __len / 2, __buffer, __buffer_size),
1076 __middle,
1077 __stable_partition_adaptive(
1078 __middle, __last, __pred,
1079 __len - __len / 2, __buffer, __buffer_size));
1080 }
1081 }
1082
1083 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1084 inline _ForwardIter
1085 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
1086 _Predicate __pred, _Tp*, _Distance*)
1087 {
1088 _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1089 if (__buf.size() > 0)
1090 return __stable_partition_adaptive(__first, __last, __pred,
1091 _Distance(__buf.requested_size()),
1092 __buf.begin(), __buf.size());
1093 else
1094 return __inplace_stable_partition(__first, __last, __pred,
1095 _Distance(__buf.requested_size()));
1096 }
1097
1098 template <class _ForwardIter, class _Predicate>
1099 inline _ForwardIter stable_partition(_ForwardIter __first,
1100 _ForwardIter __last,
1101 _Predicate __pred) {
1102 if (__first == __last)
1103 return __first;
1104 else
1105 return __stable_partition_aux(__first, __last, __pred,
1106 __VALUE_TYPE(__first),
1107 __DISTANCE_TYPE(__first));
1108 }
1109
1110 template <class _RandomAccessIter, class _Tp>
1111 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1112 _RandomAccessIter __last,
1113 _Tp __pivot)
1114 {
1115 while (true) {
1116 while (*__first < __pivot)
1117 ++__first;
1118 --__last;
1119 while (__pivot < *__last)
1120 --__last;
1121 if (!(__first < __last))
1122 return __first;
1123 iter_swap(__first, __last);
1124 ++__first;
1125 }
1126 }
1127
1128 template <class _RandomAccessIter, class _Tp, class _Compare>
1129 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1130 _RandomAccessIter __last,
1131 _Tp __pivot, _Compare __comp)
1132 {
1133 while (true) {
1134 while (__comp(*__first, __pivot))
1135 ++__first;
1136 --__last;
1137 while (__comp(__pivot, *__last))
1138 --__last;
1139 if (!(__first < __last))
1140 return __first;
1141 iter_swap(__first, __last);
1142 ++__first;
1143 }
1144 }
1145
1146 const int __stl_threshold = 16;
1147
1148 // sort() and its auxiliary functions.
1149
1150 template <class _RandomAccessIter, class _Tp>
1151 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
1152 _RandomAccessIter __next = __last;
1153 --__next;
1154 while (__val < *__next) {
1155 *__last = *__next;
1156 __last = __next;
1157 --__next;
1158 }
1159 *__last = __val;
1160 }
1161
1162 template <class _RandomAccessIter, class _Tp, class _Compare>
1163 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
1164 _Compare __comp) {
1165 _RandomAccessIter __next = __last;
1166 --__next;
1167 while (__comp(__val, *__next)) {
1168 *__last = *__next;
1169 __last = __next;
1170 --__next;
1171 }
1172 *__last = __val;
1173 }
1174
1175 template <class _RandomAccessIter, class _Tp>
1176 inline void __linear_insert(_RandomAccessIter __first,
1177 _RandomAccessIter __last, _Tp*) {
1178 _Tp __val = *__last;
1179 if (__val < *__first) {
1180 copy_backward(__first, __last, __last + 1);
1181 *__first = __val;
1182 }
1183 else
1184 __unguarded_linear_insert(__last, __val);
1185 }
1186
1187 template <class _RandomAccessIter, class _Tp, class _Compare>
1188 inline void __linear_insert(_RandomAccessIter __first,
1189 _RandomAccessIter __last, _Tp*, _Compare __comp) {
1190 _Tp __val = *__last;
1191 if (__comp(__val, *__first)) {
1192 copy_backward(__first, __last, __last + 1);
1193 *__first = __val;
1194 }
1195 else
1196 __unguarded_linear_insert(__last, __val, __comp);
1197 }
1198
1199 template <class _RandomAccessIter>
1200 void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1201 if (__first == __last) return;
1202 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1203 __linear_insert(__first, __i, __VALUE_TYPE(__first));
1204 }
1205
1206 template <class _RandomAccessIter, class _Compare>
1207 void __insertion_sort(_RandomAccessIter __first,
1208 _RandomAccessIter __last, _Compare __comp) {
1209 if (__first == __last) return;
1210 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1211 __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
1212 }
1213
1214 template <class _RandomAccessIter, class _Tp>
1215 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1216 _RandomAccessIter __last, _Tp*) {
1217 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1218 __unguarded_linear_insert(__i, _Tp(*__i));
1219 }
1220
1221 template <class _RandomAccessIter>
1222 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1223 _RandomAccessIter __last) {
1224 __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
1225 }
1226
1227 template <class _RandomAccessIter, class _Tp, class _Compare>
1228 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1229 _RandomAccessIter __last,
1230 _Tp*, _Compare __comp) {
1231 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1232 __unguarded_linear_insert(__i, _Tp(*__i), __comp);
1233 }
1234
1235 template <class _RandomAccessIter, class _Compare>
1236 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1237 _RandomAccessIter __last,
1238 _Compare __comp) {
1239 __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
1240 __comp);
1241 }
1242
1243 template <class _RandomAccessIter>
1244 void __final_insertion_sort(_RandomAccessIter __first,
1245 _RandomAccessIter __last) {
1246 if (__last - __first > __stl_threshold) {
1247 __insertion_sort(__first, __first + __stl_threshold);
1248 __unguarded_insertion_sort(__first + __stl_threshold, __last);
1249 }
1250 else
1251 __insertion_sort(__first, __last);
1252 }
1253
1254 template <class _RandomAccessIter, class _Compare>
1255 void __final_insertion_sort(_RandomAccessIter __first,
1256 _RandomAccessIter __last, _Compare __comp) {
1257 if (__last - __first > __stl_threshold) {
1258 __insertion_sort(__first, __first + __stl_threshold, __comp);
1259 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
1260 }
1261 else
1262 __insertion_sort(__first, __last, __comp);
1263 }
1264
1265 template <class _Size>
1266 inline _Size __lg(_Size __n) {
1267 _Size __k;
1268 for (__k = 0; __n != 1; __n >>= 1) ++__k;
1269 return __k;
1270 }
1271
1272 template <class _RandomAccessIter, class _Tp, class _Size>
1273 void __introsort_loop(_RandomAccessIter __first,
1274 _RandomAccessIter __last, _Tp*,
1275 _Size __depth_limit)
1276 {
1277 while (__last - __first > __stl_threshold) {
1278 if (__depth_limit == 0) {
1279 partial_sort(__first, __last, __last);
1280 return;
1281 }
1282 --__depth_limit;
1283 _RandomAccessIter __cut =
1284 __unguarded_partition(__first, __last,
1285 _Tp(__median(*__first,
1286 *(__first + (__last - __first)/2),
1287 *(__last - 1))));
1288 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
1289 __last = __cut;
1290 }
1291 }
1292
1293 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
1294 void __introsort_loop(_RandomAccessIter __first,
1295 _RandomAccessIter __last, _Tp*,
1296 _Size __depth_limit, _Compare __comp)
1297 {
1298 while (__last - __first > __stl_threshold) {
1299 if (__depth_limit == 0) {
1300 partial_sort(__first, __last, __last, __comp);
1301 return;
1302 }
1303 --__depth_limit;
1304 _RandomAccessIter __cut =
1305 __unguarded_partition(__first, __last,
1306 _Tp(__median(*__first,
1307 *(__first + (__last - __first)/2),
1308 *(__last - 1), __comp)),
1309 __comp);
1310 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
1311 __last = __cut;
1312 }
1313 }
1314
1315 template <class _RandomAccessIter>
1316 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1317 if (__first != __last) {
1318 __introsort_loop(__first, __last,
1319 __VALUE_TYPE(__first),
1320 __lg(__last - __first) * 2);
1321 __final_insertion_sort(__first, __last);
1322 }
1323 }
1324
1325 template <class _RandomAccessIter, class _Compare>
1326 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
1327 _Compare __comp) {
1328 if (__first != __last) {
1329 __introsort_loop(__first, __last,
1330 __VALUE_TYPE(__first),
1331 __lg(__last - __first) * 2,
1332 __comp);
1333 __final_insertion_sort(__first, __last, __comp);
1334 }
1335 }
1336
1337 // stable_sort() and its auxiliary functions.
1338
1339 template <class _RandomAccessIter>
1340 void __inplace_stable_sort(_RandomAccessIter __first,
1341 _RandomAccessIter __last) {
1342 if (__last - __first < 15) {
1343 __insertion_sort(__first, __last);
1344 return;
1345 }
1346 _RandomAccessIter __middle = __first + (__last - __first) / 2;
1347 __inplace_stable_sort(__first, __middle);
1348 __inplace_stable_sort(__middle, __last);
1349 __merge_without_buffer(__first, __middle, __last,
1350 __middle - __first,
1351 __last - __middle);
1352 }
1353
1354 template <class _RandomAccessIter, class _Compare>
1355 void __inplace_stable_sort(_RandomAccessIter __first,
1356 _RandomAccessIter __last, _Compare __comp) {
1357 if (__last - __first < 15) {
1358 __insertion_sort(__first, __last, __comp);
1359 return;
1360 }
1361 _RandomAccessIter __middle = __first + (__last - __first) / 2;
1362 __inplace_stable_sort(__first, __middle, __comp);
1363 __inplace_stable_sort(__middle, __last, __comp);
1364 __merge_without_buffer(__first, __middle, __last,
1365 __middle - __first,
1366 __last - __middle,
1367 __comp);
1368 }
1369
1370 template <class _RandomAccessIter1, class _RandomAccessIter2,
1371 class _Distance>
1372 void __merge_sort_loop(_RandomAccessIter1 __first,
1373 _RandomAccessIter1 __last,
1374 _RandomAccessIter2 __result, _Distance __step_size) {
1375 _Distance __two_step = 2 * __step_size;
1376
1377 while (__last - __first >= __two_step) {
1378 __result = merge(__first, __first + __step_size,
1379 __first + __step_size, __first + __two_step,
1380 __result);
1381 __first += __two_step;
1382 }
1383
1384 __step_size = min(_Distance(__last - __first), __step_size);
1385 merge(__first, __first + __step_size, __first + __step_size, __last,
1386 __result);
1387 }
1388
1389 template <class _RandomAccessIter1, class _RandomAccessIter2,
1390 class _Distance, class _Compare>
1391 void __merge_sort_loop(_RandomAccessIter1 __first,
1392 _RandomAccessIter1 __last,
1393 _RandomAccessIter2 __result, _Distance __step_size,
1394 _Compare __comp) {
1395 _Distance __two_step = 2 * __step_size;
1396
1397 while (__last - __first >= __two_step) {
1398 __result = merge(__first, __first + __step_size,
1399 __first + __step_size, __first + __two_step,
1400 __result,
1401 __comp);
1402 __first += __two_step;
1403 }
1404 __step_size = min(_Distance(__last - __first), __step_size);
1405
1406 merge(__first, __first + __step_size,
1407 __first + __step_size, __last,
1408 __result,
1409 __comp);
1410 }
1411
1412 const int __stl_chunk_size = 7;
1413
1414 template <class _RandomAccessIter, class _Distance>
1415 void __chunk_insertion_sort(_RandomAccessIter __first,
1416 _RandomAccessIter __last, _Distance __chunk_size)
1417 {
1418 while (__last - __first >= __chunk_size) {
1419 __insertion_sort(__first, __first + __chunk_size);
1420 __first += __chunk_size;
1421 }
1422 __insertion_sort(__first, __last);
1423 }
1424
1425 template <class _RandomAccessIter, class _Distance, class _Compare>
1426 void __chunk_insertion_sort(_RandomAccessIter __first,
1427 _RandomAccessIter __last,
1428 _Distance __chunk_size, _Compare __comp)
1429 {
1430 while (__last - __first >= __chunk_size) {
1431 __insertion_sort(__first, __first + __chunk_size, __comp);
1432 __first += __chunk_size;
1433 }
1434 __insertion_sort(__first, __last, __comp);
1435 }
1436
1437 template <class _RandomAccessIter, class _Pointer, class _Distance>
1438 void __merge_sort_with_buffer(_RandomAccessIter __first,
1439 _RandomAccessIter __last,
1440 _Pointer __buffer, _Distance*) {
1441 _Distance __len = __last - __first;
1442 _Pointer __buffer_last = __buffer + __len;
1443
1444 _Distance __step_size = __stl_chunk_size;
1445 __chunk_insertion_sort(__first, __last, __step_size);
1446
1447 while (__step_size < __len) {
1448 __merge_sort_loop(__first, __last, __buffer, __step_size);
1449 __step_size *= 2;
1450 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
1451 __step_size *= 2;
1452 }
1453 }
1454
1455 template <class _RandomAccessIter, class _Pointer, class _Distance,
1456 class _Compare>
1457 void __merge_sort_with_buffer(_RandomAccessIter __first,
1458 _RandomAccessIter __last, _Pointer __buffer,
1459 _Distance*, _Compare __comp) {
1460 _Distance __len = __last - __first;
1461 _Pointer __buffer_last = __buffer + __len;
1462
1463 _Distance __step_size = __stl_chunk_size;
1464 __chunk_insertion_sort(__first, __last, __step_size, __comp);
1465
1466 while (__step_size < __len) {
1467 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
1468 __step_size *= 2;
1469 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
1470 __step_size *= 2;
1471 }
1472 }
1473
1474 template <class _RandomAccessIter, class _Pointer, class _Distance>
1475 void __stable_sort_adaptive(_RandomAccessIter __first,
1476 _RandomAccessIter __last, _Pointer __buffer,
1477 _Distance __buffer_size) {
1478 _Distance __len = (__last - __first + 1) / 2;
1479 _RandomAccessIter __middle = __first + __len;
1480 if (__len > __buffer_size) {
1481 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
1482 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
1483 }
1484 else {
1485 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
1486 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
1487 }
1488 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1489 _Distance(__last - __middle), __buffer, __buffer_size);
1490 }
1491
1492 template <class _RandomAccessIter, class _Pointer, class _Distance,
1493 class _Compare>
1494 void __stable_sort_adaptive(_RandomAccessIter __first,
1495 _RandomAccessIter __last, _Pointer __buffer,
1496 _Distance __buffer_size, _Compare __comp) {
1497 _Distance __len = (__last - __first + 1) / 2;
1498 _RandomAccessIter __middle = __first + __len;
1499 if (__len > __buffer_size) {
1500 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1501 __comp);
1502 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1503 __comp);
1504 }
1505 else {
1506 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
1507 __comp);
1508 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
1509 __comp);
1510 }
1511 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1512 _Distance(__last - __middle), __buffer, __buffer_size,
1513 __comp);
1514 }
1515
1516 template <class _RandomAccessIter, class _Tp, class _Distance>
1517 inline void __stable_sort_aux(_RandomAccessIter __first,
1518 _RandomAccessIter __last, _Tp*, _Distance*) {
1519 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1520 if (buf.begin() == 0)
1521 __inplace_stable_sort(__first, __last);
1522 else
1523 __stable_sort_adaptive(__first, __last, buf.begin(),
1524 _Distance(buf.size()));
1525 }
1526
1527 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
1528 inline void __stable_sort_aux(_RandomAccessIter __first,
1529 _RandomAccessIter __last, _Tp*, _Distance*,
1530 _Compare __comp) {
1531 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1532 if (buf.begin() == 0)
1533 __inplace_stable_sort(__first, __last, __comp);
1534 else
1535 __stable_sort_adaptive(__first, __last, buf.begin(),
1536 _Distance(buf.size()),
1537 __comp);
1538 }
1539
1540 template <class _RandomAccessIter>
1541 inline void stable_sort(_RandomAccessIter __first,
1542 _RandomAccessIter __last) {
1543 __stable_sort_aux(__first, __last,
1544 __VALUE_TYPE(__first),
1545 __DISTANCE_TYPE(__first));
1546 }
1547
1548 template <class _RandomAccessIter, class _Compare>
1549 inline void stable_sort(_RandomAccessIter __first,
1550 _RandomAccessIter __last, _Compare __comp) {
1551 __stable_sort_aux(__first, __last,
1552 __VALUE_TYPE(__first),
1553 __DISTANCE_TYPE(__first),
1554 __comp);
1555 }
1556
1557 // partial_sort, partial_sort_copy, and auxiliary functions.
1558
1559 template <class _RandomAccessIter, class _Tp>
1560 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1561 _RandomAccessIter __last, _Tp*) {
1562 make_heap(__first, __middle);
1563 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1564 if (*__i < *__first)
1565 __pop_heap(__first, __middle, __i, _Tp(*__i),
1566 __DISTANCE_TYPE(__first));
1567 sort_heap(__first, __middle);
1568 }
1569
1570 template <class _RandomAccessIter>
1571 inline void partial_sort(_RandomAccessIter __first,
1572 _RandomAccessIter __middle,
1573 _RandomAccessIter __last) {
1574 __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
1575 }
1576
1577 template <class _RandomAccessIter, class _Tp, class _Compare>
1578 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1579 _RandomAccessIter __last, _Tp*, _Compare __comp) {
1580 make_heap(__first, __middle, __comp);
1581 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1582 if (__comp(*__i, *__first))
1583 __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
1584 __DISTANCE_TYPE(__first));
1585 sort_heap(__first, __middle, __comp);
1586 }
1587
1588 template <class _RandomAccessIter, class _Compare>
1589 inline void partial_sort(_RandomAccessIter __first,
1590 _RandomAccessIter __middle,
1591 _RandomAccessIter __last, _Compare __comp) {
1592 __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
1593 }
1594
1595 template <class _InputIter, class _RandomAccessIter, class _Distance,
1596 class _Tp>
1597 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1598 _InputIter __last,
1599 _RandomAccessIter __result_first,
1600 _RandomAccessIter __result_last,
1601 _Distance*, _Tp*) {
1602 if (__result_first == __result_last) return __result_last;
1603 _RandomAccessIter __result_real_last = __result_first;
1604 while(__first != __last && __result_real_last != __result_last) {
1605 *__result_real_last = *__first;
1606 ++__result_real_last;
1607 ++__first;
1608 }
1609 make_heap(__result_first, __result_real_last);
1610 while (__first != __last) {
1611 if (*__first < *__result_first)
1612 __adjust_heap(__result_first, _Distance(0),
1613 _Distance(__result_real_last - __result_first),
1614 _Tp(*__first));
1615 ++__first;
1616 }
1617 sort_heap(__result_first, __result_real_last);
1618 return __result_real_last;
1619 }
1620
1621 template <class _InputIter, class _RandomAccessIter>
1622 inline _RandomAccessIter
1623 partial_sort_copy(_InputIter __first, _InputIter __last,
1624 _RandomAccessIter __result_first,
1625 _RandomAccessIter __result_last) {
1626 return __partial_sort_copy(__first, __last, __result_first, __result_last,
1627 __DISTANCE_TYPE(__result_first),
1628 __VALUE_TYPE(__first));
1629 }
1630
1631 template <class _InputIter, class _RandomAccessIter, class _Compare,
1632 class _Distance, class _Tp>
1633 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1634 _InputIter __last,
1635 _RandomAccessIter __result_first,
1636 _RandomAccessIter __result_last,
1637 _Compare __comp, _Distance*, _Tp*) {
1638 if (__result_first == __result_last) return __result_last;
1639 _RandomAccessIter __result_real_last = __result_first;
1640 while(__first != __last && __result_real_last != __result_last) {
1641 *__result_real_last = *__first;
1642 ++__result_real_last;
1643 ++__first;
1644 }
1645 make_heap(__result_first, __result_real_last, __comp);
1646 while (__first != __last) {
1647 if (__comp(*__first, *__result_first))
1648 __adjust_heap(__result_first, _Distance(0),
1649 _Distance(__result_real_last - __result_first),
1650 _Tp(*__first),
1651 __comp);
1652 ++__first;
1653 }
1654 sort_heap(__result_first, __result_real_last, __comp);
1655 return __result_real_last;
1656 }
1657
1658 template <class _InputIter, class _RandomAccessIter, class _Compare>
1659 inline _RandomAccessIter
1660 partial_sort_copy(_InputIter __first, _InputIter __last,
1661 _RandomAccessIter __result_first,
1662 _RandomAccessIter __result_last, _Compare __comp) {
1663 return __partial_sort_copy(__first, __last, __result_first, __result_last,
1664 __comp,
1665 __DISTANCE_TYPE(__result_first),
1666 __VALUE_TYPE(__first));
1667 }
1668
1669 // nth_element() and its auxiliary functions.
1670
1671 template <class _RandomAccessIter, class _Tp>
1672 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1673 _RandomAccessIter __last, _Tp*) {
1674 while (__last - __first > 3) {
1675 _RandomAccessIter __cut =
1676 __unguarded_partition(__first, __last,
1677 _Tp(__median(*__first,
1678 *(__first + (__last - __first)/2),
1679 *(__last - 1))));
1680 if (__cut <= __nth)
1681 __first = __cut;
1682 else
1683 __last = __cut;
1684 }
1685 __insertion_sort(__first, __last);
1686 }
1687
1688 template <class _RandomAccessIter>
1689 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1690 _RandomAccessIter __last) {
1691 __nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
1692 }
1693
1694 template <class _RandomAccessIter, class _Tp, class _Compare>
1695 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1696 _RandomAccessIter __last, _Tp*, _Compare __comp) {
1697 while (__last - __first > 3) {
1698 _RandomAccessIter __cut =
1699 __unguarded_partition(__first, __last,
1700 _Tp(__median(*__first,
1701 *(__first + (__last - __first)/2),
1702 *(__last - 1),
1703 __comp)),
1704 __comp);
1705 if (__cut <= __nth)
1706 __first = __cut;
1707 else
1708 __last = __cut;
1709 }
1710 __insertion_sort(__first, __last, __comp);
1711 }
1712
1713 template <class _RandomAccessIter, class _Compare>
1714 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1715 _RandomAccessIter __last, _Compare __comp) {
1716 __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp);
1717 }
1718
1719
1720 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1721
1722 template <class _ForwardIter, class _Tp, class _Distance>
1723 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
1724 const _Tp& __val, _Distance*)
1725 {
1726 _Distance __len = 0;
1727 distance(__first, __last, __len);
1728 _Distance __half;
1729 _ForwardIter __middle;
1730
1731 while (__len > 0) {
1732 __half = __len >> 1;
1733 __middle = __first;
1734 advance(__middle, __half);
1735 if (*__middle < __val) {
1736 __first = __middle;
1737 ++__first;
1738 __len = __len - __half - 1;
1739 }
1740 else
1741 __len = __half;
1742 }
1743 return __first;
1744 }
1745
1746 template <class _ForwardIter, class _Tp>
1747 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1748 const _Tp& __val) {
1749 return __lower_bound(__first, __last, __val,
1750 __DISTANCE_TYPE(__first));
1751 }
1752
1753 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1754 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
1755 const _Tp& __val, _Compare __comp, _Distance*)
1756 {
1757 _Distance __len = 0;
1758 distance(__first, __last, __len);
1759 _Distance __half;
1760 _ForwardIter __middle;
1761
1762 while (__len > 0) {
1763 __half = __len >> 1;
1764 __middle = __first;
1765 advance(__middle, __half);
1766 if (__comp(*__middle, __val)) {
1767 __first = __middle;
1768 ++__first;
1769 __len = __len - __half - 1;
1770 }
1771 else
1772 __len = __half;
1773 }
1774 return __first;
1775 }
1776
1777 template <class _ForwardIter, class _Tp, class _Compare>
1778 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1779 const _Tp& __val, _Compare __comp) {
1780 return __lower_bound(__first, __last, __val, __comp,
1781 __DISTANCE_TYPE(__first));
1782 }
1783
1784 template <class _ForwardIter, class _Tp, class _Distance>
1785 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1786 const _Tp& __val, _Distance*)
1787 {
1788 _Distance __len = 0;
1789 distance(__first, __last, __len);
1790 _Distance __half;
1791 _ForwardIter __middle;
1792
1793 while (__len > 0) {
1794 __half = __len >> 1;
1795 __middle = __first;
1796 advance(__middle, __half);
1797 if (__val < *__middle)
1798 __len = __half;
1799 else {
1800 __first = __middle;
1801 ++__first;
1802 __len = __len - __half - 1;
1803 }
1804 }
1805 return __first;
1806 }
1807
1808 template <class _ForwardIter, class _Tp>
1809 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1810 const _Tp& __val) {
1811 return __upper_bound(__first, __last, __val,
1812 __DISTANCE_TYPE(__first));
1813 }
1814
1815 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1816 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1817 const _Tp& __val, _Compare __comp, _Distance*)
1818 {
1819 _Distance __len = 0;
1820 distance(__first, __last, __len);
1821 _Distance __half;
1822 _ForwardIter __middle;
1823
1824 while (__len > 0) {
1825 __half = __len >> 1;
1826 __middle = __first;
1827 advance(__middle, __half);
1828 if (__comp(__val, *__middle))
1829 __len = __half;
1830 else {
1831 __first = __middle;
1832 ++__first;
1833 __len = __len - __half - 1;
1834 }
1835 }
1836 return __first;
1837 }
1838
1839 template <class _ForwardIter, class _Tp, class _Compare>
1840 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1841 const _Tp& __val, _Compare __comp) {
1842 return __upper_bound(__first, __last, __val, __comp,
1843 __DISTANCE_TYPE(__first));
1844 }
1845
1846 template <class _ForwardIter, class _Tp, class _Distance>
1847 pair<_ForwardIter, _ForwardIter>
1848 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1849 _Distance*)
1850 {
1851 _Distance __len = 0;
1852 distance(__first, __last, __len);
1853 _Distance __half;
1854 _ForwardIter __middle, __left, __right;
1855
1856 while (__len > 0) {
1857 __half = __len >> 1;
1858 __middle = __first;
1859 advance(__middle, __half);
1860 if (*__middle < __val) {
1861 __first = __middle;
1862 ++__first;
1863 __len = __len - __half - 1;
1864 }
1865 else if (__val < *__middle)
1866 __len = __half;
1867 else {
1868 __left = lower_bound(__first, __middle, __val);
1869 advance(__first, __len);
1870 __right = upper_bound(++__middle, __first, __val);
1871 return pair<_ForwardIter, _ForwardIter>(__left, __right);
1872 }
1873 }
1874 return pair<_ForwardIter, _ForwardIter>(__first, __first);
1875 }
1876
1877 template <class _ForwardIter, class _Tp>
1878 inline pair<_ForwardIter, _ForwardIter>
1879 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
1880 return __equal_range(__first, __last, __val,
1881 __DISTANCE_TYPE(__first));
1882 }
1883
1884 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1885 pair<_ForwardIter, _ForwardIter>
1886 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1887 _Compare __comp, _Distance*)
1888 {
1889 _Distance __len = 0;
1890 distance(__first, __last, __len);
1891 _Distance __half;
1892 _ForwardIter __middle, __left, __right;
1893
1894 while (__len > 0) {
1895 __half = __len >> 1;
1896 __middle = __first;
1897 advance(__middle, __half);
1898 if (__comp(*__middle, __val)) {
1899 __first = __middle;
1900 ++__first;
1901 __len = __len - __half - 1;
1902 }
1903 else if (__comp(__val, *__middle))
1904 __len = __half;
1905 else {
1906 __left = lower_bound(__first, __middle, __val, __comp);
1907 advance(__first, __len);
1908 __right = upper_bound(++__middle, __first, __val, __comp);
1909 return pair<_ForwardIter, _ForwardIter>(__left, __right);
1910 }
1911 }
1912 return pair<_ForwardIter, _ForwardIter>(__first, __first);
1913 }
1914
1915 template <class _ForwardIter, class _Tp, class _Compare>
1916 inline pair<_ForwardIter, _ForwardIter>
1917 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1918 _Compare __comp) {
1919 return __equal_range(__first, __last, __val, __comp,
1920 __DISTANCE_TYPE(__first));
1921 }
1922
1923 template <class _ForwardIter, class _Tp>
1924 bool binary_search(_ForwardIter __first, _ForwardIter __last,
1925 const _Tp& __val) {
1926 _ForwardIter __i = lower_bound(__first, __last, __val);
1927 return __i != __last && !(__val < *__i);
1928 }
1929
1930 template <class _ForwardIter, class _Tp, class _Compare>
1931 bool binary_search(_ForwardIter __first, _ForwardIter __last,
1932 const _Tp& __val,
1933 _Compare __comp) {
1934 _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
1935 return __i != __last && !__comp(__val, *__i);
1936 }
1937
1938 // merge, with and without an explicitly supplied comparison function.
1939
1940 template <class _InputIter1, class _InputIter2, class _OutputIter>
1941 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1942 _InputIter2 __first2, _InputIter2 __last2,
1943 _OutputIter __result) {
1944 while (__first1 != __last1 && __first2 != __last2) {
1945 if (*__first2 < *__first1) {
1946 *__result = *__first2;
1947 ++__first2;
1948 }
1949 else {
1950 *__result = *__first1;
1951 ++__first1;
1952 }
1953 ++__result;
1954 }
1955 return copy(__first2, __last2, copy(__first1, __last1, __result));
1956 }
1957
1958 template <class _InputIter1, class _InputIter2, class _OutputIter,
1959 class _Compare>
1960 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1961 _InputIter2 __first2, _InputIter2 __last2,
1962 _OutputIter __result, _Compare __comp) {
1963 while (__first1 != __last1 && __first2 != __last2) {
1964 if (__comp(*__first2, *__first1)) {
1965 *__result = *__first2;
1966 ++__first2;
1967 }
1968 else {
1969 *__result = *__first1;
1970 ++__first1;
1971 }
1972 ++__result;
1973 }
1974 return copy(__first2, __last2, copy(__first1, __last1, __result));
1975 }
1976
1977 // inplace_merge and its auxiliary functions.
1978
1979 template <class _BidirectionalIter, class _Distance>
1980 void __merge_without_buffer(_BidirectionalIter __first,
1981 _BidirectionalIter __middle,
1982 _BidirectionalIter __last,
1983 _Distance __len1, _Distance __len2) {
1984 if (__len1 == 0 || __len2 == 0)
1985 return;
1986 if (__len1 + __len2 == 2) {
1987 if (*__middle < *__first)
1988 iter_swap(__first, __middle);
1989 return;
1990 }
1991 _BidirectionalIter __first_cut = __first;
1992 _BidirectionalIter __second_cut = __middle;
1993 _Distance __len11 = 0;
1994 _Distance __len22 = 0;
1995 if (__len1 > __len2) {
1996 __len11 = __len1 / 2;
1997 advance(__first_cut, __len11);
1998 __second_cut = lower_bound(__middle, __last, *__first_cut);
1999 distance(__middle, __second_cut, __len22);
2000 }
2001 else {
2002 __len22 = __len2 / 2;
2003 advance(__second_cut, __len22);
2004 __first_cut = upper_bound(__first, __middle, *__second_cut);
2005 distance(__first, __first_cut, __len11);
2006 }
2007 _BidirectionalIter __new_middle
2008 = rotate(__first_cut, __middle, __second_cut);
2009 __merge_without_buffer(__first, __first_cut, __new_middle,
2010 __len11, __len22);
2011 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
2012 __len2 - __len22);
2013 }
2014
2015 template <class _BidirectionalIter, class _Distance, class _Compare>
2016 void __merge_without_buffer(_BidirectionalIter __first,
2017 _BidirectionalIter __middle,
2018 _BidirectionalIter __last,
2019 _Distance __len1, _Distance __len2,
2020 _Compare __comp) {
2021 if (__len1 == 0 || __len2 == 0)
2022 return;
2023 if (__len1 + __len2 == 2) {
2024 if (__comp(*__middle, *__first))
2025 iter_swap(__first, __middle);
2026 return;
2027 }
2028 _BidirectionalIter __first_cut = __first;
2029 _BidirectionalIter __second_cut = __middle;
2030 _Distance __len11 = 0;
2031 _Distance __len22 = 0;
2032 if (__len1 > __len2) {
2033 __len11 = __len1 / 2;
2034 advance(__first_cut, __len11);
2035 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2036 distance(__middle, __second_cut, __len22);
2037 }
2038 else {
2039 __len22 = __len2 / 2;
2040 advance(__second_cut, __len22);
2041 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2042 distance(__first, __first_cut, __len11);
2043 }
2044 _BidirectionalIter __new_middle
2045 = rotate(__first_cut, __middle, __second_cut);
2046 __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
2047 __comp);
2048 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
2049 __len2 - __len22, __comp);
2050 }
2051
2052 template <class _BidirectionalIter1, class _BidirectionalIter2,
2053 class _Distance>
2054 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
2055 _BidirectionalIter1 __middle,
2056 _BidirectionalIter1 __last,
2057 _Distance __len1, _Distance __len2,
2058 _BidirectionalIter2 __buffer,
2059 _Distance __buffer_size) {
2060 _BidirectionalIter2 __buffer_end;
2061 if (__len1 > __len2 && __len2 <= __buffer_size) {
2062 __buffer_end = copy(__middle, __last, __buffer);
2063 copy_backward(__first, __middle, __last);
2064 return copy(__buffer, __buffer_end, __first);
2065 }
2066 else if (__len1 <= __buffer_size) {
2067 __buffer_end = copy(__first, __middle, __buffer);
2068 copy(__middle, __last, __first);
2069 return copy_backward(__buffer, __buffer_end, __last);
2070 }
2071 else
2072 return rotate(__first, __middle, __last);
2073 }
2074
2075 template <class _BidirectionalIter1, class _BidirectionalIter2,
2076 class _BidirectionalIter3>
2077 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
2078 _BidirectionalIter1 __last1,
2079 _BidirectionalIter2 __first2,
2080 _BidirectionalIter2 __last2,
2081 _BidirectionalIter3 __result) {
2082 if (__first1 == __last1)
2083 return copy_backward(__first2, __last2, __result);
2084 if (__first2 == __last2)
2085 return copy_backward(__first1, __last1, __result);
2086 --__last1;
2087 --__last2;
2088 while (true) {
2089 if (*__last2 < *__last1) {
2090 *--__result = *__last1;
2091 if (__first1 == __last1)
2092 return copy_backward(__first2, ++__last2, __result);
2093 --__last1;
2094 }
2095 else {
2096 *--__result = *__last2;
2097 if (__first2 == __last2)
2098 return copy_backward(__first1, ++__last1, __result);
2099 --__last2;
2100 }
2101 }
2102 }
2103
2104 template <class _BidirectionalIter1, class _BidirectionalIter2,
2105 class _BidirectionalIter3, class _Compare>
2106 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
2107 _BidirectionalIter1 __last1,
2108 _BidirectionalIter2 __first2,
2109 _BidirectionalIter2 __last2,
2110 _BidirectionalIter3 __result,
2111 _Compare __comp) {
2112 if (__first1 == __last1)
2113 return copy_backward(__first2, __last2, __result);
2114 if (__first2 == __last2)
2115 return copy_backward(__first1, __last1, __result);
2116 --__last1;
2117 --__last2;
2118 while (true) {
2119 if (__comp(*__last2, *__last1)) {
2120 *--__result = *__last1;
2121 if (__first1 == __last1)
2122 return copy_backward(__first2, ++__last2, __result);
2123 --__last1;
2124 }
2125 else {
2126 *--__result = *__last2;
2127 if (__first2 == __last2)
2128 return copy_backward(__first1, ++__last1, __result);
2129 --__last2;
2130 }
2131 }
2132 }
2133
2134 template <class _BidirectionalIter, class _Distance, class _Pointer>
2135 void __merge_adaptive(_BidirectionalIter __first,
2136 _BidirectionalIter __middle,
2137 _BidirectionalIter __last,
2138 _Distance __len1, _Distance __len2,
2139 _Pointer __buffer, _Distance __buffer_size) {
2140 if (__len1 <= __len2 && __len1 <= __buffer_size) {
2141 _Pointer __buffer_end = copy(__first, __middle, __buffer);
2142 merge(__buffer, __buffer_end, __middle, __last, __first);
2143 }
2144 else if (__len2 <= __buffer_size) {
2145 _Pointer __buffer_end = copy(__middle, __last, __buffer);
2146 __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
2147 }
2148 else {
2149 _BidirectionalIter __first_cut = __first;
2150 _BidirectionalIter __second_cut = __middle;
2151 _Distance __len11 = 0;
2152 _Distance __len22 = 0;
2153 if (__len1 > __len2) {
2154 __len11 = __len1 / 2;
2155 advance(__first_cut, __len11);
2156 __second_cut = lower_bound(__middle, __last, *__first_cut);
2157 distance(__middle, __second_cut, __len22);
2158 }
2159 else {
2160 __len22 = __len2 / 2;
2161 advance(__second_cut, __len22);
2162 __first_cut = upper_bound(__first, __middle, *__second_cut);
2163 distance(__first, __first_cut, __len11);
2164 }
2165 _BidirectionalIter __new_middle =
2166 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
2167 __len22, __buffer, __buffer_size);
2168 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2169 __len22, __buffer, __buffer_size);
2170 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2171 __len2 - __len22, __buffer, __buffer_size);
2172 }
2173 }
2174
2175 template <class _BidirectionalIter, class _Distance, class _Pointer,
2176 class _Compare>
2177 void __merge_adaptive(_BidirectionalIter __first,
2178 _BidirectionalIter __middle,
2179 _BidirectionalIter __last,
2180 _Distance __len1, _Distance __len2,
2181 _Pointer __buffer, _Distance __buffer_size,
2182 _Compare __comp) {
2183 if (__len1 <= __len2 && __len1 <= __buffer_size) {
2184 _Pointer __buffer_end = copy(__first, __middle, __buffer);
2185 merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
2186 }
2187 else if (__len2 <= __buffer_size) {
2188 _Pointer __buffer_end = copy(__middle, __last, __buffer);
2189 __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
2190 __comp);
2191 }
2192 else {
2193 _BidirectionalIter __first_cut = __first;
2194 _BidirectionalIter __second_cut = __middle;
2195 _Distance __len11 = 0;
2196 _Distance __len22 = 0;
2197 if (__len1 > __len2) {
2198 __len11 = __len1 / 2;
2199 advance(__first_cut, __len11);
2200 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2201 distance(__middle, __second_cut, __len22);
2202 }
2203 else {
2204 __len22 = __len2 / 2;
2205 advance(__second_cut, __len22);
2206 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2207 distance(__first, __first_cut, __len11);
2208 }
2209 _BidirectionalIter __new_middle =
2210 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
2211 __len22, __buffer, __buffer_size);
2212 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2213 __len22, __buffer, __buffer_size, __comp);
2214 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2215 __len2 - __len22, __buffer, __buffer_size, __comp);
2216 }
2217 }
2218
2219 template <class _BidirectionalIter, class _Tp, class _Distance>
2220 inline void __inplace_merge_aux(_BidirectionalIter __first,
2221 _BidirectionalIter __middle,
2222 _BidirectionalIter __last, _Tp*, _Distance*) {
2223 _Distance __len1 = 0;
2224 distance(__first, __middle, __len1);
2225 _Distance __len2 = 0;
2226 distance(__middle, __last, __len2);
2227
2228 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
2229 if (__buf.begin() == 0)
2230 __merge_without_buffer(__first, __middle, __last, __len1, __len2);
2231 else
2232 __merge_adaptive(__first, __middle, __last, __len1, __len2,
2233 __buf.begin(), _Distance(__buf.size()));
2234 }
2235
2236 template <class _BidirectionalIter, class _Tp,
2237 class _Distance, class _Compare>
2238 inline void __inplace_merge_aux(_BidirectionalIter __first,
2239 _BidirectionalIter __middle,
2240 _BidirectionalIter __last, _Tp*, _Distance*,
2241 _Compare __comp) {
2242 _Distance __len1 = 0;
2243 distance(__first, __middle, __len1);
2244 _Distance __len2 = 0;
2245 distance(__middle, __last, __len2);
2246
2247 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
2248 if (__buf.begin() == 0)
2249 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
2250 else
2251 __merge_adaptive(__first, __middle, __last, __len1, __len2,
2252 __buf.begin(), _Distance(__buf.size()),
2253 __comp);
2254 }
2255
2256 template <class _BidirectionalIter>
2257 inline void inplace_merge(_BidirectionalIter __first,
2258 _BidirectionalIter __middle,
2259 _BidirectionalIter __last) {
2260 if (__first == __middle || __middle == __last)
2261 return;
2262 __inplace_merge_aux(__first, __middle, __last,
2263 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
2264 }
2265
2266 template <class _BidirectionalIter, class _Compare>
2267 inline void inplace_merge(_BidirectionalIter __first,
2268 _BidirectionalIter __middle,
2269 _BidirectionalIter __last, _Compare __comp) {
2270 if (__first == __middle || __middle == __last)
2271 return;
2272 __inplace_merge_aux(__first, __middle, __last,
2273 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first),
2274 __comp);
2275 }
2276
2277 // Set algorithms: includes, set_union, set_intersection, set_difference,
2278 // set_symmetric_difference. All of these algorithms have the precondition
2279 // that their input ranges are sorted and the postcondition that their output
2280 // ranges are sorted.
2281
2282 template <class _InputIter1, class _InputIter2>
2283 bool includes(_InputIter1 __first1, _InputIter1 __last1,
2284 _InputIter2 __first2, _InputIter2 __last2) {
2285 while (__first1 != __last1 && __first2 != __last2)
2286 if (*__first2 < *__first1)
2287 return false;
2288 else if(*__first1 < *__first2)
2289 ++__first1;
2290 else
2291 ++__first1, ++__first2;
2292
2293 return __first2 == __last2;
2294 }
2295
2296 template <class _InputIter1, class _InputIter2, class _Compare>
2297 bool includes(_InputIter1 __first1, _InputIter1 __last1,
2298 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
2299 while (__first1 != __last1 && __first2 != __last2)
2300 if (__comp(*__first2, *__first1))
2301 return false;
2302 else if(__comp(*__first1, *__first2))
2303 ++__first1;
2304 else
2305 ++__first1, ++__first2;
2306
2307 return __first2 == __last2;
2308 }
2309
2310 template <class _InputIter1, class _InputIter2, class _OutputIter>
2311 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
2312 _InputIter2 __first2, _InputIter2 __last2,
2313 _OutputIter __result) {
2314 while (__first1 != __last1 && __first2 != __last2) {
2315 if (*__first1 < *__first2) {
2316 *__result = *__first1;
2317 ++__first1;
2318 }
2319 else if (*__first2 < *__first1) {
2320 *__result = *__first2;
2321 ++__first2;
2322 }
2323 else {
2324 *__result = *__first1;
2325 ++__first1;
2326 ++__first2;
2327 }
2328 ++__result;
2329 }
2330 return copy(__first2, __last2, copy(__first1, __last1, __result));
2331 }
2332
2333 template <class _InputIter1, class _InputIter2, class _OutputIter,
2334 class _Compare>
2335 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
2336 _InputIter2 __first2, _InputIter2 __last2,
2337 _OutputIter __result, _Compare __comp) {
2338 while (__first1 != __last1 && __first2 != __last2) {
2339 if (__comp(*__first1, *__first2)) {
2340 *__result = *__first1;
2341 ++__first1;
2342 }
2343 else if (__comp(*__first2, *__first1)) {
2344 *__result = *__first2;
2345 ++__first2;
2346 }
2347 else {
2348 *__result = *__first1;
2349 ++__first1;
2350 ++__first2;
2351 }
2352 ++__result;
2353 }
2354 return copy(__first2, __last2, copy(__first1, __last1, __result));
2355 }
2356
2357 template <class _InputIter1, class _InputIter2, class _OutputIter>
2358 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
2359 _InputIter2 __first2, _InputIter2 __last2,
2360 _OutputIter __result) {
2361 while (__first1 != __last1 && __first2 != __last2)
2362 if (*__first1 < *__first2)
2363 ++__first1;
2364 else if (*__first2 < *__first1)
2365 ++__first2;
2366 else {
2367 *__result = *__first1;
2368 ++__first1;
2369 ++__first2;
2370 ++__result;
2371 }
2372 return __result;
2373 }
2374
2375 template <class _InputIter1, class _InputIter2, class _OutputIter,
2376 class _Compare>
2377 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
2378 _InputIter2 __first2, _InputIter2 __last2,
2379 _OutputIter __result, _Compare __comp) {
2380 while (__first1 != __last1 && __first2 != __last2)
2381 if (__comp(*__first1, *__first2))
2382 ++__first1;
2383 else if (__comp(*__first2, *__first1))
2384 ++__first2;
2385 else {
2386 *__result = *__first1;
2387 ++__first1;
2388 ++__first2;
2389 ++__result;
2390 }
2391 return __result;
2392 }
2393
2394 template <class _InputIter1, class _InputIter2, class _OutputIter>
2395 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
2396 _InputIter2 __first2, _InputIter2 __last2,
2397 _OutputIter __result) {
2398 while (__first1 != __last1 && __first2 != __last2)
2399 if (*__first1 < *__first2) {
2400 *__result = *__first1;
2401 ++__first1;
2402 ++__result;
2403 }
2404 else if (*__first2 < *__first1)
2405 ++__first2;
2406 else {
2407 ++__first1;
2408 ++__first2;
2409 }
2410 return copy(__first1, __last1, __result);
2411 }
2412
2413 template <class _InputIter1, class _InputIter2, class _OutputIter,
2414 class _Compare>
2415 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
2416 _InputIter2 __first2, _InputIter2 __last2,
2417 _OutputIter __result, _Compare __comp) {
2418 while (__first1 != __last1 && __first2 != __last2)
2419 if (__comp(*__first1, *__first2)) {
2420 *__result = *__first1;
2421 ++__first1;
2422 ++__result;
2423 }
2424 else if (__comp(*__first2, *__first1))
2425 ++__first2;
2426 else {
2427 ++__first1;
2428 ++__first2;
2429 }
2430 return copy(__first1, __last1, __result);
2431 }
2432
2433 template <class _InputIter1, class _InputIter2, class _OutputIter>
2434 _OutputIter
2435 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
2436 _InputIter2 __first2, _InputIter2 __last2,
2437 _OutputIter __result) {
2438 while (__first1 != __last1 && __first2 != __last2)
2439 if (*__first1 < *__first2) {
2440 *__result = *__first1;
2441 ++__first1;
2442 ++__result;
2443 }
2444 else if (*__first2 < *__first1) {
2445 *__result = *__first2;
2446 ++__first2;
2447 ++__result;
2448 }
2449 else {
2450 ++__first1;
2451 ++__first2;
2452 }
2453 return copy(__first2, __last2, copy(__first1, __last1, __result));
2454 }
2455
2456 template <class _InputIter1, class _InputIter2, class _OutputIter,
2457 class _Compare>
2458 _OutputIter
2459 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
2460 _InputIter2 __first2, _InputIter2 __last2,
2461 _OutputIter __result,
2462 _Compare __comp) {
2463 while (__first1 != __last1 && __first2 != __last2)
2464 if (__comp(*__first1, *__first2)) {
2465 *__result = *__first1;
2466 ++__first1;
2467 ++__result;
2468 }
2469 else if (__comp(*__first2, *__first1)) {
2470 *__result = *__first2;
2471 ++__first2;
2472 ++__result;
2473 }
2474 else {
2475 ++__first1;
2476 ++__first2;
2477 }
2478 return copy(__first2, __last2, copy(__first1, __last1, __result));
2479 }
2480
2481 // min_element and max_element, with and without an explicitly supplied
2482 // comparison function.
2483
2484 template <class _ForwardIter>
2485 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
2486 if (__first == __last) return __first;
2487 _ForwardIter __result = __first;
2488 while (++__first != __last)
2489 if (*__result < *__first)
2490 __result = __first;
2491 return __result;
2492 }
2493
2494 template <class _ForwardIter, class _Compare>
2495 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
2496 _Compare __comp) {
2497 if (__first == __last) return __first;
2498 _ForwardIter __result = __first;
2499 while (++__first != __last)
2500 if (__comp(*__result, *__first)) __result = __first;
2501 return __result;
2502 }
2503
2504 template <class _ForwardIter>
2505 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
2506 if (__first == __last) return __first;
2507 _ForwardIter __result = __first;
2508 while (++__first != __last)
2509 if (*__first < *__result)
2510 __result = __first;
2511 return __result;
2512 }
2513
2514 template <class _ForwardIter, class _Compare>
2515 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
2516 _Compare __comp) {
2517 if (__first == __last) return __first;
2518 _ForwardIter __result = __first;
2519 while (++__first != __last)
2520 if (__comp(*__first, *__result))
2521 __result = __first;
2522 return __result;
2523 }
2524
2525 // next_permutation and prev_permutation, with and without an explicitly
2526 // supplied comparison function.
2527
2528 template <class _BidirectionalIter>
2529 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
2530 if (__first == __last)
2531 return false;
2532 _BidirectionalIter __i = __first;
2533 ++__i;
2534 if (__i == __last)
2535 return false;
2536 __i = __last;
2537 --__i;
2538
2539 for(;;) {
2540 _BidirectionalIter __ii = __i;
2541 --__i;
2542 if (*__i < *__ii) {
2543 _BidirectionalIter __j = __last;
2544 while (!(*__i < *--__j))
2545 {}
2546 iter_swap(__i, __j);
2547 reverse(__ii, __last);
2548 return true;
2549 }
2550 if (__i == __first) {
2551 reverse(__first, __last);
2552 return false;
2553 }
2554 }
2555 }
2556
2557 template <class _BidirectionalIter, class _Compare>
2558 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
2559 _Compare __comp) {
2560 if (__first == __last)
2561 return false;
2562 _BidirectionalIter __i = __first;
2563 ++__i;
2564 if (__i == __last)
2565 return false;
2566 __i = __last;
2567 --__i;
2568
2569 for(;;) {
2570 _BidirectionalIter __ii = __i;
2571 --__i;
2572 if (__comp(*__i, *__ii)) {
2573 _BidirectionalIter __j = __last;
2574 while (!__comp(*__i, *--__j))
2575 {}
2576 iter_swap(__i, __j);
2577 reverse(__ii, __last);
2578 return true;
2579 }
2580 if (__i == __first) {
2581 reverse(__first, __last);
2582 return false;
2583 }
2584 }
2585 }
2586
2587 template <class _BidirectionalIter>
2588 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
2589 if (__first == __last)
2590 return false;
2591 _BidirectionalIter __i = __first;
2592 ++__i;
2593 if (__i == __last)
2594 return false;
2595 __i = __last;
2596 --__i;
2597
2598 for(;;) {
2599 _BidirectionalIter __ii = __i;
2600 --__i;
2601 if (*__ii < *__i) {
2602 _BidirectionalIter __j = __last;
2603 while (!(*--__j < *__i))
2604 {}
2605 iter_swap(__i, __j);
2606 reverse(__ii, __last);
2607 return true;
2608 }
2609 if (__i == __first) {
2610 reverse(__first, __last);
2611 return false;
2612 }
2613 }
2614 }
2615
2616 template <class _BidirectionalIter, class _Compare>
2617 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
2618 _Compare __comp) {
2619 if (__first == __last)
2620 return false;
2621 _BidirectionalIter __i = __first;
2622 ++__i;
2623 if (__i == __last)
2624 return false;
2625 __i = __last;
2626 --__i;
2627
2628 for(;;) {
2629 _BidirectionalIter __ii = __i;
2630 --__i;
2631 if (__comp(*__ii, *__i)) {
2632 _BidirectionalIter __j = __last;
2633 while (!__comp(*--__j, *__i))
2634 {}
2635 iter_swap(__i, __j);
2636 reverse(__ii, __last);
2637 return true;
2638 }
2639 if (__i == __first) {
2640 reverse(__first, __last);
2641 return false;
2642 }
2643 }
2644 }
2645
2646 // find_first_of, with and without an explicitly supplied comparison function.
2647
2648 template <class _InputIter, class _ForwardIter>
2649 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
2650 _ForwardIter __first2, _ForwardIter __last2)
2651 {
2652 for ( ; __first1 != __last1; ++__first1)
2653 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
2654 if (*__first1 == *__iter)
2655 return __first1;
2656 return __last1;
2657 }
2658
2659 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
2660 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
2661 _ForwardIter __first2, _ForwardIter __last2,
2662 _BinaryPredicate __comp)
2663 {
2664 for ( ; __first1 != __last1; ++__first1)
2665 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
2666 if (__comp(*__first1, *__iter))
2667 return __first1;
2668 return __last1;
2669 }
2670
2671
2672 // find_end, with and without an explicitly supplied comparison function.
2673 // Search [first2, last2) as a subsequence in [first1, last1), and return
2674 // the *last* possible match. Note that find_end for bidirectional iterators
2675 // is much faster than for forward iterators.
2676
2677 // find_end for forward iterators.
2678 template <class _ForwardIter1, class _ForwardIter2>
2679 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2680 _ForwardIter2 __first2, _ForwardIter2 __last2,
2681 forward_iterator_tag, forward_iterator_tag)
2682 {
2683 if (__first2 == __last2)
2684 return __last1;
2685 else {
2686 _ForwardIter1 __result = __last1;
2687 while (1) {
2688 _ForwardIter1 __new_result
2689 = search(__first1, __last1, __first2, __last2);
2690 if (__new_result == __last1)
2691 return __result;
2692 else {
2693 __result = __new_result;
2694 __first1 = __new_result;
2695 ++__first1;
2696 }
2697 }
2698 }
2699 }
2700
2701 template <class _ForwardIter1, class _ForwardIter2,
2702 class _BinaryPredicate>
2703 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2704 _ForwardIter2 __first2, _ForwardIter2 __last2,
2705 forward_iterator_tag, forward_iterator_tag,
2706 _BinaryPredicate __comp)
2707 {
2708 if (__first2 == __last2)
2709 return __last1;
2710 else {
2711 _ForwardIter1 __result = __last1;
2712 while (1) {
2713 _ForwardIter1 __new_result
2714 = search(__first1, __last1, __first2, __last2, __comp);
2715 if (__new_result == __last1)
2716 return __result;
2717 else {
2718 __result = __new_result;
2719 __first1 = __new_result;
2720 ++__first1;
2721 }
2722 }
2723 }
2724 }
2725
2726 // find_end for bidirectional iterators. Requires partial specialization.
2727 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
2728
2729 template <class _BidirectionalIter1, class _BidirectionalIter2>
2730 _BidirectionalIter1
2731 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2732 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2733 bidirectional_iterator_tag, bidirectional_iterator_tag)
2734 {
2735 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
2736 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
2737
2738 _RevIter1 __rlast1(__first1);
2739 _RevIter2 __rlast2(__first2);
2740 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
2741 _RevIter2(__last2), __rlast2);
2742
2743 if (__rresult == __rlast1)
2744 return __last1;
2745 else {
2746 _BidirectionalIter1 __result = __rresult.base();
2747 advance(__result, -distance(__first2, __last2));
2748 return __result;
2749 }
2750 }
2751
2752 template <class _BidirectionalIter1, class _BidirectionalIter2,
2753 class _BinaryPredicate>
2754 _BidirectionalIter1
2755 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2756 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2757 bidirectional_iterator_tag, bidirectional_iterator_tag,
2758 _BinaryPredicate __comp)
2759 {
2760 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
2761 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
2762
2763 _RevIter1 __rlast1(__first1);
2764 _RevIter2 __rlast2(__first2);
2765 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
2766 _RevIter2(__last2), __rlast2,
2767 __comp);
2768
2769 if (__rresult == __rlast1)
2770 return __last1;
2771 else {
2772 _BidirectionalIter1 __result = __rresult.base();
2773 advance(__result, -distance(__first2, __last2));
2774 return __result;
2775 }
2776 }
2777 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
2778
2779 // Dispatching functions for find_end.
2780
2781 template <class _ForwardIter1, class _ForwardIter2>
2782 inline _ForwardIter1
2783 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2784 _ForwardIter2 __first2, _ForwardIter2 __last2)
2785 {
2786 return __find_end(__first1, __last1, __first2, __last2,
2787 __ITERATOR_CATEGORY(__first1),
2788 __ITERATOR_CATEGORY(__first2));
2789 }
2790
2791 template <class _ForwardIter1, class _ForwardIter2,
2792 class _BinaryPredicate>
2793 inline _ForwardIter1
2794 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2795 _ForwardIter2 __first2, _ForwardIter2 __last2,
2796 _BinaryPredicate __comp)
2797 {
2798 return __find_end(__first1, __last1, __first2, __last2,
2799 __ITERATOR_CATEGORY(__first1),
2800 __ITERATOR_CATEGORY(__first2),
2801 __comp);
2802 }
2803
2804 // is_heap, a predicate testing whether or not a range is
2805 // a heap. This function is an extension, not part of the C++
2806 // standard.
2807
2808 template <class _RandomAccessIter, class _Distance>
2809 bool __is_heap(_RandomAccessIter __first, _Distance __n)
2810 {
2811 _Distance __parent = 0;
2812 for (_Distance __child = 1; __child < __n; ++__child) {
2813 if (__first[__parent] < __first[__child])
2814 return false;
2815 if ((__child & 1) == 0)
2816 ++__parent;
2817 }
2818 return true;
2819 }
2820
2821 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
2822 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
2823 _Distance __n)
2824 {
2825 _Distance __parent = 0;
2826 for (_Distance __child = 1; __child < __n; ++__child) {
2827 if (__comp(__first[__parent], __first[__child]))
2828 return false;
2829 if ((__child & 1) == 0)
2830 ++__parent;
2831 }
2832 return true;
2833 }
2834
2835 template <class _RandomAccessIter>
2836 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
2837 {
2838 return __is_heap(__first, __last - __first);
2839 }
2840
2841
2842 template <class _RandomAccessIter, class _StrictWeakOrdering>
2843 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
2844 _StrictWeakOrdering __comp)
2845 {
2846 return __is_heap(__first, __comp, __last - __first);
2847 }
2848
2849 // is_sorted, a predicated testing whether a range is sorted in
2850 // nondescending order. This is an extension, not part of the C++
2851 // standard.
2852
2853 template <class _ForwardIter>
2854 bool is_sorted(_ForwardIter __first, _ForwardIter __last)
2855 {
2856 if (__first == __last)
2857 return true;
2858
2859 _ForwardIter __next = __first;
2860 for (++__next; __next != __last; __first = __next, ++__next) {
2861 if (*__next < *__first)
2862 return false;
2863 }
2864
2865 return true;
2866 }
2867
2868 template <class _ForwardIter, class _StrictWeakOrdering>
2869 bool is_sorted(_ForwardIter __first, _ForwardIter __last,
2870 _StrictWeakOrdering __comp)
2871 {
2872 if (__first == __last)
2873 return true;
2874
2875 _ForwardIter __next = __first;
2876 for (++__next; __next != __last; __first = __next, ++__next) {
2877 if (__comp(*__next, *__first))
2878 return false;
2879 }
2880
2881 return true;
2882 }
2883
2884 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
2885 #pragma reset woff 1209
2886 #endif
2887
2888 __STL_END_NAMESPACE
2889
2890 #endif /* __SGI_STL_INTERNAL_ALGO_H */
2891
2892 // Local Variables:
2893 // mode:C++
2894 // End:
Clone of Haiku svn repository