diff options
Diffstat (limited to 'system/include/libcxx/algorithm')
| -rw-r--r-- | system/include/libcxx/algorithm | 236 |
1 files changed, 223 insertions, 13 deletions
diff --git a/system/include/libcxx/algorithm b/system/include/libcxx/algorithm index 4adcc696..2fc1f8ab 100644 --- a/system/include/libcxx/algorithm +++ b/system/include/libcxx/algorithm @@ -87,30 +87,63 @@ 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, @@ -1087,6 +1120,32 @@ mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __fi 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> @@ -1110,6 +1169,60 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first 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> @@ -1169,6 +1282,100 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 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> @@ -1398,7 +1605,7 @@ __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, // 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_ + if (__first >= __s) // return __last if no element matches __value_ return __last; if (__pred(*__first, __value_)) break; @@ -1780,17 +1987,23 @@ replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator _ template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_, false_type) +__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) { for (; __n > 0; ++__first, --__n) *__first = __value_; return __first; } -template <class _OutputIterator, class _Size, class _Tp> +template <class _Tp, class _Size, class _Up> inline _LIBCPP_INLINE_VISIBILITY -_OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_, true_type) +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)); @@ -1802,10 +2015,7 @@ inline _LIBCPP_INLINE_VISIBILITY _OutputIterator fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) { - return _VSTD::__fill_n(__first, __n, __value_, integral_constant<bool, - is_pointer<_OutputIterator>::value && - is_trivially_copy_assignable<_Tp>::value && - sizeof(_Tp) == 1>()); + return _VSTD::__fill_n(__first, __n, __value_); } // fill @@ -3778,10 +3988,10 @@ sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp); } -#ifdef _MSC_VER +#ifdef _LIBCPP_MSVC #pragma warning( push ) #pragma warning( disable: 4231) -#endif // _MSC_VER +#endif // _LIBCPP_MSVC _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) @@ -3815,9 +4025,9 @@ _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<double>&, double _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) _LIBCPP_EXTERN_TEMPLATE(unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&)) -#ifdef _MSC_VER +#ifdef _LIBCPP_MSVC #pragma warning( pop ) -#endif // _MSC_VER +#endif // _LIBCPP_MSVC // lower_bound |