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