Google Git
Sign in
flutter / third_party / libcxx / refs/heads/upstream/release_35 / . / include / algorithm
blob: 3b74a6b2736f47a1cde91cfca0470285cdb96e15 [file] [log] [blame] [edit]
// -*- C++ -*-
//===-------------------------- algorithm ---------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP_ALGORITHM
#define _LIBCPP_ALGORITHM
/*
algorithm synopsis
#include <initializer_list>
namespace std
{
template <class InputIterator, class Predicate>
bool
all_of(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator, class Predicate>
bool
any_of(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator, class Predicate>
bool
none_of(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator, class Function>
Function
for_each(InputIterator first, InputIterator last, Function f);
template <class InputIterator, class T>
InputIterator
find(InputIterator first, InputIterator last, const T& value);
template <class InputIterator, class Predicate>
InputIterator
find_if(InputIterator first, InputIterator last, Predicate pred);
template<class InputIterator, class Predicate>
InputIterator
find_if_not(InputIterator first, InputIterator last, Predicate pred);
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
template <class ForwardIterator>
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2); // **C++14**
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred); // **C++14**
template <class InputIterator1, class InputIterator2>
bool
equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator1, class InputIterator2>
bool
equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2); // **C++14**
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool
equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool
equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred); // **C++14**
template<class ForwardIterator1, class ForwardIterator2>
bool
is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ForwardIterator1, class ForwardIterator2>
bool
is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool
is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool
is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred); // **C++14**
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
template <class ForwardIterator, class Size, class T>
ForwardIterator
search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator
search_n(ForwardIterator first, ForwardIterator last,
Size count, const T& value, BinaryPredicate pred);
template <class InputIterator, class OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result);
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator
copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class InputIterator, class Size, class OutputIterator>
OutputIterator
copy_n(InputIterator first, Size n, OutputIterator result);
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
BidirectionalIterator2 result);
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
template <class ForwardIterator1, class ForwardIterator2>
void
iter_swap(ForwardIterator1 a, ForwardIterator2 b);
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator
transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
OutputIterator
transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
OutputIterator result, BinaryOperation binary_op);
template <class ForwardIterator, class T>
void
replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
template <class ForwardIterator, class Predicate, class T>
void
replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
template <class InputIterator, class OutputIterator, class T>
OutputIterator
replace_copy(InputIterator first, InputIterator last, OutputIterator result,
const T& old_value, const T& new_value);
template <class InputIterator, class OutputIterator, class Predicate, class T>
OutputIterator
replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
template <class ForwardIterator, class T>
void
fill(ForwardIterator first, ForwardIterator last, const T& value);
template <class OutputIterator, class Size, class T>
OutputIterator
fill_n(OutputIterator first, Size n, const T& value);
template <class ForwardIterator, class Generator>
void
generate(ForwardIterator first, ForwardIterator last, Generator gen);
template <class OutputIterator, class Size, class Generator>
OutputIterator
generate_n(OutputIterator first, Size n, Generator gen);
template <class ForwardIterator, class T>
ForwardIterator
remove(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class Predicate>
ForwardIterator
remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
template <class InputIterator, class OutputIterator, class T>
OutputIterator
remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator
remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
template <class ForwardIterator>
ForwardIterator
unique(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator
unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
template <class InputIterator, class OutputIterator>
OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
template <class BidirectionalIterator>
void
reverse(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class OutputIterator>
OutputIterator
reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
template <class ForwardIterator>
ForwardIterator
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
template <class ForwardIterator, class OutputIterator>
OutputIterator
rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
template <class RandomAccessIterator>
void
random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14
template <class RandomAccessIterator, class RandomNumberGenerator>
void
random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand); // deprecated in C++14
template<class RandomAccessIterator, class UniformRandomNumberGenerator>
void shuffle(RandomAccessIterator first, RandomAccessIterator last,
UniformRandomNumberGenerator&& g);
template <class InputIterator, class Predicate>
bool
is_partitioned(InputIterator first, InputIterator last, Predicate pred);
template <class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first, ForwardIterator last, Predicate pred);
template <class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false,
Predicate pred);
template <class ForwardIterator, class Predicate>
ForwardIterator
stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
template<class ForwardIterator, class Predicate>
ForwardIterator
partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
template <class ForwardIterator>
bool
is_sorted(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
bool
is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
template<class ForwardIterator>
ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
template <class RandomAccessIterator>
void
sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
void
stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
void
partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first, RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
template <class RandomAccessIterator>
void
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
template <class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
template <class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
template <class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
template <class BidirectionalIterator>
void
inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
void
inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
template <class InputIterator1, class InputIterator2>
bool
includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class Compare>
bool
includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
template <class RandomAccessIterator>
void
push_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
void
pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
void
make_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
void
sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
bool
is_heap(RandomAccessIterator first, RandomAccessiterator last);
template <class RandomAccessIterator, class Compare>
bool
is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
template <class RandomAccessIterator>
RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
template <class RandomAccessIterator, class Compare>
RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
template <class ForwardIterator>
ForwardIterator
min_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator
min_element(ForwardIterator first, ForwardIterator last, Compare comp);
template <class T>
const T&
min(const T& a, const T& b); // constexpr in C++14
template <class T, class Compare>
const T&
min(const T& a, const T& b, Compare comp); // constexpr in C++14
template<class T>
T
min(initializer_list<T> t); // constexpr in C++14
template<class T, class Compare>
T
min(initializer_list<T> t, Compare comp); // constexpr in C++14
template <class ForwardIterator>
ForwardIterator
max_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator
max_element(ForwardIterator first, ForwardIterator last, Compare comp);
template <class T>
const T&
max(const T& a, const T& b); // constexpr in C++14
template <class T, class Compare>
const T&
max(const T& a, const T& b, Compare comp); // constexpr in C++14
template<class T>
T
max(initializer_list<T> t); // constexpr in C++14
template<class T, class Compare>
T
max(initializer_list<T> t, Compare comp); // constexpr in C++14
template<class ForwardIterator>
pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
template<class T>
pair<const T&, const T&>
minmax(const T& a, const T& b); // constexpr in C++14
template<class T, class Compare>
pair<const T&, const T&>
minmax(const T& a, const T& b, Compare comp); // constexpr in C++14
template<class T>
pair<T, T>
minmax(initializer_list<T> t); // constexpr in C++14
template<class T, class Compare>
pair<T, T>
minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
template <class InputIterator1, class InputIterator2>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class Compare>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);
template <class BidirectionalIterator>
bool
next_permutation(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
bool
next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
template <class BidirectionalIterator>
bool
prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
bool
prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
} // std
*/
#include <__config>
#include <initializer_list>
#include <type_traits>
#include <cstring>
#include <utility>
#include <memory>
#include <iterator>
#include <cstddef>
#if defined(__IBMCPP__)
#include "support/ibm/support.h"
#endif
#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)
#include "support/win32/support.h"
#endif
#include <__undef_min_max>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_BEGIN_NAMESPACE_STD
// I'd like to replace these with _VSTD::equal_to<void>, but can't because:
// * That only works with C++14 and later, and
// * We haven't included <functional> here.
template <class _T1, class _T2 = _T1>
struct __equal_to
{
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
};
template <class _T1>
struct __equal_to<_T1, _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
};
template <class _T1>
struct __equal_to<const _T1, _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
};
template <class _T1>
struct __equal_to<_T1, const _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
};
template <class _T1, class _T2 = _T1>
struct __less
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
};
template <class _T1>
struct __less<_T1, _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
};
template <class _T1>
struct __less<const _T1, _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
};
template <class _T1>
struct __less<_T1, const _T1>
{
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
};
template <class _Predicate>
class __negate
{
private:
_Predicate __p_;
public:
_LIBCPP_INLINE_VISIBILITY __negate() {}
_LIBCPP_INLINE_VISIBILITY
explicit __negate(_Predicate __p) : __p_(__p) {}
template <class _T1>
_LIBCPP_INLINE_VISIBILITY
bool operator()(const _T1& __x) {return !__p_(__x);}
template <class _T1, class _T2>
_LIBCPP_INLINE_VISIBILITY
bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
};
#ifdef _LIBCPP_DEBUG
template <class _Compare>
struct __debug_less
{
_Compare __comp_;
__debug_less(_Compare& __c) : __comp_(__c) {}
template <class _Tp, class _Up>
bool operator()(const _Tp& __x, const _Up& __y)
{
bool __r = __comp_(__x, __y);
if (__r)
_LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");
return __r;
}
};
#endif // _LIBCPP_DEBUG
// Precondition: __x != 0
inline _LIBCPP_INLINE_VISIBILITY
unsigned
__ctz(unsigned __x)
{
return static_cast<unsigned>(__builtin_ctz(__x));
}
inline _LIBCPP_INLINE_VISIBILITY
unsigned long
__ctz(unsigned long __x)
{
return static_cast<unsigned long>(__builtin_ctzl(__x));
}
inline _LIBCPP_INLINE_VISIBILITY
unsigned long long
__ctz(unsigned long long __x)
{
return static_cast<unsigned long long>(__builtin_ctzll(__x));
}
// Precondition: __x != 0
inline _LIBCPP_INLINE_VISIBILITY
unsigned
__clz(unsigned __x)
{
return static_cast<unsigned>(__builtin_clz(__x));
}
inline _LIBCPP_INLINE_VISIBILITY
unsigned long
__clz(unsigned long __x)
{
return static_cast<unsigned long>(__builtin_clzl (__x));
}
inline _LIBCPP_INLINE_VISIBILITY
unsigned long long
__clz(unsigned long long __x)
{
return static_cast<unsigned long long>(__builtin_clzll(__x));
}
inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}
inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}
inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
// all_of
template <class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (!__pred(*__first))
return false;
return true;
}
// any_of
template <class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
return true;
return false;
}
// none_of
template <class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
return false;
return true;
}
// for_each
template <class _InputIterator, class _Function>
inline _LIBCPP_INLINE_VISIBILITY
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
for (; __first != __last; ++__first)
__f(*__first);
return _VSTD::move(__f); // explicitly moved for (emulated) C++03
}
// find
template <class _InputIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_InputIterator
find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
for (; __first != __last; ++__first)
if (*__first == __value_)
break;
return __first;
}
// find_if
template <class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_InputIterator
find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
break;
return __first;
}
// find_if_not
template<class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_InputIterator
find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (!__pred(*__first))
break;
return __first;
}
// find_end
template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
_ForwardIterator1
__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
forward_iterator_tag, forward_iterator_tag)
{
// modeled after search algorithm
_ForwardIterator1 __r = __last1; // __last1 is the "default" answer
if (__first2 == __last2)
return __r;
while (true)
{
while (true)
{
if (__first1 == __last1) // if source exhausted return last correct answer
return __r; // (or __last1 if never found)
if (__pred(*__first1, *__first2))
break;
++__first1;
}
// *__first1 matches *__first2, now match elements after here
_ForwardIterator1 __m1 = __first1;
_ForwardIterator2 __m2 = __first2;
while (true)
{
if (++__m2 == __last2)
{ // Pattern exhaused, record answer and search for another one
__r = __first1;
++__first1;
break;
}
if (++__m1 == __last1) // Source exhausted, return last answer
return __r;
if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
{
++__first1;
break;
} // else there is a match, check next elements
}
}
}
template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
_BidirectionalIterator1
__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
_BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
bidirectional_iterator_tag, bidirectional_iterator_tag)
{
// modeled after search algorithm (in reverse)
if (__first2 == __last2)
return __last1; // Everything matches an empty sequence
_BidirectionalIterator1 __l1 = __last1;
_BidirectionalIterator2 __l2 = __last2;
--__l2;
while (true)
{
// Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
while (true)
{
if (__first1 == __l1) // return __last1 if no element matches *__first2
return __last1;
if (__pred(*--__l1, *__l2))
break;
}
// *__l1 matches *__l2, now match elements before here
_BidirectionalIterator1 __m1 = __l1;
_BidirectionalIterator2 __m2 = __l2;
while (true)
{
if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
return __m1;
if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
return __last1;
if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
{
break;
} // else there is a match, check next elements
}
}
}
template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
_RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
random_access_iterator_tag, random_access_iterator_tag)
{
// Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
if (__len2 == 0)
return __last1;
typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
if (__len1 < __len2)
return __last1;
const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
_RandomAccessIterator1 __l1 = __last1;
_RandomAccessIterator2 __l2 = __last2;
--__l2;
while (true)
{
while (true)
{
if (__s == __l1)
return __last1;
if (__pred(*--__l1, *__l2))
break;
}
_RandomAccessIterator1 __m1 = __l1;
_RandomAccessIterator2 __m2 = __l2;
while (true)
{
if (__m2 == __first2)
return __m1;
// no need to check range on __m1 because __s guarantees we have enough source
if (!__pred(*--__m1, *--__m2))
{
break;
}
}
}
}
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
{
return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __last2, __pred,
typename iterator_traits<_ForwardIterator1>::iterator_category(),
typename iterator_traits<_ForwardIterator2>::iterator_category());
}
template <class _ForwardIterator1, class _ForwardIterator2>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
}
// find_first_of
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
{
for (; __first1 != __last1; ++__first1)
for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
if (__pred(*__first1, *__j))
return __first1;
return __last1;
}
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
{
return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
}
template <class _ForwardIterator1, class _ForwardIterator2>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
}
// adjacent_find
template <class _ForwardIterator, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
{
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
{
if (__pred(*__first, *__i))
return __first;
__first = __i;
}
}
return __last;
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
{
typedef typename iterator_traits<_ForwardIterator>::value_type __v;
return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
}
// count
template <class _InputIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
typename iterator_traits<_InputIterator>::difference_type
count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
typename iterator_traits<_InputIterator>::difference_type __r(0);
for (; __first != __last; ++__first)
if (*__first == __value_)
++__r;
return __r;
}
// count_if
template <class _InputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __r(0);
for (; __first != __last; ++__first)
if (__pred(*__first))
++__r;
return __r;
}
// mismatch
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _BinaryPredicate __pred)
{
for (; __first1 != __last1; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
break;
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
template <class _InputIterator1, class _InputIterator2>
inline _LIBCPP_INLINE_VISIBILITY
pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
{
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
}
#if _LIBCPP_STD_VER > 11
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_BinaryPredicate __pred)
{
for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
break;
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
template <class _InputIterator1, class _InputIterator2>
inline _LIBCPP_INLINE_VISIBILITY
pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
}
#endif
// equal
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
{
for (; __first1 != __last1; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
return false;
return true;
}
template <class _InputIterator1, class _InputIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
{
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
}
#if _LIBCPP_STD_VER > 11
template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
__equal(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
input_iterator_tag, input_iterator_tag )
{
for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
return false;
return __first1 == __last1 && __first2 == __last2;
}
template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
_RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
random_access_iterator_tag, random_access_iterator_tag )
{
if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
return false;
return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __pred );
}
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
equal(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
{
return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __last2, __pred,
typename iterator_traits<_InputIterator1>::iterator_category(),
typename iterator_traits<_InputIterator2>::iterator_category());
}
template <class _InputIterator1, class _InputIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
equal(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
typename iterator_traits<_InputIterator1>::iterator_category(),
typename iterator_traits<_InputIterator2>::iterator_category());
}
#endif
// is_permutation
template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _BinaryPredicate __pred)
{
// shorten sequences as much as possible by lopping of any equal parts
for (; __first1 != __last1; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
goto __not_done;
return true;
__not_done:
// __first1 != __last1 && *__first1 != *__first2
typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
_D1 __l1 = _VSTD::distance(__first1, __last1);
if (__l1 == _D1(1))
return false;
_ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
// For each element in [f1, l1) see if there are the same number of
// equal elements in [f2, l2)
for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
{
// Have we already counted the number of *__i in [f1, l1)?
for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
if (__pred(*__j, *__i))
goto __next_iter;
{
// Count number of *__i in [f2, l2)
_D1 __c2 = 0;
for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
if (__pred(*__i, *__j))
++__c2;
if (__c2 == 0)
return false;
// Count number of *__i in [__i, l1) (we can start with 1)
_D1 __c1 = 1;
for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
if (__pred(*__i, *__j))
++__c1;
if (__c1 != __c2)
return false;
}
__next_iter:;
}
return true;
}
template<class _ForwardIterator1, class _ForwardIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2)
{
typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
}
#if _LIBCPP_STD_VER > 11
template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
bool
__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __pred,
forward_iterator_tag, forward_iterator_tag )
{
// shorten sequences as much as possible by lopping of any equal parts
for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
if (!__pred(*__first1, *__first2))
goto __not_done;
return __first1 == __last1 && __first2 == __last2;
__not_done:
// __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2
typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
_D1 __l1 = _VSTD::distance(__first1, __last1);
typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
_D2 __l2 = _VSTD::distance(__first2, __last2);
if (__l1 != __l2)
return false;
// For each element in [f1, l1) see if there are the same number of
// equal elements in [f2, l2)
for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
{
// Have we already counted the number of *__i in [f1, l1)?
for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
if (__pred(*__j, *__i))
goto __next_iter;
{
// Count number of *__i in [f2, l2)
_D1 __c2 = 0;
for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
if (__pred(*__i, *__j))
++__c2;
if (__c2 == 0)
return false;
// Count number of *__i in [__i, l1) (we can start with 1)
_D1 __c1 = 1;
for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
if (__pred(*__i, *__j))
++__c1;
if (__c1 != __c2)
return false;
}
__next_iter:;
}
return true;
}
template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
bool
__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
_RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
_BinaryPredicate __pred,
random_access_iterator_tag, random_access_iterator_tag )
{
if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
return false;
return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __pred );
}
template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __pred )
{
return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __last2, __pred,
typename iterator_traits<_ForwardIterator1>::iterator_category(),
typename iterator_traits<_ForwardIterator2>::iterator_category());
}
template<class _ForwardIterator1, class _ForwardIterator2>
inline _LIBCPP_INLINE_VISIBILITY
bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
__equal_to<__v1, __v2>(),
typename iterator_traits<_ForwardIterator1>::iterator_category(),
typename iterator_traits<_ForwardIterator2>::iterator_category());
}
#endif
// search
template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
_ForwardIterator1
__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
forward_iterator_tag, forward_iterator_tag)
{
if (__first2 == __last2)
return __first1; // Everything matches an empty sequence
while (true)
{
// Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
while (true)
{
if (__first1 == __last1) // return __last1 if no element matches *__first2
return __last1;
if (__pred(*__first1, *__first2))
break;
++__first1;
}
// *__first1 matches *__first2, now match elements after here
_ForwardIterator1 __m1 = __first1;
_ForwardIterator2 __m2 = __first2;
while (true)
{
if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
return __first1;
if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
return __last1;
if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
{
++__first1;
break;
} // else there is a match, check next elements
}
}
}
template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
_RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
random_access_iterator_tag, random_access_iterator_tag)
{
typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1;
typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2;
// Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
_D2 __len2 = __last2 - __first2;
if (__len2 == 0)
return __first1;
_D1 __len1 = __last1 - __first1;
if (__len1 < __len2)
return __last1;
const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
while (true)
{
#if !_LIBCPP_UNROLL_LOOPS
while (true)
{
if (__first1 == __s)
return __last1;
if (__pred(*__first1, *__first2))
break;
++__first1;
}
#else // !_LIBCPP_UNROLL_LOOPS
for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
{
if (__pred(*__first1, *__first2))
goto __phase2;
if (__pred(*++__first1, *__first2))
goto __phase2;
if (__pred(*++__first1, *__first2))
goto __phase2;
if (__pred(*++__first1, *__first2))
goto __phase2;
++__first1;
}
switch (__s - __first1)
{
case 3:
if (__pred(*__first1, *__first2))
break;
++__first1;
case 2:
if (__pred(*__first1, *__first2))
break;
++__first1;
case 1:
if (__pred(*__first1, *__first2))
break;
case 0:
return __last1;
}
__phase2:
#endif // !_LIBCPP_UNROLL_LOOPS
_RandomAccessIterator1 __m1 = __first1;
_RandomAccessIterator2 __m2 = __first2;
#if !_LIBCPP_UNROLL_LOOPS
while (true)
{
if (++__m2 == __last2)
return __first1;
++__m1; // no need to check range on __m1 because __s guarantees we have enough source
if (!__pred(*__m1, *__m2))
{
++__first1;
break;
}
}
#else // !_LIBCPP_UNROLL_LOOPS
++__m2;
++__m1;
for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
{
if (!__pred(*__m1, *__m2))
goto __continue;
if (!__pred(*++__m1, *++__m2))
goto __continue;
if (!__pred(*++__m1, *++__m2))
goto __continue;
if (!__pred(*++__m1, *++__m2))
goto __continue;
++__m1;
++__m2;
}
switch (__last2 - __m2)
{
case 3:
if (!__pred(*__m1, *__m2))
break;
++__m1;
++__m2;
case 2:
if (!__pred(*__m1, *__m2))
break;
++__m1;
++__m2;
case 1:
if (!__pred(*__m1, *__m2))
break;
case 0:
return __first1;
}
__continue:
++__first1;
#endif // !_LIBCPP_UNROLL_LOOPS
}
}
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
{
return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first1, __last1, __first2, __last2, __pred,
typename std::iterator_traits<_ForwardIterator1>::iterator_category(),
typename std::iterator_traits<_ForwardIterator2>::iterator_category());
}
template <class _ForwardIterator1, class _ForwardIterator2>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1;
typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2;
return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
}
// search_n
template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
_ForwardIterator
__search_n(_ForwardIterator __first, _ForwardIterator __last,
_Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
{
if (__count <= 0)
return __first;
while (true)
{
// Find first element in sequence that matchs __value_, with a mininum of loop checks
while (true)
{
if (__first == __last) // return __last if no element matches __value_
return __last;
if (__pred(*__first, __value_))
break;
++__first;
}
// *__first matches __value_, now match elements after here
_ForwardIterator __m = __first;
_Size __c(0);
while (true)
{
if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
return __first;
if (++__m == __last) // Otherwise if source exhaused, pattern not found
return __last;
if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
{
__first = __m;
++__first;
break;
} // else there is a match, check next elements
}
}
}
template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
_RandomAccessIterator
__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
{
if (__count <= 0)
return __first;
_Size __len = static_cast<_Size>(__last - __first);
if (__len < __count)
return __last;
const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
while (true)
{
// Find first element in sequence that matchs __value_, with a mininum of loop checks
while (true)
{
if (__first >= __s) // return __last if no element matches __value_
return __last;
if (__pred(*__first, __value_))
break;
++__first;
}
// *__first matches __value_, now match elements after here
_RandomAccessIterator __m = __first;
_Size __c(0);
while (true)
{
if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
return __first;
++__m; // no need to check range on __m because __s guarantees we have enough source
if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
{
__first = __m;
++__first;
break;
} // else there is a match, check next elements
}
}
}
template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Size __count, const _Tp& __value_, _BinaryPredicate __pred)
{
return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
}
template <class _ForwardIterator, class _Size, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
{
typedef typename iterator_traits<_ForwardIterator>::value_type __v;
return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>());
}
// copy
template <class _Iter>
struct __libcpp_is_trivial_iterator
{
static const bool value = is_pointer<_Iter>::value;
};
template <class _Iter>
struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
{
static const bool value = is_pointer<_Iter>::value;
};
template <class _Iter>
struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
{
static const bool value = is_pointer<_Iter>::value;
};
template <class _Iter>
inline _LIBCPP_INLINE_VISIBILITY
_Iter
__unwrap_iter(_Iter __i)
{
return __i;
}
template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_trivially_copy_assignable<_Tp>::value,
_Tp*
>::type
__unwrap_iter(move_iterator<_Tp*> __i)
{
return __i.base();
}
#if _LIBCPP_DEBUG_LEVEL < 2
template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_trivially_copy_assignable<_Tp>::value,
_Tp*
>::type
__unwrap_iter(__wrap_iter<_Tp*> __i)
{
return __i.base();
}
#endif // _LIBCPP_DEBUG_LEVEL < 2
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
for (; __first != __last; ++__first, ++__result)
*__result = *__first;
return __result;
}
template <class _Tp, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_same<typename remove_const<_Tp>::type, _Up>::value &&
is_trivially_copy_assignable<_Up>::value,
_Up*
>::type
__copy(_Tp* __first, _Tp* __last, _Up* __result)
{
const size_t __n = static_cast<size_t>(__last - __first);
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
return __result + __n;
}
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
}
// copy_backward
template <class _BidirectionalIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
{
while (__first != __last)
*--__result = *--__last;
return __result;
}
template <class _Tp, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_same<typename remove_const<_Tp>::type, _Up>::value &&
is_trivially_copy_assignable<_Up>::value,
_Up*
>::type
__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
{
const size_t __n = static_cast<size_t>(__last - __first);
__result -= __n;
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
return __result;
}
template <class _BidirectionalIterator1, class _BidirectionalIterator2>
inline _LIBCPP_INLINE_VISIBILITY
_BidirectionalIterator2
copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
_BidirectionalIterator2 __result)
{
return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
}
// copy_if
template<class _InputIterator, class _OutputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _Predicate __pred)
{
for (; __first != __last; ++__first)
{
if (__pred(*__first))
{
*__result = *__first;
++__result;
}
}
return __result;
}
// copy_n
template<class _InputIterator, class _Size, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_input_iterator<_InputIterator>::value &&
!__is_random_access_iterator<_InputIterator>::value,
_OutputIterator
>::type
copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
{
if (__n > 0)
{
*__result = *__first;
++__result;
for (--__n; __n > 0; --__n)
{
++__first;
*__result = *__first;
++__result;
}
}
return __result;
}
template<class _InputIterator, class _Size, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_random_access_iterator<_InputIterator>::value,
_OutputIterator
>::type
copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
{
return _VSTD::copy(__first, __first + __n, __result);
}
// move
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
for (; __first != __last; ++__first, ++__result)
*__result = _VSTD::move(*__first);
return __result;
}
template <class _Tp, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_same<typename remove_const<_Tp>::type, _Up>::value &&
is_trivially_copy_assignable<_Up>::value,
_Up*
>::type
__move(_Tp* __first, _Tp* __last, _Up* __result)
{
const size_t __n = static_cast<size_t>(__last - __first);
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
return __result + __n;
}
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
}
// move_backward
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
while (__first != __last)
*--__result = _VSTD::move(*--__last);
return __result;
}
template <class _Tp, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_same<typename remove_const<_Tp>::type, _Up>::value &&
is_trivially_copy_assignable<_Up>::value,
_Up*
>::type
__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
{
const size_t __n = static_cast<size_t>(__last - __first);
__result -= __n;
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
return __result;
}
template <class _BidirectionalIterator1, class _BidirectionalIterator2>
inline _LIBCPP_INLINE_VISIBILITY
_BidirectionalIterator2
move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
_BidirectionalIterator2 __result)
{
return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
}
// iter_swap
// moved to <type_traits> for better swap / noexcept support
// transform
template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
{
for (; __first != __last; ++__first, ++__result)
*__result = __op(*__first);
return __result;
}
template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
_OutputIterator __result, _BinaryOperation __binary_op)
{
for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
*__result = __binary_op(*__first1, *__first2);
return __result;
}
// replace
template <class _ForwardIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
void
replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
{
for (; __first != __last; ++__first)
if (*__first == __old_value)
*__first = __new_value;
}
// replace_if
template <class _ForwardIterator, class _Predicate, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
void
replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
*__first = __new_value;
}
// replace_copy
template <class _InputIterator, class _OutputIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
const _Tp& __old_value, const _Tp& __new_value)
{
for (; __first != __last; ++__first, ++__result)
if (*__first == __old_value)
*__result = __new_value;
else
*__result = *__first;
return __result;
}
// replace_copy_if
template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
_Predicate __pred, const _Tp& __new_value)
{
for (; __first != __last; ++__first, ++__result)
if (__pred(*__first))
*__result = __new_value;
else
*__result = *__first;
return __result;
}
// fill_n
template <class _OutputIterator, class _Size, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
{
for (; __n > 0; ++__first, --__n)
*__first = __value_;
return __first;
}
template <class _Tp, class _Size, class _Up>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if
<
is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
!is_same<_Tp, bool>::value &&
is_integral<_Up>::value && sizeof(_Up) == 1,
_Tp*
>::type
__fill_n(_Tp* __first, _Size __n,_Up __value_)
{
if (__n > 0)
_VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
return __first + __n;
}
template <class _OutputIterator, class _Size, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
{
return _VSTD::__fill_n(__first, __n, __value_);
}
// fill
template <class _ForwardIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
void
__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
{
for (; __first != __last; ++__first)
*__first = __value_;
}
template <class _RandomAccessIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
void
__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
{
_VSTD::fill_n(__first, __last - __first, __value_);
}
template <class _ForwardIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
void
fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
{
_VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
}
// generate
template <class _ForwardIterator, class _Generator>
inline _LIBCPP_INLINE_VISIBILITY
void
generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
{
for (; __first != __last; ++__first)
*__first = __gen();
}
// generate_n
template <class _OutputIterator, class _Size, class _Generator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
{
for (; __n > 0; ++__first, --__n)
*__first = __gen();
return __first;
}
// remove
template <class _ForwardIterator, class _Tp>
_ForwardIterator
remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
{
__first = _VSTD::find(__first, __last, __value_);
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
{
if (!(*__i == __value_))
{
*__first = _VSTD::move(*__i);
++__first;
}
}
}
return __first;
}
// remove_if
template <class _ForwardIterator, class _Predicate>
_ForwardIterator
remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
__first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
(__first, __last, __pred);
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
{
if (!__pred(*__i))
{
*__first = _VSTD::move(*__i);
++__first;
}
}
}
return __first;
}
// remove_copy
template <class _InputIterator, class _OutputIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
{
for (; __first != __last; ++__first)
{
if (!(*__first == __value_))
{
*__result = *__first;
++__result;
}
}
return __result;
}
// remove_copy_if
template <class _InputIterator, class _OutputIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
{
for (; __first != __last; ++__first)
{
if (!__pred(*__first))
{
*__result = *__first;
++__result;
}
}
return __result;
}
// unique
template <class _ForwardIterator, class _BinaryPredicate>
_ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
{
__first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
(__first, __last, __pred);
if (__first != __last)
{
// ... a a ? ...
// f i
_ForwardIterator __i = __first;
for (++__i; ++__i != __last;)
if (!__pred(*__first, *__i))
*++__first = _VSTD::move(*__i);
++__first;
}
return __first;
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last)
{
typedef typename iterator_traits<_ForwardIterator>::value_type __v;
return _VSTD::unique(__first, __last, __equal_to<__v>());
}
// unique_copy
template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
_OutputIterator
__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
input_iterator_tag, output_iterator_tag)
{
if (__first != __last)
{
typename iterator_traits<_InputIterator>::value_type __t(*__first);
*__result = __t;
++__result;
while (++__first != __last)
{
if (!__pred(__t, *__first))
{
__t = *__first;
*__result = __t;
++__result;
}
}
}
return __result;
}
template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
_OutputIterator
__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
forward_iterator_tag, output_iterator_tag)
{
if (__first != __last)
{
_ForwardIterator __i = __first;
*__result = *__i;
++__result;
while (++__first != __last)
{
if (!__pred(*__i, *__first))
{
*__result = *__first;
++__result;
__i = __first;
}
}
}
return __result;
}
template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
_ForwardIterator
__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
input_iterator_tag, forward_iterator_tag)
{
if (__first != __last)
{
*__result = *__first;
while (++__first != __last)
if (!__pred(*__result, *__first))
*++__result = *__first;
++__result;
}
return __result;
}
template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
{
return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
(__first, __last, __result, __pred,
typename iterator_traits<_InputIterator>::iterator_category(),
typename iterator_traits<_OutputIterator>::iterator_category());
}
template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
{
typedef typename iterator_traits<_InputIterator>::value_type __v;
return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
}
// reverse
template <class _BidirectionalIterator>
inline _LIBCPP_INLINE_VISIBILITY
void
__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
{
while (__first != __last)
{
if (__first == --__last)
break;
swap(*__first, *__last);
++__first;
}
}
template <class _RandomAccessIterator>
inline _LIBCPP_INLINE_VISIBILITY
void
__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
{
if (__first != __last)
for (; __first < --__last; ++__first)
swap(*__first, *__last);
}
template <class _BidirectionalIterator>
inline _LIBCPP_INLINE_VISIBILITY
void
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
{
_VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
}
// reverse_copy
template <class _BidirectionalIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
{
for (; __first != __last; ++__result)
*__result = *--__last;
return __result;
}
// rotate
template <class _ForwardIterator>
_ForwardIterator
__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
{
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
value_type __tmp = _VSTD::move(*__first);
_ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
*__lm1 = _VSTD::move(__tmp);
return __lm1;
}
template <class _BidirectionalIterator>
_BidirectionalIterator
__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
{
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
_BidirectionalIterator __lm1 = _VSTD::prev(__last);
value_type __tmp = _VSTD::move(*__lm1);
_BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
*__first = _VSTD::move(__tmp);
return __fp1;
}
template <class _ForwardIterator>
_ForwardIterator
__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
{
_ForwardIterator __i = __middle;
while (true)
{
swap(*__first, *__i);
++__first;
if (++__i == __last)
break;
if (__first == __middle)
__middle = __i;
}
_ForwardIterator __r = __first;
if (__first != __middle)
{
__i = __middle;
while (true)
{
swap(*__first, *__i);
++__first;
if (++__i == __last)
{
if (__first == __middle)
break;
__i = __middle;
}
else if (__first == __middle)
__middle = __i;
}
}
return __r;
}
template<typename _Integral>
inline _LIBCPP_INLINE_VISIBILITY
_Integral
__gcd(_Integral __x, _Integral __y)
{
do
{
_Integral __t = __x % __y;
__x = __y;
__y = __t;
} while (__y);
return __x;
}
template<typename _RandomAccessIterator>
_RandomAccessIterator
__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
const difference_type __m1 = __middle - __first;
const difference_type __m2 = __last - __middle;
if (__m1 == __m2)
{
_VSTD::swap_ranges(__first, __middle, __middle);
return __middle;
}
const difference_type __g = _VSTD::__gcd(__m1, __m2);
for (_RandomAccessIterator __p = __first + __g; __p != __first;)
{
value_type __t(_VSTD::move(*--__p));
_RandomAccessIterator __p1 = __p;
_RandomAccessIterator __p2 = __p1 + __m1;
do
{
*__p1 = _VSTD::move(*__p2);
__p1 = __p2;
const difference_type __d = __last - __p2;
if (__m1 < __d)
__p2 += __m1;
else
__p2 = __first + (__m1 - __d);
} while (__p2 != __p);
*__p1 = _VSTD::move(__t);
}
return __first + __m2;
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
_VSTD::forward_iterator_tag)
{
typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
if (_VSTD::is_trivially_move_assignable<value_type>::value)
{
if (_VSTD::next(__first) == __middle)
return _VSTD::__rotate_left(__first, __last);
}
return _VSTD::__rotate_forward(__first, __middle, __last);
}
template <class _BidirectionalIterator>
inline _LIBCPP_INLINE_VISIBILITY
_BidirectionalIterator
__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
_VSTD::bidirectional_iterator_tag)
{
typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
if (_VSTD::is_trivially_move_assignable<value_type>::value)
{
if (_VSTD::next(__first) == __middle)
return _VSTD::__rotate_left(__first, __last);
if (_VSTD::next(__middle) == __last)
return _VSTD::__rotate_right(__first, __last);
}
return _VSTD::__rotate_forward(__first, __middle, __last);
}
template <class _RandomAccessIterator>
inline _LIBCPP_INLINE_VISIBILITY
_RandomAccessIterator
__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
_VSTD::random_access_iterator_tag)
{
typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
if (_VSTD::is_trivially_move_assignable<value_type>::value)
{
if (_VSTD::next(__first) == __middle)
return _VSTD::__rotate_left(__first, __last);
if (_VSTD::next(__middle) == __last)
return _VSTD::__rotate_right(__first, __last);
return _VSTD::__rotate_gcd(__first, __middle, __last);
}
return _VSTD::__rotate_forward(__first, __middle, __last);
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
{
if (__first == __middle)
return __last;
if (__middle == __last)
return __first;
return _VSTD::__rotate(__first, __middle, __last,
typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
}
// rotate_copy
template <class _ForwardIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
{
return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
}
// min_element
template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator
__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
if (__comp(*__i, *__first))
__first = __i;
}
return __first;
}
template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
return __min_element(__first, __last, __comp);
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last)
{
return __min_element(__first, __last,
__less<typename iterator_traits<_ForwardIterator>::value_type>());
}
// min
template <class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
return __comp(__b, __a) ? __b : __a;
}
template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
min(const _Tp& __a, const _Tp& __b)
{
return _VSTD::min(__a, __b, __less<_Tp>());
}
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
template<class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp
min(initializer_list<_Tp> __t, _Compare __comp)
{
return *__min_element(__t.begin(), __t.end(), __comp);
}
template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp
min(initializer_list<_Tp> __t)
{
return *__min_element(__t.begin(), __t.end(), __less<_Tp>());
}
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
// max_element
template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator
__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
if (__comp(*__first, *__i))
__first = __i;
}
return __first;
}
template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
return __max_element(__first, __last, __comp);
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last)
{
return __max_element(__first, __last,
__less<typename iterator_traits<_ForwardIterator>::value_type>());
}
// max
template <class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
return __comp(__a, __b) ? __b : __a;
}
template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
max(const _Tp& __a, const _Tp& __b)
{
return _VSTD::max(__a, __b, __less<_Tp>());
}
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
template<class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp
max(initializer_list<_Tp> __t, _Compare __comp)
{
return *__max_element(__t.begin(), __t.end(), __comp);
}
template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp
max(initializer_list<_Tp> __t)
{
return *__max_element(__t.begin(), __t.end(), __less<_Tp>());
}
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
// minmax_element
template <class _ForwardIterator, class _Compare>
std::pair<_ForwardIterator, _ForwardIterator>
minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
if (__first != __last)
{
if (++__first != __last)
{
if (__comp(*__first, *__result.first))
__result.first = __first;
else
__result.second = __first;
while (++__first != __last)
{
_ForwardIterator __i = __first;
if (++__first == __last)
{
if (__comp(*__i, *__result.first))
__result.first = __i;
else if (!__comp(*__i, *__result.second))
__result.second = __i;
break;
}
else
{
if (__comp(*__first, *__i))
{
if (__comp(*__first, *__result.first))
__result.first = __first;
if (!__comp(*__i, *__result.second))
__result.second = __i;
}
else
{
if (__comp(*__i, *__result.first))
__result.first = __i;
if (!__comp(*__first, *__result.second))
__result.second = __first;
}
}
}
}
}
return __result;
}
template <class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
std::pair<_ForwardIterator, _ForwardIterator>
minmax_element(_ForwardIterator __first, _ForwardIterator __last)
{
return _VSTD::minmax_element(__first, __last,
__less<typename iterator_traits<_ForwardIterator>::value_type>());
}
// minmax
template<class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
pair<const _Tp&, const _Tp&>
minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
pair<const _Tp&, const _Tp&>(__a, __b);
}
template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
pair<const _Tp&, const _Tp&>
minmax(const _Tp& __a, const _Tp& __b)
{
return _VSTD::minmax(__a, __b, __less<_Tp>());
}
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
template<class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
pair<_Tp, _Tp>
minmax(initializer_list<_Tp> __t, _Compare __comp)
{
typedef typename initializer_list<_Tp>::const_iterator _Iter;
_Iter __first = __t.begin();
_Iter __last = __t.end();
std::pair<_Tp, _Tp> __result ( *__first, *__first );
++__first;
if (__t.size() % 2 == 0)
{
if (__comp(*__first, __result.first))
__result.first = *__first;
else
__result.second = *__first;
++__first;
}
while (__first != __last)
{
_Tp __prev = *__first++;
if (__comp(__prev, *__first)) {
if (__comp(__prev, __result.first)) __result.first = __prev;
if (__comp(__result.second, *__first)) __result.second = *__first;
}
else {
if (__comp(*__first, __result.first)) __result.first = *__first;
if (__comp(__result.second, __prev)) __result.second = __prev;
}
__first++;
}
return __result;
}
template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
pair<_Tp, _Tp>
minmax(initializer_list<_Tp> __t)
{
return _VSTD::minmax(__t, __less<_Tp>());
}
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
// random_shuffle
// __independent_bits_engine
template <unsigned long long _Xp, size_t _Rp>
struct __log2_imp
{
static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
: __log2_imp<_Xp, _Rp - 1>::value;
};
template <unsigned long long _Xp>
struct __log2_imp<_Xp, 0>
{
static const size_t value = 0;
};
template <size_t _Rp>
struct __log2_imp<0, _Rp>
{
static const size_t value = _Rp + 1;
};
template <class _UI, _UI _Xp>
struct __log2
{
static const size_t value = __log2_imp<_Xp,
sizeof(_UI) * __CHAR_BIT__ - 1>::value;
};
template<class _Engine, class _UIntType>
class __independent_bits_engine
{
public:
// types
typedef _UIntType result_type;
private:
typedef typename _Engine::result_type _Engine_result_type;
typedef typename conditional
<
sizeof(_Engine_result_type) <= sizeof(result_type),
result_type,
_Engine_result_type
>::type _Working_result_type;
_Engine& __e_;
size_t __w_;
size_t __w0_;
size_t __n_;
size_t __n0_;
_Working_result_type __y0_;
_Working_result_type __y1_;
_Engine_result_type __mask0_;
_Engine_result_type __mask1_;
#ifdef _LIBCPP_HAS_NO_CONSTEXPR
static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
+ _Working_result_type(1);
#else
static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
+ _Working_result_type(1);
#endif
static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
public:
// constructors and seeding functions
__independent_bits_engine(_Engine& __e, size_t __w);
// generating functions
result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
private:
result_type __eval(false_type);
result_type __eval(true_type);
};
template<class _Engine, class _UIntType>
__independent_bits_engine<_Engine, _UIntType>
::__independent_bits_engine(_Engine& __e, size_t __w)
: __e_(__e),
__w_(__w)
{
__n_ = __w_ / __m + (__w_ % __m != 0);
__w0_ = __w_ / __n_;
if (_Rp == 0)
__y0_ = _Rp;
else if (__w0_ < _WDt)
__y0_ = (_Rp >> __w0_) << __w0_;
else
__y0_ = 0;
if (_Rp - __y0_ > __y0_ / __n_)
{
++__n_;
__w0_ = __w_ / __n_;
if (__w0_ < _WDt)
__y0_ = (_Rp >> __w0_) << __w0_;
else
__y0_ = 0;
}
__n0_ = __n_ - __w_ % __n_;
if (__w0_ < _WDt - 1)
__y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
else
__y1_ = 0;
__mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
_Engine_result_type(0);
__mask1_ = __w0_ < _EDt - 1 ?
_Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
_Engine_result_type(~0);
}
template<class _Engine, class _UIntType>
inline
_UIntType
__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
{
return static_cast<result_type>(__e_() & __mask0_);
}
template<class _Engine, class _UIntType>
_UIntType
__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
{
result_type _Sp = 0;
for (size_t __k = 0; __k < __n0_; ++__k)
{
_Engine_result_type __u;
do
{
__u = __e_() - _Engine::min();
} while (__u >= __y0_);
if (__w0_ < _WDt)
_Sp <<= __w0_;
else
_Sp = 0;
_Sp += __u & __mask0_;
}
for (size_t __k = __n0_; __k < __n_; ++__k)
{
_Engine_result_type __u;
do
{
__u = __e_() - _Engine::min();
} while (__u >= __y1_);
if (__w0_ < _WDt - 1)
_Sp <<= __w0_ + 1;
else
_Sp = 0;
_Sp += __u & __mask1_;
}
return _Sp;
}
// uniform_int_distribution
template<class _IntType = int>
class uniform_int_distribution
{
public:
// types
typedef _IntType result_type;
class param_type
{
result_type __a_;
result_type __b_;
public:
typedef uniform_int_distribution distribution_type;
explicit param_type(result_type __a = 0,
result_type __b = numeric_limits<result_type>::max())
: __a_(__a), __b_(__b) {}
result_type a() const {return __a_;}
result_type b() const {return __b_;}
friend bool operator==(const param_type& __x, const param_type& __y)
{return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
friend bool operator!=(const param_type& __x, const param_type& __y)
{return !(__x == __y);}
};
private:
param_type __p_;
public:
// constructors and reset functions
explicit uniform_int_distribution(result_type __a = 0,
result_type __b = numeric_limits<result_type>::max())
: __p_(param_type(__a, __b)) {}
explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
void reset() {}
// generating functions
template<class _URNG> result_type operator()(_URNG& __g)
{return (*this)(__g, __p_);}
template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
// property functions
result_type a() const {return __p_.a();}
result_type b() const {return __p_.b();}
param_type param() const {return __p_;}
void param(const param_type& __p) {__p_ = __p;}
result_type min() const {return a();}
result_type max() const {return b();}
friend bool operator==(const uniform_int_distribution& __x,
const uniform_int_distribution& __y)
{return __x.__p_ == __y.__p_;}
friend bool operator!=(const uniform_int_distribution& __x,
const uniform_int_distribution& __y)
{return !(__x == __y);}
};
template<class _IntType>
template<class _URNG>
typename uniform_int_distribution<_IntType>::result_type
uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
{
typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
uint32_t, uint64_t>::type _UIntType;
const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
if (_Rp == 1)
return __p.a();
const size_t _Dt = numeric_limits<_UIntType>::digits;
typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
if (_Rp == 0)
return static_cast<result_type>(_Eng(__g, _Dt)());
size_t __w = _Dt - __clz(_Rp) - 1;
if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
++__w;
_Eng __e(__g, __w);
_UIntType __u;
do
{
__u = __e();
} while (__u >= _Rp);
return static_cast<result_type>(__u + __p.a());
}
class _LIBCPP_TYPE_VIS __rs_default;
_LIBCPP_FUNC_VIS __rs_default __rs_get();
class _LIBCPP_TYPE_VIS __rs_default
{
static unsigned __c_;
__rs_default();
public:
typedef uint_fast32_t result_type;
static const result_type _Min = 0;
static const result_type _Max = 0xFFFFFFFF;
__rs_default(const __rs_default&);
~__rs_default();
result_type operator()();
static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
};
_LIBCPP_FUNC_VIS __rs_default __rs_get();
template <class _RandomAccessIterator>
void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
typedef uniform_int_distribution<ptrdiff_t> _Dp;
typedef typename _Dp::param_type _Pp;
difference_type __d = __last - __first;
if (__d > 1)
{
_Dp __uid;
__rs_default __g = __rs_get();
for (--__last, --__d; __first < __last; ++__first, --__d)
{
difference_type __i = __uid(__g, _Pp(0, __d));
if (__i != difference_type(0))
swap(*__first, *(__first + __i));
}
}
}
template <class _RandomAccessIterator, class _RandomNumberGenerator>
void
random_shuffle