diff options
Diffstat (limited to 'contrib/libc++/include/algorithm')
| -rw-r--r-- | contrib/libc++/include/algorithm | 223 |
1 files changed, 132 insertions, 91 deletions
diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index 7a6db7a..5eec80c 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -89,7 +89,7 @@ template <class InputIterator1, class InputIterator2> template <class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> - mismatch(InputIterator1 first1, InputIterator1 last1, + mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); // **C++14** template <class InputIterator1, class InputIterator2, class BinaryPredicate> @@ -109,7 +109,7 @@ template <class InputIterator1, class InputIterator2> template <class InputIterator1, class InputIterator2> bool - equal(InputIterator1 first1, InputIterator1 last1, + equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); // **C++14** template <class InputIterator1, class InputIterator2, class BinaryPredicate> @@ -288,6 +288,12 @@ template <class RandomAccessIterator, class RandomNumberGenerator> random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); // deprecated in C++14 +template<class PopulationIterator, class SampleIterator, + class Distance, class UniformRandomBitGenerator> + SampleIterator sample(PopulationIterator first, PopulationIterator last, + SampleIterator out, Distance n, + UniformRandomBitGenerator&& g); // C++17 + template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g); @@ -688,7 +694,7 @@ struct __equal_to<_T1, const _T1> template <class _T1, class _T2 = _T1> struct __less { - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 + _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 @@ -749,14 +755,28 @@ 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"); + __do_compare_assert(0, __y, __x); return __r; } + + template <class _LHS, class _RHS> + inline _LIBCPP_INLINE_VISIBILITY + decltype((void)_VSTD::declval<_Compare&>()( + _VSTD::declval<_LHS const&>(), _VSTD::declval<_RHS const&>())) + __do_compare_assert(int, _LHS const& __l, _RHS const& __r) { + _LIBCPP_ASSERT(!__comp_(__l, __r), + "Comparator does not induce a strict weak ordering"); + } + + template <class _LHS, class _RHS> + inline _LIBCPP_INLINE_VISIBILITY + void __do_compare_assert(long, _LHS const&, _RHS const&) {} }; #endif // _LIBCPP_DEBUG @@ -857,7 +877,7 @@ for_each(_InputIterator __first, _InputIterator __last, _Function __f) { for (; __first != __last; ++__first) __f(*__first); - return _LIBCPP_EXPLICIT_MOVE(__f); // explicitly moved for (emulated) C++03 + return __f; } // find @@ -1215,7 +1235,7 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2> inline _LIBCPP_INLINE_VISIBILITY bool -__equal(_InputIterator1 __first1, _InputIterator1 __last1, +__equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag ) { @@ -1228,8 +1248,8 @@ __equal(_InputIterator1 __first1, _InputIterator1 __last1, template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> inline _LIBCPP_INLINE_VISIBILITY bool -__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, +__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)) @@ -1242,11 +1262,11 @@ __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> inline _LIBCPP_INLINE_VISIBILITY bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, +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, + (__first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(), typename iterator_traits<_InputIterator2>::iterator_category()); } @@ -1254,7 +1274,7 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1, template <class _InputIterator1, class _InputIterator2> inline _LIBCPP_INLINE_VISIBILITY bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { typedef typename iterator_traits<_InputIterator1>::value_type __v1; @@ -1328,7 +1348,7 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> bool __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag ) { @@ -1379,7 +1399,7 @@ __next_iter:; template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, - _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, + _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag ) { @@ -1458,7 +1478,7 @@ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, } template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 +_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, @@ -1474,9 +1494,9 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, if (__len1 < __len2) return make_pair(__last1, __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) @@ -1485,40 +1505,9 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, 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 make_pair(__last1, __last1); - } - __phase2: -#endif // !_LIBCPP_UNROLL_LOOPS + _RandomAccessIterator1 __m1 = __first1; _RandomAccessIterator2 __m2 = __first2; -#if !_LIBCPP_UNROLL_LOOPS while (true) { if (++__m2 == __last2) @@ -1530,43 +1519,6 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, 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 make_pair(__first1, __first1 + __len2); - } - __continue: - ++__first1; -#endif // !_LIBCPP_UNROLL_LOOPS } } @@ -1729,6 +1681,20 @@ __unwrap_iter(__wrap_iter<_Tp*> __i) return __i.base(); } +#else + +template <class _Tp> +inline _LIBCPP_INLINE_VISIBILITY +typename enable_if +< + is_trivially_copy_assignable<_Tp>::value, + __wrap_iter<_Tp*> +>::type +__unwrap_iter(__wrap_iter<_Tp*> __i) +{ + return __i; +} + #endif // _LIBCPP_DEBUG_LEVEL < 2 template <class _InputIterator, class _OutputIterator> @@ -1802,7 +1768,9 @@ _BidirectionalIterator2 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); + return _VSTD::__copy_backward(__unwrap_iter(__first), + __unwrap_iter(__last), + __unwrap_iter(__result)); } // copy_if @@ -2417,7 +2385,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt template<typename _Integral> inline _LIBCPP_INLINE_VISIBILITY _Integral -__gcd(_Integral __x, _Integral __y) +__algo_gcd(_Integral __x, _Integral __y) { do { @@ -2442,7 +2410,7 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran _VSTD::swap_ranges(__first, __middle, __middle); return __middle; } - const difference_type __g = _VSTD::__gcd(__m1, __m2); + const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); for (_RandomAccessIterator __p = __first + __g; __p != __first;) { value_type __t(_VSTD::move(*--__p)); @@ -2785,7 +2753,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp) __result.second = *__first; ++__first; } - + while (__first != __last) { _Tp __prev = *__first++; @@ -2797,7 +2765,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp) if ( __comp(__prev, __result.first)) __result.first = __prev; if (!__comp(*__first, __result.second)) __result.second = *__first; } - + __first++; } return __result; @@ -3128,6 +3096,78 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, } } +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __output, + _Distance __n, + _UniformRandomNumberGenerator & __g, + input_iterator_tag) { + + _Distance __k = 0; + for (; __first != __last && __k < __n; ++__first, (void)++__k) + __output[__k] = *__first; + _Distance __sz = __k; + for (; __first != __last; ++__first, (void)++__k) { + _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); + if (__r < __sz) + __output[__r] = *__first; + } + return __output + _VSTD::min(__n, __k); +} + +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __output, + _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) { + *__output++ = *__first; + --__n; + } + } + return __output; +} + +template <class _PopulationIterator, class _SampleIterator, class _Distance, + class _UniformRandomNumberGenerator> +_LIBCPP_INLINE_VISIBILITY +_SampleIterator __sample(_PopulationIterator __first, + _PopulationIterator __last, _SampleIterator __output, + _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, __output, _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 __output, + _Distance __n, _UniformRandomNumberGenerator&& __g) { + return _VSTD::__sample(__first, __last, __output, __n, __g); +} +#endif // _LIBCPP_STD_VER > 14 + template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -4423,7 +4463,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator<value_type*> _Rv; - __half_inplace_merge(_Rv(__p), _Rv(__buff), + __half_inplace_merge(_Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), __negate<_Compare>(__comp)); } @@ -4871,7 +4911,8 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) template <class _Compare, class _RandomAccessIterator> void -__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, +__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, + _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, _RandomAccessIterator __start) { |
