Ne.app NeANT
The Ne.app NeANT User module of the NeANT distribution.
algorithm.cc
Go to the documentation of this file.
1
43_RWSTD_NAMESPACE (std) {
44
45
46_EXPORT
47template <class _FwdIter1, class _FwdIter2, class _Dist>
48_FwdIter1 __find_end (_FwdIter1 __first1, _FwdIter1 __last1,
49 _FwdIter2 __first2, _FwdIter2 __last2,
50 _Dist*)
51{
52 _RWSTD_ASSERT_RANGE (__first1, __last1);
53 _RWSTD_ASSERT_RANGE (__first2, __last2);
54
55 const _Dist __dist1 = _DISTANCE (__first2, __last2, _Dist);
56
57 if (!__dist1)
58 return __last1;
59
60 _Dist __dist2 = _DISTANCE (__first1, __last1, _Dist);
61
62 _FwdIter1 __res = __last1;
63
64 while (__dist2 >= __dist1) {
65 if (equal (__first2, __last2, __first1))
66 __res = __first1;
67
68 __dist2 = _DISTANCE (++__first1, __last1, _Dist);
69 }
70 return __res;
71}
72
73
74
75_EXPORT
76template <class _FwdIter1, class _FwdIter2,
77 class _BinaryPredicate, class _Dist>
78_FwdIter1 __find_end (_FwdIter1 __first1, _FwdIter1 __last1,
79 _FwdIter2 __first2, _FwdIter2 __last2,
80 _BinaryPredicate __pred, _Dist*)
81{
82 _RWSTD_ASSERT_RANGE (__first1, __last1);
83 _RWSTD_ASSERT_RANGE (__first2, __last2);
84
85 const _Dist __dist1 = _DISTANCE (__first2, __last2, _Dist);
86
87 if (!__dist1)
88 return __last1;
89
90 _Dist __dist2 = _DISTANCE (__first1, __last1, _Dist);
91
92 _FwdIter1 __res = __last1;
93
94 while (__dist2 >= __dist1) {
95 if (_STD::equal (__first2, __last2, __first1, __pred))
96 __res = __first1;
97
98 __dist2 = _DISTANCE (++__first1, __last1, _Dist);
99 }
100 return __res;
101}
102
103
104_EXPORT
105template <class _FwdIter1, class _FwdIter2>
106_FwdIter1 find_first_of (_FwdIter1 __first1, _FwdIter1 __last1,
107 _FwdIter2 __first2, _FwdIter2 __last2)
108{
109 _RWSTD_ASSERT_RANGE (__first1, __last1);
110 _RWSTD_ASSERT_RANGE (__first2, __last2);
111
112 if (__first2 == __last2)
113 return __last1;
114
115 for (_FwdIter1 __next = __first1; !(__next == __last1); ++__next)
116 if (!(_STD::find (__first2, __last2, *__next) == __last2))
117 return __next;
118
119 return __last1;
120}
121
122
123_EXPORT
124template <class _FwdIter1, class _FwdIter2,
125 class _BinaryPredicate>
126_FwdIter1 find_first_of (_FwdIter1 __first1, _FwdIter1 __last1,
127 _FwdIter2 __first2, _FwdIter2 __last2,
128 _BinaryPredicate __pred)
129{
130 _RWSTD_ASSERT_RANGE (__first1, __last1);
131 _RWSTD_ASSERT_RANGE (__first2, __last2);
132
133 if (__first2 == __last2)
134 return __last1;
135
136 for (_FwdIter1 __next = __first1; !(__next == __last1); ++__next)
137 for (_FwdIter2 __iter = __first2; !(__iter == __last2); ++__iter)
138 if (!(__pred (*__next, *__iter) == false))
139 return __next;
140
141 return __last1;
142}
143
144
145_EXPORT
146template <class _FwdIter>
147_FwdIter adjacent_find (_FwdIter __first, _FwdIter __last)
148{
149 _RWSTD_ASSERT_RANGE (__first, __last);
150
151 if (__first == __last)
152 return __last;
153
154 for (_FwdIter __next = __first; !(++__next == __last); __first = __next)
155 if (*__first == *__next)
156 return __first;
157
158 return __last;
159}
160
161
162_EXPORT
163template <class _FwdIter, class _BinaryPredicate>
164_FwdIter adjacent_find (_FwdIter __first, _FwdIter __last,
165 _BinaryPredicate __pred)
166{
167 _RWSTD_ASSERT_RANGE (__first, __last);
168
169 if (__first == __last)
170 return __last;
171
172 for (_FwdIter __next = __first; !(++__next == __last); __first = __next)
173 if (!(__pred (*__first, *__next) == false))
174 return __first;
175
176 return __last;
177}
178
179
180_EXPORT
181template <class _FwdIter1, class _FwdIter2, class _Dist1, class _Dist2>
182_FwdIter1 __search (_FwdIter1 __first1, _FwdIter1 __last1,
183 _FwdIter2 __first2, _FwdIter2 __last2,
184 _Dist1*, _Dist2*)
185{
186 _RWSTD_ASSERT_RANGE (__first1, __last1);
187 _RWSTD_ASSERT_RANGE (__first2, __last2);
188
189 _Dist1 __dist1 = _DISTANCE (__first1, __last1, _Dist1);
190 _Dist2 __dist2 = _DISTANCE (__first2, __last2, _Dist2);
191
192 if (__dist1 < __dist2)
193 return __last1;
194
195 _FwdIter1 __cur1 = __first1;
196 _FwdIter2 __cur2 = __first2;
197
198 while (!(__cur2 == __last2)) {
199 if (!(*__cur1 == *__cur2)) {
200 ++__cur1;
201 ++__cur2;
202 if (__dist1-- == __dist2)
203 return __last1;
204
205 __cur1 = ++__first1;
206 __cur2 = __first2;
207 }
208 else {
209 ++__cur1;
210 ++__cur2;
211 }
212 }
213
214 return (__cur2 == __last2) ? __first1 : __last1;
215}
216
217
218_EXPORT
219template <class _FwdIter1, class _FwdIter2,
220 class _BinaryPredicate, class _Dist1, class _Dist2>
221_FwdIter1 __search (_FwdIter1 __first1, _FwdIter1 __last1,
222 _FwdIter2 __first2, _FwdIter2 __last2,
223 _BinaryPredicate __pred, _Dist1*, _Dist2*)
224{
225 _RWSTD_ASSERT_RANGE (__first1, __last1);
226 _RWSTD_ASSERT_RANGE (__first2, __last2);
227
228 _Dist1 __dist1 = _DISTANCE (__first1, __last1, _Dist1);
229 _Dist2 __dist2 = _DISTANCE (__first2, __last2, _Dist2);
230
231 if (__dist1 < __dist2) return __last1;
232
233 _FwdIter1 __cur1 = __first1;
234 _FwdIter2 __cur2 = __first2;
235
236 while (!(__cur2 == __last2)) {
237 if (__pred (*__cur1, *__cur2) == false) {
238 ++__cur1;
239 ++__cur2;
240 if (__dist1-- == __dist2)
241 return __last1;
242
243 __cur1 = ++__first1;
244 __cur2 = __first2;
245 }
246 else {
247 ++__cur1;
248 ++__cur2;
249 }
250 }
251
252 return (__cur2 == __last2) ? __first1 : __last1;
253}
254
255
256_EXPORT
257template <class _FwdIter, class _Dist, class _Size, class _TypeT>
258_FwdIter __search_n (_FwdIter __first, _FwdIter __last,
259 _Dist*, _Size __count, const _TypeT& __val)
260{
261 _RWSTD_ASSERT_RANGE (__first, __last);
262
263 if (__count <= 0)
264 return __last;
265
266 const _Dist __dist = _DISTANCE (__first, __last, _Dist);
267
268 if (__dist < _Dist (__count))
269 return __last;
270
271 _Dist __span = __dist - _Dist (__count);
272 _Dist __matches = 0;
273
274 _FwdIter __current = __first;
275
276 while (!(__current == __last)) {
277 if (!(*__current == __val)) {
278 if (__span < __matches + 1)
279 return __last;
280 __span -= __matches + 1;
281 __matches = 0;
282 __first = ++__current;
283 }
284 else {
285 if (++__matches == _Dist (__count))
286 return __first;
287 ++__current;
288 }
289 }
290
291 return __last;
292}
293
294
295_EXPORT
296template <class _FwdIter, class _Dist, class _Size, class _TypeT,
297 class _BinaryPredicate>
298_FwdIter __search_n (_FwdIter __first, _FwdIter __last,
299 _Dist*, _Size __count, const _TypeT& __val,
300 _BinaryPredicate __pred)
301{
302 _RWSTD_ASSERT_RANGE (__first, __last);
303
304 const _Dist __dist = _DISTANCE (__first, __last, _Dist);
305
306 const _RWSTD_PTRDIFF_T __int_count = __count;
307
308 if (__dist < __int_count || __int_count <= 0)
309 return __last;
310
311 _Dist __span = __dist - __int_count;
312 _Dist __matches = 0;
313 _FwdIter __current = __first;
314
315 while (!(__current == __last)) {
316 if (__pred (*__current, __val) == false) {
317 if (__span < __matches + 1)
318 return __last;
319 __span -= __matches + 1;
320 __matches = 0;
321 __first = ++__current;
322 }
323 else {
324 if (++__matches == __count)
325 return __first;
326 ++__current;
327 }
328 }
329
330 return __last;
331}
332
333//
334// Modifying sequence operations.
335//
336
337_EXPORT
338template <class _Iter, class _OutputIter, class _Predicate, class _TypeT>
339_OutputIter replace_copy_if (_Iter __first, _Iter __last,
340 _OutputIter __res, _Predicate __pred,
341 const _TypeT& __new_value)
342{
343 _RWSTD_ASSERT_RANGE (__first, __last);
344
345 for (; !(__first == __last); ++__res, ++__first)
346 *__res = __pred (*__first) == false ? *__first : __new_value;
347
348 return __res;
349}
350
351
352_EXPORT
353template <class _InputIter, class _OutputIter, class _TypeT>
354_OutputIter remove_copy (_InputIter __first, _InputIter __last,
355 _OutputIter __res, const _TypeT& __val)
356{
357 _RWSTD_ASSERT_RANGE (__first, __last);
358
359 for (; !(__first == __last); ++__first)
360 if (!(*__first == __val)) {
361 *__res = *__first;
362 ++__res;
363 }
364 return __res;
365}
366
367
368_EXPORT
369template <class _InputIter, class _OutputIter, class _Predicate>
370_OutputIter remove_copy_if (_InputIter __first, _InputIter __last,
371 _OutputIter __res, _Predicate __pred)
372{
373 _RWSTD_ASSERT_RANGE (__first, __last);
374
375 for (; !(__first == __last); ++__first)
376 if (__pred (*__first) == false) {
377 *__res = *__first;
378 ++__res;
379 }
380 return __res;
381}
382
383
384_EXPORT
385template <class _FwdIter>
386_FwdIter
387unique (_FwdIter __first, _FwdIter __last)
388{
389 // find the first of two equal elements
390 __first = _STD::adjacent_find (__first, __last);
391
392 if (__first == __last)
393 return __first;
394
395 // advance `first' to point at the copy (may be overwritten later)
396 _FwdIter __next = ++__first;
397
398 // skip over all subsequent elements that are equal to the first
399 while (!(++__next == __last))
400 if (!(*__next == *__first))
401 break;
402
403 // invoke unique_copy to copy over the original sequence
404 // starting at one past the first element
405 return __unique_copy (__next, __last, __first,
406 _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
407}
408
409
410_EXPORT
411template <class _FwdIter, class _BinaryPredicate>
412_FwdIter
413unique (_FwdIter __first, _FwdIter __last, _BinaryPredicate __pred)
414{
415 __first = _STD::adjacent_find (__first, __last, __pred);
416
417 if (__first == __last)
418 return __first;
419
420 _FwdIter __next = ++__first;
421
422 while (!(++__next == __last))
423 if (__pred (*__next, *__first) == false)
424 break;
425
426 return __unique_copy (__next, __last, __first, __pred,
427 _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
428}
429
430
431_EXPORT
432template <class _InputIter, class _FwdIter>
433_FwdIter __unique_copy (_InputIter __first, _InputIter __last,
434 _FwdIter __res, forward_iterator_tag)
435{
436 _RWSTD_ASSERT_RANGE (__first, __last);
437
438 if (__first == __last)
439 return __res;
440
441 *__res = *__first;
442 while (!(++__first == __last))
443 if (!(*__res == *__first))
444 *++__res = *__first;
445 return ++__res;
446}
447
448
449_EXPORT
450template <class _InputIter, class _OutputIter, class _TypeT>
451_OutputIter __unique_copy (_InputIter __first, _InputIter __last,
452 _OutputIter __res, _TypeT*)
453{
454 _RWSTD_ASSERT_RANGE (__first, __last);
455
456 if (__first == __last)
457 return __res;
458
459 _TypeT __val = *__first;
460
461 for (*__res = __val; !(++__first == __last); )
462 if (!(__val == *__first)) {
463 __val = *__first;
464 *++__res = __val;
465 }
466
467 return ++__res;
468}
469
470
471_EXPORT
472template <class _InputIter, class _FwdIter, class _BinaryPredicate>
473_FwdIter __unique_copy (_InputIter __first, _InputIter __last,
474 _FwdIter __res,
475 _BinaryPredicate __pred,
476 forward_iterator_tag)
477{
478 _RWSTD_ASSERT_RANGE (__first, __last);
479
480 if (__first == __last)
481 return __res;
482
483 for (*__res = *__first; !(++__first == __last); )
484 if (__pred (*__res, *__first) == false)
485 *++__res = *__first;
486
487 return ++__res;
488}
489
490
491_EXPORT
492template <class _InputIter, class _OutputIter, class _BinaryPredicate,
493 class _TypeT>
494_OutputIter __unique_copy (_InputIter __first, _InputIter __last,
495 _OutputIter __res,
496 _BinaryPredicate __pred, _TypeT*)
497{
498 _RWSTD_ASSERT_RANGE (__first, __last);
499
500 if (__first == __last)
501 return __res;
502
503 _TypeT __val = *__first;
504
505 for (*__res = __val; !(++__first == __last); )
506 if (__pred (__val, *__first) == false) {
507 __val = *__first;
508 *++__res = __val;
509 }
510
511 return ++__res;
512}
513
514
515_EXPORT
516template <class _FwdIter, class _Dist>
517void __rotate (_FwdIter __first, _FwdIter __middle,
518 _FwdIter __last, _Dist*, forward_iterator_tag)
519{
520 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
521
522 for (_FwdIter __i = __middle; ; ) {
523 _STD::iter_swap (__first, __i);
524 ++__i;
525 if (++__first == __middle) {
526 if (__i == __last)
527 return;
528 __middle = __i;
529 }
530 else if (__i == __last)
531 __i = __middle;
532 }
533}
534
535
536_EXPORT
537template <class _EuclideanRingElement>
538_EuclideanRingElement __gcd (_EuclideanRingElement __m,
539 _EuclideanRingElement __n)
540{
541 while (!(__n == _EuclideanRingElement ())) {
542 const _EuclideanRingElement __r = __m % __n;
543 __m = __n;
544 __n = __r;
545 }
546 return __m;
547}
548
549
550_EXPORT
551template <class _RandomAccessIter, class _Dist, class _TypeT>
552void __rotate_cycle (_RandomAccessIter __first, _RandomAccessIter __last,
553 _RandomAccessIter __first2, _Dist __shift, _TypeT*)
554{
555 _RWSTD_ASSERT_RANGE (__first, __last);
556
557 const _TypeT __val = *__first2;
558
559 _RandomAccessIter __it1 = __first2;
560
561 for (_RandomAccessIter __it2 = __it1 + __shift; !(__it2 == __first2); ) {
562 *__it1 = *__it2;
563 __it1 = __it2;
564
565 if (__last - __it2 > __shift)
566 __it2 += __shift;
567 else
568 __it2 = __first + (__shift - (__last - __it2));
569 }
570
571 *__it1 = __val;
572}
573
574
575_EXPORT
576template <class _RandomAccessIter, class _Dist>
577void __rotate (_RandomAccessIter __first, _RandomAccessIter __middle,
578 _RandomAccessIter __last, _Dist*,
579 random_access_iterator_tag)
580{
581 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
582
583 for (_Dist __n = __gcd (__last - __first, __middle - __first); __n--; )
584 __rotate_cycle (__first, __last, __first + __n, __middle - __first,
585 _RWSTD_VALUE_TYPE (_RandomAccessIter));
586}
587
588
589_EXPORT
590template <class _RandomAccessIter, class _RandomNumberGenerator>
591void random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last,
592 _RandomNumberGenerator &__rand)
593{
594 _RWSTD_ASSERT_RANGE (__first, __last);
595
596 if (!(__first == __last)) {
597
598#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
599 typedef typename
600 iterator_traits<_RandomAccessIter>::difference_type _DiffT;
601#else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)
602 typedef _RWSTD_PTRDIFF_T _DiffT;
603#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC
604
605 _DiffT __limit = 2;
606
607 for (_RandomAccessIter __i = __first; !(++__i == __last); ++__limit) {
608
609 // the argument to and the return value of the random number
610 // generator's operator() is required to be convertinble from
611 // and to the iterator's difference_type but nothing else
612 const _DiffT __rndoff (__rand (__limit));
613
614 // returned value must be non-negative and less than the limit
615 _RWSTD_ASSERT (0 <= __rndoff && __rndoff < __limit);
616
617 _STD::iter_swap (__i, __first + __rndoff);
618 }
619 }
620}
621
622
623_EXPORT
624template <class _BidirIter, class _Predicate>
625_BidirIter partition (_BidirIter __first, _BidirIter __last, _Predicate __pred)
626{
627 _RWSTD_ASSERT_RANGE (__first, __last);
628
629 for ( ; ; ++__first) {
630 for ( ; ; ) {
631 if (__first == __last)
632 return __first;
633 if (!(__pred (*__first) == false))
634 ++__first;
635 else
636 break;
637 }
638
639 for (--__last; ; ) {
640 if (__first == __last)
641 return __first;
642 if (__pred (*__last) == false)
643 --__last;
644 else
645 break;
646 }
647 _STD::iter_swap (__first, __last);
648 }
649}
650
651
652template <class _BidirIter, class _Predicate, class _Dist>
653_BidirIter __inplace_stable_partition (_BidirIter __first, _BidirIter __last,
654 _Predicate __pred, _Dist __dist)
655{
656 _RWSTD_ASSERT_RANGE (__first, __last);
657
658 if (__dist == 1)
659 return !(__pred (*__first) == false) ? __last : __first;
660
661 _BidirIter __middle = __first;
662 _STD::advance (__middle, __dist / 2);
663 _BidirIter
664 __first_cut = __inplace_stable_partition (__first, __middle, __pred,
665 __dist / 2);
666 _BidirIter
667 __second_cut = __inplace_stable_partition (__middle, __last, __pred,
668 __dist - __dist / 2);
669 _STD::rotate (__first_cut, __middle, __second_cut);
670 __dist = _DISTANCE (__middle, __second_cut, _Dist);
671 _STD::advance (__first_cut, __dist);
672 return __first_cut;
673}
674
675
676_EXPORT
677template <class _BidirIter, class _Pointer, class _Predicate,
678 class _Dist, class _TypeT>
679_BidirIter __stable_partition_adaptive (_BidirIter __first, _BidirIter __last,
680 _Predicate __pred, _Dist __dist,
681 _Pointer __buf,
682 _Dist __buf_size,
683 _Dist& __fill_pointer, _TypeT*)
684{
685 _RWSTD_ASSERT_RANGE (__first, __last);
686
687 if (__dist <= __buf_size)
688 {
689 __dist = 0;
690 _BidirIter __res1 = __first;
691 _Pointer __res2 = __buf;
692 for (; !(__first == __last) && __dist < __fill_pointer; ++__first)
693 {
694 if (!(__pred (*__first) == false)) {
695 *__res1 = *__first;
696 ++__res1;
697 }
698 else {
699 *__res2 = *__first;
700 ++__res2;
701 ++__dist;
702 }
703 }
704 if (!(__first == __last))
705 {
706 raw_storage_iterator<_Pointer, _TypeT> __res3 (__res2);
707 for (; !(__first == __last); ++__first)
708 {
709 if (!(__pred (*__first) == false)) {
710 *__res1 = *__first;
711 ++__res1;
712 }
713 else {
714 *__res3 = *__first;
715 ++__res3;
716 ++__dist;
717 }
718 }
719 __fill_pointer = __dist;
720 }
721 _STD::copy (__buf, __buf + __dist, __res1);
722 return __res1;
723 }
724 _BidirIter __middle = __first;
725 _STD::advance (__middle, __dist / 2);
726
727 // (__dist / 2)'s type may not be the same as that of __dist,
728 // hence the seemingly redundant casts below
729 _BidirIter __first_cut =
730 __stable_partition_adaptive (__first, __middle, __pred,
731 _Dist (__dist / 2),
732 __buf, __buf_size,
733 __fill_pointer, (_TypeT*)0);
734 _BidirIter __second_cut =
735 __stable_partition_adaptive (__middle, __last, __pred,
736 _Dist (__dist - __dist / 2),
737 __buf, __buf_size,
738 __fill_pointer, (_TypeT*)0);
739
740 _STD::rotate (__first_cut, __middle, __second_cut);
741 __dist = _DISTANCE (__middle, __second_cut, _Dist);
742 _STD::advance (__first_cut, __dist);
743 return __first_cut;
744}
745
746
747_EXPORT
748template <class _BidirIter, class _Predicate, class _TypeT, class _Dist>
749_BidirIter __stable_partition (_BidirIter __first, _BidirIter __last,
750 _Predicate __pred, _TypeT*, _Dist*)
751{
752 _RWSTD_ASSERT_RANGE (__first, __last);
753
754 const _Dist __dist = _DISTANCE (__first, __last, _Dist);
755
756 if (!__dist)
757 return __last;
758
759 // call an extension of get_temporary_buffer<>() in case partial class
760 // specialization (and iterator_traits<>) isn't supported by compiler
761 pair<_TypeT*, _Dist> __pair =
762 _STD::get_temporary_buffer (__dist, (_TypeT*)0);
763
764 if (__pair.first == 0)
765 return __inplace_stable_partition (__first, __last, __pred, __dist);
766
767 _Dist __fill = 0;
768
769 const _BidirIter __res =
770 __stable_partition_adaptive (__first, __last, __pred, __dist,
771 __pair.first, __pair.second,
772 __fill, (_TypeT*)0);
773
774 for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first == __ptr--); )
775 (*__ptr).~_TypeT ();
776
777 _STD::return_temporary_buffer (__pair.first);
778
779 return __res;
780}
781
782//
783// Sorting and related operations.
784//
785
786template <class _RandomAccessIter, class _TypeT, class _Compare>
787_RandomAccessIter __unguarded_partition (_RandomAccessIter __first,
788 _RandomAccessIter __last,
789 _TypeT __pivot, _Compare __comp)
790{
791 _RWSTD_ASSERT_RANGE (__first, __last);
792
793 for ( ; ; ++__first) {
794 for (; __comp (*__first, __pivot); ++__first);
795
796 while (__comp (__pivot, *--__last));
797
798 if (!(__first < __last))
799 return __first;
800
801 _STD::iter_swap (__first, __last);
802 }
803}
804
805
806template <class _TypeT, class _Compare>
807inline const _TypeT& __median (const _TypeT& __a, const _TypeT& __b,
808 const _TypeT& __c, _Compare __comp)
809{
810 return __comp (__a, __b)
811 ? __comp (__b, __c) ? __b : __comp (__a, __c) ? __c : __a
812 : __comp (__a, __c) ? __a : __comp (__b, __c) ? __c : __b;
813}
814
815
816enum { __rw_threshold = 16 };
817
818template <class _RandomAccessIter, class _TypeT, class _Compare>
819void __quick_sort_loop_aux (_RandomAccessIter __first,
820 _RandomAccessIter __last, _TypeT*,
821 _Compare __comp)
822{
823 _RWSTD_ASSERT_RANGE (__first, __last);
824
825 while (__last - __first > __rw_threshold) {
826 _RandomAccessIter __cut =
827 __unguarded_partition (__first, __last,
828 _TypeT (__median (*__first,
829 * (__first +
830 (__last - __first)/2),
831 * (__last - 1),
832 __comp)),
833 __comp);
834 if (__cut - __first >= __last - __cut) {
835 __quick_sort_loop_aux (__cut, __last,
836 _RWSTD_VALUE_TYPE (_RandomAccessIter),
837 __comp);
838 __last = __cut;
839 }
840 else {
841 __quick_sort_loop_aux (__first, __cut,
842 _RWSTD_VALUE_TYPE (_RandomAccessIter),
843 __comp);
844 __first = __cut;
845 }
846 }
847}
848
849
850template <class _RandomAccessIter, class _TypeT>
851inline void __linear_insert (_RandomAccessIter __first,
852 _RandomAccessIter __last, _TypeT*)
853{
854 const _TypeT __val = *__last;
855
856 if (__val < *__first) {
857 _STD::copy_backward (__first, __last, __last + 1);
858 *__first = __val;
859 }
860 else
861 __unguarded_linear_insert (__last, __val);
862}
863
864
865template <class _RandomAccessIter, class _TypeT, class _Compare>
866inline void
867__linear_insert (_RandomAccessIter __first, _RandomAccessIter __last, _TypeT*,
868 _Compare __comp)
869{
870 const _TypeT __val = *__last;
871
872 if (__comp (__val, *__first)) {
873 _STD::copy_backward (__first, __last, __last + 1);
874 *__first = __val;
875 }
876 else
877 __unguarded_linear_insert (__last, __val, __comp);
878}
879
880
881_EXPORT
882template <class _RandomAccessIter, class _Compare>
883void __insertion_sort (_RandomAccessIter __first,
884 _RandomAccessIter __last, _Compare __comp)
885{
886 _RWSTD_ASSERT_RANGE (__first, __last);
887
888 if (! (__first == __last))
889 for (_RandomAccessIter __i = __first + 1; !(__i == __last); ++__i)
890 __linear_insert (__first, __i,
891 _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
892}
893
894_EXPORT
895template <class _RandomAccessIter, class _TypeT, class _Compare>
896void __unguarded_linear_insert (_RandomAccessIter __last, _TypeT __val,
897 _Compare __comp)
898{
899 for (_RandomAccessIter __next = __last; __comp (__val, *--__next); ) {
900 *__last = *__next;
901 __last = __next;
902 }
903 *__last = __val;
904}
905
906
907_EXPORT
908template <class _RandomAccessIter, class _Compare>
909void __final_insertion_sort (_RandomAccessIter __first,
910 _RandomAccessIter __last, _Compare __comp)
911{
912 _RWSTD_ASSERT_RANGE (__first, __last);
913
914 if (__last - __first > __rw_threshold) {
915 __insertion_sort (__first, __first + __rw_threshold, __comp);
916 __unguarded_insertion_sort (__first + __rw_threshold, __last, __comp);
917 }
918 else
919 __insertion_sort (__first, __last, __comp);
920}
921
922
923template <class _RandomAccessIter1, class _RandomAccessIter2,
924 class _Dist, class _Compare>
925void __merge_sort_loop (_RandomAccessIter1 __first,
926 _RandomAccessIter1 __last,
927 _RandomAccessIter2 __res, _Dist __step,
928 _Compare __comp)
929{
930 _RWSTD_ASSERT_RANGE (__first, __last);
931
932 const _Dist __two_step = 2 * __step;
933
934 while (__last - __first >= __two_step) {
935 __res = _STD::merge (__first, __first + __step,
936 __first + __step, __first + __two_step, __res,
937 __comp);
938 __first += __two_step;
939 }
940 __step = (_STD::min)(_Dist (__last - __first), __step);
941
942 _STD::merge (__first, __first + __step, __first + __step, __last,
943 __res, __comp);
944}
945
946
947template <class _RandomAccessIter, class _Dist, class _Compare>
948void __chunk_insertion_sort (_RandomAccessIter __first,
949 _RandomAccessIter __last,
950 _Dist __chunk_size, _Compare __comp)
951{
952 _RWSTD_ASSERT_RANGE (__first, __last);
953
954 while (__last - __first >= __chunk_size)
955 {
956 __insertion_sort (__first, __first + __chunk_size, __comp);
957 __first += __chunk_size;
958 }
959 __insertion_sort (__first, __last, __comp);
960}
961
962
963_EXPORT
964template <class _RandomAccessIter, class _Pointer, class _Dist,
965 class _Compare>
966void __merge_sort_with_buffer (_RandomAccessIter __first,
967 _RandomAccessIter __last, _Pointer __buf,
968 _Dist*, _Compare __comp)
969{
970 _RWSTD_ASSERT_RANGE (__first, __last);
971
972 const _Dist __dist = __last - __first;
973 const _Pointer __bufend = __buf + __dist;
974
975 _Dist __step = 7; // STL chunk size
976
977 __chunk_insertion_sort (__first, __last, __step, __comp);
978
979 while (__step < __dist) {
980 __merge_sort_loop (__first, __last, __buf, __step, __comp);
981 __step *= 2;
982 __merge_sort_loop (__buf, __bufend, __first, __step, __comp);
983 __step *= 2;
984 }
985}
986
987
988template <class _BidirIter, class _Dist, class _Pointer, class _Compare>
989void __merge_adaptive (_BidirIter, _BidirIter, _BidirIter,
990 _Dist, _Dist, _Pointer, _Dist, _Compare);
991
992_EXPORT
993template <class _RandomAccessIter, class _Pointer, class _Dist,
994 class _TypeT, class _Compare>
995void __stable_sort_adaptive (_RandomAccessIter __first,
996 _RandomAccessIter __last, _Pointer __buf,
997 _Dist __buf_size, _TypeT*,
998 _Compare __comp)
999{
1000 _RWSTD_ASSERT_RANGE (__first, __last);
1001
1002 const _Dist __dist = (__last - __first + 1) / 2;
1003 const _RandomAccessIter __middle = __first + __dist;
1004
1005 if (__dist > __buf_size) {
1006 __stable_sort_adaptive (__first, __middle, __buf, __buf_size,
1007 (_TypeT*)0, __comp);
1008 __stable_sort_adaptive (__middle, __last, __buf, __buf_size,
1009 (_TypeT*)0, __comp);
1010 }
1011 else {
1012 __merge_sort_with_buffer (__first, __middle, __buf,
1013 (_Dist*)0, __comp);
1014 __merge_sort_with_buffer (__middle, __last, __buf,
1015 (_Dist*)0, __comp);
1016 }
1017 __merge_adaptive (__first, __middle, __last,
1018 _Dist (__middle - __first),
1019 _Dist (__last - __middle), __buf, __buf_size, __comp);
1020}
1021
1022
1023_EXPORT
1024template <class _RandomAccessIter, class _TypeT, class _Dist, class _Compare>
1025void
1026__stable_sort (_RandomAccessIter __first, _RandomAccessIter __last,
1027 _TypeT*, _Dist*, _Compare __comp)
1028{
1029 // call an extension of get_temporary_buffer<>() in case partial class
1030 // specialization (and iterator_traits<>) isn't supported by compiler
1031 pair<_TypeT*, _Dist> __p =
1032 _STD::get_temporary_buffer (_Dist (__last - __first), (_TypeT*)0);
1033
1034 if (__p.first == 0)
1035 __inplace_stable_sort (__first, __last, __comp);
1036 else {
1037 _Dist __len = (_STD::min)(_Dist (__p.second),
1038 _Dist (__last - __first));
1039 _STD::copy (__first, __first + __len,
1040 raw_storage_iterator<_TypeT*, _TypeT>(__p.first));
1041
1042 __stable_sort_adaptive (__first, __last, __p.first, __p.second,
1043 (_TypeT*)0, __comp);
1044
1045 for (_TypeT *__ptr = __p.first + __len; !(__p.first == --__ptr); )
1046 (*__ptr).~_TypeT ();
1047
1048 _STD::return_temporary_buffer (__p.first);
1049 }
1050}
1051
1052
1053_EXPORT
1054template <class _RandomAccessIter, class _TypeT, class _Compare>
1055void __partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle,
1056 _RandomAccessIter __last, _TypeT*, _Compare __comp)
1057{
1058 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
1059
1060 _STD::make_heap (__first, __middle, __comp);
1061
1062 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1063 if (__comp (*__i, *__first))
1064 __pop_heap (__first, __middle, __i, *__i, __comp,
1065 _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter));
1066
1067 _STD::sort_heap (__first, __middle, __comp);
1068}
1069
1070
1071_EXPORT
1072template <class _InputIter, class _RandomAccessIter, class _Compare,
1073 class _Dist, class _TypeT>
1074_RandomAccessIter __partial_sort_copy (_InputIter __first,
1075 _InputIter __last,
1076 _RandomAccessIter __first2,
1077 _RandomAccessIter __last2,
1078 _Compare __comp,
1079 _Dist*, _TypeT*)
1080{
1081 _RWSTD_ASSERT_RANGE (__first, __last);
1082 _RWSTD_ASSERT_RANGE (__first2, __last2);
1083
1084 if (__first2 == __last2)
1085 return __last2;
1086
1087 _RandomAccessIter __res = __first2;
1088
1089 for (; !(__first == __last) && !(__res == __last2); ++__first, ++__res)
1090 *__res = *__first;
1091
1092 _STD::make_heap (__first2, __res, __comp);
1093
1094 for (; !(__first == __last); ++__first) {
1095 if (__comp (*__first, *__first2))
1096 __adjust_heap (__first2, _Dist (), _Dist (__res - __first2),
1097 *__first, __comp);
1098 }
1099
1100 _STD::sort_heap (__first2, __res, __comp);
1101
1102 return __res;
1103}
1104
1105
1106// David R. Musser's Introspective Sorting algorithm
1107// (see www.cs.rpi.edu/~musser/gp/introsort.ps)
1108// O(N * log (N)) worst case complexity
1109_EXPORT
1110template <class _RandomAccessIter, class _Dist, class _Compare>
1111void __introsort_loop (_RandomAccessIter __first, _RandomAccessIter __last,
1112 _Dist __max_depth, _Compare __comp)
1113{
1114 for ( ; __rw_threshold < __last - __first; ) {
1115 if (0 == __max_depth) {
1116 __partial_sort (__first, __last, __last,
1117 _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
1118 break;
1119 }
1120
1121 _RandomAccessIter __cut =
1122 __unguarded_partition (__first, __last,
1123 __median (*__first,
1124 *(__first + (__last - __first) /2),
1125 *(__last - 1), __comp), __comp);
1126
1127 // limit the depth of the recursion tree to log2 (last - first)
1128 // where first and last are the initial values passed in from sort()
1129 __introsort_loop (__cut, __last, __max_depth /= 2, __comp);
1130 __last = __cut;
1131 }
1132}
1133
1134
1135_EXPORT
1136template <class _RandomAccessIter, class _TypeT, class _Compare>
1137void __nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
1138 _RandomAccessIter __last, _TypeT*, _Compare __comp)
1139{
1140 _RWSTD_ASSERT_IN_RANGE (__nth, __first, __last);
1141
1142 while (__last - __first > 3) {
1143 const _RandomAccessIter __cut =
1144 __unguarded_partition (__first, __last,
1145 _TypeT (__median (*__first,
1146 * (__first +
1147 (__last - __first)/2),
1148 * (__last - 1),
1149 __comp)),
1150 __comp);
1151 if (!(__nth < __cut))
1152 __first = __cut;
1153 else
1154 __last = __cut;
1155 }
1156 __insertion_sort (__first, __last, __comp);
1157}
1158
1159//
1160// Binary search.
1161//
1162
1163_EXPORT
1164template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
1165_FwdIter __lower_bound (_FwdIter __first, _FwdIter __last,
1166 const _TypeT& __val, _Compare __comp,
1167 _Dist*, forward_iterator_tag)
1168{
1169 _RWSTD_ASSERT_RANGE (__first, __last);
1170
1171 for (_Dist __dist = _DISTANCE (__first, __last, _Dist); __dist; ) {
1172
1173 const _Dist __half = __dist / 2;
1174 _FwdIter __middle = __first;
1175
1176 _STD::advance (__middle, __half);
1177
1178 if (__comp (*__middle, __val)) {
1179 __first = __middle;
1180 ++__first;
1181 __dist = __dist - __half - 1;
1182 }
1183 else
1184 __dist = __half;
1185 }
1186 return __first;
1187}
1188
1189
1190_EXPORT
1191template <class _RandomAccessIter, class _TypeT, class _Compare,
1192 class _Dist>
1193_RandomAccessIter __lower_bound (_RandomAccessIter __first,
1194 _RandomAccessIter __last,
1195 const _TypeT& __val,
1196 _Compare __comp,
1197 _Dist*,
1198 random_access_iterator_tag)
1199{
1200 _RWSTD_ASSERT_RANGE (__first, __last);
1201
1202 for (_Dist __dist = __last - __first; __dist > 0; ) {
1203
1204 const _Dist __half = __dist / 2;
1205 const _RandomAccessIter __middle = __first + __half;
1206
1207 if (__comp (*__middle, __val)) {
1208 __first = __middle + 1;
1209 __dist = __dist - __half - 1;
1210 }
1211 else
1212 __dist = __half;
1213 }
1214
1215 return __first;
1216}
1217
1218
1219_EXPORT
1220template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
1221_FwdIter __upper_bound (_FwdIter __first, _FwdIter __last,
1222 const _TypeT& __val, _Compare __comp,
1223 _Dist*, forward_iterator_tag)
1224{
1225 _RWSTD_ASSERT_RANGE (__first, __last);
1226
1227 for (_Dist __dist = _DISTANCE (__first, __last, _Dist); __dist; ) {
1228
1229 const _Dist __half = __dist / 2;
1230 _FwdIter __middle = __first;
1231
1232 _STD::advance (__middle, __half);
1233
1234 if (__comp (__val, *__middle))
1235 __dist = __half;
1236 else {
1237 __first = __middle;
1238 ++__first;
1239 __dist = __dist - __half - 1;
1240 }
1241 }
1242
1243 return __first;
1244}
1245
1246
1247_EXPORT
1248template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist>
1249_RandomAccessIter __upper_bound (_RandomAccessIter __first,
1250 _RandomAccessIter __last,
1251 const _TypeT& __val,
1252 _Compare __comp, _Dist*,
1253 random_access_iterator_tag)
1254{
1255 _RWSTD_ASSERT_RANGE (__first, __last);
1256
1257 for (_Dist __dist = __last - __first; __dist; ) {
1258
1259 const _Dist __half = __dist / 2;
1260 const _RandomAccessIter __middle = __first + __half;
1261
1262 if (__comp (__val, *__middle))
1263 __dist = __half;
1264 else {
1265 __first = __middle + 1;
1266 __dist = __dist - __half - 1;
1267 }
1268 }
1269
1270 return __first;
1271}
1272
1273
1274_EXPORT
1275template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
1276pair<_FwdIter, _FwdIter>
1277__equal_range (_FwdIter __first, _FwdIter __last, const _TypeT& __val,
1278 _Compare __comp, _Dist*, forward_iterator_tag)
1279{
1280 _RWSTD_ASSERT_RANGE (__first, __last);
1281
1282 for (_Dist __dist = _DISTANCE (__first, __last, _Dist); __dist; ) {
1283
1284 const _Dist __half = __dist / 2;
1285 _FwdIter __middle = __first;
1286
1287 _STD::advance (__middle, __half);
1288
1289 if (__comp (*__middle, __val)) {
1290 __first = __middle;
1291 ++__first;
1292 __dist = __dist - __half - 1;
1293 }
1294 else if (__comp (__val, *__middle))
1295 __dist = __half;
1296 else {
1297 const _FwdIter __left =
1298 _STD::lower_bound (__first, __middle, __val, __comp);
1299
1300 _STD::advance (__first, __dist);
1301
1302 const _FwdIter __right =
1303 _STD::upper_bound (++__middle, __first, __val, __comp);
1304
1305 return pair<_FwdIter, _FwdIter>(__left, __right);
1306 }
1307 }
1308
1309 return pair<_FwdIter, _FwdIter>(__first, __first);
1310}
1311
1312
1313_EXPORT
1314template <class _RandomAccessIter, class _TypeT, class _Compare,
1315 class _Dist>
1316pair<_RandomAccessIter, _RandomAccessIter>
1317__equal_range (_RandomAccessIter __first, _RandomAccessIter __last,
1318 const _TypeT& __val, _Compare __comp, _Dist*,
1319 random_access_iterator_tag)
1320{
1321 _RWSTD_ASSERT_RANGE (__first, __last);
1322
1323 for (_Dist __dist = __last - __first; __dist; ) {
1324
1325 const _Dist __half = __dist / 2;
1326 const _RandomAccessIter __middle = __first + __half;
1327
1328 if (__comp (*__middle, __val)) {
1329 __first = __middle + 1;
1330 __dist = __dist - __half - 1;
1331 }
1332 else if (__comp (__val, *__middle))
1333 __dist = __half;
1334 else {
1335 const _RandomAccessIter __left =
1336 _STD::lower_bound (__first, __middle, __val, __comp);
1337
1338 const _RandomAccessIter __right =
1339 _STD::upper_bound (__middle + 1, __first + __dist,
1340 __val, __comp);
1341
1342 return pair<_RandomAccessIter, _RandomAccessIter>(__left, __right);
1343 }
1344 }
1345
1346 return pair<_RandomAccessIter, _RandomAccessIter>(__first, __first);
1347}
1348
1349//
1350// Merge
1351//
1352
1353_EXPORT
1354template <class _InputIter1, class _InputIter2, class _OutputIter,
1355 class _Compare>
1356_OutputIter merge (_InputIter1 __first1, _InputIter1 __last1,
1357 _InputIter2 __first2, _InputIter2 __last2,
1358 _OutputIter __res, _Compare __comp)
1359{
1360 _RWSTD_ASSERT_RANGE (__first1, __last1);
1361 _RWSTD_ASSERT_RANGE (__first2, __last2);
1362
1363 for (; !(__first1 == __last1) && !(__first2 == __last2); ++__res) {
1364 if (__comp (*__first2, *__first1)) {
1365 *__res = *__first2;
1366 ++__first2;
1367 }
1368 else {
1369 *__res = *__first1;
1370 ++__first1;
1371 }
1372 }
1373 return _STD::copy (__first2, __last2, _STD::copy(__first1, __last1, __res));
1374}
1375
1376
1377_EXPORT
1378template <class _BidirIter, class _Dist, class _Compare>
1379void __merge_without_buffer (_BidirIter __first,
1380 _BidirIter __middle,
1381 _BidirIter __last,
1382 _Dist __dist1, _Dist __dist2,
1383 _Compare __comp)
1384{
1385 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
1386
1387 if (__dist1 == 0 || __dist2 == 0)
1388 return;
1389
1390 if (__dist1 + __dist2 == 2) {
1391 if (__comp (*__middle, *__first))
1392 _STD::iter_swap (__first, __middle);
1393 return;
1394 }
1395
1396 _BidirIter __first_cut = __first;
1397 _BidirIter __second_cut = __middle;
1398 _Dist __dist11;
1399 _Dist __dist22;
1400
1401 if (__dist1 > __dist2) {
1402 __dist11 = __dist1 / 2;
1403 _STD::advance (__first_cut, __dist11);
1404 __second_cut = _STD::lower_bound (__middle, __last,
1405 *__first_cut, __comp);
1406 __dist22 = _DISTANCE (__middle, __second_cut, _Dist);
1407 }
1408 else {
1409 __dist22 = __dist2 / 2;
1410 _STD::advance (__second_cut, __dist22);
1411 __first_cut = _STD::upper_bound (__first, __middle,
1412 *__second_cut, __comp);
1413 __dist11 = _DISTANCE (__first, __first_cut, _Dist);
1414 }
1415 _STD::rotate (__first_cut, __middle, __second_cut);
1416
1417 _BidirIter __middle2 = __first_cut;
1418
1419 _STD::advance (__middle2, __dist22);
1420
1421 __merge_without_buffer (__first, __first_cut, __middle2,
1422 __dist11, __dist22, __comp);
1423 __merge_without_buffer (__middle2, __second_cut, __last,
1424 __dist1 - __dist11, __dist2 - __dist22, __comp);
1425}
1426
1427_EXPORT
1428template <class _BidirIter1, class _BidirIter2, class _Dist>
1429_BidirIter1 __rotate_adaptive (_BidirIter1 __first,
1430 _BidirIter1 __middle,
1431 _BidirIter1 __last,
1432 _Dist __dist1, _Dist __dist2,
1433 _BidirIter2 __buf,
1434 _Dist __buf_size)
1435{
1436 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
1437
1438 if (__dist1 > __dist2 && __dist2 <= __buf_size) {
1439 _BidirIter2 __buf_end = _STD::copy (__middle, __last, __buf);
1440 _STD::copy_backward (__first, __middle, __last);
1441 return _STD::copy (__buf, __buf_end, __first);
1442 }
1443
1444 if (__dist1 <= __buf_size) {
1445 _BidirIter2 __buf_end = _STD::copy (__first, __middle, __buf);
1446 _STD::copy (__middle, __last, __first);
1447 return _STD::copy_backward (__buf, __buf_end, __last);
1448 }
1449
1450 _STD::rotate (__first, __middle, __last);
1451 _STD::advance (__first, __dist2);
1452 return __first;
1453}
1454
1455
1456template <class _BidirIter1, class _BidirIter2,
1457 class _BidirIter3>
1458_BidirIter3 __merge_backward (_BidirIter1 __first1,
1459 _BidirIter1 __last1,
1460 _BidirIter2 __first2,
1461 _BidirIter2 __last2,
1462 _BidirIter3 __res)
1463{
1464 _RWSTD_ASSERT_RANGE (__first1, __last1);
1465 _RWSTD_ASSERT_RANGE (__first2, __last2);
1466
1467 if (__first1 == __last1)
1468 return _STD::copy_backward (__first2, __last2, __res);
1469
1470 if (__first2 == __last2)
1471 return _STD::copy_backward (__first1, __last1, __res);
1472
1473 for (--__last1, --__last2; ; ) {
1474 if (*__last2 < *__last1) {
1475 *--__res = *__last1;
1476 if (__first1 == __last1)
1477 return _STD::copy_backward (__first2, ++__last2, __res);
1478 --__last1;
1479 }
1480 else {
1481 *--__res = *__last2;
1482 if (__first2 == __last2)
1483 return _STD::copy_backward (__first1, ++__last1, __res);
1484 --__last2;
1485 }
1486 }
1487}
1488
1489
1490_EXPORT
1491template <class _BidirIter1, class _BidirIter2,
1492 class _BidirIter3, class _Compare>
1493_BidirIter3 __merge_backward (_BidirIter1 __first1,
1494 _BidirIter1 __last1,
1495 _BidirIter2 __first2,
1496 _BidirIter2 __last2,
1497 _BidirIter3 __res,
1498 _Compare __comp)
1499{
1500 _RWSTD_ASSERT_RANGE (__first1, __last1);
1501 _RWSTD_ASSERT_RANGE (__first2, __last2);
1502
1503 if (__first1 == __last1)
1504 return _STD::copy_backward (__first2, __last2, __res);
1505 if (__first2 == __last2)
1506 return _STD::copy_backward (__first1, __last1, __res);
1507
1508 for (--__last1, --__last2; ; ) {
1509 if (__comp (*__last2, *__last1)) {
1510 *--__res = *__last1;
1511 if (__first1 == __last1)
1512 return _STD::copy_backward (__first2, ++__last2, __res);
1513 --__last1;
1514 }
1515 else {
1516 *--__res = *__last2;
1517 if (__first2 == __last2)
1518 return _STD::copy_backward (__first1, ++__last1, __res);
1519 --__last2;
1520 }
1521 }
1522}
1523
1524
1525template <class _BidirIter, class _Dist, class _Pointer, class _Compare>
1526void __merge_adaptive (_BidirIter __first, _BidirIter __middle,
1527 _BidirIter __last,
1528 _Dist __dist1, _Dist __dist2,
1529 _Pointer __buf, _Dist __buf_size,
1530 _Compare __comp)
1531{
1532 _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
1533
1534 if (__dist1 <= __dist2 && __dist1 <= __buf_size)
1535 {
1536 _Pointer __buf_end = _STD::copy (__first, __middle, __buf);
1537 _STD::merge (__buf, __buf_end, __middle, __last, __first, __comp);
1538 }
1539 else if (__dist2 <= __buf_size)
1540 {
1541 _Pointer __buf_end = _STD::copy (__middle, __last, __buf);
1542 __merge_backward (__first, __middle, __buf, __buf_end, __last,
1543 __comp);
1544 }
1545 else
1546 {
1547 _BidirIter __first_cut = __first;
1548 _BidirIter __second_cut = __middle;
1549 _Dist __dist11;
1550 _Dist __dist22;
1551 if (__dist1 > __dist2)
1552 {
1553 __dist11 = __dist1 / 2;
1554 _STD::advance (__first_cut, __dist11);
1555 __second_cut = _STD::lower_bound (__middle, __last, *__first_cut,
1556 __comp);
1557 __dist22 = _DISTANCE (__middle, __second_cut, _Dist);
1558 }
1559 else
1560 {
1561 __dist22 = __dist2 / 2;
1562 _STD::advance (__second_cut, __dist22);
1563 __first_cut = _STD::upper_bound (__first, __middle, *__second_cut,
1564 __comp);
1565 __dist11 = _DISTANCE (__first, __first_cut, _Dist);
1566 }
1567 _BidirIter __middle2 =
1568 __rotate_adaptive (__first_cut, __middle, __second_cut,
1569 __dist1 - __dist11, __dist22,
1570 __buf, __buf_size);
1571 __merge_adaptive (__first, __first_cut, __middle2,
1572 __dist11, __dist22,
1573 __buf, __buf_size, __comp);
1574 __merge_adaptive (__middle2, __second_cut, __last,
1575 __dist1 - __dist11, __dist2 - __dist22,
1576 __buf, __buf_size, __comp);
1577 }
1578}
1579
1580
1581_EXPORT
1582template <class _BidirIter, class _Dist, class _TypeT, class _Compare>
1583void __inplace_merge (_BidirIter __first, _BidirIter __middle,
1584 _BidirIter __last, _Dist*, _TypeT*, _Compare __comp)
1585{
1586 _Dist __dist1 = _DISTANCE (__first, __middle, _Dist);
1587 _Dist __dist2 = _DISTANCE (__middle, __last, _Dist);
1588
1589 // call an extension of get_temporary_buffer<>() in case partial class
1590 // specialization (and iterator_traits<>) isn't supported by compiler
1591 pair<_TypeT*, _Dist> __pair =
1592 _STD::get_temporary_buffer (__dist1 + __dist2, (_TypeT*)0);
1593
1594 if (__pair.first == 0) {
1595 __merge_without_buffer (__first, __middle, __last, __dist1, __dist2,
1596 __comp);
1597 }
1598 else {
1599 _Dist __dist = (_STD::min)(__pair.second, __dist1 + __dist2);
1600
1601 _STD::fill_n (raw_storage_iterator<_TypeT*, _TypeT> (__pair.first),
1602 __dist, *__first);
1603 __merge_adaptive (__first, __middle, __last, __dist1, __dist2,
1604 __pair.first, __pair.second, __comp);
1605
1606 for (_TypeT *__ptr = __pair.first + __dist;
1607 !(__pair.first == --__ptr); )
1608 (*__ptr).~_TypeT ();
1609
1610 _STD::return_temporary_buffer (__pair.first);
1611 }
1612}
1613
1614//
1615// Set operations. Assume sorted sequences.
1616//
1617
1618
1619// 25.3.5.1 - returns true iff every (not necessarily distinct) element
1620// in [first2, last2) occurs (at least as many times) in [first1, last1)
1621_EXPORT
1622template <class _InputIter1, class _InputIter2, class _Compare>
1623bool includes (_InputIter1 __first1, _InputIter1 __last1,
1624 _InputIter2 __first2, _InputIter2 __last2,
1625 _Compare __comp)
1626{
1627 _RWSTD_ASSERT_RANGE (__first1, __last1);
1628 _RWSTD_ASSERT_RANGE (__first2, __last2);
1629
1630 for (; !(__first1 == __last1) && !(__first2 == __last2); ++__first1) {
1631 if (__comp (*__first2, *__first1))
1632 return false;
1633
1634 if (__comp (*__first1, *__first2) == false)
1635 ++__first2;
1636 }
1637
1638 return __first2 == __last2;
1639}
1640
1641
1642_EXPORT
1643template <class _InputIter1, class _InputIter2, class _OutputIter,
1644 class _Compare>
1645_OutputIter set_union (_InputIter1 __first1, _InputIter1 __last1,
1646 _InputIter2 __first2, _InputIter2 __last2,
1647 _OutputIter __res, _Compare __comp)
1648{
1649 _RWSTD_ASSERT_RANGE (__first1, __last1);
1650 _RWSTD_ASSERT_RANGE (__first2, __last2);
1651
1652 for (; !(__first1 == __last1) && !(__first2 == __last2); ++__res) {
1653 if (__comp (*__first1, *__first2)) {
1654 *__res = *__first1;
1655 ++__first1;
1656 }
1657 else if (__comp (*__first2, *__first1)) {
1658 *__res = *__first2;
1659 ++__first2;
1660 }
1661 else {
1662 *__res = *__first1;
1663 ++__first1;
1664 ++__first2;
1665 }
1666 }
1667 return _STD::copy (__first2, __last2,
1668 _STD::copy (__first1, __last1, __res));
1669}
1670
1671
1672_EXPORT
1673template <class _InputIter1, class _InputIter2, class _OutputIter,
1674 class _Compare>
1675_OutputIter set_intersection (_InputIter1 __first1, _InputIter1 __last1,
1676 _InputIter2 __first2, _InputIter2 __last2,
1677 _OutputIter __res, _Compare __comp)
1678{
1679 _RWSTD_ASSERT_RANGE (__first1, __last1);
1680 _RWSTD_ASSERT_RANGE (__first2, __last2);
1681
1682 while (!(__first1 == __last1) && !(__first2 == __last2)) {
1683 if (__comp (*__first1, *__first2))
1684 ++__first1;
1685 else if (__comp (*__first2, *__first1))
1686 ++__first2;
1687 else {
1688 *__res = *__first1;
1689 ++__res;
1690 ++__first1;
1691 ++__first2;
1692 }
1693 }
1694
1695 return __res;
1696}
1697
1698
1699_EXPORT
1700template <class _InputIter1, class _InputIter2, class _OutputIter,
1701 class _Compare>
1702_OutputIter set_difference (_InputIter1 __first1, _InputIter1 __last1,
1703 _InputIter2 __first2, _InputIter2 __last2,
1704 _OutputIter __res, _Compare __comp)
1705{
1706 _RWSTD_ASSERT_RANGE (__first1, __last1);
1707 _RWSTD_ASSERT_RANGE (__first2, __last2);
1708
1709 while (!(__first1 == __last1) && !(__first2 == __last2)) {
1710 if (__comp (*__first1, *__first2)) {
1711 *__res = *__first1;
1712 ++__res;
1713 ++__first1;
1714 }
1715 else if (__comp (*__first2, *__first1))
1716 ++__first2;
1717 else {
1718 ++__first1;
1719 ++__first2;
1720 }
1721 }
1722
1723 return _STD::copy (__first1, __last1, __res);
1724}
1725
1726
1727_EXPORT
1728template <class _InputIter1, class _InputIter2, class _OutputIter,
1729 class _Compare>
1730_OutputIter set_symmetric_difference (_InputIter1 __first1,
1731 _InputIter1 __last1,
1732 _InputIter2 __first2,
1733 _InputIter2 __last2,
1734 _OutputIter __res,
1735 _Compare __comp)
1736{
1737 _RWSTD_ASSERT_RANGE (__first1, __last1);
1738 _RWSTD_ASSERT_RANGE (__first2, __last2);
1739
1740 while (!(__first1 == __last1) && !(__first2 == __last2)) {
1741 if (__comp (*__first1, *__first2)) {
1742 *__res = *__first1;
1743 ++__res;
1744 ++__first1;
1745 }
1746 else if (__comp (*__first2, *__first1)) {
1747 *__res = *__first2;
1748 ++__res;
1749 ++__first2;
1750 }
1751 else {
1752 ++__first1;
1753 ++__first2;
1754 }
1755 }
1756
1757 return _STD::copy (__first2, __last2, _STD::copy(__first1, __last1, __res));
1758}
1759
1760//
1761// Minimum and maximum.
1762//
1763
1764
1765_EXPORT
1766template <class _FwdIter, class _Compare>
1767_FwdIter min_element (_FwdIter __first, _FwdIter __last, _Compare __comp)
1768{
1769 _RWSTD_ASSERT_RANGE (__first, __last);
1770
1771 _FwdIter __res = __first;
1772
1773 if (!(__first == __last)) {
1774 while (!(++__first == __last)) {
1775 if (__comp (*__first, *__res))
1776 __res = __first;
1777 }
1778 }
1779
1780 return __res;
1781}
1782
1783
1784_EXPORT
1785template <class _FwdIter, class _Compare>
1786_FwdIter max_element (_FwdIter __first, _FwdIter __last, _Compare __comp)
1787{
1788 _RWSTD_ASSERT_RANGE (__first, __last);
1789
1790 _FwdIter __res = __first;
1791
1792 if (!(__first == __last)) {
1793 while (!(++__first == __last)) {
1794 if (__comp (*__res, *__first))
1795 __res = __first;
1796 }
1797 }
1798
1799 return __res;
1800}
1801
1802//
1803// Permutations.
1804//
1805
1806_EXPORT
1807template <class _BidirIter, class _Compare>
1808bool next_permutation (_BidirIter __first, _BidirIter __last, _Compare __comp)
1809{
1810 _RWSTD_ASSERT_RANGE (__first, __last);
1811
1812 if (__first == __last)
1813 return false;
1814
1815 _BidirIter __i = __first;
1816
1817 if (++__i == __last)
1818 return false;
1819
1820 bool __res;
1821
1822 for (__i = __last, --__i; ; ) {
1823 const _BidirIter __ii = __i;
1824
1825 if (__comp (*--__i, *__ii)) {
1826
1827 _BidirIter __j = __last;
1828
1829 while (__comp (*__i, *--__j) == false);
1830
1831 _STD::iter_swap (__i, __j);
1832
1833 __first = __ii;
1834 __res = true;
1835 break;
1836 }
1837
1838 if (__i == __first) {
1839 __res = false;
1840 break;
1841 }
1842 }
1843
1844 _STD::reverse (__first, __last);
1845
1846 return __res;
1847}
1848
1849
1850_EXPORT
1851template <class _BidirIter, class _Compare>
1852bool prev_permutation (_BidirIter __first, _BidirIter __last, _Compare __comp)
1853{
1854 _RWSTD_ASSERT_RANGE (__first, __last);
1855
1856 if (__first == __last)
1857 return false;
1858
1859 _BidirIter __i = __first;
1860
1861 if (++__i == __last)
1862 return false;
1863
1864 bool __res;
1865
1866 for (__i = __last, --__i; ; ) {
1867 const _BidirIter __ii = __i;
1868
1869 if (__comp (*__ii, *--__i)) {
1870
1871 _BidirIter __j = __last;
1872
1873 while (__comp (*--__j, *__i) == false);
1874
1875 _STD::iter_swap (__i, __j);
1876
1877 __first = __ii;
1878 __res = true;
1879 break;
1880 }
1881
1882 if (__i == __first) {
1883 __res = false;
1884 break;
1885 }
1886 }
1887
1888 _STD::reverse (__first, __last);
1889
1890 return __res;
1891}
1892
1893
1894} // namespace std
equal
bool equal(const T &x, const U &y)
Definition 20.tuple.cnstr.cpp:51
_RWSTD_VALUE_TYPE
#define _RWSTD_VALUE_TYPE(iterT)
Definition _defs.h:1042
_RWSTD_ASSERT_IN_RANGE
#define _RWSTD_ASSERT_IN_RANGE(ign1, ign2, ign3)
Definition _defs.h:1248
_RWSTD_NAMESPACE
#define _RWSTD_NAMESPACE(name)
Definition _defs.h:567
_EXPORT
#define _EXPORT
Definition _defs.h:498
_RWSTD_ASSERT
#define _RWSTD_ASSERT(ignore)
Definition _defs.h:1108
_DISTANCE
#define _DISTANCE(first, last, ignore)
Definition _defs.h:1225
_RWSTD_ASSERT_RANGE
#define _RWSTD_ASSERT_RANGE(ign1, ign2)
Definition _defs.h:1247
_RWSTD_DIFFERENCE_TYPE
#define _RWSTD_DIFFERENCE_TYPE(iterT)
Definition _defs.h:1044
_RWSTD_ITERATOR_CATEGORY
#define _RWSTD_ITERATOR_CATEGORY(iterT, ignore)
Definition _defs.h:1055
std
Definition json.h:5363
Generated by doxygen 1.9.8