Skip to content

Instantly share code, notes, and snippets.

@EricWF

EricWF/updated_patch.patch

Created December 30, 2016 11:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save EricWF/a69933b79adf8cd61f1daa68c633cc03 to your computer and use it in GitHub Desktop.
Save EricWF/a69933b79adf8cd61f1daa68c633cc03 to your computer and use it in GitHub Desktop.
Download ZIP
updated patch
Raw
updated_patch.patch
diff --git a/include/algorithm b/include/algorithm
index 189991e..66b1ece 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -2070,2021 +2070,2021 @@ generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
// generate_n
template <class _OutputIterator, class _Size, class _Generator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
{
typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
_IntegralSize __n = __orig_n;
for (; __n > 0; ++__first, (void) --__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;
_VSTD::iter_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)
_VSTD::iter_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
__algo_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::__algo_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>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last)
{
return _VSTD::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 *_VSTD::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 *_VSTD::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>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last)
{
return _VSTD::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 *_VSTD::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 *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
}
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
#if _LIBCPP_STD_VER > 14
// clamp
template<class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
const _Tp&
clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
{
_LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
}
template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
const _Tp&
clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
{
return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
}
#endif
// minmax_element
template <class _ForwardIterator, class _Compare>
_LIBCPP_CONSTEXPR_AFTER_CXX11
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 _LIBCPP_CONSTEXPR_AFTER_CXX11
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(*__first, __prev)) {
if ( __comp(*__first, __result.first)) __result.first = *__first;
if (!__comp(__prev, __result.second)) __result.second = __prev;
}
else {
if ( __comp(__prev, __result.first)) __result.first = __prev;
if (!__comp(*__first, __result.second)) __result.second = *__first;
}
__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 & (std::numeric_limits<_UIntType>::max() >> (_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)
+ for (--__last, (void) --__d; __first < __last; ++__first, (void) --__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(_RandomAccessIterator __first, _RandomAccessIterator __last,
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
_RandomNumberGenerator&& __rand)
#else
_RandomNumberGenerator& __rand)
#endif
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
difference_type __d = __last - __first;
if (__d > 1)
{
- for (--__last; __first < __last; ++__first, --__d)
+ for (--__last; __first < __last; ++__first, (void) --__d)
{
difference_type __i = __rand(__d);
swap(*__first, *(__first + __i));
}
}
}
template <class _PopulationIterator, class _SampleIterator, class _Distance,
class _UniformRandomNumberGenerator>
_LIBCPP_INLINE_VISIBILITY
_SampleIterator __sample(_PopulationIterator __first,
_PopulationIterator __last, _SampleIterator __out,
_Distance __n,
_UniformRandomNumberGenerator & __g,
input_iterator_tag) {
_Distance __k = 0;
for (; __first != __last && __k < __n; ++__first, (void)++__k)
__out[__k] = *__first;
_Distance __sz = __k;
for (; __first != __last; ++__first, (void)++__k) {
_Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
if (__r < __sz)
__out[__r] = *__first;
}
return __out + _VSTD::min(__n, __k);
}
template <class _PopulationIterator, class _SampleIterator, class _Distance,
class _UniformRandomNumberGenerator>
_LIBCPP_INLINE_VISIBILITY
_SampleIterator __sample(_PopulationIterator __first,
_PopulationIterator __last, _SampleIterator __out,
_Distance __n,
_UniformRandomNumberGenerator& __g,
forward_iterator_tag) {
_Distance __unsampled_sz = _VSTD::distance(__first, __last);
for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
_Distance __r =
_VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
if (__r < __n) {
*__out++ = *__first;
--__n;
}
}
return __out;
}
template <class _PopulationIterator, class _SampleIterator, class _Distance,
class _UniformRandomNumberGenerator>
_LIBCPP_INLINE_VISIBILITY
_SampleIterator __sample(_PopulationIterator __first,
_PopulationIterator __last, _SampleIterator __out,
_Distance __n, _UniformRandomNumberGenerator& __g) {
typedef typename iterator_traits<_PopulationIterator>::iterator_category
_PopCategory;
typedef typename iterator_traits<_PopulationIterator>::difference_type
_Difference;
static_assert(__is_forward_iterator<_PopulationIterator>::value ||
__is_random_access_iterator<_SampleIterator>::value,
"SampleIterator must meet the requirements of RandomAccessIterator");
typedef typename common_type<_Distance, _Difference>::type _CommonType;
_LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
return _VSTD::__sample(
__first, __last, __out, _CommonType(__n),
__g, _PopCategory());
}
#if _LIBCPP_STD_VER > 14
template <class _PopulationIterator, class _SampleIterator, class _Distance,
class _UniformRandomNumberGenerator>
inline _LIBCPP_INLINE_VISIBILITY
_SampleIterator sample(_PopulationIterator __first,
_PopulationIterator __last, _SampleIterator __out,
_Distance __n, _UniformRandomNumberGenerator&& __g) {
return _VSTD::__sample(__first, __last, __out, __n, __g);
}
#endif // _LIBCPP_STD_VER > 14
template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
_UniformRandomNumberGenerator&& __g)
#else
_UniformRandomNumberGenerator& __g)
#endif
{
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;
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 _InputIterator, class _Predicate>
bool
is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (!__pred(*__first))
break;
if ( __first == __last )
return true;
++__first;
for (; __first != __last; ++__first)
if (__pred(*__first))
return false;
return true;
}
// partition
template <class _Predicate, class _ForwardIterator>
_ForwardIterator
__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
{
while (true)
{
if (__first == __last)
return __first;
if (!__pred(*__first))
break;
++__first;
}
for (_ForwardIterator __p = __first; ++__p != __last;)
{
if (__pred(*__p))
{
swap(*__first, *__p);
++__first;
}
}
return __first;
}
template <class _Predicate, class _BidirectionalIterator>
_BidirectionalIterator
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
bidirectional_iterator_tag)
{
while (true)
{
while (true)
{
if (__first == __last)
return __first;
if (!__pred(*__first))
break;
++__first;
}
do
{
if (__first == --__last)
return __first;
} while (!__pred(*__last));
swap(*__first, *__last);
++__first;
}
}
template <class _ForwardIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
}
// partition_copy
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)
{
for (; __first != __last; ++__first)
{
if (__pred(*__first))
{
*__out_true = *__first;
++__out_true;
}
else
{
*__out_false = *__first;
++__out_false;
}
}
return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
}
// partition_point
template<class _ForwardIterator, class _Predicate>
_ForwardIterator
partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
difference_type __len = _VSTD::distance(__first, __last);
while (__len != 0)
{
difference_type __l2 = __len / 2;
_ForwardIterator __m = __first;
_VSTD::advance(__m, __l2);
if (__pred(*__m))
{
__first = ++__m;
__len -= __l2 + 1;
}
else
__len = __l2;
}
return __first;
}
// stable_partition
template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
_ForwardIterator
__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
_Distance __len, _Pair __p, forward_iterator_tag __fit)
{
// *__first is known to be false
// __len >= 1
if (__len == 1)
return __first;
if (__len == 2)
{
_ForwardIterator __m = __first;
if (__pred(*++__m))
{
swap(*__first, *__m);
return __m;
}
return __first;
}
if (__len <= __p.second)
{ // The buffer is big enough to use
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
__destruct_n __d(0);
unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
// Move the falses into the temporary buffer, and the trues to the front of the line
// Update __first to always point to the end of the trues
value_type* __t = __p.first;
::new(__t) value_type(_VSTD::move(*__first));
__d.__incr((value_type*)0);
++__t;
_ForwardIterator __i = __first;
while (++__i != __last)
{
if (__pred(*__i))
{
*__first = _VSTD::move(*__i);
++__first;
}
else
{
::new(__t) value_type(_VSTD::move(*__i));
__d.__incr((value_type*)0);
++__t;
}
}
// All trues now at start of range, all falses in buffer
// Move falses back into range, but don't mess up __first which points to first false
__i = __first;
for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
*__i = _VSTD::move(*__t2);
// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
return __first;
}
// Else not enough buffer, do in place
// __len >= 3
_ForwardIterator __m = __first;
_Distance __len2 = __len / 2; // __len2 >= 2
_VSTD::advance(__m, __len2);
// recurse on [__first, __m), *__first know to be false
// F?????????????????
// f m l
typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
_ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
// TTTFFFFF??????????
// f ff m l
// recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
_ForwardIterator __m1 = __m;
_ForwardIterator __second_false = __last;
_Distance __len_half = __len - __len2;
while (__pred(*__m1))
{
if (++__m1 == __last)
goto __second_half_done;
--__len_half;
}
// TTTFFFFFTTTF??????
// f ff m m1 l
__second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
__second_half_done:
// TTTFFFFFTTTTTFFFFF
// f ff m sf l
return _VSTD::rotate(__first_false, __m, __second_false);
// TTTTTTTTFFFFFFFFFF
// |
}
struct __return_temporary_buffer
{
template <class _Tp>
_LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
};
template <class _Predicate, class _ForwardIterator>
_ForwardIterator
__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
forward_iterator_tag)
{
const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
// Either prove all true and return __first or point to first false
while (true)
{
if (__first == __last)
return __first;
if (!__pred(*__first))
break;
++__first;
}
// We now have a reduced range [__first, __last)
// *__first is known to be false
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
difference_type __len = _VSTD::distance(__first, __last);
pair<value_type*, ptrdiff_t> __p(0, 0);
unique_ptr<value_type, __return_temporary_buffer> __h;
if (__len >= __alloc_limit)
{
__p = _VSTD::get_temporary_buffer<value_type>(__len);
__h.reset(__p.first);
}
return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
(__first, __last, __pred, __len, __p, forward_iterator_tag());
}
template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
_BidirectionalIterator
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
_Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
{
// *__first is known to be false
// *__last is known to be true
// __len >= 2
if (__len == 2)
{
swap(*__first, *__last);
return __last;
}
if (__len == 3)
{
_BidirectionalIterator __m = __first;
if (__pred(*++__m))
{
swap(*__first, *__m);
swap(*__m, *__last);
return __last;
}
swap(*__m, *__last);
swap(*__first, *__m);
return __m;
}
if (__len <= __p.second)
{ // The buffer is big enough to use
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
__destruct_n __d(0);
unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
// Move the falses into the temporary buffer, and the trues to the front of the line
// Update __first to always point to the end of the trues
value_type* __t = __p.first;
::new(__t) value_type(_VSTD::move(*__first));
__d.__incr((value_type*)0);
++__t;
_BidirectionalIterator __i = __first;
while (++__i != __last)
{
if (__pred(*__i))
{
*__first = _VSTD::move(*__i);
++__first;
}
else
{
::new(__t) value_type(_VSTD::move(*__i));
__d.__incr((value_type*)0);
++__t;
}
}
// move *__last, known to be true
*__first = _VSTD::move(*__i);
__i = ++__first;
// All trues now at start of range, all falses in buffer
// Move falses back into range, but don't mess up __first which points to first false
for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
*__i = _VSTD::move(*__t2);
// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
return __first;
}
// Else not enough buffer, do in place
// __len >= 4
_BidirectionalIterator __m = __first;
_Distance __len2 = __len / 2; // __len2 >= 2
_VSTD::advance(__m, __len2);
// recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
// F????????????????T
// f m l
_BidirectionalIterator __m1 = __m;
_BidirectionalIterator __first_false = __first;
_Distance __len_half = __len2;
while (!__pred(*--__m1))
{
if (__m1 == __first)
goto __first_half_done;
--__len_half;
}
// F???TFFF?????????T
// f m1 m l
typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
__first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
__first_half_done:
// TTTFFFFF?????????T
// f ff m l
// recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
__m1 = __m;
_BidirectionalIterator __second_false = __last;
++__second_false;
__len_half = __len - __len2;
while (__pred(*__m1))
{
if (++__m1 == __last)
goto __second_half_done;
--__len_half;
}
// TTTFFFFFTTTF?????T
// f ff m m1 l
__second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
__second_half_done:
// TTTFFFFFTTTTTFFFFF
// f ff m sf l
return _VSTD::rotate(__first_false, __m, __second_false);
// TTTTTTTTFFFFFFFFFF
// |
}
template <class _Predicate, class _BidirectionalIterator>
_BidirectionalIterator
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
bidirectional_iterator_tag)
{
typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
// Either prove all true and return __first or point to first false
while (true)
{
if (__first == __last)
return __first;
if (!__pred(*__first))
break;
++__first;
}
// __first points to first false, everything prior to __first is already set.
// Either prove [__first, __last) is all false and return __first, or point __last to last true
do
{
if (__first == --__last)
return __first;
} while (!__pred(*__last));
// We now have a reduced range [__first, __last]
// *__first is known to be false
// *__last is known to be true
// __len >= 2
difference_type __len = _VSTD::distance(__first, __last) + 1;
pair<value_type*, ptrdiff_t> __p(0, 0);
unique_ptr<value_type, __return_temporary_buffer> __h;
if (__len >= __alloc_limit)
{
__p = _VSTD::get_temporary_buffer<value_type>(__len);
__h.reset(__p.first);
}
return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
(__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
}
template <class _ForwardIterator, class _Predicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
}
// is_sorted_until
template <class _ForwardIterator, class _Compare>
_ForwardIterator
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
if (__first != __last)
{
_ForwardIterator __i = __first;
while (++__i != __last)
{
if (__comp(*__i, *__first))
return __i;
__first = __i;
}
}
return __last;
}
template<class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
{
return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
}
// is_sorted
template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
bool
is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
}
template<class _ForwardIterator>
inline _LIBCPP_INLINE_VISIBILITY
bool
is_sorted(_ForwardIterator __first, _ForwardIterator __last)
{
return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
}
// sort
// stable, 2-3 compares, 0-2 swaps
template <class _Compare, class _ForwardIterator>
unsigned
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
{
unsigned __r = 0;
if (!__c(*__y, *__x)) // if x <= y
{
if (!__c(*__z, *__y)) // if y <= z
return __r; // x <= y && y <= z
// x <= y && y > z
swap(*__y, *__z); // x <= z && y < z
__r = 1;
if (__c(*__y, *__x)) // if x > y
{
swap(*__x, *__y); // x < y && y <= z
__r = 2;
}
return __r; // x <= y && y < z
}
if (__c(*__z, *__y)) // x > y, if y > z
{
swap(*__x, *__z); // x < y && y < z
__r = 1;
return __r;
}
swap(*__x, *__y); // x > y && y <= z
__r = 1; // x < y && x <= z
if (__c(*__z, *__y)) // if y > z
{
swap(*__y, *__z); // x <= y && y < z
__r = 2;
}
return __r;
} // x <= y && y <= z
// stable, 3-6 compares, 0-5 swaps
template <class _Compare, class _ForwardIterator>
unsigned
__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
_ForwardIterator __x4, _Compare __c)
{
unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
if (__c(*__x4, *__x3))
{
swap(*__x3, *__x4);
++__r;
if (__c(*__x3, *__x2))
{
swap(*__x2, *__x3);
++__r;
if (__c(*__x2, *__x1))
{
swap(*__x1, *__x2);
++__r;
}
}
}
return __r;
}
// stable, 4-10 compares, 0-9 swaps
template <class _Compare, class _ForwardIterator>
unsigned
__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
_ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
{
unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
if (__c(*__x5, *__x4))
{
swap(*__x4, *__x5);
++__r;
if (__c(*__x4, *__x3))
{
swap(*__x3, *__x4);
++__r;
if (__c(*__x3, *__x2))
{
swap(*__x2, *__x3);
++__r;
if (__c(*__x2, *__x1))
{
swap(*__x1, *__x2);
++__r;
}
}
}
}
return __r;
}
// Assumes size > 0
template <class _Compare, class _BirdirectionalIterator>
void
__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
{
_BirdirectionalIterator __lm1 = __last;
for (--__lm1; __first != __lm1; ++__first)
{
_BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
typename add_lvalue_reference<_Compare>::type>
(__first, __last, __comp);
if (__i != __first)
swap(*__first, *__i);
}
}
template <class _Compare, class _BirdirectionalIterator>
void
__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
{
typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
if (__first != __last)
{
_BirdirectionalIterator __i = __first;
for (++__i; __i != __last; ++__i)
{
_BirdirectionalIterator __j = __i;
value_type __t(_VSTD::move(*__j));
for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
*__j = _VSTD::move(*__k);
*__j = _VSTD::move(__t);
}
}
}
template <class _Compare, class _RandomAccessIterator>
void
__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
_RandomAccessIterator __j = __first+2;
__sort3<_Compare>(__first, __first+1, __j, __comp);
for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
{
if (__comp(*__i, *__j))
{
value_type __t(_VSTD::move(*__i));
_RandomAccessIterator __k = __j;
__j = __i;
do
{
*__j = _VSTD::move(*__k);
__j = __k;
} while (__j != __first && __comp(__t, *--__k));
*__j = _VSTD::move(__t);
}
__j = __i;
}
}
template <class _Compare, class _RandomAccessIterator>
bool
__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
switch (__last - __first)
{
case 0:
case 1:
return true;
case 2:
if (__comp(*--__last, *__first))
swap(*__first, *__last);
return true;
case 3:
_VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
return true;
case 4:
_VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
return true;
case 5:
_VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
return true;
}
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
_RandomAccessIterator __j = __first+2;
__sort3<_Compare>(__first, __first+1, __j, __comp);
const unsigned __limit = 8;
unsigned __count = 0;
for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
{
if (__comp(*__i, *__j))
{
value_type __t(_VSTD::move(*__i));
_RandomAccessIterator __k = __j;
__j = __i;
do
{
*__j = _VSTD::move(*__k);
__j = __k;
} while (__j != __first && __comp(__t, *--__k));
*__j = _VSTD::move(__t);
if (++__count == __limit)
return ++__i == __last;
}
__j = __i;
}
return true;
}
template <class _Compare, class _BirdirectionalIterator>
void
__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
{
typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
if (__first1 != __last1)
{
__destruct_n __d(0);
unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
value_type* __last2 = __first2;
::new(__last2) value_type(_VSTD::move(*__first1));
__d.__incr((value_type*)0);
for (++__last2; ++__first1 != __last1; ++__last2)
{
value_type* __j2 = __last2;
value_type* __i2 = __j2;
if (__comp(*__first1, *--__i2))
{
::new(__j2) value_type(_VSTD::move(*__i2));
__d.__incr((value_type*)0);
for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
*__j2 = _VSTD::move(*__i2);
*__j2 = _VSTD::move(*__first1);
}
else
{
::new(__j2) value_type(_VSTD::move(*__first1));
__d.__incr((value_type*)0);
}
}
__h.release();
}
}
template <class _Compare, class _RandomAccessIterator>
void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
// _Compare is known to be a reference type
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
is_trivially_copy_assignable<value_type>::value ? 30 : 6;
while (true)
{
__restart:
difference_type __len = __last - __first;
switch (__len)
{
case 0:
case 1:
return;
case 2:
if (__comp(*--__last, *__first))
swap(*__first, *__last);
return;
case 3:
_VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
return;
case 4:
_VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
return;
case 5:
_VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
return;
}
if (__len <= __limit)
{
_VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
return;
}
// __len > 5
_RandomAccessIterator __m = __first;
_RandomAccessIterator __lm1 = __last;
--__lm1;
unsigned __n_swaps;
{
difference_type __delta;
if (__len >= 1000)
{
__delta = __len/2;
__m += __delta;
__delta /= 2;
__n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
}
else
{
__delta = __len/2;
__m += __delta;
__n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
}
}
// *__m is median
// partition [__first, __m) < *__m and *__m <= [__m, __last)
// (this inhibits tossing elements equivalent to __m around unnecessarily)
_RandomAccessIterator __i = __first;
_RandomAccessIterator __j = __lm1;
// j points beyond range to be tested, *__m is known to be <= *__lm1
// The search going up is known to be guarded but the search coming down isn't.
// Prime the downward search with a guard.
if (!__comp(*__i, *__m)) // if *__first == *__m
{
// *__first == *__m, *__first doesn't go in first part
// manually guard downward moving __j against __i
while (true)
{
if (__i == --__j)
{
// *__first == *__m, *__m <= all other elements
// Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
++__i; // __first + 1
__j = __last;
if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
{
while (true)
{
if (__i == __j)
return; // [__first, __last) all equivalent elements
if (__comp(*__first, *__i))
{
swap(*__i, *__j);
++__n_swaps;
++__i;
break;
}
++__i;
}
}
// [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
if (__i == __j)
return;
while (true)
{
while (!__comp(*__first, *__i))
++__i;
while (__comp(*__first, *--__j))
;
if (__i >= __j)
break;
swap(*__i, *__j);
++__n_swaps;
++__i;
}
// [__first, __i) == *__first and *__first < [__i, __last)
// The first part is sorted, sort the secod part
// _VSTD::__sort<_Compare>(__i, __last, __comp);
__first = __i;
goto __restart;
}
if (__comp(*__j, *__m))
{
swap(*__i, *__j);
++__n_swaps;
break; // found guard for downward moving __j, now use unguarded partition
}
}
}
// It is known that *__i < *__m
++__i;
// j points beyond range to be tested, *__m is known to be <= *__lm1
// if not yet partitioned...
if (__i < __j)
{
// known that *(__i - 1) < *__m
// known that __i <= __m
while (true)
{
// __m still guards upward moving __i
while (__comp(*__i, *__m))
++__i;
// It is now known that a guard exists for downward moving __j
while (!__comp(*--__j, *__m))
;
if (__i > __j)
break;
swap(*__i, *__j);
++__n_swaps;
// It is known that __m != __j
// If __m just moved, follow it
if (__m == __i)
__m = __j;
++__i;
}
}
// [__first, __i) < *__m and *__m <= [__i, __last)
if (__i != __m && __comp(*__m, *__i))
{
swap(*__i, *__m);
++__n_swaps;
}
// [__first, __i) < *__i and *__i <= [__i+1, __last)
// If we were given a perfect partition, see if insertion sort is quick...
if (__n_swaps == 0)
{
bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
{
if (__fs)
return;
__last = __i;
continue;
}
else
{
if (__fs)
{
__first = ++__i;
continue;
}
}
}
// sort smaller range with recursive call and larger with tail recursion elimination
if (__i - __first < __last - __i)
{
_VSTD::__sort<_Compare>(__first, __i, __comp);
// _VSTD::__sort<_Compare>(__i+1, __last, __comp);
__first = ++__i;
}
else
{
_VSTD::__sort<_Compare>(__i+1, __last, __comp);
// _VSTD::__sort<_Compare>(__first, __i, __comp);
__last = __i;
}
}
}
// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
#ifdef _LIBCPP_DEBUG
typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
__debug_less<_Compare> __c(__comp);
__sort<_Comp_ref>(__first, __last, __c);
#else // _LIBCPP_DEBUG
typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
diff --git a/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
index e24598a..e62d787 100644
--- a/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
+++ b/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
@@ -1,34 +1,61 @@
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//
// <algorithm>
// template<RandomAccessIterator Iter>
// requires ShuffleIterator<Iter>
// void
// random_shuffle(Iter first, Iter last);
#include <algorithm>
#include <cassert>
-#include "test_macros.h"
+#include "test_iterators.h"
-int main()
+void test_initial_sequence()
{
int ia[] = {1, 2, 3, 4};
int ia1[] = {1, 4, 3, 2};
int ia2[] = {4, 1, 2, 3};
const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+
std::random_shuffle(ia, ia+sa);
LIBCPP_ASSERT(std::equal(ia, ia+sa, ia1));
assert(std::is_permutation(ia, ia+sa, ia1));
+
std::random_shuffle(ia, ia+sa);
LIBCPP_ASSERT(std::equal(ia, ia+sa, ia2));
assert(std::is_permutation(ia, ia+sa, ia2));
}
+
+template <class Iter>
+void
+test_with_iterator()
+{
+ int empty[] = {};
+ std::random_shuffle(Iter(empty), Iter(empty));
+
+ int all_elements[] = {1, 2, 3, 4};
+ int shuffled[] = {1, 2, 3, 4};
+ const unsigned size = sizeof(all_elements)/sizeof(all_elements[0]);
+
+ std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+ assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+
+ std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+ assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+}
+
+int main()
+{
+ test_initial_sequence();
+ test_with_iterator<random_access_iterator<int*> >();
+ test_with_iterator<int*>();
+}
diff --git a/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
index c923d84..ae1aeb5 100644
--- a/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
+++ b/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
@@ -1,41 +1,107 @@
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//
// <algorithm>
// template<RandomAccessIterator Iter, Callable<auto, Iter::difference_type> Rand>
// requires ShuffleIterator<Iter>
// && Convertible<Rand::result_type, Iter::difference_type>
// void
// random_shuffle(Iter first, Iter last, Rand&& rand);
#include <algorithm>
#include <cassert>
-#include <cstddef>
#include "test_macros.h"
+#include "test_iterators.h"
+
+struct min_swappable {
+ static int swaps;
+ int value;
+#if TEST_STD_VER >= 11
+ min_swappable(const min_swappable&) = delete;
+ void operator=(const min_swappable&) = delete;
+#endif
+};
+
+int min_swappable::swaps = 0;
+
+void swap(min_swappable& lhs, min_swappable& rhs)
+{
+ std::swap(lhs.value, rhs.value);
+ ++min_swappable::swaps;
+}
+
+bool operator==(const min_swappable& lhs, const min_swappable& rhs)
+{
+ return lhs.value == rhs.value;
+}
+
+struct init_gen {};
struct gen
{
- std::ptrdiff_t operator()(std::ptrdiff_t n)
+ gen(init_gen) {}
+
+ static int calls;
+
+ int operator()(int n)
{
+ ++calls;
return n-1;
}
+
+private:
+ gen(const gen&);
+ void operator=(const gen&);
};
+int gen::calls = 0;
+
+template <class Iter, class ValueType>
+void
+test_with_iterator()
+{
+ gen::calls = 0;
+
+ ValueType empty[] = {};
+ std::random_shuffle(Iter(empty), Iter(empty));
+ assert(gen::calls == 0);
+
+ ValueType shuffled[] = {{1}, {2}, {3}, {4}};
+ ValueType shuffled1[] = {{4}, {1}, {2}, {3}};
+ ValueType shuffled2[] = {{3}, {4}, {1}, {2}};
+ const unsigned size = sizeof(shuffled)/sizeof(shuffled[0]);
+ gen r((init_gen()));
+
+ std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+ assert(std::is_permutation(shuffled, shuffled+size, shuffled1));
+ LIBCPP_ASSERT(std::equal(shuffled, shuffled+size, shuffled1));
+ assert(gen::calls == 3);
+
+ std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+ assert(std::is_permutation(shuffled, shuffled+size, shuffled2));
+ LIBCPP_ASSERT(std::equal(shuffled, shuffled+size, shuffled2));
+ assert(gen::calls == 6);
+}
+
int main()
{
- int ia[] = {1, 2, 3, 4};
- int ia1[] = {4, 1, 2, 3};
- const unsigned sa = sizeof(ia)/sizeof(ia[0]);
- gen r;
- std::random_shuffle(ia, ia+sa, r);
- LIBCPP_ASSERT(std::equal(ia, ia+sa, ia1));
- assert(std::is_permutation(ia, ia+sa, ia1));
+ min_swappable::swaps = 0;
+ test_with_iterator<random_access_iterator<min_swappable*>, min_swappable >();
+ assert(min_swappable::swaps == 6);
+
+ test_with_iterator<random_access_iterator<int*>, int >();
+
+ min_swappable::swaps = 0;
+ test_with_iterator<min_swappable*, min_swappable>();
+ assert(min_swappable::swaps == 6);
+
+ test_with_iterator<int*, int>();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment