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