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