Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / f5256e16dfc425c1d466f6308d4026d529ce9e0b / . / include / algorithm
blob: f3412f72600cb8d7d7be16ea78e3f16e82f6343b [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1// -*- C++ -*-
2//===-------------------------- algorithm ---------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +0000[diff] [blame^]4// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_ALGORITHM
12#define _LIBCPP_ALGORITHM
13
14/*
15 algorithm synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22template <class InputIterator, class Predicate>
23 bool
24 all_of(InputIterator first, InputIterator last, Predicate pred);
25
26template <class InputIterator, class Predicate>
27 bool
28 any_of(InputIterator first, InputIterator last, Predicate pred);
29
30template <class InputIterator, class Predicate>
31 bool
32 none_of(InputIterator first, InputIterator last, Predicate pred);
33
34template <class InputIterator, class Function>
35 Function
36 for_each(InputIterator first, InputIterator last, Function f);
37
38template <class InputIterator, class T>
39 InputIterator
40 find(InputIterator first, InputIterator last, const T& value);
41
42template <class InputIterator, class Predicate>
43 InputIterator
44 find_if(InputIterator first, InputIterator last, Predicate pred);
45
46template<class InputIterator, class Predicate>
47 InputIterator
48 find_if_not(InputIterator first, InputIterator last, Predicate pred);
49
50template <class ForwardIterator1, class ForwardIterator2>
51 ForwardIterator1
52 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
53 ForwardIterator2 first2, ForwardIterator2 last2);
54
55template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
56 ForwardIterator1
57 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
58 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
59
60template <class ForwardIterator1, class ForwardIterator2>
61 ForwardIterator1
62 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
63 ForwardIterator2 first2, ForwardIterator2 last2);
64
65template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
66 ForwardIterator1
67 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
68 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
69
70template <class ForwardIterator>
71 ForwardIterator
72 adjacent_find(ForwardIterator first, ForwardIterator last);
73
74template <class ForwardIterator, class BinaryPredicate>
75 ForwardIterator
76 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
77
78template <class InputIterator, class T>
79 typename iterator_traits<InputIterator>::difference_type
80 count(InputIterator first, InputIterator last, const T& value);
81
82template <class InputIterator, class Predicate>
83 typename iterator_traits<InputIterator>::difference_type
84 count_if(InputIterator first, InputIterator last, Predicate pred);
85
86template <class InputIterator1, class InputIterator2>
87 pair<InputIterator1, InputIterator2>
88 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
89
90template <class InputIterator1, class InputIterator2, class BinaryPredicate>
91 pair<InputIterator1, InputIterator2>
92 mismatch(InputIterator1 first1, InputIterator1 last1,
93 InputIterator2 first2, BinaryPredicate pred);
94
95template <class InputIterator1, class InputIterator2>
96 bool
97 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
98
99template <class InputIterator1, class InputIterator2, class BinaryPredicate>
100 bool
101 equal(InputIterator1 first1, InputIterator1 last1,
102 InputIterator2 first2, BinaryPredicate pred);
103
104template<class ForwardIterator1, class ForwardIterator2>
105 bool
106 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
107 ForwardIterator2 first2);
108
109template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
110 bool
111 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
112 ForwardIterator2 first2, BinaryPredicate pred);
113
114template <class ForwardIterator1, class ForwardIterator2>
115 ForwardIterator1
116 search(ForwardIterator1 first1, ForwardIterator1 last1,
117 ForwardIterator2 first2, ForwardIterator2 last2);
118
119template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
120 ForwardIterator1
121 search(ForwardIterator1 first1, ForwardIterator1 last1,
122 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
123
124template <class ForwardIterator, class Size, class T>
125 ForwardIterator
126 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
127
128template <class ForwardIterator, class Size, class T, class BinaryPredicate>
129 ForwardIterator
130 search_n(ForwardIterator first, ForwardIterator last,
131 Size count, const T& value, BinaryPredicate pred);
132
133template <class InputIterator, class OutputIterator>
134 OutputIterator
135 copy(InputIterator first, InputIterator last, OutputIterator result);
136
137template<class InputIterator, class OutputIterator, class Predicate>
138 OutputIterator
139 copy_if(InputIterator first, InputIterator last,
140 OutputIterator result, Predicate pred);
141
142template<class InputIterator, class Size, class OutputIterator>
143 OutputIterator
144 copy_n(InputIterator first, Size n, OutputIterator result);
145
146template <class BidirectionalIterator1, class BidirectionalIterator2>
147 BidirectionalIterator2
148 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
149 BidirectionalIterator2 result);
150
151template <class ForwardIterator1, class ForwardIterator2>
152 ForwardIterator2
153 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
154
155template <class ForwardIterator1, class ForwardIterator2>
156 void
157 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
158
159template <class InputIterator, class OutputIterator, class UnaryOperation>
160 OutputIterator
161 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
162
163template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
164 OutputIterator
165 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
166 OutputIterator result, BinaryOperation binary_op);
167
168template <class ForwardIterator, class T>
169 void
170 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
171
172template <class ForwardIterator, class Predicate, class T>
173 void
174 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
175
176template <class InputIterator, class OutputIterator, class T>
177 OutputIterator
178 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
179 const T& old_value, const T& new_value);
180
181template <class InputIterator, class OutputIterator, class Predicate, class T>
182 OutputIterator
183 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
184
185template <class ForwardIterator, class T>
186 void
187 fill(ForwardIterator first, ForwardIterator last, const T& value);
188
189template <class OutputIterator, class Size, class T>
190 OutputIterator
191 fill_n(OutputIterator first, Size n, const T& value);
192
193template <class ForwardIterator, class Generator>
194 void
195 generate(ForwardIterator first, ForwardIterator last, Generator gen);
196
197template <class OutputIterator, class Size, class Generator>
198 OutputIterator
199 generate_n(OutputIterator first, Size n, Generator gen);
200
201template <class ForwardIterator, class T>
202 ForwardIterator
203 remove(ForwardIterator first, ForwardIterator last, const T& value);
204
205template <class ForwardIterator, class Predicate>
206 ForwardIterator
207 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
208
209template <class InputIterator, class OutputIterator, class T>
210 OutputIterator
211 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
212
213template <class InputIterator, class OutputIterator, class Predicate>
214 OutputIterator
215 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
216
217template <class ForwardIterator>
218 ForwardIterator
219 unique(ForwardIterator first, ForwardIterator last);
220
221template <class ForwardIterator, class BinaryPredicate>
222 ForwardIterator
223 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
224
225template <class InputIterator, class OutputIterator>
226 OutputIterator
227 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
228
229template <class InputIterator, class OutputIterator, class BinaryPredicate>
230 OutputIterator
231 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
232
233template <class BidirectionalIterator>
234 void
235 reverse(BidirectionalIterator first, BidirectionalIterator last);
236
237template <class BidirectionalIterator, class OutputIterator>
238 OutputIterator
239 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
240
241template <class ForwardIterator>
242 ForwardIterator
243 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
244
245template <class ForwardIterator, class OutputIterator>
246 OutputIterator
247 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
248
249template <class RandomAccessIterator>
250 void
251 random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
252
253template <class RandomAccessIterator, class RandomNumberGenerator>
254 void
255 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
256
257template <class InputIterator, class Predicate>
258 bool
259 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
260
261template <class ForwardIterator, class Predicate>
262 ForwardIterator
263 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
264
265template <class InputIterator, class OutputIterator1,
266 class OutputIterator2, class Predicate>
267 pair<OutputIterator1, OutputIterator2>
268 partition_copy(InputIterator first, InputIterator last,
269 OutputIterator1 out_true, OutputIterator2 out_false,
270 Predicate pred);
271
272template <class ForwardIterator, class Predicate>
273 ForwardIterator
274 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
275
276template<class ForwardIterator, class Predicate>
277 ForwardIterator
278 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
279
280template <class ForwardIterator>
281 bool
282 is_sorted(ForwardIterator first, ForwardIterator last);
283
284template <class ForwardIterator, class Compare>
285 bool
286 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
287
288template<class ForwardIterator>
289 ForwardIterator
290 is_sorted_until(ForwardIterator first, ForwardIterator last);
291
292template <class ForwardIterator, class Compare>
293 ForwardIterator
294 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
295
296template <class RandomAccessIterator>
297 void
298 sort(RandomAccessIterator first, RandomAccessIterator last);
299
300template <class RandomAccessIterator, class Compare>
301 void
302 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
303
304template <class RandomAccessIterator>
305 void
306 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
307
308template <class RandomAccessIterator, class Compare>
309 void
310 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
311
312template <class RandomAccessIterator>
313 void
314 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
315
316template <class RandomAccessIterator, class Compare>
317 void
318 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
319
320template <class InputIterator, class RandomAccessIterator>
321 RandomAccessIterator
322 partial_sort_copy(InputIterator first, InputIterator last,
323 RandomAccessIterator result_first, RandomAccessIterator result_last);
324
325template <class InputIterator, class RandomAccessIterator, class Compare>
326 RandomAccessIterator
327 partial_sort_copy(InputIterator first, InputIterator last,
328 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
329
330template <class RandomAccessIterator>
331 void
332 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
333
334template <class RandomAccessIterator, class Compare>
335 void
336 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
337
338template <class ForwardIterator, class T>
339 ForwardIterator
340 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
341
342template <class ForwardIterator, class T, class Compare>
343 ForwardIterator
344 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
345
346template <class ForwardIterator, class T>
347 ForwardIterator
348 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
349
350template <class ForwardIterator, class T, class Compare>
351 ForwardIterator
352 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
353
354template <class ForwardIterator, class T>
355 pair<ForwardIterator, ForwardIterator>
356 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
357
358template <class ForwardIterator, class T, class Compare>
359 pair<ForwardIterator, ForwardIterator>
360 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
361
362template <class ForwardIterator, class T>
363 bool
364 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
365
366template <class ForwardIterator, class T, class Compare>
367 bool
368 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
369
370template <class InputIterator1, class InputIterator2, class OutputIterator>
371 OutputIterator
372 merge(InputIterator1 first1, InputIterator1 last1,
373 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
374
375template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
376 OutputIterator
377 merge(InputIterator1 first1, InputIterator1 last1,
378 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
379
380template <class BidirectionalIterator>
381 void
382 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
383
384template <class BidirectionalIterator, class Compare>
385 void
386 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
387
388template <class InputIterator1, class InputIterator2>
389 bool
390 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
391
392template <class InputIterator1, class InputIterator2, class Compare>
393 bool
394 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
395
396template <class InputIterator1, class InputIterator2, class OutputIterator>
397 OutputIterator
398 set_union(InputIterator1 first1, InputIterator1 last1,
399 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
400
401template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
402 OutputIterator
403 set_union(InputIterator1 first1, InputIterator1 last1,
404 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
405
406template <class InputIterator1, class InputIterator2, class OutputIterator>
407 OutputIterator
408 set_intersection(InputIterator1 first1, InputIterator1 last1,
409 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
410
411template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
412 OutputIterator
413 set_intersection(InputIterator1 first1, InputIterator1 last1,
414 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
415
416template <class InputIterator1, class InputIterator2, class OutputIterator>
417 OutputIterator
418 set_difference(InputIterator1 first1, InputIterator1 last1,
419 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
420
421template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
422 OutputIterator
423 set_difference(InputIterator1 first1, InputIterator1 last1,
424 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
425
426template <class InputIterator1, class InputIterator2, class OutputIterator>
427 OutputIterator
428 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
429 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
430
431template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
432 OutputIterator
433 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
434 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
435
436template <class RandomAccessIterator>
437 void
438 push_heap(RandomAccessIterator first, RandomAccessIterator last);
439
440template <class RandomAccessIterator, class Compare>
441 void
442 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
443
444template <class RandomAccessIterator>
445 void
446 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
447
448template <class RandomAccessIterator, class Compare>
449 void
450 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
451
452template <class RandomAccessIterator>
453 void
454 make_heap(RandomAccessIterator first, RandomAccessIterator last);
455
456template <class RandomAccessIterator, class Compare>
457 void
458 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
459
460template <class RandomAccessIterator>
461 void
462 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
463
464template <class RandomAccessIterator, class Compare>
465 void
466 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
467
468template <class RandomAccessIterator>
469 bool
470 is_heap(RandomAccessIterator first, RandomAccessiterator last);
471
472template <class RandomAccessIterator, class Compare>
473 bool
474 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
475
476template <class RandomAccessIterator>
477 RandomAccessIterator
478 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
479
480template <class RandomAccessIterator, class Compare>
481 RandomAccessIterator
482 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
483
484template <class T>
485 const T&
486 min(const T& a, const T& b);
487
488template <class T, class Compare>
489 const T&
490 min(const T& a, const T& b, Compare comp);
491
492template <class T>
493 const T&
494 max(const T& a, const T& b);
495
496template <class T, class Compare>
497 const T&
498 max(const T& a, const T& b, Compare comp);
499
500template <class ForwardIterator>
501 ForwardIterator
502 min_element(ForwardIterator first, ForwardIterator last);
503
504template <class ForwardIterator, class Compare>
505 ForwardIterator
506 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
507
508template <class ForwardIterator>
509 ForwardIterator
510 max_element(ForwardIterator first, ForwardIterator last);
511
512template <class ForwardIterator, class Compare>
513 ForwardIterator
514 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
515
516template <class InputIterator1, class InputIterator2>
517 bool
518 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
519
520template <class InputIterator1, class InputIterator2, class Compare>
521 bool
522 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
523 InputIterator2 first2, InputIterator2 last2, Compare comp);
524
525template <class BidirectionalIterator>
526 bool
527 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
528
529template <class BidirectionalIterator, class Compare>
530 bool
531 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
532
533template <class BidirectionalIterator>
534 bool
535 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
536
537template <class BidirectionalIterator, class Compare>
538 bool
539 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
540
541} // std
542
543*/
544
545#include <__config>
546#include <initializer_list>
547#include <type_traits>
548#include <cstring>
549#include <utility>
550#include <memory>
551#include <iterator>
552#ifdef _LIBCPP_DEBUG
553#include <cassert>
554#endif
555//#include <cstdlib>
556#define RAND_MAX 0x7fffffff // #include <cstdlib>
557extern "C" int rand(void); // #include <cstdlib>
558
559#pragma GCC system_header
560
561_LIBCPP_BEGIN_NAMESPACE_STD
562
563using ::rand; // #include <cstdlib>
564
565template <class _T1, class _T2 = _T1>
566struct __equal_to
567{
568 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
569 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
570 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
571 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
572};
573
574template <class _T1>
575struct __equal_to<_T1, _T1>
576{
577 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
578};
579
580template <class _T1>
581struct __equal_to<const _T1, _T1>
582{
583 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
584};
585
586template <class _T1>
587struct __equal_to<_T1, const _T1>
588{
589 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
590};
591
592template <class _T1, class _T2 = _T1>
593struct __less
594{
595 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
596 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
597 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
598 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
599};
600
601template <class _T1>
602struct __less<_T1, _T1>
603{
604 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
605};
606
607template <class _T1>
608struct __less<const _T1, _T1>
609{
610 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
611};
612
613template <class _T1>
614struct __less<_T1, const _T1>
615{
616 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
617};
618
619template <class _Predicate>
620class __negate
621{
622private:
623 _Predicate __p_;
624public:
625 _LIBCPP_INLINE_VISIBILITY __negate() {}
626
627 _LIBCPP_INLINE_VISIBILITY
628 explicit __negate(_Predicate __p) : __p_(__p) {}
629
630 template <class _T1>
631 _LIBCPP_INLINE_VISIBILITY
632 bool operator()(const _T1& __x) {return !__p_(__x);}
633
634 template <class _T1, class _T2>
635 _LIBCPP_INLINE_VISIBILITY
636 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
637};
638
639#ifdef _LIBCPP_DEBUG
640
641template <class _Compare>
642struct __debug_less
643{
644 _Compare __comp_;
645 __debug_less(_Compare& __c) : __comp_(__c) {}
646 template <class _Tp, class _Up>
647 bool operator()(const _Tp& __x, const _Up& __y)
648 {
649 bool __r = __comp_(__x, __y);
650 if (__r)
651 assert(!__comp_(__y, __x));
652 return __r;
653 }
654};
655
656#endif // _LIBCPP_DEBUG
657
658// all_of
659
660template <class _InputIterator, class _Predicate>
661inline _LIBCPP_INLINE_VISIBILITY
662bool
663all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
664{
665 for (; __first != __last; ++__first)
666 if (!__pred(*__first))
667 return false;
668 return true;
669}
670
671// any_of
672
673template <class _InputIterator, class _Predicate>
674inline _LIBCPP_INLINE_VISIBILITY
675bool
676any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
677{
678 for (; __first != __last; ++__first)
679 if (__pred(*__first))
680 return true;
681 return false;
682}
683
684// none_of
685
686template <class _InputIterator, class _Predicate>
687inline _LIBCPP_INLINE_VISIBILITY
688bool
689none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
690{
691 for (; __first != __last; ++__first)
692 if (__pred(*__first))
693 return false;
694 return true;
695}
696
697// for_each
698
699template <class _InputIterator, class _Function>
700inline _LIBCPP_INLINE_VISIBILITY
701_Function
702for_each(_InputIterator __first, _InputIterator __last, _Function __f)
703{
704 for (; __first != __last; ++__first)
705 __f(*__first);
706 return _STD::move(__f);
707}
708
709// find
710
711template <class _InputIterator, class _Tp>
712inline _LIBCPP_INLINE_VISIBILITY
713_InputIterator
714find(_InputIterator __first, _InputIterator __last, const _Tp& __value)
715{
716 for (; __first != __last; ++__first)
717 if (*__first == __value)
718 break;
719 return __first;
720}
721
722// find_if
723
724template <class _InputIterator, class _Predicate>
725inline _LIBCPP_INLINE_VISIBILITY
726_InputIterator
727find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
728{
729 for (; __first != __last; ++__first)
730 if (__pred(*__first))
731 break;
732 return __first;
733}
734
735// find_if_not
736
737template<class _InputIterator, class _Predicate>
738inline _LIBCPP_INLINE_VISIBILITY
739_InputIterator
740find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
741{
742 for (; __first != __last; ++__first)
743 if (!__pred(*__first))
744 break;
745 return __first;
746}
747
748// find_end
749
750template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
751_ForwardIterator1
752__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
753 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
754 forward_iterator_tag, forward_iterator_tag)
755{
756 // modeled after search algorithm
757 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
758 if (__first2 == __last2)
759 return __r;
760 while (true)
761 {
762 while (true)
763 {
764 if (__first1 == __last1) // if source exhausted return last correct answer
765 return __r; // (or __last1 if never found)
766 if (__pred(*__first1, *__first2))
767 break;
768 ++__first1;
769 }
770 // *__first1 matches *__first2, now match elements after here
771 _ForwardIterator1 __m1 = __first1;
772 _ForwardIterator2 __m2 = __first2;
773 while (true)
774 {
775 if (++__m2 == __last2)
776 { // Pattern exhaused, record answer and search for another one
777 __r = __first1;
778 ++__first1;
779 break;
780 }
781 if (++__m1 == __last1) // Source exhausted, return last answer
782 return __r;
783 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
784 {
785 ++__first1;
786 break;
787 } // else there is a match, check next elements
788 }
789 }
790}
791
792template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
793_BidirectionalIterator1
794__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
795 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
796 bidirectional_iterator_tag, bidirectional_iterator_tag)
797{
798 // modeled after search algorithm (in reverse)
799 if (__first2 == __last2)
800 return __last1; // Everything matches an empty sequence
801 _BidirectionalIterator1 __l1 = __last1;
802 _BidirectionalIterator2 __l2 = __last2;
803 --__l2;
804 while (true)
805 {
806 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
807 while (true)
808 {
809 if (__first1 == __l1) // return __last1 if no element matches *__first2
810 return __last1;
811 if (__pred(*--__l1, *__l2))
812 break;
813 }
814 // *__l1 matches *__l2, now match elements before here
815 _BidirectionalIterator1 __m1 = __l1;
816 _BidirectionalIterator2 __m2 = __l2;
817 while (true)
818 {
819 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
820 return __m1;
821 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
822 return __last1;
823 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
824 {
825 break;
826 } // else there is a match, check next elements
827 }
828 }
829}
830
831template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
832_RandomAccessIterator1
833__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
834 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
835 random_access_iterator_tag, random_access_iterator_tag)
836{
837 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
838 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
839 if (__len2 == 0)
840 return __last1;
841 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
842 if (__len1 < __len2)
843 return __last1;
844 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
845 _RandomAccessIterator1 __l1 = __last1;
846 _RandomAccessIterator2 __l2 = __last2;
847 --__l2;
848 while (true)
849 {
850 while (true)
851 {
852 if (__s == __l1)
853 return __last1;
854 if (__pred(*--__l1, *__l2))
855 break;
856 }
857 _RandomAccessIterator1 __m1 = __l1;
858 _RandomAccessIterator2 __m2 = __l2;
859 while (true)
860 {
861 if (__m2 == __first2)
862 return __m1;
863 // no need to check range on __m1 because __s guarantees we have enough source
864 if (!__pred(*--__m1, *--__m2))
865 {
866 break;
867 }
868 }
869 }
870}
871
872template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
873inline _LIBCPP_INLINE_VISIBILITY
874_ForwardIterator1
875find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
876 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
877{
878 return _STD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
879 (__first1, __last1, __first2, __last2, __pred,
880 typename iterator_traits<_ForwardIterator1>::iterator_category(),
881 typename iterator_traits<_ForwardIterator2>::iterator_category());
882}
883
884template <class _ForwardIterator1, class _ForwardIterator2>
885inline _LIBCPP_INLINE_VISIBILITY
886_ForwardIterator1
887find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
888 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
889{
890 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
891 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
892 return _STD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
893}
894
895// find_first_of
896
897template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
898_ForwardIterator1
899find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
900 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
901{
902 for (; __first1 != __last1; ++__first1)
903 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
904 if (__pred(*__first1, *__j))
905 return __first1;
906 return __last1;
907}
908
909template <class _ForwardIterator1, class _ForwardIterator2>
910inline _LIBCPP_INLINE_VISIBILITY
911_ForwardIterator1
912find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
913 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
914{
915 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
916 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
917 return _STD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
918}
919
920// adjacent_find
921
922template <class _ForwardIterator, class _BinaryPredicate>
923inline _LIBCPP_INLINE_VISIBILITY
924_ForwardIterator
925adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
926{
927 if (__first != __last)
928 {
929 _ForwardIterator __i = __first;
930 while (++__i != __last)
931 {
932 if (__pred(*__first, *__i))
933 return __first;
934 __first = __i;
935 }
936 }
937 return __last;
938}
939
940template <class _ForwardIterator>
941inline _LIBCPP_INLINE_VISIBILITY
942_ForwardIterator
943adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
944{
945 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
946 return _STD::adjacent_find(__first, __last, __equal_to<__v>());
947}
948
949// count
950
951template <class _InputIterator, class _Tp>
952inline _LIBCPP_INLINE_VISIBILITY
953typename iterator_traits<_InputIterator>::difference_type
954count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
955{
956 typename iterator_traits<_InputIterator>::difference_type __r(0);
957 for (; __first != __last; ++__first)
958 if (*__first == __value)
959 ++__r;
960 return __r;
961}
962
963// count_if
964
965template <class _InputIterator, class _Predicate>
966inline _LIBCPP_INLINE_VISIBILITY
967typename iterator_traits<_InputIterator>::difference_type
968count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
969{
970 typename iterator_traits<_InputIterator>::difference_type __r(0);
971 for (; __first != __last; ++__first)
972 if (__pred(*__first))
973 ++__r;
974 return __r;
975}
976
977// mismatch
978
979template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
980inline _LIBCPP_INLINE_VISIBILITY
981pair<_InputIterator1, _InputIterator2>
982mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
983 _InputIterator2 __first2, _BinaryPredicate __pred)
984{
985 for (; __first1 != __last1; ++__first1, ++__first2)
986 if (!__pred(*__first1, *__first2))
987 break;
988 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
989}
990
991template <class _InputIterator1, class _InputIterator2>
992inline _LIBCPP_INLINE_VISIBILITY
993pair<_InputIterator1, _InputIterator2>
994mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
995{
996 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
997 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
998 return _STD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
999}
1000
1001// equal
1002
1003template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1004inline _LIBCPP_INLINE_VISIBILITY
1005bool
1006equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1007{
1008 for (; __first1 != __last1; ++__first1, ++__first2)
1009 if (!__pred(*__first1, *__first2))
1010 return false;
1011 return true;
1012}
1013
1014template <class _InputIterator1, class _InputIterator2>
1015inline _LIBCPP_INLINE_VISIBILITY
1016bool
1017equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1018{
1019 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1020 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1021 return _STD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1022}
1023
1024// is_permutation
1025
1026template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1027bool
1028is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1029 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1030{
1031 // shorten sequences as much as possible by lopping of any equal parts
1032 for (; __first1 != __last1; ++__first1, ++__first2)
1033 if (!__pred(*__first1, *__first2))
1034 goto __not_done;
1035 return true;
1036__not_done:
1037 // __first1 != __last1 && *__first1 != *__first2
1038 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1039 _D1 __l1 = _STD::distance(__first1, __last1);
1040 if (__l1 == _D1(1))
1041 return false;
1042 _ForwardIterator2 __last2 = _STD::next(__first2, __l1);
1043 // For each element in [f1, l1) see if there are the same number of
1044 // equal elements in [f2, l2)
1045 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1046 {
1047 // Have we already counted the number of *__i in [f1, l1)?
1048 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1049 if (__pred(*__j, *__i))
1050 goto __next_iter;
1051 {
1052 // Count number of *__i in [f2, l2)
1053 _D1 __c2 = 0;
1054 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1055 if (__pred(*__i, *__j))
1056 ++__c2;
1057 if (__c2 == 0)
1058 return false;
1059 // Count number of *__i in [__i, l1) (we can start with 1)
1060 _D1 __c1 = 1;
1061 for (_ForwardIterator1 __j = _STD::next(__i); __j != __last1; ++__j)
1062 if (__pred(*__i, *__j))
1063 ++__c1;
1064 if (__c1 != __c2)
1065 return false;
1066 }
1067__next_iter:;
1068 }
1069 return true;
1070}
1071
1072template<class _ForwardIterator1, class _ForwardIterator2>
1073inline _LIBCPP_INLINE_VISIBILITY
1074bool
1075is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1076 _ForwardIterator2 __first2)
1077{
1078 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1079 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1080 return _STD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1081}
1082
1083// search
1084
1085template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1086_ForwardIterator1
1087__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1088 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1089 forward_iterator_tag, forward_iterator_tag)
1090{
1091 if (__first2 == __last2)
1092 return __first1; // Everything matches an empty sequence
1093 while (true)
1094 {
1095 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1096 while (true)
1097 {
1098 if (__first1 == __last1) // return __last1 if no element matches *__first2
1099 return __last1;
1100 if (__pred(*__first1, *__first2))
1101 break;
1102 ++__first1;
1103 }
1104 // *__first1 matches *__first2, now match elements after here
1105 _ForwardIterator1 __m1 = __first1;
1106 _ForwardIterator2 __m2 = __first2;
1107 while (true)
1108 {
1109 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1110 return __first1;
1111 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1112 return __last1;
1113 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1114 {
1115 ++__first1;
1116 break;
1117 } // else there is a match, check next elements
1118 }
1119 }
1120}
1121
1122template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1123_RandomAccessIterator1
1124__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1125 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1126 random_access_iterator_tag, random_access_iterator_tag)
1127{
1128 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1129 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1130 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1131 _D2 __len2 = __last2 - __first2;
1132 if (__len2 == 0)
1133 return __first1;
1134 _D1 __len1 = __last1 - __first1;
1135 if (__len1 < __len2)
1136 return __last1;
1137 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1138 while (true)
1139 {
1140#if !_LIBCPP_UNROLL_LOOPS
1141 while (true)
1142 {
1143 if (__first1 == __s)
1144 return __last1;
1145 if (__pred(*__first1, *__first2))
1146 break;
1147 ++__first1;
1148 }
1149#else // _LIBCPP_UNROLL_LOOPS
1150 for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
1151 {
1152 if (__pred(*__first1, *__first2))
1153 goto __phase2;
1154 if (__pred(*++__first1, *__first2))
1155 goto __phase2;
1156 if (__pred(*++__first1, *__first2))
1157 goto __phase2;
1158 if (__pred(*++__first1, *__first2))
1159 goto __phase2;
1160 ++__first1;
1161 }
1162 switch (__s - __first1)
1163 {
1164 case 3:
1165 if (__pred(*__first1, *__first2))
1166 break;
1167 ++__first1;
1168 case 2:
1169 if (__pred(*__first1, *__first2))
1170 break;
1171 ++__first1;
1172 case 1:
1173 if (__pred(*__first1, *__first2))
1174 break;
1175 case 0:
1176 return __last1;
1177 }
1178 __phase2:
1179#endif // _LIBCPP_UNROLL_LOOPS
1180 _RandomAccessIterator1 __m1 = __first1;
1181 _RandomAccessIterator2 __m2 = __first2;
1182#if !_LIBCPP_UNROLL_LOOPS
1183 while (true)
1184 {
1185 if (++__m2 == __last2)
1186 return __first1;
1187 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1188 if (!__pred(*__m1, *__m2))
1189 {
1190 ++__first1;
1191 break;
1192 }
1193 }
1194#else // _LIBCPP_UNROLL_LOOPS
1195 ++__m2;
1196 ++__m1;
1197 for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
1198 {
1199 if (!__pred(*__m1, *__m2))
1200 goto __continue;
1201 if (!__pred(*++__m1, *++__m2))
1202 goto __continue;
1203 if (!__pred(*++__m1, *++__m2))
1204 goto __continue;
1205 if (!__pred(*++__m1, *++__m2))
1206 goto __continue;
1207 ++__m1;
1208 ++__m2;
1209 }
1210 switch (__last2 - __m2)
1211 {
1212 case 3:
1213 if (!__pred(*__m1, *__m2))
1214 break;
1215 ++__m1;
1216 ++__m2;
1217 case 2:
1218 if (!__pred(*__m1, *__m2))
1219 break;
1220 ++__m1;
1221 ++__m2;
1222 case 1:
1223 if (!__pred(*__m1, *__m2))
1224 break;
1225 case 0:
1226 return __first1;
1227 }
1228 __continue:
1229 ++__first1;
1230#endif // _LIBCPP_UNROLL_LOOPS
1231 }
1232}
1233
1234template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1235inline _LIBCPP_INLINE_VISIBILITY
1236_ForwardIterator1
1237search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1238 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1239{
1240 return _STD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1241 (__first1, __last1, __first2, __last2, __pred,
1242 typename std::iterator_traits<_ForwardIterator1>::iterator_category(),
1243 typename std::iterator_traits<_ForwardIterator2>::iterator_category());
1244}
1245
1246template <class _ForwardIterator1, class _ForwardIterator2>
1247inline _LIBCPP_INLINE_VISIBILITY
1248_ForwardIterator1
1249search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1250 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1251{
1252 typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1;
1253 typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2;
1254 return _STD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1255}
1256
1257// search_n
1258
1259template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1260_ForwardIterator
1261__search_n(_ForwardIterator __first, _ForwardIterator __last,
1262 _Size __count, const _Tp& __value, _BinaryPredicate __pred, forward_iterator_tag)
1263{
1264 if (__count <= 0)
1265 return __first;
1266 while (true)
1267 {
1268 // Find first element in sequence that matchs __value, with a mininum of loop checks
1269 while (true)
1270 {
1271 if (__first == __last) // return __last if no element matches __value
1272 return __last;
1273 if (__pred(*__first, __value))
1274 break;
1275 ++__first;
1276 }
1277 // *__first matches __value, now match elements after here
1278 _ForwardIterator __m = __first;
1279 _Size __c(0);
1280 while (true)
1281 {
1282 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1283 return __first;
1284 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1285 return __last;
1286 if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first
1287 {
1288 __first = __m;
1289 ++__first;
1290 break;
1291 } // else there is a match, check next elements
1292 }
1293 }
1294}
1295
1296template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1297_RandomAccessIterator
1298__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1299 _Size __count, const _Tp& __value, _BinaryPredicate __pred, random_access_iterator_tag)
1300{
1301 if (__count <= 0)
1302 return __first;
1303 _Size __len = static_cast<_Size>(__last - __first);
1304 if (__len < __count)
1305 return __last;
1306 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1307 while (true)
1308 {
1309 // Find first element in sequence that matchs __value, with a mininum of loop checks
1310 while (true)
1311 {
1312 if (__first == __s) // return __last if no element matches __value
1313 return __last;
1314 if (__pred(*__first, __value))
1315 break;
1316 ++__first;
1317 }
1318 // *__first matches __value, now match elements after here
1319 _RandomAccessIterator __m = __first;
1320 _Size __c(0);
1321 while (true)
1322 {
1323 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1324 return __first;
1325 ++__m; // no need to check range on __m because __s guarantees we have enough source
1326 if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first
1327 {
1328 __first = __m;
1329 ++__first;
1330 break;
1331 } // else there is a match, check next elements
1332 }
1333 }
1334}
1335
1336template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1337inline _LIBCPP_INLINE_VISIBILITY
1338_ForwardIterator
1339search_n(_ForwardIterator __first, _ForwardIterator __last,
1340 _Size __count, const _Tp& __value, _BinaryPredicate __pred)
1341{
1342 return _STD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1343 (__first, __last, __count, __value, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
1344}
1345
1346template <class _ForwardIterator, class _Size, class _Tp>
1347inline _LIBCPP_INLINE_VISIBILITY
1348_ForwardIterator
1349search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value)
1350{
1351 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1352 return _STD::search_n(__first, __last, __count, __value, __equal_to<__v, _Tp>());
1353}
1354
1355// copy
1356
1357template <class _Iter>
1358struct __libcpp_is_trivial_iterator
1359{
1360 static const bool value = is_pointer<_Iter>::value;
1361};
1362
1363template <class _Iter>
1364struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1365{
1366 static const bool value = is_pointer<_Iter>::value;
1367};
1368
1369template <class _Iter>
1370struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1371{
1372 static const bool value = is_pointer<_Iter>::value;
1373};
1374
1375template <class _Iter>
1376inline _LIBCPP_INLINE_VISIBILITY
1377_Iter
1378__unwrap_iter(_Iter __i)
1379{
1380 return __i;
1381}
1382
1383template <class _Tp>
1384inline _LIBCPP_INLINE_VISIBILITY
1385typename enable_if
1386<
1387 has_trivial_copy_assign<_Tp>::value,
1388 _Tp*
1389>::type
1390__unwrap_iter(move_iterator<_Tp*> __i)
1391{
1392 return __i.base();
1393}
1394
1395template <class _Tp>
1396inline _LIBCPP_INLINE_VISIBILITY
1397typename enable_if
1398<
1399 has_trivial_copy_assign<_Tp>::value,
1400 _Tp*
1401>::type
1402__unwrap_iter(__wrap_iter<_Tp*> __i)
1403{
1404 return __i.base();
1405}
1406
1407template <class _InputIterator, class _OutputIterator>
1408inline _LIBCPP_INLINE_VISIBILITY
1409_OutputIterator
1410__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1411{
1412 for (; __first != __last; ++__first, ++__result)
1413 *__result = *__first;
1414 return __result;
1415}
1416
1417template <class _Tp, class _Up>
1418inline _LIBCPP_INLINE_VISIBILITY
1419typename enable_if
1420<
1421 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1422 has_trivial_copy_assign<_Up>::value,
1423 _Up*
1424>::type
1425__copy(_Tp* __first, _Tp* __last, _Up* __result)
1426{
1427 const size_t __n = static_cast<size_t>(__last - __first);
1428 _STD::memmove(__result, __first, __n * sizeof(_Up));
1429 return __result + __n;
1430}
1431
1432template <class _InputIterator, class _OutputIterator>
1433inline _LIBCPP_INLINE_VISIBILITY
1434_OutputIterator
1435copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1436{
1437 return _STD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1438}
1439
1440// copy_backward
1441
1442template <class _InputIterator, class _OutputIterator>
1443inline _LIBCPP_INLINE_VISIBILITY
1444_OutputIterator
1445__copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1446{
1447 while (__first != __last)
1448 *--__result = *--__last;
1449 return __result;
1450}
1451
1452template <class _Tp, class _Up>
1453inline _LIBCPP_INLINE_VISIBILITY
1454typename enable_if
1455<
1456 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1457 has_trivial_copy_assign<_Up>::value,
1458 _Up*
1459>::type
1460__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1461{
1462 const size_t __n = static_cast<size_t>(__last - __first);
1463 __result -= __n;
1464 _STD::memmove(__result, __first, __n * sizeof(_Up));
1465 return __result;
1466}
1467
1468template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1469inline _LIBCPP_INLINE_VISIBILITY
1470_BidirectionalIterator2
1471copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1472 _BidirectionalIterator2 __result)
1473{
1474 return _STD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1475}
1476
1477// copy_if
1478
1479template<class _InputIterator, class _OutputIterator, class _Predicate>
1480inline _LIBCPP_INLINE_VISIBILITY
1481_OutputIterator
1482copy_if(_InputIterator __first, _InputIterator __last,
1483 _OutputIterator __result, _Predicate __pred)
1484{
1485 for (; __first != __last; ++__first)
1486 {
1487 if (__pred(*__first))
1488 {
1489 *__result = *__first;
1490 ++__result;
1491 }
1492 }
1493 return __result;
1494}
1495
1496// copy_n
1497
1498template<class _InputIterator, class _Size, class _OutputIterator>
1499inline _LIBCPP_INLINE_VISIBILITY
1500typename enable_if
1501<
1502 __is_input_iterator<_InputIterator>::value &&
1503 !__is_random_access_iterator<_InputIterator>::value,
1504 _OutputIterator
1505>::type
1506copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1507{
1508 for (; __n > 0; --__n, ++__first, ++__result)
1509 *__result = *__first;
1510 return __result;
1511}
1512
1513template<class _InputIterator, class _Size, class _OutputIterator>
1514inline _LIBCPP_INLINE_VISIBILITY
1515typename enable_if
1516<
1517 __is_random_access_iterator<_InputIterator>::value,
1518 _OutputIterator
1519>::type
1520copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1521{
1522 return copy(__first, __first + __n, __result);
1523}
1524
1525// move
1526
1527template <class _InputIterator, class _OutputIterator>
1528inline _LIBCPP_INLINE_VISIBILITY
1529_OutputIterator
1530__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1531{
1532 for (; __first != __last; ++__first, ++__result)
1533 *__result = _STD::move(*__first);
1534 return __result;
1535}
1536
1537template <class _Tp, class _Up>
1538inline _LIBCPP_INLINE_VISIBILITY
1539typename enable_if
1540<
1541 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1542 has_trivial_copy_assign<_Up>::value,
1543 _Up*
1544>::type
1545__move(_Tp* __first, _Tp* __last, _Up* __result)
1546{
1547 const size_t __n = static_cast<size_t>(__last - __first);
1548 _STD::memmove(__result, __first, __n * sizeof(_Up));
1549 return __result + __n;
1550}
1551
1552template <class _InputIterator, class _OutputIterator>
1553inline _LIBCPP_INLINE_VISIBILITY
1554_OutputIterator
1555move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1556{
1557 return _STD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1558}
1559
1560// move_backward
1561
1562template <class _InputIterator, class _OutputIterator>
1563inline _LIBCPP_INLINE_VISIBILITY
1564_OutputIterator
1565__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1566{
1567 while (__first != __last)
1568 *--__result = _STD::move(*--__last);
1569 return __result;
1570}
1571
1572template <class _Tp, class _Up>
1573inline _LIBCPP_INLINE_VISIBILITY
1574typename enable_if
1575<
1576 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1577 has_trivial_copy_assign<_Up>::value,
1578 _Up*
1579>::type
1580__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1581{
1582 const size_t __n = static_cast<size_t>(__last - __first);
1583 __result -= __n;
1584 _STD::memmove(__result, __first, __n * sizeof(_Up));
1585 return __result;
1586}
1587
1588template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1589inline _LIBCPP_INLINE_VISIBILITY
1590_BidirectionalIterator2
1591move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1592 _BidirectionalIterator2 __result)
1593{
1594 return _STD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1595}
1596
1597// iter_swap
1598
1599template <class _ForwardIterator1, class _ForwardIterator2>
1600inline _LIBCPP_INLINE_VISIBILITY
1601void
1602iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1603{
1604 swap(*__a, *__b);
1605}
1606
1607// transform
1608
1609template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1610inline _LIBCPP_INLINE_VISIBILITY
1611_OutputIterator
1612transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1613{
1614 for (; __first != __last; ++__first, ++__result)
1615 *__result = __op(*__first);
1616 return __result;
1617}
1618
1619template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1620inline _LIBCPP_INLINE_VISIBILITY
1621_OutputIterator
1622transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1623 _OutputIterator __result, _BinaryOperation __binary_op)
1624{
1625 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
1626 *__result = __binary_op(*__first1, *__first2);
1627 return __result;
1628}
1629
1630// replace
1631
1632template <class _ForwardIterator, class _Tp>
1633inline _LIBCPP_INLINE_VISIBILITY
1634void
1635replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1636{
1637 for (; __first != __last; ++__first)
1638 if (*__first == __old_value)
1639 *__first = __new_value;
1640}
1641
1642// replace_if
1643
1644template <class _ForwardIterator, class _Predicate, class _Tp>
1645inline _LIBCPP_INLINE_VISIBILITY
1646void
1647replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1648{
1649 for (; __first != __last; ++__first)
1650 if (__pred(*__first))
1651 *__first = __new_value;
1652}
1653
1654// replace_copy
1655
1656template <class _InputIterator, class _OutputIterator, class _Tp>
1657inline _LIBCPP_INLINE_VISIBILITY
1658_OutputIterator
1659replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1660 const _Tp& __old_value, const _Tp& __new_value)
1661{
1662 for (; __first != __last; ++__first, ++__result)
1663 if (*__first == __old_value)
1664 *__result = __new_value;
1665 else
1666 *__result = *__first;
1667 return __result;
1668}
1669
1670// replace_copy_if
1671
1672template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1673inline _LIBCPP_INLINE_VISIBILITY
1674_OutputIterator
1675replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1676 _Predicate __pred, const _Tp& __new_value)
1677{
1678 for (; __first != __last; ++__first, ++__result)
1679 if (__pred(*__first))
1680 *__result = __new_value;
1681 else
1682 *__result = *__first;
1683 return __result;
1684}
1685
1686// fill_n
1687
1688template <class _OutputIterator, class _Size, class _Tp>
1689inline _LIBCPP_INLINE_VISIBILITY
1690_OutputIterator
1691__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, false_type)
1692{
1693 for (; __n > 0; ++__first, --__n)
1694 *__first = __value;
1695 return __first;
1696}
1697
1698template <class _OutputIterator, class _Size, class _Tp>
1699inline _LIBCPP_INLINE_VISIBILITY
1700_OutputIterator
1701__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, true_type)
1702{
1703 if (__n > 0)
1704 _STD::memset(__first, (unsigned char)__value, (size_t)(__n));
1705 return __first + __n;
1706}
1707
1708template <class _OutputIterator, class _Size, class _Tp>
1709inline _LIBCPP_INLINE_VISIBILITY
1710_OutputIterator
1711fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
1712{
1713 return _STD::__fill_n(__first, __n, __value, integral_constant<bool,
1714 is_pointer<_OutputIterator>::value &&
1715 has_trivial_copy_assign<_Tp>::value &&
1716 sizeof(_Tp) == 1>());
1717}
1718
1719// fill
1720
1721template <class _ForwardIterator, class _Tp>
1722inline _LIBCPP_INLINE_VISIBILITY
1723void
1724__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag)
1725{
1726 for (; __first != __last; ++__first)
1727 *__first = __value;
1728}
1729
1730template <class _RandomAccessIterator, class _Tp>
1731inline _LIBCPP_INLINE_VISIBILITY
1732void
1733__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag)
1734{
1735 _STD::fill_n(__first, __last - __first, __value);
1736}
1737
1738template <class _ForwardIterator, class _Tp>
1739inline _LIBCPP_INLINE_VISIBILITY
1740void
1741fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1742{
1743 _STD::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category());
1744}
1745
1746// generate
1747
1748template <class _ForwardIterator, class _Generator>
1749inline _LIBCPP_INLINE_VISIBILITY
1750void
1751generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
1752{
1753 for (; __first != __last; ++__first)
1754 *__first = __gen();
1755}
1756
1757// generate_n
1758
1759template <class _OutputIterator, class _Size, class _Generator>
1760inline _LIBCPP_INLINE_VISIBILITY
1761_OutputIterator
1762generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
1763{
1764 for (; __n > 0; ++__first, --__n)
1765 *__first = __gen();
1766 return __first;
1767}
1768
1769// remove
1770
1771template <class _ForwardIterator, class _Tp>
1772_ForwardIterator
1773remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1774{
1775 __first = _STD::find(__first, __last, __value);
1776 if (__first != __last)
1777 {
1778 _ForwardIterator __i = __first;
1779 while (++__i != __last)
1780 {
1781 if (!(*__i == __value))
1782 {
1783 *__first = _STD::move(*__i);
1784 ++__first;
1785 }
1786 }
1787 }
1788 return __first;
1789}
1790
1791// remove_if
1792
1793template <class _ForwardIterator, class _Predicate>
1794_ForwardIterator
1795remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
1796{
1797 __first = _STD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
1798 (__first, __last, __pred);
1799 if (__first != __last)
1800 {
1801 _ForwardIterator __i = __first;
1802 while (++__i != __last)
1803 {
1804 if (!__pred(*__i))
1805 {
1806 *__first = _STD::move(*__i);
1807 ++__first;
1808 }
1809 }
1810 }
1811 return __first;
1812}
1813
1814// remove_copy
1815
1816template <class _InputIterator, class _OutputIterator, class _Tp>
1817inline _LIBCPP_INLINE_VISIBILITY
1818_OutputIterator
1819remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value)
1820{
1821 for (; __first != __last; ++__first)
1822 {
1823 if (!(*__first == __value))
1824 {
1825 *__result = *__first;
1826 ++__result;
1827 }
1828 }
1829 return __result;
1830}
1831
1832// remove_copy_if
1833
1834template <class _InputIterator, class _OutputIterator, class _Predicate>
1835inline _LIBCPP_INLINE_VISIBILITY
1836_OutputIterator
1837remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
1838{
1839 for (; __first != __last; ++__first)
1840 {
1841 if (!__pred(*__first))
1842 {
1843 *__result = *__first;
1844 ++__result;
1845 }
1846 }
1847 return __result;
1848}
1849
1850// unique
1851
1852template <class _ForwardIterator, class _BinaryPredicate>
1853_ForwardIterator
1854unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1855{
1856 __first = _STD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
1857 (__first, __last, __pred);
1858 if (__first != __last)
1859 {
1860 // ... a a ? ...
1861 // f i
1862 _ForwardIterator __i = __first;
1863 for (++__i; ++__i != __last;)
1864 if (!__pred(*__first, *__i))
1865 *++__first = _STD::move(*__i);
1866 ++__first;
1867 }
1868 return __first;
1869}
1870
1871template <class _ForwardIterator>
1872inline _LIBCPP_INLINE_VISIBILITY
1873_ForwardIterator
1874unique(_ForwardIterator __first, _ForwardIterator __last)
1875{
1876 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1877 return _STD::unique(__first, __last, __equal_to<__v>());
1878}
1879
1880// unique_copy
1881
1882template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
1883_OutputIterator
1884__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
1885 input_iterator_tag, output_iterator_tag)
1886{
1887 if (__first != __last)
1888 {
1889 typename iterator_traits<_InputIterator>::value_type __t(*__first);
1890 *__result = __t;
1891 ++__result;
1892 while (++__first != __last)
1893 {
1894 if (!__pred(__t, *__first))
1895 {
1896 __t = *__first;
1897 *__result = __t;
1898 ++__result;
1899 }
1900 }
1901 }
1902 return __result;
1903}
1904
1905template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
1906_OutputIterator
1907__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
1908 forward_iterator_tag, output_iterator_tag)
1909{
1910 if (__first != __last)
1911 {
1912 _ForwardIterator __i = __first;
1913 *__result = *__i;
1914 ++__result;
1915 while (++__first != __last)
1916 {
1917 if (!__pred(*__i, *__first))
1918 {
1919 *__result = *__first;
1920 ++__result;
1921 __i = __first;
1922 }
1923 }
1924 }
1925 return __result;
1926}
1927
1928template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
1929_ForwardIterator
1930__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
1931 input_iterator_tag, forward_iterator_tag)
1932{
1933 if (__first != __last)
1934 {
1935 *__result = *__first;
1936 while (++__first != __last)
1937 if (!__pred(*__result, *__first))
1938 *++__result = *__first;
1939 ++__result;
1940 }
1941 return __result;
1942}
1943
1944
1945template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
1946inline _LIBCPP_INLINE_VISIBILITY
1947_OutputIterator
1948unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
1949{
1950 return _STD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
1951 (__first, __last, __result, __pred,
1952 typename iterator_traits<_InputIterator>::iterator_category(),
1953 typename iterator_traits<_OutputIterator>::iterator_category());
1954}
1955
1956template <class _InputIterator, class _OutputIterator>
1957inline _LIBCPP_INLINE_VISIBILITY
1958_OutputIterator
1959unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1960{
1961 typedef typename iterator_traits<_InputIterator>::value_type __v;
1962 return _STD::unique_copy(__first, __last, __result, __equal_to<__v>());
1963}
1964
1965// reverse
1966
1967template <class _BidirectionalIterator>
1968inline _LIBCPP_INLINE_VISIBILITY
1969void
1970__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
1971{
1972 while (__first != __last)
1973 {
1974 if (__first == --__last)
1975 break;
1976 swap(*__first, *__last);
1977 ++__first;
1978 }
1979}
1980
1981template <class _RandomAccessIterator>
1982inline _LIBCPP_INLINE_VISIBILITY
1983void
1984__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
1985{
1986 if (__first != __last)
1987 for (; __first < --__last; ++__first)
1988 swap(*__first, *__last);
1989}
1990
1991template <class _BidirectionalIterator>
1992inline _LIBCPP_INLINE_VISIBILITY
1993void
1994reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1995{
1996 _STD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
1997}
1998
1999// reverse_copy
2000
2001template <class _BidirectionalIterator, class _OutputIterator>
2002inline _LIBCPP_INLINE_VISIBILITY
2003_OutputIterator
2004reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2005{
2006 for (; __first != __last; ++__result)
2007 *__result = *--__last;
2008 return __result;
2009}
2010
2011// rotate
2012
2013template <class _ForwardIterator>
2014_ForwardIterator
2015__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, false_type)
2016{
2017 if (__first == __middle)
2018 return __last;
2019 if (__middle == __last)
2020 return __first;
2021 _ForwardIterator __i = __middle;
2022 while (true)
2023 {
2024 swap(*__first, *__i);
2025 ++__first;
2026 if (++__i == __last)
2027 break;
2028 if (__first == __middle)
2029 __middle = __i;
2030 }
2031 _ForwardIterator __r = __first;
2032 if (__first != __middle)
2033 {
2034 __i = __middle;
2035 while (true)
2036 {
2037 swap(*__first, *__i);
2038 ++__first;
2039 if (++__i == __last)
2040 {
2041 if (__first == __middle)
2042 break;
2043 __i = __middle;
2044 }
2045 else if (__first == __middle)
2046 __middle = __i;
2047 }
2048 }
2049 return __r;
2050}
2051
2052template<typename _Integral>
2053inline _LIBCPP_INLINE_VISIBILITY
2054_Integral
2055__gcd(_Integral __x, _Integral __y)
2056{
2057 do
2058 {
2059 _Integral __t = __x % __y;
2060 __x = __y;
2061 __y = __t;
2062 } while (__y);
2063 return __x;
2064}
2065
2066template<typename _RandomAccessIterator>
2067_RandomAccessIterator
2068__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, true_type)
2069{
2070 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2071 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2072
2073 if (__first == __middle)
2074 return __last;
2075 if (__middle == __last)
2076 return __first;
2077 const difference_type __m1 = __middle - __first;
2078 const difference_type __m2 = __last - __middle;
2079 if (__m1 == __m2)
2080 {
2081 _STD::swap_ranges(__first, __middle, __middle);
2082 return __middle;
2083 }
2084 const difference_type __g = __gcd(__m1, __m2);
2085 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2086 {
2087 value_type __t(*--__p);
2088 _RandomAccessIterator __p1 = __p;
2089 _RandomAccessIterator __p2 = __p1 + __m1;
2090 do
2091 {
2092 *__p1 = *__p2;
2093 __p1 = __p2;
2094 const difference_type __d = __last - __p2;
2095 if (__m1 < __d)
2096 __p2 += __m1;
2097 else
2098 __p2 = __first + (__m1 - __d);
2099 } while (__p2 != __p);
2100 *__p1 = __t;
2101 }
2102 return __first + __m2;
2103}
2104
2105template <class _ForwardIterator>
2106inline _LIBCPP_INLINE_VISIBILITY
2107_ForwardIterator
2108rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2109{
2110 return _STD::__rotate(__first, __middle, __last,
2111 integral_constant
2112 <
2113 bool,
2114 is_convertible
2115 <
2116 typename iterator_traits<_ForwardIterator>::iterator_category,
2117 random_access_iterator_tag
2118 >::value &&
2119 has_trivial_copy_assign
2120 <
2121 typename iterator_traits<_ForwardIterator>::value_type
2122 >::value
2123 >());
2124}
2125
2126// rotate_copy
2127
2128template <class _ForwardIterator, class _OutputIterator>
2129inline _LIBCPP_INLINE_VISIBILITY
2130_OutputIterator
2131rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2132{
2133 return _STD::copy(__first, __middle, _STD::copy(__middle, __last, __result));
2134}
2135
2136// min
2137
2138template <class _Tp, class _Compare>
2139inline _LIBCPP_INLINE_VISIBILITY
2140const _Tp&
2141min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2142{
2143 return __comp(__b, __a) ? __b : __a;
2144}
2145
2146template <class _Tp>
2147inline _LIBCPP_INLINE_VISIBILITY
2148const _Tp&
2149min(const _Tp& __a, const _Tp& __b)
2150{
2151 return _STD::min(__a, __b, __less<_Tp>());
2152}
2153
2154// max
2155
2156template <class _Tp, class _Compare>
2157inline _LIBCPP_INLINE_VISIBILITY
2158const _Tp&
2159max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2160{
2161 return __comp(__a, __b) ? __b : __a;
2162}
2163
2164template <class _Tp>
2165inline _LIBCPP_INLINE_VISIBILITY
2166const _Tp&
2167max(const _Tp& __a, const _Tp& __b)
2168{
2169 return _STD::max(__a, __b, __less<_Tp>());
2170}
2171
2172// min_element
2173
2174template <class _ForwardIterator, class _Compare>
2175inline _LIBCPP_INLINE_VISIBILITY
2176_ForwardIterator
2177min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2178{
2179 if (__first != __last)
2180 {
2181 _ForwardIterator __i = __first;
2182 while (++__i != __last)
2183 if (__comp(*__i, *__first))
2184 __first = __i;
2185 }
2186 return __first;
2187}
2188
2189template <class _ForwardIterator>
2190inline _LIBCPP_INLINE_VISIBILITY
2191_ForwardIterator
2192min_element(_ForwardIterator __first, _ForwardIterator __last)
2193{
2194 return _STD::min_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2195}
2196
2197// max_element
2198
2199template <class _ForwardIterator, class _Compare>
2200inline _LIBCPP_INLINE_VISIBILITY
2201_ForwardIterator
2202max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2203{
2204 if (__first != __last)
2205 {
2206 _ForwardIterator __i = __first;
2207 while (++__i != __last)
2208 if (__comp(*__first, *__i))
2209 __first = __i;
2210 }
2211 return __first;
2212}
2213
2214template <class _ForwardIterator>
2215inline _LIBCPP_INLINE_VISIBILITY
2216_ForwardIterator
2217max_element(_ForwardIterator __first, _ForwardIterator __last)
2218{
2219 return _STD::max_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2220}
2221
2222// minmax_element
2223
2224template <class _ForwardIterator, class _Compare>
2225std::pair<_ForwardIterator, _ForwardIterator>
2226minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2227{
2228 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2229 if (__first != __last)
2230 {
2231 if (++__first != __last)
2232 {
2233 if (__comp(*__first, *__result.first))
2234 {
2235 __result.second = __result.first;
2236 __result.first = __first;
2237 }
2238 else
2239 __result.second = __first;
2240 while (++__first != __last)
2241 {
2242 _ForwardIterator __i = __first;
2243 if (++__first == __last)
2244 {
2245 if (__comp(*__i, *__result.first))
2246 __result.first = __i;
2247 else if (!__comp(*__i, *__result.second))
2248 __result.second = __i;
2249 break;
2250 }
2251 else
2252 {
2253 if (__comp(*__first, *__i))
2254 {
2255 if (__comp(*__first, *__result.first))
2256 __result.first = __first;
2257 if (!__comp(*__i, *__result.second))
2258 __result.second = __i;
2259 }
2260 else
2261 {
2262 if (__comp(*__i, *__result.first))
2263 __result.first = __i;
2264 if (!__comp(*__first, *__result.second))
2265 __result.second = __first;
2266 }
2267 }
2268 }
2269 }
2270 }
2271 return __result;
2272}
2273
2274template <class _ForwardIterator>
2275inline _LIBCPP_INLINE_VISIBILITY
2276std::pair<_ForwardIterator, _ForwardIterator>
2277minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2278{
2279 return _STD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2280}
2281
2282// random_shuffle
2283
2284template <unsigned int _Bits>
2285struct __num_bits
2286{
2287 static const int __value = 1 + __num_bits<(_Bits >> 1)>::__value;
2288};
2289
2290template <>
2291struct __num_bits<0>
2292{
2293 static const int __value = 0;
2294};
2295
2296const int __rbits = __num_bits<RAND_MAX>::__value;
2297const int __lbits = static_cast<int>(sizeof(unsigned long) * __CHAR_BIT__);
2298
2299template <int _NBits, bool = _NBits <= __rbits>
2300struct __random_bits
2301{
2302 _LIBCPP_INLINE_VISIBILITY operator unsigned long () const
2303 {return static_cast<unsigned long>(_STD::rand()) >> (__rbits - _NBits);}
2304};
2305
2306template <int _NBits>
2307struct __random_bits<_NBits, false>
2308{
2309 _LIBCPP_INLINE_VISIBILITY operator unsigned long () const
2310 {return static_cast<unsigned long>(_STD::rand()) << (_NBits - __rbits) | __random_bits<_NBits - __rbits>();}
2311};
2312
2313template <int _NBits>
2314inline _LIBCPP_INLINE_VISIBILITY
2315unsigned long
2316__slab_size(unsigned long __n)
2317{
2318 return (1UL << _NBits) / __n;
2319}
2320
2321template <>
2322inline _LIBCPP_INLINE_VISIBILITY
2323unsigned long
2324__slab_size<__lbits>(unsigned long __n)
2325{
2326 if (__n & 1)
2327 return (unsigned long)(~0) / __n;
2328 return (1UL << (__lbits-1)) / (__n >> 1);
2329}
2330
2331template <int _NBits>
2332inline _LIBCPP_INLINE_VISIBILITY
2333unsigned long
2334__scaled_random_number(unsigned long __n)
2335{
2336 const unsigned long __slab = __slab_size<_NBits>(__n);
2337 const unsigned long __usable = __slab * __n;
2338 unsigned long __raw;
2339 do
2340 __raw = __random_bits<_NBits>();
2341 while (__raw >= __usable);
2342 return __raw / __slab;
2343}
2344
2345template <bool __b, unsigned long = __lbits/__rbits> struct __rs_default;
2346
2347template <bool __b>
2348struct __rs_default<__b, 1>
2349{
2350 unsigned long operator()(unsigned long __n = 0) const;
2351};
2352
2353template <bool __b>
2354unsigned long
2355__rs_default<__b, 1>::operator()(unsigned long __n) const
2356{
2357 switch (__n)
2358 {
2359 case 0:
2360 return __random_bits<__lbits>();
2361 case 1:
2362 return 0;
2363 }
2364 if (__n <= (1UL << __rbits))
2365 return __scaled_random_number<__rbits>(__n);
2366 return __scaled_random_number<__lbits>(__n);
2367}
2368
2369template <bool __b>
2370struct __rs_default<__b, 2>
2371{
2372 unsigned long operator()(unsigned long __n = 0) const;
2373};
2374
2375template <bool __b>
2376unsigned long
2377__rs_default<__b, 2>::operator()(unsigned long __n) const
2378{
2379 switch (__n)
2380 {
2381 case 0:
2382 return __random_bits<__lbits>();
2383 case 1:
2384 return 0;
2385 }
2386 int __nb = __rbits;
2387 while (__nb < __lbits && __n > (1UL << __nb))
2388 __nb += _STD::min(__rbits, __lbits - __nb);
2389 switch (__nb)
2390 {
2391 case __rbits:
2392 return __scaled_random_number<__rbits>(__n);
2393 case 2*__rbits:
2394 return __scaled_random_number<2*__rbits>(__n);
2395 }
2396 return __scaled_random_number<__lbits>(__n);
2397}
2398
2399template <class _RandomAccessIterator>
2400void
2401random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2402{
2403 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2404 difference_type __d = __last - __first;
2405 if (__d > 1)
2406 {
2407 for (--__last; __first < __last; ++__first, --__d)
2408 swap(*__first, *(__first
2409 + static_cast<difference_type>(__rs_default<true>()(static_cast<unsigned long>(__d)))));
2410 }
2411}
2412
2413template <class _RandomAccessIterator, class _RandomNumberGenerator>
2414void
2415random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2416#ifdef _LIBCPP_MOVE
2417 _RandomNumberGenerator&& __rand)
2418#else
2419 _RandomNumberGenerator& __rand)
2420#endif
2421{
2422 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2423 difference_type __d = __last - __first;
2424 if (__d > 1)
2425 {
2426 for (--__last; __first < __last; ++__first, --__d)
2427 swap(*__first, *(__first + __rand(__d)));
2428 }
2429}
2430
2431template <class _InputIterator, class _Predicate>
2432bool
2433is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2434{
2435 for (; __first != __last; ++__first)
2436 if (!__pred(*__first))
2437 break;
2438 for (; __first != __last; ++__first)
2439 if (__pred(*__first))
2440 return false;
2441 return true;
2442}
2443
2444// partition
2445
2446template <class _Predicate, class _ForwardIterator>
2447_ForwardIterator
2448__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
2449{
2450 while (true)
2451 {
2452 if (__first == __last)
2453 return __first;
2454 if (!__pred(*__first))
2455 break;
2456 ++__first;
2457 }
2458 for (_ForwardIterator __p = __first; ++__p != __last;)
2459 {
2460 if (__pred(*__p))
2461 {
2462 swap(*__first, *__p);
2463 ++__first;
2464 }
2465 }
2466 return __first;
2467}
2468
2469template <class _Predicate, class _BidirectionalIterator>
2470_BidirectionalIterator
2471__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2472 bidirectional_iterator_tag)
2473{
2474 while (true)
2475 {
2476 while (true)
2477 {
2478 if (__first == __last)
2479 return __first;
2480 if (!__pred(*__first))
2481 break;
2482 ++__first;
2483 }
2484 do
2485 {
2486 if (__first == --__last)
2487 return __first;
2488 } while (!__pred(*__last));
2489 swap(*__first, *__last);
2490 ++__first;
2491 }
2492}
2493
2494template <class _ForwardIterator, class _Predicate>
2495inline _LIBCPP_INLINE_VISIBILITY
2496_ForwardIterator
2497partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2498{
2499 return _STD::__partition<typename add_lvalue_reference<_Predicate>::type>
2500 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
2501}
2502
2503// partition_copy
2504
2505template <class _InputIterator, class _OutputIterator1,
2506 class _OutputIterator2, class _Predicate>
2507pair<_OutputIterator1, _OutputIterator2>
2508partition_copy(_InputIterator __first, _InputIterator __last,
2509 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
2510 _Predicate __pred)
2511{
2512 for (; __first != __last; ++__first)
2513 {
2514 if (__pred(*__first))
2515 {
2516 *__out_true = *__first;
2517 ++__out_true;
2518 }
2519 else
2520 {
2521 *__out_false = *__first;
2522 ++__out_false;
2523 }
2524 }
2525 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
2526}
2527
2528// partition_point
2529
2530template<class _ForwardIterator, class _Predicate>
2531_ForwardIterator
2532partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2533{
2534 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2535 difference_type __len = _STD::distance(__first, __last);
2536 while (__len != 0)
2537 {
2538 difference_type __l2 = __len / 2;
2539 _ForwardIterator __m = __first;
2540 _STD::advance(__m, __l2);
2541 if (__pred(*__m))
2542 {
2543 __first = ++__m;
2544 __len -= __l2 + 1;
2545 }
2546 else
2547 __len = __l2;
2548 }
2549 return __first;
2550}
2551
2552// stable_partition
2553
2554template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
2555_ForwardIterator
2556__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2557 _Distance __len, _Pair __p, forward_iterator_tag __fit)
2558{
2559 // *__first is known to be false
2560 // __len >= 1
2561 if (__len == 1)
2562 return __first;
2563 if (__len == 2)
2564 {
2565 _ForwardIterator __m = __first;
2566 if (__pred(*++__m))
2567 {
2568 swap(*__first, *__m);
2569 return __m;
2570 }
2571 return __first;
2572 }
2573 if (__len <= __p.second)
2574 { // The buffer is big enough to use
2575 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2576 __destruct_n __d(0);
2577 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
2578 // Move the falses into the temporary buffer, and the trues to the front of the line
2579 // Update __first to always point to the end of the trues
2580 value_type* __t = __p.first;
2581 ::new(__t) value_type(_STD::move(*__first));
2582 __d.__incr((value_type*)0);
2583 ++__t;
2584 _ForwardIterator __i = __first;
2585 while (++__i != __last)
2586 {
2587 if (__pred(*__i))
2588 {
2589 *__first = _STD::move(*__i);
2590 ++__first;
2591 }
2592 else
2593 {
2594 ::new(__t) value_type(_STD::move(*__i));
2595 __d.__incr((value_type*)0);
2596 ++__t;
2597 }
2598 }
2599 // All trues now at start of range, all falses in buffer
2600 // Move falses back into range, but don't mess up __first which points to first false
2601 __i = __first;
2602 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
2603 *__i = _STD::move(*__t2);
2604 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
2605 return __first;
2606 }
2607 // Else not enough buffer, do in place
2608 // __len >= 3
2609 _ForwardIterator __m = __first;
2610 _Distance __len2 = __len / 2; // __len2 >= 2
2611 _STD::advance(__m, __len2);
2612 // recurse on [__first, __m), *__first know to be false
2613 // F?????????????????
2614 // f m l
2615 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
2616 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
2617 // TTTFFFFF??????????
2618 // f ff m l
2619 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
2620 _ForwardIterator __m1 = __m;
2621 _ForwardIterator __second_false = __last;
2622 _Distance __len_half = __len - __len2;
2623 while (__pred(*__m1))
2624 {
2625 if (++__m1 == __last)
2626 goto __second_half_done;
2627 --__len_half;
2628 }
2629 // TTTFFFFFTTTF??????
2630 // f ff m m1 l
2631 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
2632__second_half_done:
2633 // TTTFFFFFTTTTTFFFFF
2634 // f ff m sf l
2635 return _STD::rotate(__first_false, __m, __second_false);
2636 // TTTTTTTTFFFFFFFFFF
2637 // |
2638}
2639
2640struct __return_temporary_buffer
2641{
2642 template <class _Tp>
2643 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_STD::return_temporary_buffer(__p);}
2644};
2645
2646template <class _Predicate, class _ForwardIterator>
2647_ForwardIterator
2648__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2649 forward_iterator_tag)
2650{
2651 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
2652 // Either prove all true and return __first or point to first false
2653 while (true)
2654 {
2655 if (__first == __last)
2656 return __first;
2657 if (!__pred(*__first))
2658 break;
2659 ++__first;
2660 }
2661 // We now have a reduced range [__first, __last)
2662 // *__first is known to be false
2663 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2664 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2665 difference_type __len = _STD::distance(__first, __last);
2666 pair<value_type*, ptrdiff_t> __p(0, 0);
2667 unique_ptr<value_type, __return_temporary_buffer> __h;
2668 if (__len >= __alloc_limit)
2669 {
2670 __p = _STD::get_temporary_buffer<value_type>(__len);
2671 __h.reset(__p.first);
2672 }
2673 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
2674 (__first, __last, __pred, __len, __p, forward_iterator_tag());
2675}
2676
2677template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
2678_BidirectionalIterator
2679__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2680 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
2681{
2682 // *__first is known to be false
2683 // *__last is known to be true
2684 // __len >= 2
2685 if (__len == 2)
2686 {
2687 swap(*__first, *__last);
2688 return __last;
2689 }
2690 if (__len == 3)
2691 {
2692 _BidirectionalIterator __m = __first;
2693 if (__pred(*++__m))
2694 {
2695 swap(*__first, *__m);
2696 swap(*__m, *__last);
2697 return __last;
2698 }
2699 swap(*__m, *__last);
2700 swap(*__first, *__m);
2701 return __m;
2702 }
2703 if (__len <= __p.second)
2704 { // The buffer is big enough to use
2705 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2706 __destruct_n __d(0);
2707 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
2708 // Move the falses into the temporary buffer, and the trues to the front of the line
2709 // Update __first to always point to the end of the trues
2710 value_type* __t = __p.first;
2711 ::new(__t) value_type(_STD::move(*__first));
2712 __d.__incr((value_type*)0);
2713 ++__t;
2714 _BidirectionalIterator __i = __first;
2715 while (++__i != __last)
2716 {
2717 if (__pred(*__i))
2718 {
2719 *__first = _STD::move(*__i);
2720 ++__first;
2721 }
2722 else
2723 {
2724 ::new(__t) value_type(_STD::move(*__i));
2725 __d.__incr((value_type*)0);
2726 ++__t;
2727 }
2728 }
2729 // move *__last, known to be true
2730 *__first = _STD::move(*__i);
2731 __i = ++__first;
2732 // All trues now at start of range, all falses in buffer
2733 // Move falses back into range, but don't mess up __first which points to first false
2734 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
2735 *__i = _STD::move(*__t2);
2736 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
2737 return __first;
2738 }
2739 // Else not enough buffer, do in place
2740 // __len >= 4
2741 _BidirectionalIterator __m = __first;
2742 _Distance __len2 = __len / 2; // __len2 >= 2
2743 _STD::advance(__m, __len2);
2744 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
2745 // F????????????????T
2746 // f m l
2747 _BidirectionalIterator __m1 = __m;
2748 _BidirectionalIterator __first_false = __first;
2749 _Distance __len_half = __len2;
2750 while (!__pred(*--__m1))
2751 {
2752 if (__m1 == __first)
2753 goto __first_half_done;
2754 --__len_half;
2755 }
2756 // F???TFFF?????????T
2757 // f m1 m l
2758 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
2759 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
2760__first_half_done:
2761 // TTTFFFFF?????????T
2762 // f ff m l
2763 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
2764 __m1 = __m;
2765 _BidirectionalIterator __second_false = __last;
2766 ++__second_false;
2767 __len_half = __len - __len2;
2768 while (__pred(*__m1))
2769 {
2770 if (++__m1 == __last)
2771 goto __second_half_done;
2772 --__len_half;
2773 }
2774 // TTTFFFFFTTTF?????T
2775 // f ff m m1 l
2776 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
2777__second_half_done:
2778 // TTTFFFFFTTTTTFFFFF
2779 // f ff m sf l
2780 return _STD::rotate(__first_false, __m, __second_false);
2781 // TTTTTTTTFFFFFFFFFF
2782 // |
2783}
2784
2785template <class _Predicate, class _BidirectionalIterator>
2786_BidirectionalIterator
2787__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2788 bidirectional_iterator_tag)
2789{
2790 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
2791 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2792 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
2793 // Either prove all true and return __first or point to first false
2794 while (true)
2795 {
2796 if (__first == __last)
2797 return __first;
2798 if (!__pred(*__first))
2799 break;
2800 ++__first;
2801 }
2802 // __first points to first false, everything prior to __first is already set.
2803 // Either prove [__first, __last) is all false and return __first, or point __last to last true
2804 do
2805 {
2806 if (__first == --__last)
2807 return __first;
2808 } while (!__pred(*__last));
2809 // We now have a reduced range [__first, __last]
2810 // *__first is known to be false
2811 // *__last is known to be true
2812 // __len >= 2
2813 difference_type __len = _STD::distance(__first, __last) + 1;
2814 pair<value_type*, ptrdiff_t> __p(0, 0);
2815 unique_ptr<value_type, __return_temporary_buffer> __h;
2816 if (__len >= __alloc_limit)
2817 {
2818 __p = _STD::get_temporary_buffer<value_type>(__len);
2819 __h.reset(__p.first);
2820 }
2821 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
2822 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
2823}
2824
2825template <class _ForwardIterator, class _Predicate>
2826inline _LIBCPP_INLINE_VISIBILITY
2827_ForwardIterator
2828stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2829{
2830 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
2831 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
2832}
2833
2834// is_sorted_until
2835
2836template <class _ForwardIterator, class _Compare>
2837_ForwardIterator
2838is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2839{
2840 if (__first != __last)
2841 {
2842 _ForwardIterator __i = __first;
2843 while (++__i != __last)
2844 {
2845 if (__comp(*__i, *__first))
2846 return __i;
2847 __first = __i;
2848 }
2849 }
2850 return __last;
2851}
2852
2853template<class _ForwardIterator>
2854inline _LIBCPP_INLINE_VISIBILITY
2855_ForwardIterator
2856is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
2857{
2858 return _STD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2859}
2860
2861// is_sorted
2862
2863template <class _ForwardIterator, class _Compare>
2864inline _LIBCPP_INLINE_VISIBILITY
2865bool
2866is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2867{
2868 return _STD::is_sorted_until(__first, __last, __comp) == __last;
2869}
2870
2871template<class _ForwardIterator>
2872inline _LIBCPP_INLINE_VISIBILITY
2873bool
2874is_sorted(_ForwardIterator __first, _ForwardIterator __last)
2875{
2876 return _STD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2877}
2878
2879// sort
2880
2881// stable, 2-3 compares, 0-2 swaps
2882
2883template <class _Compare, class _ForwardIterator>
2884unsigned
2885__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
2886{
2887 unsigned __r = 0;
2888 if (!__c(*__y, *__x)) // if x <= y
2889 {
2890 if (!__c(*__z, *__y)) // if y <= z
2891 return __r; // x <= y && y <= z
2892 // x <= y && y > z
2893 swap(*__y, *__z); // x <= z && y < z
2894 __r = 1;
2895 if (__c(*__y, *__x)) // if x > y
2896 {
2897 swap(*__x, *__y); // x < y && y <= z
2898 __r = 2;
2899 }
2900 return __r; // x <= y && y < z
2901 }
2902 if (__c(*__z, *__y)) // x > y, if y > z
2903 {
2904 swap(*__x, *__z); // x < y && y < z
2905 __r = 1;
2906 return __r;
2907 }
2908 swap(*__x, *__y); // x > y && y <= z
2909 __r = 1; // x < y && x <= z
2910 if (__c(*__z, *__y)) // if y > z
2911 {
2912 swap(*__y, *__z); // x <= y && y < z
2913 __r = 2;
2914 }
2915 return __r;
2916} // x <= y && y <= z
2917
2918// stable, 3-6 compares, 0-5 swaps
2919
2920template <class _Compare, class _ForwardIterator>
2921unsigned
2922__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
2923 _ForwardIterator __x4, _Compare __c)
2924{
2925 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
2926 if (__c(*__x4, *__x3))
2927 {
2928 swap(*__x3, *__x4);
2929 ++__r;
2930 if (__c(*__x3, *__x2))
2931 {
2932 swap(*__x2, *__x3);
2933 ++__r;
2934 if (__c(*__x2, *__x1))
2935 {
2936 swap(*__x1, *__x2);
2937 ++__r;
2938 }
2939 }
2940 }
2941 return __r;
2942}
2943
2944// stable, 4-10 compares, 0-9 swaps
2945
2946template <class _Compare, class _ForwardIterator>
2947unsigned
2948__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
2949 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
2950{
2951 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
2952 if (__c(*__x5, *__x4))
2953 {
2954 swap(*__x4, *__x5);
2955 ++__r;
2956 if (__c(*__x4, *__x3))
2957 {
2958 swap(*__x3, *__x4);
2959 ++__r;
2960 if (__c(*__x3, *__x2))
2961 {
2962 swap(*__x2, *__x3);
2963 ++__r;
2964 if (__c(*__x2, *__x1))
2965 {
2966 swap(*__x1, *__x2);
2967 ++__r;
2968 }
2969 }
2970 }
2971 }
2972 return __r;
2973}
2974
2975// Assumes size > 0
2976template <class _Compare, class _BirdirectionalIterator>
2977void
2978__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
2979{
2980 _BirdirectionalIterator __lm1 = __last;
2981 for (--__lm1; __first != __lm1; ++__first)
2982 {
2983 _BirdirectionalIterator __i = _STD::min_element<_BirdirectionalIterator,
2984 typename add_lvalue_reference<_Compare>::type>
2985 (__first, __last, __comp);
2986 if (__i != __first)
2987 swap(*__first, *__i);
2988 }
2989}
2990
2991template <class _Compare, class _BirdirectionalIterator>
2992void
2993__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
2994{
2995 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
2996 if (__first != __last)
2997 {
2998 _BirdirectionalIterator __i = __first;
2999 for (++__i; __i != __last; ++__i)
3000 {
3001 _BirdirectionalIterator __j = __i;
3002 value_type __t(_STD::move(*__j));
3003 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3004 *__j = _STD::move(*__k);
3005 *__j = _STD::move(__t);
3006 }
3007 }
3008}
3009
3010template <class _Compare, class _RandomAccessIterator>
3011void
3012__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3013{
3014 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3015 _RandomAccessIterator __j = __first+2;
3016 __sort3<_Compare>(__first, __first+1, __j, __comp);
3017 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3018 {
3019 if (__comp(*__i, *__j))
3020 {
3021 value_type __t(_STD::move(*__i));
3022 _RandomAccessIterator __k = __j;
3023 __j = __i;
3024 do
3025 {
3026 *__j = _STD::move(*__k);
3027 __j = __k;
3028 } while (__j != __first && __comp(__t, *--__k));
3029 *__j = _STD::move(__t);
3030 }
3031 __j = __i;
3032 }
3033}
3034
3035template <class _Compare, class _RandomAccessIterator>
3036bool
3037__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3038{
3039 switch (__last - __first)
3040 {
3041 case 0:
3042 case 1:
3043 return true;
3044 case 2:
3045 if (__comp(*--__last, *__first))
3046 swap(*__first, *__last);
3047 return true;
3048 case 3:
3049 _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3050 return true;
3051 case 4:
3052 _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3053 return true;
3054 case 5:
3055 _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3056 return true;
3057 }
3058 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3059 _RandomAccessIterator __j = __first+2;
3060 __sort3<_Compare>(__first, __first+1, __j, __comp);
3061 const unsigned __limit = 8;
3062 unsigned __count = 0;
3063 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3064 {
3065 if (__comp(*__i, *__j))
3066 {
3067 value_type __t(_STD::move(*__i));
3068 _RandomAccessIterator __k = __j;
3069 __j = __i;
3070 do
3071 {
3072 *__j = _STD::move(*__k);
3073 __j = __k;
3074 } while (__j != __first && __comp(__t, *--__k));
3075 *__j = _STD::move(__t);
3076 if (++__count == __limit)
3077 return ++__i == __last;
3078 }
3079 __j = __i;
3080 }
3081 return true;
3082}
3083
3084template <class _Compare, class _BirdirectionalIterator>
3085void
3086__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3087 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3088{
3089 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3090 if (__first1 != __last1)
3091 {
3092 __destruct_n __d(0);
3093 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3094 value_type* __last2 = __first2;
3095 ::new(__last2) value_type(_STD::move(*__first1));
3096 __d.__incr((value_type*)0);
3097 for (++__last2; ++__first1 != __last1; ++__last2)
3098 {
3099 value_type* __j2 = __last2;
3100 value_type* __i2 = __j2;
3101 if (__comp(*__first1, *--__i2))
3102 {
3103 ::new(__j2) value_type(_STD::move(*__i2));
3104 __d.__incr((value_type*)0);
3105 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3106 *__j2 = _STD::move(*__i2);
3107 *__j2 = _STD::move(*__first1);
3108 }
3109 else
3110 {
3111 ::new(__j2) value_type(_STD::move(*__first1));
3112 __d.__incr((value_type*)0);
3113 }
3114 }
3115 __h.release();
3116 }
3117}
3118
3119template <class _Compare, class _RandomAccessIterator>
3120void
3121__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3122{
3123 // _Compare is known to be a reference type
3124 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3125 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3126 const difference_type __limit = has_trivial_copy_constructor<value_type>::value &&
3127 has_trivial_copy_assign<value_type>::value ? 30 : 6;
3128 while (true)
3129 {
3130 __restart:
3131 difference_type __len = __last - __first;
3132 switch (__len)
3133 {
3134 case 0:
3135 case 1:
3136 return;
3137 case 2:
3138 if (__comp(*--__last, *__first))
3139 swap(*__first, *__last);
3140 return;
3141 case 3:
3142 _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3143 return;
3144 case 4:
3145 _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3146 return;
3147 case 5:
3148 _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3149 return;
3150 }
3151 if (__len <= __limit)
3152 {
3153 _STD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3154 return;
3155 }
3156 // __len > 5
3157 _RandomAccessIterator __m = __first;
3158 _RandomAccessIterator __lm1 = __last;
3159 --__lm1;
3160 unsigned __n_swaps;
3161 {
3162 difference_type __delta;
3163 if (__len >= 1000)
3164 {
3165 __delta = __len/2;
3166 __m += __delta;
3167 __delta /= 2;
3168 __n_swaps = _STD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3169 }
3170 else
3171 {
3172 __delta = __len/2;
3173 __m += __delta;
3174 __n_swaps = _STD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3175 }
3176 }
3177 // *__m is median
3178 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3179 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3180 _RandomAccessIterator __i = __first;
3181 _RandomAccessIterator __j = __lm1;
3182 // j points beyond range to be tested, *__m is known to be <= *__lm1
3183 // The search going up is known to be guarded but the search coming down isn't.
3184 // Prime the downward search with a guard.
3185 if (!__comp(*__i, *__m)) // if *__first == *__m
3186 {
3187 // *__first == *__m, *__first doesn't go in first part
3188 // manually guard downward moving __j against __i
3189 while (true)
3190 {
3191 if (__i == --__j)
3192 {
3193 // *__first == *__m, *__m <= all other elements
3194 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3195 ++__i; // __first + 1
3196 __j = __last;
3197 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3198 {
3199 while (true)
3200 {
3201 if (__i == __j)
3202 return; // [__first, __last) all equivalent elements
3203 if (__comp(*__first, *__i))
3204 {
3205 swap(*__i, *__j);
3206 ++__n_swaps;
3207 ++__i;
3208 break;
3209 }
3210 ++__i;
3211 }
3212 }
3213 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3214 if (__i == __j)
3215 return;
3216 while (true)
3217 {
3218 while (!__comp(*__first, *__i))
3219 ++__i;
3220 while (__comp(*__first, *--__j))
3221 ;
3222 if (__i >= __j)
3223 break;
3224 swap(*__i, *__j);
3225 ++__n_swaps;
3226 ++__i;
3227 }
3228 // [__first, __i) == *__first and *__first < [__i, __last)
3229 // The first part is sorted, sort the secod part
3230 // _STD::__sort<_Compare>(__i, __last, __comp);
3231 __first = __i;
3232 goto __restart;
3233 }
3234 if (__comp(*__j, *__m))
3235 {
3236 swap(*__i, *__j);
3237 ++__n_swaps;
3238 break; // found guard for downward moving __j, now use unguarded partition
3239 }
3240 }
3241 }
3242 // It is known that *__i < *__m
3243 ++__i;
3244 // j points beyond range to be tested, *__m is known to be <= *__lm1
3245 // if not yet partitioned...
3246 if (__i < __j)
3247 {
3248 // known that *(__i - 1) < *__m
3249 // known that __i <= __m
3250 while (true)
3251 {
3252 // __m still guards upward moving __i
3253 while (__comp(*__i, *__m))
3254 ++__i;
3255 // It is now known that a guard exists for downward moving __j
3256 while (!__comp(*--__j, *__m))
3257 ;
3258 if (__i > __j)
3259 break;
3260 swap(*__i, *__j);
3261 ++__n_swaps;
3262 // It is known that __m != __j
3263 // If __m just moved, follow it
3264 if (__m == __i)
3265 __m = __j;
3266 ++__i;
3267 }
3268 }
3269 // [__first, __i) < *__m and *__m <= [__i, __last)
3270 if (__i != __m && __comp(*__m, *__i))
3271 {
3272 swap(*__i, *__m);
3273 ++__n_swaps;
3274 }
3275 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3276 // If we were given a perfect partition, see if insertion sort is quick...
3277 if (__n_swaps == 0)
3278 {
3279 bool __fs = _STD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3280 if (_STD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3281 {
3282 if (__fs)
3283 return;
3284 __last = __i;
3285 continue;
3286 }
3287 else
3288 {
3289 if (__fs)
3290 {
3291 __first = ++__i;
3292 continue;
3293 }
3294 }
3295 }
3296 // sort smaller range with recursive call and larger with tail recursion elimination
3297 if (__i - __first < __last - __i)
3298 {
3299 _STD::__sort<_Compare>(__first, __i, __comp);
3300 // _STD::__sort<_Compare>(__i+1, __last, __comp);
3301 __first = ++__i;
3302 }
3303 else
3304 {
3305 _STD::__sort<_Compare>(__i+1, __last, __comp);
3306 // _STD::__sort<_Compare>(__first, __i, __comp);
3307 __last = __i;
3308 }
3309 }
3310}
3311
3312// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
3313template <class _RandomAccessIterator, class _Compare>
3314inline _LIBCPP_INLINE_VISIBILITY
3315void
3316sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3317{
3318#ifdef _LIBCPP_DEBUG
3319 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3320 __debug_less<_Compare> __c(__comp);
3321 __sort<_Comp_ref>(__first, __last, __c);
3322#else
3323 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3324 __sort<_Comp_ref>(__first, __last, __comp);
3325#endif
3326}
3327
3328template <class _RandomAccessIterator>
3329inline _LIBCPP_INLINE_VISIBILITY
3330void
3331sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3332{
3333 _STD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
3334}
3335
3336template <class _Tp>
3337inline _LIBCPP_INLINE_VISIBILITY
3338void
3339sort(_Tp** __first, _Tp** __last)
3340{
3341 _STD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
3342}
3343
3344template <class _Tp>
3345inline _LIBCPP_INLINE_VISIBILITY
3346void
3347sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
3348{
3349 _STD::sort(__first.base(), __last.base());
3350}
3351
3352extern template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
3353extern template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3354extern template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3355extern template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3356extern template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
3357extern template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3358extern template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
3359extern template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3360extern template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
3361extern template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3362extern template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3363extern template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3364extern template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
3365extern template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
3366extern template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3367
3368extern template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
3369extern template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3370extern template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3371extern template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3372extern template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
3373extern template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3374extern template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
3375extern template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3376extern template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
3377extern template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3378extern template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3379extern template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3380extern template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
3381extern template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
3382extern template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3383
3384extern template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
3385
3386// lower_bound
3387
3388template <class _Compare, class _ForwardIterator, class _Tp>
3389_ForwardIterator
3390__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3391{
3392 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3393 difference_type __len = _STD::distance(__first, __last);
3394 while (__len != 0)
3395 {
3396 difference_type __l2 = __len / 2;
3397 _ForwardIterator __m = __first;
3398 _STD::advance(__m, __l2);
3399 if (__comp(*__m, __value))
3400 {
3401 __first = ++__m;
3402 __len -= __l2 + 1;
3403 }
3404 else
3405 __len = __l2;
3406 }
3407 return __first;
3408}
3409
3410template <class _ForwardIterator, class _Tp, class _Compare>
3411inline _LIBCPP_INLINE_VISIBILITY
3412_ForwardIterator
3413lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3414{
3415#ifdef _LIBCPP_DEBUG
3416 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3417 __debug_less<_Compare> __c(__comp);
3418 return __lower_bound<_Comp_ref>(__first, __last, __value, __c);
3419#else
3420 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3421 return __lower_bound<_Comp_ref>(__first, __last, __value, __comp);
3422#endif
3423}
3424
3425template <class _ForwardIterator, class _Tp>
3426inline _LIBCPP_INLINE_VISIBILITY
3427_ForwardIterator
3428lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3429{
3430 return _STD::lower_bound(__first, __last, __value,
3431 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3432}
3433
3434// upper_bound
3435
3436template <class _Compare, class _ForwardIterator, class _Tp>
3437_ForwardIterator
3438__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3439{
3440 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3441 difference_type __len = _STD::distance(__first, __last);
3442 while (__len != 0)
3443 {
3444 difference_type __l2 = __len / 2;
3445 _ForwardIterator __m = __first;
3446 _STD::advance(__m, __l2);
3447 if (__comp(__value, *__m))
3448 __len = __l2;
3449 else
3450 {
3451 __first = ++__m;
3452 __len -= __l2 + 1;
3453 }
3454 }
3455 return __first;
3456}
3457
3458template <class _ForwardIterator, class _Tp, class _Compare>
3459inline _LIBCPP_INLINE_VISIBILITY
3460_ForwardIterator
3461upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3462{
3463#ifdef _LIBCPP_DEBUG
3464 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3465 __debug_less<_Compare> __c(__comp);
3466 return __upper_bound<_Comp_ref>(__first, __last, __value, __c);
3467#else
3468 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3469 return __upper_bound<_Comp_ref>(__first, __last, __value, __comp);
3470#endif
3471}
3472
3473template <class _ForwardIterator, class _Tp>
3474inline _LIBCPP_INLINE_VISIBILITY
3475_ForwardIterator
3476upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3477{
3478 return _STD::upper_bound(__first, __last, __value,
3479 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
3480}
3481
3482// equal_range
3483
3484template <class _Compare, class _ForwardIterator, class _Tp>
3485pair<_ForwardIterator, _ForwardIterator>
3486__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3487{
3488 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3489 difference_type __len = _STD::distance(__first, __last);
3490 while (__len != 0)
3491 {
3492 difference_type __l2 = __len / 2;
3493 _ForwardIterator __m = __first;
3494 _STD::advance(__m, __l2);
3495 if (__comp(*__m, __value))
3496 {
3497 __first = ++__m;
3498 __len -= __l2 + 1;
3499 }
3500 else if (__comp(__value, *__m))
3501 {
3502 __last = __m;
3503 __len = __l2;
3504 }
3505 else
3506 {
3507 _ForwardIterator __mp1 = __m;
3508 return pair<_ForwardIterator, _ForwardIterator>
3509 (
3510 __lower_bound<_Compare>(__first, __m, __value, __comp),
3511 __upper_bound<_Compare>(++__mp1, __last, __value, __comp)
3512 );
3513 }
3514 }
3515 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3516}
3517
3518template <class _ForwardIterator, class _Tp, class _Compare>
3519inline _LIBCPP_INLINE_VISIBILITY
3520pair<_ForwardIterator, _ForwardIterator>
3521equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3522{
3523#ifdef _LIBCPP_DEBUG
3524 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3525 __debug_less<_Compare> __c(__comp);
3526 return __equal_range<_Comp_ref>(__first, __last, __value, __c);
3527#else
3528 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3529 return __equal_range<_Comp_ref>(__first, __last, __value, __comp);
3530#endif
3531}
3532
3533template <class _ForwardIterator, class _Tp>
3534inline _LIBCPP_INLINE_VISIBILITY
3535pair<_ForwardIterator, _ForwardIterator>
3536equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3537{
3538 return _STD::equal_range(__first, __last, __value,
3539 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3540}
3541
3542// binary_search
3543
3544template <class _Compare, class _ForwardIterator, class _Tp>
3545inline _LIBCPP_INLINE_VISIBILITY
3546bool
3547__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3548{
3549 __first = __lower_bound<_Compare>(__first, __last, __value, __comp);
3550 return __first != __last && !__comp(__value, *__first);
3551}
3552
3553template <class _ForwardIterator, class _Tp, class _Compare>
3554inline _LIBCPP_INLINE_VISIBILITY
3555bool
3556binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3557{
3558#ifdef _LIBCPP_DEBUG
3559 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3560 __debug_less<_Compare> __c(__comp);
3561 return __binary_search<_Comp_ref>(__first, __last, __value, __c);
3562#else
3563 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3564 return __binary_search<_Comp_ref>(__first, __last, __value, __comp);
3565#endif
3566}
3567
3568template <class _ForwardIterator, class _Tp>
3569inline _LIBCPP_INLINE_VISIBILITY
3570bool
3571binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3572{
3573 return _STD::binary_search(__first, __last, __value,
3574 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3575}
3576
3577// merge
3578
3579template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
3580_OutputIterator
3581__merge(_InputIterator1 __first1, _InputIterator1 __last1,
3582 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3583{
3584 for (; __first1 != __last1; ++__result)
3585 {
3586 if (__first2 == __last2)
3587 return _STD::copy(__first1, __last1, __result);
3588 if (__comp(*__first2, *__first1))
3589 {
3590 *__result = *__first2;
3591 ++__first2;
3592 }
3593 else
3594 {
3595 *__result = *__first1;
3596 ++__first1;
3597 }
3598 }
3599 return _STD::copy(__first2, __last2, __result);
3600}
3601
3602template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
3603inline _LIBCPP_INLINE_VISIBILITY
3604_OutputIterator
3605merge(_InputIterator1 __first1, _InputIterator1 __last1,
3606 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3607{
3608#ifdef _LIBCPP_DEBUG
3609 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3610 __debug_less<_Compare> __c(__comp);
3611 return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
3612#else
3613 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3614 return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
3615#endif
3616}
3617
3618template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
3619inline _LIBCPP_INLINE_VISIBILITY
3620_OutputIterator
3621merge(_InputIterator1 __first1, _InputIterator1 __last1,
3622 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
3623{
3624 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
3625 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
3626 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
3627}
3628
3629// inplace_merge
3630
3631template <class _Compare, class _BidirectionalIterator>
3632void
3633__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3634 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3635 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3636 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
3637{
3638 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3639 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3640 typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer;
3641 __destruct_n __d(0);
3642 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
3643 if (__len1 <= __len2)
3644 {
3645 value_type* __p = __buff;
3646 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p)
3647 ::new(__p) value_type(_STD::move(*__i));
3648 __merge<_Compare>(move_iterator<value_type*>(__buff),
3649 move_iterator<value_type*>(__p),
3650 move_iterator<_BidirectionalIterator>(__middle),
3651 move_iterator<_BidirectionalIterator>(__last),
3652 __first, __comp);
3653 }
3654 else
3655 {
3656 value_type* __p = __buff;
3657 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p)
3658 ::new(__p) value_type(_STD::move(*__i));
3659 typedef reverse_iterator<_BidirectionalIterator> _RBi;
3660 typedef reverse_iterator<value_type*> _Rv;
3661 __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
3662 move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
3663 _RBi(__last), __negate<_Compare>(__comp));
3664 }
3665}
3666
3667template <class _Compare, class _BidirectionalIterator>
3668void
3669__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3670 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3671 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3672 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
3673{
3674 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3675 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3676 while (true)
3677 {
3678 // if __middle == __last, we're done
3679 if (__len2 == 0)
3680 return;
3681 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
3682 for (; true; ++__first, --__len1)
3683 {
3684 if (__len1 == 0)
3685 return;
3686 if (__comp(*__middle, *__first))
3687 break;
3688 }
3689 if (__len1 <= __buff_size || __len2 <= __buff_size)
3690 {
3691 __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
3692 return;
3693 }
3694 // __first < __middle < __last
3695 // *__first > *__middle
3696 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
3697 // all elements in:
3698 // [__first, __m1) <= [__middle, __m2)
3699 // [__middle, __m2) < [__m1, __middle)
3700 // [__m1, __middle) <= [__m2, __last)
3701 // and __m1 or __m2 is in the middle of its range
3702 _BidirectionalIterator __m1; // "median" of [__first, __middle)
3703 _BidirectionalIterator __m2; // "median" of [__middle, __last)
3704 difference_type __len11; // distance(__first, __m1)
3705 difference_type __len21; // distance(__middle, __m2)
3706 // binary search smaller range
3707 if (__len1 < __len2)
3708 { // __len >= 1, __len2 >= 2
3709 __len21 = __len2 / 2;
3710 __m2 = __middle;
3711 _STD::advance(__m2, __len21);
3712 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
3713 __len11 = _STD::distance(__first, __m1);
3714 }
3715 else
3716 {
3717 if (__len1 == 1)
3718 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
3719 // It is known *__first > *__middle
3720 swap(*__first, *__middle);
3721 return;
3722 }
3723 // __len1 >= 2, __len2 >= 1
3724 __len11 = __len1 / 2;
3725 __m1 = __first;
3726 _STD::advance(__m1, __len11);
3727 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
3728 __len21 = _STD::distance(__middle, __m2);
3729 }
3730 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
3731 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
3732 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
3733 // swap middle two partitions
3734 __middle = _STD::rotate(__m1, __middle, __m2);
3735 // __len12 and __len21 now have swapped meanings
3736 // merge smaller range with recurisve call and larger with tail recursion elimination
3737 if (__len11 + __len21 < __len12 + __len22)
3738 {
3739 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
3740// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
3741 __first = __middle;
3742 __middle = __m2;
3743 __len1 = __len12;
3744 __len2 = __len22;
3745 }
3746 else
3747 {
3748 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
3749// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
3750 __last = __middle;
3751 __middle = __m1;
3752 __len1 = __len11;
3753 __len2 = __len21;
3754 }
3755 }
3756}
3757
3758template <class _Tp>
3759struct __inplace_merge_switch
3760{
3761 static const unsigned value = has_trivial_copy_assign<_Tp>::value;
3762};
3763
3764template <class _BidirectionalIterator, class _Compare>
3765inline _LIBCPP_INLINE_VISIBILITY
3766void
3767inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3768 _Compare __comp)
3769{
3770 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3771 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3772 difference_type __len1 = _STD::distance(__first, __middle);
3773 difference_type __len2 = _STD::distance(__middle, __last);
3774 difference_type __buf_size = _STD::min(__len1, __len2);
3775 pair<value_type*, ptrdiff_t> __buf(0, 0);
3776 unique_ptr<value_type, __return_temporary_buffer> __h;
3777 if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
3778 {
3779 __buf = _STD::get_temporary_buffer<value_type>(__buf_size);
3780 __h.reset(__buf.first);
3781 }
3782#ifdef _LIBCPP_DEBUG
3783 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3784 __debug_less<_Compare> __c(__comp);
3785 return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
3786 __buf.first, __buf.second);
3787#else
3788 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3789 return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
3790 __buf.first, __buf.second);
3791#endif
3792}
3793
3794template <class _BidirectionalIterator>
3795inline _LIBCPP_INLINE_VISIBILITY
3796void
3797inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
3798{
3799 _STD::inplace_merge(__first, __middle, __last,
3800 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
3801}
3802
3803// stable_sort
3804
3805template <class _Compare, class _InputIterator1, class _InputIterator2>
3806void
3807__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
3808 _InputIterator2 __first2, _InputIterator2 __last2,
3809 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
3810{
3811 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
3812 __destruct_n __d(0);
3813 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
3814 for (; true; ++__result)
3815 {
3816 if (__first1 == __last1)
3817 {
3818 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
3819 ::new (__result) value_type(_STD::move(*__first2));
3820 __h.release();
3821 return;
3822 }
3823 if (__first2 == __last2)
3824 {
3825 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
3826 ::new (__result) value_type(_STD::move(*__first1));
3827 __h.release();
3828 return;
3829 }
3830 if (__comp(*__first2, *__first1))
3831 {
3832 ::new (__result) value_type(_STD::move(*__first2));
3833 __d.__incr((value_type*)0);
3834 ++__first2;
3835 }
3836 else
3837 {
3838 ::new (__result) value_type(_STD::move(*__first1));
3839 __d.__incr((value_type*)0);
3840 ++__first1;
3841 }
3842 }
3843}
3844
3845template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
3846void
3847__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
3848 _InputIterator2 __first2, _InputIterator2 __last2,
3849 _OutputIterator __result, _Compare __comp)
3850{
3851 for (; __first1 != __last1; ++__result)
3852 {
3853 if (__first2 == __last2)
3854 {
3855 for (; __first1 != __last1; ++__first1, ++__result)
3856 *__result = _STD::move(*__first1);
3857 return;
3858 }
3859 if (__comp(*__first2, *__first1))
3860 {
3861 *__result = _STD::move(*__first2);
3862 ++__first2;
3863 }
3864 else
3865 {
3866 *__result = _STD::move(*__first1);
3867 ++__first1;
3868 }
3869 }
3870 for (; __first2 != __last2; ++__first2, ++__result)
3871 *__result = _STD::move(*__first2);
3872}
3873
3874template <class _Compare, class _RandomAccessIterator>
3875void
3876__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
3877 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
3878 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
3879
3880template <class _Compare, class _RandomAccessIterator>
3881void
3882__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
3883 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
3884 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
3885{
3886 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3887 switch (__len)
3888 {
3889 case 0:
3890 return;
3891 case 1:
3892 ::new(__first2) value_type(_STD::move(*__first1));
3893 return;
3894 case 2:
3895 __destruct_n __d(0);
3896 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
3897 if (__comp(*--__last1, *__first1))
3898 {
3899 ::new(__first2) value_type(_STD::move(*__last1));
3900 __d.__incr((value_type*)0);
3901 ++__first2;
3902 ::new(__first2) value_type(_STD::move(*__first1));
3903 }
3904 else
3905 {
3906 ::new(__first2) value_type(_STD::move(*__first1));
3907 __d.__incr((value_type*)0);
3908 ++__first2;
3909 ::new(__first2) value_type(_STD::move(*__last1));
3910 }
3911 __h2.release();
3912 return;
3913 }
3914 if (__len <= 8)
3915 {
3916 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
3917 return;
3918 }
3919 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
3920 _RandomAccessIterator __m = __first1 + __l2;
3921 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
3922 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
3923 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
3924}
3925
3926template <class _Tp>
3927struct __stable_sort_switch
3928{
3929 static const unsigned value = 128*has_trivial_copy_assign<_Tp>::value;
3930};
3931
3932template <class _Compare, class _RandomAccessIterator>
3933void
3934__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
3935 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
3936 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
3937{
3938 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3939 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3940 switch (__len)
3941 {
3942 case 0:
3943 case 1:
3944 return;
3945 case 2:
3946 if (__comp(*--__last, *__first))
3947 swap(*__first, *__last);
3948 return;
3949 }
3950 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
3951 {
3952 __insertion_sort<_Compare>(__first, __last, __comp);
3953 return;
3954 }
3955 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
3956 _RandomAccessIterator __m = __first + __l2;
3957 if (__len <= __buff_size)
3958 {
3959 __destruct_n __d(0);
3960 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
3961 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
3962 __d.__set(__l2, (value_type*)0);
3963 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
3964 __d.__set(__len, (value_type*)0);
3965 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
3966// __merge<_Compare>(move_iterator<value_type*>(__buff),
3967// move_iterator<value_type*>(__buff + __l2),
3968// move_iterator<_RandomAccessIterator>(__buff + __l2),
3969// move_iterator<_RandomAccessIterator>(__buff + __len),
3970// __first, __comp);
3971 return;
3972 }
3973 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
3974 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
3975 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
3976}
3977
3978template <class _RandomAccessIterator, class _Compare>
3979inline _LIBCPP_INLINE_VISIBILITY
3980void
3981stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3982{
3983 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3984 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3985 difference_type __len = __last - __first;
3986 pair<value_type*, ptrdiff_t> __buf(0, 0);
3987 unique_ptr<value_type, __return_temporary_buffer> __h;
3988 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
3989 {
3990 __buf = _STD::get_temporary_buffer<value_type>(__len);
3991 __h.reset(__buf.first);
3992 }
3993#ifdef _LIBCPP_DEBUG
3994 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3995 __debug_less<_Compare> __c(__comp);
3996 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
3997#else
3998 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3999 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4000#endif
4001}
4002
4003template <class _RandomAccessIterator>
4004inline _LIBCPP_INLINE_VISIBILITY
4005void
4006stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4007{
4008 _STD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4009}
4010
4011// is_heap_until
4012
4013template <class _RandomAccessIterator, class _Compare>
4014_RandomAccessIterator
4015is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4016{
4017 typedef typename _STD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4018 difference_type __len = __last - __first;
4019 difference_type __p = 0;
4020 difference_type __c = 1;
4021 _RandomAccessIterator __pp = __first;
4022 while (__c < __len)
4023 {
4024 _RandomAccessIterator __cp = __first + __c;
4025 if (__comp(*__pp, *__cp))
4026 return __cp;
4027 ++__c;
4028 ++__cp;
4029 if (__c == __len)
4030 return __last;
4031 if (__comp(*__pp, *__cp))
4032 return __cp;
4033 ++__p;
4034 ++__pp;
4035 __c = 2 * __p + 1;
4036 }
4037 return __last;
4038}
4039
4040template<class _RandomAccessIterator>
4041inline _LIBCPP_INLINE_VISIBILITY
4042_RandomAccessIterator
4043is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4044{
4045 return _STD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4046}
4047
4048// is_heap
4049
4050template <class _RandomAccessIterator, class _Compare>
4051inline _LIBCPP_INLINE_VISIBILITY
4052bool
4053is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4054{
4055 return _STD::is_heap_until(__first, __last, __comp) == __last;
4056}
4057
4058template<class _RandomAccessIterator>
4059inline _LIBCPP_INLINE_VISIBILITY
4060bool
4061is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4062{
4063 return _STD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4064}
4065
4066// push_heap
4067
4068template <class _Compare, class _RandomAccessIterator>
4069void
4070__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp,
4071 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4072{
4073 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4074 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4075 if (__len > 1)
4076 {
4077 difference_type __p = 0;
4078 _RandomAccessIterator __pp = __first;
4079 difference_type __c = 2;
4080 _RandomAccessIterator __cp = __first + __c;
4081 if (__c == __len || __comp(*__cp, *(__cp - 1)))
4082 {
4083 --__c;
4084 --__cp;
4085 }
4086 if (__comp(*__pp, *__cp))
4087 {
4088 value_type __t(_STD::move(*__pp));
4089 do
4090 {
4091 *__pp = _STD::move(*__cp);
4092 __pp = __cp;
4093 __p = __c;
4094 __c = (__p + 1) * 2;
4095 if (__c > __len)
4096 break;
4097 __cp = __first + __c;
4098 if (__c == __len || __comp(*__cp, *(__cp - 1)))
4099 {
4100 --__c;
4101 --__cp;
4102 }
4103 } while (__comp(__t, *__cp));
4104 *__pp = _STD::move(__t);
4105 }
4106 }
4107}
4108
4109template <class _Compare, class _RandomAccessIterator>
4110void
4111__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4112 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4113{
4114 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4115 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4116 if (__len > 1)
4117 {
4118 __len = (__len - 2) / 2;
4119 _RandomAccessIterator __ptr = __first + __len;
4120 if (__comp(*__ptr, *--__last))
4121 {
4122 value_type __t(_STD::move(*__last));
4123 do
4124 {
4125 *__last = _STD::move(*__ptr);
4126 __last = __ptr;
4127 if (__len == 0)
4128 break;
4129 __len = (__len - 1) / 2;
4130 __ptr = __first + __len;
4131 } while (__comp(*__ptr, __t));
4132 *__last = _STD::move(__t);
4133 }
4134 }
4135}
4136
4137template <class _RandomAccessIterator, class _Compare>
4138inline _LIBCPP_INLINE_VISIBILITY
4139void
4140push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4141{
4142#ifdef _LIBCPP_DEBUG
4143 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4144 __debug_less<_Compare> __c(__comp);
4145 __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first);
4146#else
4147 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4148 __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first);
4149#endif
4150}
4151
4152template <class _RandomAccessIterator>
4153inline _LIBCPP_INLINE_VISIBILITY
4154void
4155push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4156{
4157 _STD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4158}
4159
4160// pop_heap
4161
4162template <class _Compare, class _RandomAccessIterator>
4163inline _LIBCPP_INLINE_VISIBILITY
4164void
4165__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4166 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4167{
4168 if (__len > 1)
4169 {
4170 swap(*__first, *--__last);
4171 __push_heap_front<_Compare>(__first, __last, __comp, __len-1);
4172 }
4173}
4174
4175template <class _RandomAccessIterator, class _Compare>
4176inline _LIBCPP_INLINE_VISIBILITY
4177void
4178pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4179{
4180#ifdef _LIBCPP_DEBUG
4181 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4182 __debug_less<_Compare> __c(__comp);
4183 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4184#else
4185 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4186 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4187#endif
4188}
4189
4190template <class _RandomAccessIterator>
4191inline _LIBCPP_INLINE_VISIBILITY
4192void
4193pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4194{
4195 _STD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4196}
4197
4198// make_heap
4199
4200template <class _Compare, class _RandomAccessIterator>
4201void
4202__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4203{
4204 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4205 difference_type __n = __last - __first;
4206 if (__n > 1)
4207 {
4208 __last = __first;
4209 ++__last;
4210 for (difference_type __i = 1; __i < __n;)
4211 __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
4212 }
4213}
4214
4215template <class _RandomAccessIterator, class _Compare>
4216inline _LIBCPP_INLINE_VISIBILITY
4217void
4218make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4219{
4220#ifdef _LIBCPP_DEBUG
4221 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4222 __debug_less<_Compare> __c(__comp);
4223 __make_heap<_Comp_ref>(__first, __last, __c);
4224#else
4225 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4226 __make_heap<_Comp_ref>(__first, __last, __comp);
4227#endif
4228}
4229
4230template <class _RandomAccessIterator>
4231inline _LIBCPP_INLINE_VISIBILITY
4232void
4233make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4234{
4235 _STD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4236}
4237
4238// sort_heap
4239
4240template <class _Compare, class _RandomAccessIterator>
4241void
4242__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4243{
4244 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4245 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4246 __pop_heap<_Compare>(__first, __last, __comp, __n);
4247}
4248
4249template <class _RandomAccessIterator, class _Compare>
4250inline _LIBCPP_INLINE_VISIBILITY
4251void
4252sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4253{
4254#ifdef _LIBCPP_DEBUG
4255 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4256 __debug_less<_Compare> __c(__comp);
4257 __sort_heap<_Comp_ref>(__first, __last, __c);
4258#else
4259 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4260 __sort_heap<_Comp_ref>(__first, __last, __comp);
4261#endif
4262}
4263
4264template <class _RandomAccessIterator>
4265inline _LIBCPP_INLINE_VISIBILITY
4266void
4267sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4268{
4269 _STD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4270}
4271
4272// partial_sort
4273
4274template <class _Compare, class _RandomAccessIterator>
4275void
4276__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4277 _Compare __comp)
4278{
4279 __make_heap<_Compare>(__first, __middle, __comp);
4280 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4281 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
4282 {
4283 if (__comp(*__i, *__first))
4284 {
4285 swap(*__i, *__first);
4286 __push_heap_front<_Compare>(__first, __middle, __comp, __len);
4287 }
4288 }
4289 __sort_heap<_Compare>(__first, __middle, __comp);
4290}
4291
4292template <class _RandomAccessIterator, class _Compare>
4293inline _LIBCPP_INLINE_VISIBILITY
4294void
4295partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4296 _Compare __comp)
4297{
4298#ifdef _LIBCPP_DEBUG
4299 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4300 __debug_less<_Compare> __c(__comp);
4301 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
4302#else
4303 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4304 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
4305#endif
4306}
4307
4308template <class _RandomAccessIterator>
4309inline _LIBCPP_INLINE_VISIBILITY
4310void
4311partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
4312{
4313 _STD::partial_sort(__first, __middle, __last,
4314 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4315}
4316
4317// partial_sort_copy
4318
4319template <class _Compare, class _InputIterator, class _RandomAccessIterator>
4320_RandomAccessIterator
4321__partial_sort_copy(_InputIterator __first, _InputIterator __last,
4322 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4323{
4324 _RandomAccessIterator __r = __result_first;
4325 if (__r != __result_last)
4326 {
4327 typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0;
4328 for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len)
4329 *__r = *__first;
4330 __make_heap<_Compare>(__result_first, __r, __comp);
4331 for (; __first != __last; ++__first)
4332 if (__comp(*__first, *__result_first))
4333 {
4334 *__result_first = *__first;
4335 __push_heap_front<_Compare>(__result_first, __r, __comp, __len);
4336 }
4337 __sort_heap<_Compare>(__result_first, __r, __comp);
4338 }
4339 return __r;
4340}
4341
4342template <class _InputIterator, class _RandomAccessIterator, class _Compare>
4343inline _LIBCPP_INLINE_VISIBILITY
4344_RandomAccessIterator
4345partial_sort_copy(_InputIterator __first, _InputIterator __last,
4346 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4347{
4348#ifdef _LIBCPP_DEBUG
4349 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4350 __debug_less<_Compare> __c(__comp);
4351 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
4352#else
4353 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4354 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
4355#endif
4356}
4357
4358template <class _InputIterator, class _RandomAccessIterator>
4359inline _LIBCPP_INLINE_VISIBILITY
4360_RandomAccessIterator
4361partial_sort_copy(_InputIterator __first, _InputIterator __last,
4362 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
4363{
4364 return _STD::partial_sort_copy(__first, __last, __result_first, __result_last,
4365 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4366}
4367
4368// nth_element
4369
4370template <class _Compare, class _RandomAccessIterator>
4371void
4372__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4373{
4374 // _Compare is known to be a reference type
4375 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4376 const difference_type __limit = 7;
4377 while (true)
4378 {
4379 __restart:
4380 difference_type __len = __last - __first;
4381 switch (__len)
4382 {
4383 case 0:
4384 case 1:
4385 return;
4386 case 2:
4387 if (__comp(*--__last, *__first))
4388 swap(*__first, *__last);
4389 return;
4390 case 3:
4391 {
4392 _RandomAccessIterator __m = __first;
4393 _STD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
4394 return;
4395 }
4396 }
4397 if (__len <= __limit)
4398 {
4399 __selection_sort<_Compare>(__first, __last, __comp);
4400 return;
4401 }
4402 // __len > __limit >= 3
4403 _RandomAccessIterator __m = __first + __len/2;
4404 _RandomAccessIterator __lm1 = __last;
4405 unsigned __n_swaps = _STD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
4406 // *__m is median
4407 // partition [__first, __m) < *__m and *__m <= [__m, __last)
4408 // (this inhibits tossing elements equivalent to __m around unnecessarily)
4409 _RandomAccessIterator __i = __first;
4410 _RandomAccessIterator __j = __lm1;
4411 // j points beyond range to be tested, *__lm1 is known to be <= *__m
4412 // The search going up is known to be guarded but the search coming down isn't.
4413 // Prime the downward search with a guard.
4414 if (!__comp(*__i, *__m)) // if *__first == *__m
4415 {
4416 // *__first == *__m, *__first doesn't go in first part
4417 // manually guard downward moving __j against __i
4418 while (true)
4419 {
4420 if (__i == --__j)
4421 {
4422 // *__first == *__m, *__m <= all other elements
4423 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4424 ++__i; // __first + 1
4425 __j = __last;
4426 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
4427 {
4428 while (true)
4429 {
4430 if (__i == __j)
4431 return; // [__first, __last) all equivalent elements
4432 if (__comp(*__first, *__i))
4433 {
4434 swap(*__i, *__j);
4435 ++__n_swaps;
4436 ++__i;
4437 break;
4438 }
4439 ++__i;
4440 }
4441 }
4442 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4443 if (__i == __j)
4444 return;
4445 while (true)
4446 {
4447 while (!__comp(*__first, *__i))
4448 ++__i;
4449 while (__comp(*__first, *--__j))
4450 ;
4451 if (__i >= __j)
4452 break;
4453 swap(*__i, *__j);
4454 ++__n_swaps;
4455 ++__i;
4456 }
4457 // [__first, __i) == *__first and *__first < [__i, __last)
4458 // The first part is sorted,
4459 if (__nth < __i)
4460 return;
4461 // __nth_element the secod part
4462 // __nth_element<_Compare>(__i, __nth, __last, __comp);
4463 __first = __i;
4464 goto __restart;
4465 }
4466 if (__comp(*__j, *__m))
4467 {
4468 swap(*__i, *__j);
4469 ++__n_swaps;
4470 break; // found guard for downward moving __j, now use unguarded partition
4471 }
4472 }
4473 }
4474 ++__i;
4475 // j points beyond range to be tested, *__lm1 is known to be <= *__m
4476 // if not yet partitioned...
4477 if (__i < __j)
4478 {
4479 // known that *(__i - 1) < *__m
4480 while (true)
4481 {
4482 // __m still guards upward moving __i
4483 while (__comp(*__i, *__m))
4484 ++__i;
4485 // It is now known that a guard exists for downward moving __j
4486 while (!__comp(*--__j, *__m))
4487 ;
4488 if (__i >= __j)
4489 break;
4490 swap(*__i, *__j);
4491 ++__n_swaps;
4492 // It is known that __m != __j
4493 // If __m just moved, follow it
4494 if (__m == __i)
4495 __m = __j;
4496 ++__i;
4497 }
4498 }
4499 // [__first, __i) < *__m and *__m <= [__i, __last)
4500 if (__i != __m && __comp(*__m, *__i))
4501 {
4502 swap(*__i, *__m);
4503 ++__n_swaps;
4504 }
4505 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4506 if (__nth == __i)
4507 return;
4508 if (__n_swaps == 0)
4509 {
4510 // We were given a perfectly partitioned sequence. Coincidence?
4511 if (__nth < __i)
4512 {
4513 // Check for [__first, __i) already sorted
4514 __j = __m = __first;
4515 while (++__j != __i)
4516 {
4517 if (__comp(*__j, *__m))
4518 // not yet sorted, so sort
4519 goto not_sorted;
4520 __m = __j;
4521 }
4522 // [__first, __i) sorted
4523 return;
4524 }
4525 else
4526 {
4527 // Check for [__i, __last) already sorted
4528 __j = __m = __i;
4529 while (++__j != __last)
4530 {
4531 if (__comp(*__j, *__m))
4532 // not yet sorted, so sort
4533 goto not_sorted;
4534 __m = __j;
4535 }
4536 // [__i, __last) sorted
4537 return;
4538 }
4539 }
4540not_sorted:
4541 // __nth_element on range containing __nth
4542 if (__nth < __i)
4543 {
4544 // __nth_element<_Compare>(__first, __nth, __i, __comp);
4545 __last = __i;
4546 }
4547 else
4548 {
4549 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
4550 __first = ++__i;
4551 }
4552 }
4553}
4554
4555template <class _RandomAccessIterator, class _Compare>
4556inline _LIBCPP_INLINE_VISIBILITY
4557void
4558nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4559{
4560#ifdef _LIBCPP_DEBUG
4561 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4562 __debug_less<_Compare> __c(__comp);
4563 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
4564#else
4565 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4566 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
4567#endif
4568}
4569
4570template <class _RandomAccessIterator>
4571inline _LIBCPP_INLINE_VISIBILITY
4572void
4573nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
4574{
4575 _STD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4576}
4577
4578// includes
4579
4580template <class _Compare, class _InputIterator1, class _InputIterator2>
4581bool
4582__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4583 _Compare __comp)
4584{
4585 for (; __first2 != __last2; ++__first1)
4586 {
4587 if (__first1 == __last1 || __comp(*__first2, *__first1))
4588 return false;
4589 if (!__comp(*__first1, *__first2))
4590 ++__first2;
4591 }
4592 return true;
4593}
4594
4595template <class _InputIterator1, class _InputIterator2, class _Compare>
4596inline _LIBCPP_INLINE_VISIBILITY
4597bool
4598includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4599 _Compare __comp)
4600{
4601#ifdef _LIBCPP_DEBUG
4602 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4603 __debug_less<_Compare> __c(__comp);
4604 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
4605#else
4606 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4607 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
4608#endif
4609}
4610
4611template <class _InputIterator1, class _InputIterator2>
4612inline _LIBCPP_INLINE_VISIBILITY
4613bool
4614includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
4615{
4616 return _STD::includes(__first1, __last1, __first2, __last2,
4617 __less<typename iterator_traits<_InputIterator1>::value_type,
4618 typename iterator_traits<_InputIterator2>::value_type>());
4619}
4620
4621// set_union
4622
4623template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4624_OutputIterator
4625__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4626 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4627{
4628 for (; __first1 != __last1; ++__result)
4629 {
4630 if (__first2 == __last2)
4631 return _STD::copy(__first1, __last1, __result);
4632 if (__comp(*__first2, *__first1))
4633 {
4634 *__result = *__first2;
4635 ++__first2;
4636 }
4637 else
4638 {
4639 *__result = *__first1;
4640 if (!__comp(*__first1, *__first2))
4641 ++__first2;
4642 ++__first1;
4643 }
4644 }
4645 return _STD::copy(__first2, __last2, __result);
4646}
4647
4648template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4649inline _LIBCPP_INLINE_VISIBILITY
4650_OutputIterator
4651set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4652 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4653{
4654#ifdef _LIBCPP_DEBUG
4655 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4656 __debug_less<_Compare> __c(__comp);
4657 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4658#else
4659 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4660 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4661#endif
4662}
4663
4664template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4665inline _LIBCPP_INLINE_VISIBILITY
4666_OutputIterator
4667set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4668 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4669{
4670 return _STD::set_union(__first1, __last1, __first2, __last2, __result,
4671 __less<typename iterator_traits<_InputIterator1>::value_type,
4672 typename iterator_traits<_InputIterator2>::value_type>());
4673}
4674
4675// set_intersection
4676
4677template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4678_OutputIterator
4679__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4680 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4681{
4682 while (__first1 != __last1 && __first2 != __last2)
4683 {
4684 if (__comp(*__first1, *__first2))
4685 ++__first1;
4686 else
4687 {
4688 if (!__comp(*__first2, *__first1))
4689 {
4690 *__result = *__first1;
4691 ++__result;
4692 ++__first1;
4693 }
4694 ++__first2;
4695 }
4696 }
4697 return __result;
4698}
4699
4700template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4701inline _LIBCPP_INLINE_VISIBILITY
4702_OutputIterator
4703set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4704 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4705{
4706#ifdef _LIBCPP_DEBUG
4707 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4708 __debug_less<_Compare> __c(__comp);
4709 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4710#else
4711 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4712 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4713#endif
4714}
4715
4716template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4717inline _LIBCPP_INLINE_VISIBILITY
4718_OutputIterator
4719set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4720 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4721{
4722 return _STD::set_intersection(__first1, __last1, __first2, __last2, __result,
4723 __less<typename iterator_traits<_InputIterator1>::value_type,
4724 typename iterator_traits<_InputIterator2>::value_type>());
4725}
4726
4727// set_difference
4728
4729template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4730_OutputIterator
4731__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4732 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4733{
4734 while (__first1 != __last1)
4735 {
4736 if (__first2 == __last2)
4737 return _STD::copy(__first1, __last1, __result);
4738 if (__comp(*__first1, *__first2))
4739 {
4740 *__result = *__first1;
4741 ++__result;
4742 ++__first1;
4743 }
4744 else
4745 {
4746 if (!__comp(*__first2, *__first1))
4747 ++__first1;
4748 ++__first2;
4749 }
4750 }
4751 return __result;
4752}
4753
4754template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4755inline _LIBCPP_INLINE_VISIBILITY
4756_OutputIterator
4757set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4758 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4759{
4760#ifdef _LIBCPP_DEBUG
4761 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4762 __debug_less<_Compare> __c(__comp);
4763 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4764#else
4765 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4766 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4767#endif
4768}
4769
4770template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4771inline _LIBCPP_INLINE_VISIBILITY
4772_OutputIterator
4773set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4774 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4775{
4776 return _STD::set_difference(__first1, __last1, __first2, __last2, __result,
4777 __less<typename iterator_traits<_InputIterator1>::value_type,
4778 typename iterator_traits<_InputIterator2>::value_type>());
4779}
4780
4781// set_symmetric_difference
4782
4783template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4784_OutputIterator
4785__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4786 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4787{
4788 while (__first1 != __last1)
4789 {
4790 if (__first2 == __last2)
4791 return _STD::copy(__first1, __last1, __result);
4792 if (__comp(*__first1, *__first2))
4793 {
4794 *__result = *__first1;
4795 ++__result;
4796 ++__first1;
4797 }
4798 else
4799 {
4800 if (__comp(*__first2, *__first1))
4801 {
4802 *__result = *__first2;
4803 ++__result;
4804 }
4805 else
4806 ++__first1;
4807 ++__first2;
4808 }
4809 }
4810 return _STD::copy(__first2, __last2, __result);
4811}
4812
4813template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4814inline _LIBCPP_INLINE_VISIBILITY
4815_OutputIterator
4816set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4817 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4818{
4819#ifdef _LIBCPP_DEBUG
4820 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4821 __debug_less<_Compare> __c(__comp);
4822 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4823#else
4824 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4825 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4826#endif
4827}
4828
4829template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4830inline _LIBCPP_INLINE_VISIBILITY
4831_OutputIterator
4832set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4833 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4834{
4835 return _STD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
4836 __less<typename iterator_traits<_InputIterator1>::value_type,
4837 typename iterator_traits<_InputIterator2>::value_type>());
4838}
4839
4840// lexicographical_compare
4841
4842template <class _Compare, class _InputIterator1, class _InputIterator2>
4843bool
4844__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
4845 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
4846{
4847 for (; __first2 != __last2; ++__first1, ++__first2)
4848 {
4849 if (__first1 == __last1 || __comp(*__first1, *__first2))
4850 return true;
4851 if (__comp(*__first2, *__first1))
4852 return false;
4853 }
4854 return false;
4855}
4856
4857template <class _InputIterator1, class _InputIterator2, class _Compare>
4858inline _LIBCPP_INLINE_VISIBILITY
4859bool
4860lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
4861 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
4862{
4863#ifdef _LIBCPP_DEBUG
4864 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4865 __debug_less<_Compare> __c(__comp);
4866 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
4867#else
4868 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4869 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
4870#endif
4871}
4872
4873template <class _InputIterator1, class _InputIterator2>
4874inline _LIBCPP_INLINE_VISIBILITY
4875bool
4876lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
4877 _InputIterator2 __first2, _InputIterator2 __last2)
4878{
4879 return _STD::lexicographical_compare(__first1, __last1, __first2, __last2,
4880 __less<typename iterator_traits<_InputIterator1>::value_type,
4881 typename iterator_traits<_InputIterator2>::value_type>());
4882}
4883
4884// next_permutation
4885
4886template <class _Compare, class _BidirectionalIterator>
4887bool
4888__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
4889{
4890 _BidirectionalIterator __i = __last;
4891 if (__first == __last || __first == --__i)
4892 return false;
4893 while (true)
4894 {
4895 _BidirectionalIterator __ip1 = __i;
4896 if (__comp(*--__i, *__ip1))
4897 {
4898 _BidirectionalIterator __j = __last;
4899 while (!__comp(*__i, *--__j))
4900 ;
4901 swap(*__i, *__j);
4902 _STD::reverse(__ip1, __last);
4903 return true;
4904 }
4905 if (__i == __first)
4906 {
4907 _STD::reverse(__first, __last);
4908 return false;
4909 }
4910 }
4911}
4912
4913template <class _BidirectionalIterator, class _Compare>
4914inline _LIBCPP_INLINE_VISIBILITY
4915bool
4916next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
4917{
4918#ifdef _LIBCPP_DEBUG
4919 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4920 __debug_less<_Compare> __c(__comp);
4921 return __next_permutation<_Comp_ref>(__first, __last, __c);
4922#else
4923 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4924 return __next_permutation<_Comp_ref>(__first, __last, __comp);
4925#endif
4926}
4927
4928template <class _BidirectionalIterator>
4929inline _LIBCPP_INLINE_VISIBILITY
4930bool
4931next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
4932{
4933 return _STD::next_permutation(__first, __last,
4934 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4935}
4936
4937// prev_permutation
4938
4939template <class _Compare, class _BidirectionalIterator>
4940bool
4941__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
4942{
4943 _BidirectionalIterator __i = __last;
4944 if (__first == __last || __first == --__i)
4945 return false;
4946 while (true)
4947 {
4948 _BidirectionalIterator __ip1 = __i;
4949 if (__comp(*__ip1, *--__i))
4950 {
4951 _BidirectionalIterator __j = __last;
4952 while (!__comp(*--__j, *__i))
4953 ;
4954 swap(*__i, *__j);
4955 _STD::reverse(__ip1, __last);
4956 return true;
4957 }
4958 if (__i == __first)
4959 {
4960 _STD::reverse(__first, __last);
4961 return false;
4962 }
4963 }
4964}
4965
4966template <class _BidirectionalIterator, class _Compare>
4967inline _LIBCPP_INLINE_VISIBILITY
4968bool
4969prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
4970{
4971#ifdef _LIBCPP_DEBUG
4972 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4973 __debug_less<_Compare> __c(__comp);
4974 return __prev_permutation<_Comp_ref>(__first, __last, __c);
4975#else
4976 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4977 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
4978#endif
4979}
4980
4981template <class _BidirectionalIterator>
4982inline _LIBCPP_INLINE_VISIBILITY
4983bool
4984prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
4985{
4986 return _STD::prev_permutation(__first, __last,
4987 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4988}
4989
4990template <class _Tp>
4991inline _LIBCPP_INLINE_VISIBILITY
4992typename enable_if
4993<
4994 is_integral<_Tp>::value,
4995 _Tp
4996>::type
4997__rotate_left(_Tp __t, _Tp __n = 1)
4998{
4999 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5000 __n &= __bits;
5001 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5002}
5003
5004template <class _Tp>
5005inline _LIBCPP_INLINE_VISIBILITY
5006typename enable_if
5007<
5008 is_integral<_Tp>::value,
5009 _Tp
5010>::type
5011__rotate_right(_Tp __t, _Tp __n = 1)
5012{
5013 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5014 __n &= __bits;
5015 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5016}
5017
5018// Precondition: __x != 0
5019inline _LIBCPP_INLINE_VISIBILITY unsigned __ctz(unsigned __x) {return __builtin_ctz (__x);}
5020inline _LIBCPP_INLINE_VISIBILITY unsigned long __ctz(unsigned long __x) {return __builtin_ctzl (__x);}
5021inline _LIBCPP_INLINE_VISIBILITY unsigned long long __ctz(unsigned long long __x) {return __builtin_ctzll(__x);}
5022
5023// Precondition: __x != 0
5024inline _LIBCPP_INLINE_VISIBILITY unsigned __clz(unsigned __x) {return __builtin_clz (__x);}
5025inline _LIBCPP_INLINE_VISIBILITY unsigned long __clz(unsigned long __x) {return __builtin_clzl (__x);}
5026inline _LIBCPP_INLINE_VISIBILITY unsigned long long __clz(unsigned long long __x) {return __builtin_clzll(__x);}
5027
5028inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}
5029inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}
5030inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
5031
5032_LIBCPP_END_NAMESPACE_STD
5033
5034#endif // _LIBCPP_ALGORITHM