diff options
author | hiddenpath <hiddenpath@yandex-team.com> | 2023-12-06 01:17:18 +0300 |
---|---|---|
committer | hiddenpath <hiddenpath@yandex-team.com> | 2023-12-06 01:59:21 +0300 |
commit | 525f68b21befc656ea5f25bb7e30035d2d350768 (patch) | |
tree | 961461b8e22c97629f0cf96c09708f2c4555998c /contrib/libs/cxxsupp/libcxx/include/__algorithm | |
parent | d663b05d2ce78f55bfdd6823d01986944391f4a7 (diff) | |
download | ydb-525f68b21befc656ea5f25bb7e30035d2d350768.tar.gz |
Upd libc++ to 12 July 2022 81c48436bbd29736f77a111fc207e28854939907
Diffstat (limited to 'contrib/libs/cxxsupp/libcxx/include/__algorithm')
38 files changed, 1476 insertions, 286 deletions
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/binary_search.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/binary_search.h index 121a741d07..a440072378 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/binary_search.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/binary_search.h @@ -25,20 +25,20 @@ template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { using _Comp_ref = typename __comp_ref_type<_Compare>::type; - __first = std::lower_bound<_ForwardIterator, _Tp, _Comp_ref>(__first, __last, __value_, __comp); - return __first != __last && !__comp(__value_, *__first); + __first = std::lower_bound<_ForwardIterator, _Tp, _Comp_ref>(__first, __last, __value, __comp); + return __first != __last && !__comp(__value, *__first); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::binary_search(__first, __last, __value_, + return std::binary_search(__first, __last, __value, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/count.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/count.h index e18128cae8..5b54693403 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/count.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/count.h @@ -22,10 +22,10 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 typename iterator_traits<_InputIterator>::difference_type - count(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { + count(_InputIterator __first, _InputIterator __last, const _Tp& __value) { typename iterator_traits<_InputIterator>::difference_type __r(0); for (; __first != __last; ++__first) - if (*__first == __value_) + if (*__first == __value) ++__r; return __r; } diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/equal_range.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/equal_range.h index 2a07364bb6..cbfcd3c1ec 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/equal_range.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/equal_range.h @@ -30,7 +30,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); @@ -39,12 +39,12 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); - if (__comp(*__m, __value_)) + if (__comp(*__m, __value)) { __first = ++__m; __len -= __l2 + 1; } - else if (__comp(__value_, *__m)) + else if (__comp(__value, *__m)) { __last = __m; __len = __l2; @@ -55,8 +55,8 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value_, __comp, __proj), - _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) + _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value, __comp, __proj), + _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp) ); } } @@ -67,19 +67,19 @@ template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value, __comp); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return _VSTD::equal_range(__first, __last, __value_, + return _VSTD::equal_range(__first, __last, __value, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill.h index be5b4740a5..ec9968fdb8 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill.h @@ -23,26 +23,26 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag) +__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag) { for (; __first != __last; ++__first) - *__first = __value_; + *__first = __value; } template <class _RandomAccessIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag) +__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag) { - _VSTD::fill_n(__first, __last - __first, __value_); + _VSTD::fill_n(__first, __last - __first, __value); } template <class _ForwardIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category()); + _VSTD::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill_n.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill_n.h index 590c8f38f3..7482a4188d 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill_n.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/fill_n.h @@ -22,19 +22,19 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) +__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { for (; __n > 0; ++__first, (void) --__n) - *__first = __value_; + *__first = __value; return __first; } template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) +fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { - return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_); + return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/find.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/find.h index 641b85e2f6..ab37d81262 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/find.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/find.h @@ -20,9 +20,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator -find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { +find(_InputIterator __first, _InputIterator __last, const _Tp& __value) { for (; __first != __last; ++__first) - if (*__first == __value_) + if (*__first == __value) break; return __first; } diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/iterator_operations.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/iterator_operations.h index c02f9bf649..3d86f35f59 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/iterator_operations.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/iterator_operations.h @@ -13,6 +13,7 @@ #include <__iterator/advance.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -24,6 +25,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD struct _RangesIterOps { static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; + static constexpr auto next = ranges::next; }; #endif @@ -40,6 +42,12 @@ struct _StdIterOps { return std::distance(__first, __last); } + template <class _Iterator> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + _Iterator next(_Iterator, _Iterator __last) { + return __last; + } + }; _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/lower_bound.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/lower_bound.h index fbcd5c7e90..431ac92a64 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/lower_bound.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/lower_bound.h @@ -48,17 +48,17 @@ _Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Com template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value, "The comparator has to be callable"); auto __proj = std::__identity(); - return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value_, __comp, __proj); + return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value, __comp, __proj); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) { - return std::lower_bound(__first, __last, __value_, +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { + return std::lower_bound(__first, __last, __value, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_heap.h index acac0aabf1..bc39d82bf9 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_heap.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_heap.h @@ -14,6 +14,7 @@ #include <__algorithm/sift_down.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,36 +23,32 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __n = __last - __first; - if (__n > 1) - { - // start from the first parent, there is no need to consider children - for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) - { - _VSTD::__sift_down<_Compare>(__first, __comp, __n, __first + __start); - } +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + difference_type __n = __last - __first; + if (__n > 1) { + // start from the first parent, there is no need to consider children + for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { + std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start); } + } } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__make_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::make_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h index 8141c4ed17..6d8ebfd3d9 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h @@ -13,6 +13,8 @@ #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> +#include <__type_traits/decay.h> +#include <__type_traits/is_member_pointer.h> #include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -28,7 +30,7 @@ namespace ranges { template <class _Comp, class _Proj> _LIBCPP_HIDE_FROM_ABI constexpr static decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { - if constexpr (same_as<_Proj, identity>) { + if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Comp>>) { // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable // optimizations that rely on the type of the comparator. return __comp; @@ -42,6 +44,24 @@ decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { } } +template <class _Comp, class _Proj1, class _Proj2> +_LIBCPP_HIDE_FROM_ABI constexpr static +decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { + if constexpr (same_as<decay_t<_Proj1>, identity> && same_as<decay_t<_Proj2>, identity> && + !is_member_pointer_v<decay_t<_Comp>>) { + // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable + // optimizations that rely on the type of the comparator. + return __comp; + + } else { + return [&](auto&& __lhs, auto&& __rhs) { + return std::invoke(__comp, + std::invoke(__proj1, std::forward<decltype(__lhs)>(__lhs)), + std::invoke(__proj2, std::forward<decltype(__rhs)>(__rhs))); + }; + } +} + } // namespace ranges _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/minmax_element.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/minmax_element.h index fe5f20bf1c..cf67184e0b 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/minmax_element.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/minmax_element.h @@ -24,17 +24,17 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Comp, class _Proj> class _MinmaxElementLessFunc { - _Comp& __comp; - _Proj& __proj; + _Comp& __comp_; + _Proj& __proj_; public: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR - _MinmaxElementLessFunc(_Comp& __comp_, _Proj& __proj_) : __comp(__comp_), __proj(__proj_) {} + _MinmaxElementLessFunc(_Comp& __comp, _Proj& __proj) : __comp_(__comp), __proj_(__proj) {} template <class _Iter> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(_Iter& __it1, _Iter& __it2) { - return std::__invoke(__comp, std::__invoke(__proj, *__it1), std::__invoke(__proj, *__it2)); + return std::__invoke(__comp_, std::__invoke(__proj_, *__it1), std::__invoke(__proj_, *__it2)); } }; diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h index 60b9280f75..c7cdef5be8 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h @@ -14,13 +14,11 @@ #include <__algorithm/sort.h> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -223,25 +221,35 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) -{ - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare& __comp) { + if (__nth == __last) + return; + + std::__debug_randomize_range(__first, __last); + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + + std::__debug_randomize_range(__first, __nth); if (__nth != __last) { - _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last); + std::__debug_randomize_range(++__nth, __last); } } +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare __comp) { + std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp); +} + template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) -{ - _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { + std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<typename + iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h index 3870c0cc93..e008c0c996 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h @@ -16,13 +16,10 @@ #include <__algorithm/sort_heap.h> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -55,10 +52,10 @@ void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); + std::__debug_randomize_range(__first, __last); typedef typename __comp_ref_type<_Compare>::type _Comp_ref; _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last); + std::__debug_randomize_range(__middle, __last); } template <class _RandomAccessIterator> diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/pop_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/pop_heap.h index 2932a5e31d..cadda81f6c 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/pop_heap.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/pop_heap.h @@ -13,6 +13,7 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/push_heap.h> #include <__algorithm/sift_down.h> +#include <__assert> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> @@ -24,44 +25,43 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { + _LIBCPP_ASSERT(__len > 0, "The heap given to pop_heap must be non-empty"); - if (__len > 1) - { - value_type __top = std::move(*__first); // create a hole at __first - _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len); - --__last; - if (__hole == __last) { - *__hole = std::move(__top); - } else { - *__hole = std::move(*__last); - ++__hole; - *__last = std::move(__top); - std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first); - } + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + if (__len > 1) { + value_type __top = std::move(*__first); // create a hole at __first + _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len); + --__last; + + if (__hole == __last) { + *__hole = std::move(__top); + } else { + *__hole = std::move(*__last); + ++__hole; + *__last = std::move(__top); + std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first); } + } } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; + std::__pop_heap(std::move(__first), std::move(__last), __comp, __len); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::pop_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/push_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/push_heap.h index 66973e082f..1e3eec373d 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/push_heap.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/push_heap.h @@ -22,47 +22,50 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - if (__len > 1) - { - __len = (__len - 2) / 2; - _RandomAccessIterator __ptr = __first + __len; - if (__comp(*__ptr, *--__last)) - { - value_type __t(_VSTD::move(*__last)); - do - { - *__last = _VSTD::move(*__ptr); - __last = __ptr; - if (__len == 0) - break; - __len = (__len - 1) / 2; - __ptr = __first + __len; - } while (__comp(*__ptr, __t)); - *__last = _VSTD::move(__t); - } +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + + if (__len > 1) { + __len = (__len - 2) / 2; + _RandomAccessIterator __ptr = __first + __len; + + if (__comp(*__ptr, *--__last)) { + value_type __t(std::move(*__last)); + do { + *__last = std::move(*__ptr); + __last = __ptr; + if (__len == 0) + break; + __len = (__len - 1) / 2; + __ptr = __first + __len; + } while (__comp(*__ptr, __t)); + + *__last = std::move(__t); } + } +} + +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; + std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len); } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__push_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::push_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_make_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_make_heap.h new file mode 100644 index 0000000000..fd488dc11a --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_make_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H + +#include <__algorithm/make_heap.h> +#include <__algorithm/make_projected.h> +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __make_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __make_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__make_heap(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __make_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __make_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __make_heap + +inline namespace __cpo { + inline constexpr auto make_heap = __make_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_merge.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_merge.h new file mode 100644 index 0000000000..eb621c2351 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_merge.h @@ -0,0 +1,142 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MERGE_H +#define _LIBCPP___ALGORITHM_RANGES_MERGE_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> +#include <type_traits> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter1, class _InIter2, class _OutIter> +using merge_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __merge { + +template < + class _InIter1, + class _Sent1, + class _InIter2, + class _Sent2, + class _OutIter, + class _Comp, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI constexpr merge_result<__uncvref_t<_InIter1>, __uncvref_t<_InIter2>, __uncvref_t<_OutIter>> +__merge_impl( + _InIter1&& __first1, + _Sent1&& __last1, + _InIter2&& __first2, + _Sent2&& __last2, + _OutIter&& __result, + _Comp&& __comp, + _Proj1&& __proj1, + _Proj2&& __proj2) { + for (; __first1 != __last1 && __first2 != __last2; ++__result) { + if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) { + *__result = *__first2; + ++__first2; + } else { + *__result = *__first1; + ++__first1; + } + } + auto __ret1 = ranges::copy(std::move(__first1), std::move(__last1), std::move(__result)); + auto __ret2 = ranges::copy(std::move(__first2), std::move(__last2), std::move(__ret1.out)); + return {std::move(__ret1.in), std::move(__ret2.in), std::move(__ret2.out)}; +} + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr merge_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __merge::__merge_impl(__first1, __last1, __first2, __last2, __result, __comp, __proj1, __proj2); + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable< + iterator_t<_Range1>, + iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr merge_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __merge::__merge_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __result, + __comp, + __proj1, + __proj2); + } +}; + +} // namespace __merge + +inline namespace __cpo { + inline constexpr auto merge = __merge::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MERGE_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_nth_element.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_nth_element.h new file mode 100644 index 0000000000..2a929eacb8 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_nth_element.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/nth_element.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __nth_element { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__nth_element_impl(std::move(__first), std::move(__nth), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Iter __nth, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __nth_element_fn_impl(std::move(__first), std::move(__nth), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, iterator_t<_Range> __nth, _Comp __comp = {}, + _Proj __proj = {}) const { + return __nth_element_fn_impl(ranges::begin(__r), std::move(__nth), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __nth_element + +inline namespace __cpo { + inline constexpr auto nth_element = __nth_element::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_pop_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_pop_heap.h new file mode 100644 index 0000000000..d0b8314e5b --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_pop_heap.h @@ -0,0 +1,80 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/pop_heap.h> +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __pop_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + auto __len = __last_iter - __first; + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __pop_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __pop_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __pop_heap + +inline namespace __cpo { + inline constexpr auto pop_heap = __pop_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_push_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_push_heap.h new file mode 100644 index 0000000000..e46ad19cfe --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_push_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/push_heap.h> +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __push_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __push_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__push_heap(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __push_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __push_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __push_heap + +inline namespace __cpo { + inline constexpr auto push_heap = __push_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove.h new file mode 100644 index 0000000000..a6a1200763 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove.h @@ -0,0 +1,64 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REMOVE_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_H +#include <__config> + +#include <__algorithm/ranges_remove_if.h> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __remove { +struct __fn { + + template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __other) { return __value == __other; }; + return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <forward_range _Range, class _Type, class _Proj = identity> + requires permutable<iterator_t<_Range>> + && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __other) { return __value == __other; }; + return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __remove + +inline namespace __cpo { + inline constexpr auto remove = __remove::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove_if.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove_if.h new file mode 100644 index 0000000000..d4e382e551 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_remove_if.h @@ -0,0 +1,85 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H +#include <__config> + +#include <__algorithm/ranges_find_if.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__iterator/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Iter, class _Sent, class _Proj, class _Pred> +_LIBCPP_HIDE_FROM_ABI constexpr +subrange<_Iter> __remove_if_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + auto __new_end = ranges::__find_if_impl(__first, __last, __pred, __proj); + if (__new_end == __last) + return {__new_end, __new_end}; + + _Iter __i = __new_end; + while (++__i != __last) { + if (!std::invoke(__pred, std::invoke(__proj, *__i))) { + *__new_end = ranges::iter_move(__i); + ++__new_end; + } + } + return {__new_end, __i}; +} + +namespace __remove_if { +struct __fn { + + template <permutable _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <forward_range _Range, + class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } + +}; +} // namespace __remove_if + +inline namespace __cpo { + inline constexpr auto remove_if = __remove_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_reverse_copy.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_reverse_copy.h new file mode 100644 index 0000000000..e2da9b484a --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_reverse_copy.h @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using reverse_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __reverse_copy { +struct __fn { + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return (*this)(subrange(std::move(__first), std::move(__last)), std::move(__result)); + } + + template <bidirectional_range _Range, weakly_incrementable _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const { + auto __ret = ranges::copy(std::__reverse_range(__range), std::move(__result)); + return {ranges::next(ranges::begin(__range), ranges::end(__range)), std::move(__ret.out)}; + } + +}; +} // namespace __reverse_copy + +inline namespace __cpo { + inline constexpr auto reverse_copy = __reverse_copy::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_rotate_copy.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_rotate_copy.h new file mode 100644 index 0000000000..d7a282c867 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_rotate_copy.h @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using rotate_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __rotate_copy { +struct __fn { + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _InIter __middle, _Sent __last, _OutIter __result) const { + auto __res1 = ranges::copy(__middle, __last, std::move(__result)); + auto __res2 = ranges::copy(__first, __middle, std::move(__res1.out)); + return {std::move(__res1.in), std::move(__res2.out)}; + } + + template <bidirectional_range _Range, weakly_incrementable _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, iterator_t<_Range> __middle, _OutIter __result) const { + return (*this)(ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __rotate_copy + +inline namespace __cpo { + inline constexpr auto rotate_copy = __rotate_copy::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_difference.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_difference.h new file mode 100644 index 0000000000..efafbda554 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_difference.h @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H +#define _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_difference.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__type_traits/decay.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using set_difference_result = in_out_result<_InIter, _OutIter>; + +namespace __set_difference { + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<_InIter1, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_difference( + __first1, __last1, __first2, __last2, __result, ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<borrowed_iterator_t<_Range1>, _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_difference( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __result, + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.first), std::move(__ret.second)}; + } +}; + +} // namespace __set_difference + +inline namespace __cpo { + inline constexpr auto set_difference = __set_difference::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +#endif // _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_intersection.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_intersection.h new file mode 100644 index 0000000000..feb0fe4222 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_set_intersection.h @@ -0,0 +1,117 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H +#define _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_intersection.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter1, class _InIter2, class _OutIter> +using set_intersection_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __set_intersection { + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_intersection<_RangesIterOps>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)}; + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable< + iterator_t<_Range1>, + iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<borrowed_iterator_t<_Range1>, + borrowed_iterator_t<_Range2>, + _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_intersection<_RangesIterOps>( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)}; + } +}; + +} // namespace __set_intersection + +inline namespace __cpo { + inline constexpr auto set_intersection = __set_intersection::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +#endif // _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h index a446a53e06..8297940df2 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h @@ -11,7 +11,6 @@ #include <__algorithm/make_projected.h> #include <__algorithm/sort.h> -#include <__concepts/same_as.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> @@ -44,7 +43,7 @@ struct __fn { _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = __make_projected_comp(__comp, __proj); + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); std::__sort_impl(std::move(__first), __last_iter, __projected_comp); return __last_iter; diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort_heap.h new file mode 100644 index 0000000000..c753e20c44 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/sort_heap.h> +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __sort_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __sort_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__sort_heap(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __sort_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __sort_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __sort_heap + +inline namespace __cpo { + inline constexpr auto sort_heap = __sort_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_stable_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_stable_sort.h new file mode 100644 index 0000000000..20e8404264 --- /dev/null +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_stable_sort.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H +#define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/stable_sort.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __stable_sort { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI + static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __stable_sort + +inline namespace __cpo { + inline constexpr auto stable_sort = __stable_sort::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove.h index c00f96f78a..8a7e99ba09 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove.h @@ -22,15 +22,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - __first = _VSTD::find(__first, __last, __value_); + __first = _VSTD::find(__first, __last, __value); if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { - if (!(*__i == __value_)) + if (!(*__i == __value)) { *__first = _VSTD::move(*__i); ++__first; diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove_copy.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove_copy.h index a29a385af9..55fc1d90a1 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove_copy.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/remove_copy.h @@ -20,11 +20,11 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_) +remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value) { for (; __first != __last; ++__first) { - if (!(*__first == __value_)) + if (!(*__first == __value)) { *__result = *__first; ++__result; diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/search_n.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/search_n.h index 4c083de65e..c51701415b 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/search_n.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/search_n.h @@ -23,7 +23,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, + _Size __count, const _Tp& __value, _BinaryPredicate __pred, forward_iterator_tag) { if (__count <= 0) return __first; @@ -32,7 +32,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __fir while (true) { if (__first == __last) // return __last if no element matches __value_ return __last; - if (__pred(*__first, __value_)) + if (__pred(*__first, __value)) break; ++__first; } @@ -44,7 +44,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __fir 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 + if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; @@ -57,7 +57,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __fir template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __count, - const _Tp& __value_, _BinaryPredicate __pred, + const _Tp& __value, _BinaryPredicate __pred, random_access_iterator_tag) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; if (__count <= 0) @@ -71,7 +71,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter while (true) { if (__first >= __s) // return __last if no element matches __value_ return __last; - if (__pred(*__first, __value_)) + if (__pred(*__first, __value)) break; ++__first; } @@ -82,7 +82,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter 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 + if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; @@ -94,17 +94,17 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( - _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { + _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value, _BinaryPredicate __pred) { return _VSTD::__search_n<_BinaryPredicate&>( - __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, + __first, __last, _VSTD::__convert_to_integral(__count), __value, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); } template <class _ForwardIterator, class _Size, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { +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, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); + return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_difference.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_difference.h index 5e2dca24e4..4378bd5304 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_difference.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_difference.h @@ -13,7 +13,12 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> +#include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,50 +26,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - while (__first1 != __last1) - { - if (__first2 == __last2) - return _VSTD::copy(__first1, __last1, __result); - if (__comp(*__first1, *__first2)) - { - *__result = *__first1; - ++__result; - ++__first1; - } - else - { - if (!__comp(*__first2, *__first1)) - ++__first1; - ++__first2; - } +template < class _Comp, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<__uncvref_t<_InIter1>, __uncvref_t<_OutIter> > +__set_difference( + _InIter1&& __first1, _Sent1&& __last1, _InIter2&& __first2, _Sent2&& __last2, _OutIter&& __result, _Comp&& __comp) { + while (__first1 != __last1 && __first2 != __last2) { + if (__comp(*__first1, *__first2)) { + *__result = *__first1; + ++__first1; + ++__result; + } else if (__comp(*__first2, *__first1)) { + ++__first2; + } else { + ++__first1; + ++__first2; } - return __result; + } + return std::__copy(std::move(__first1), std::move(__last1), std::move(__result)); } template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp).second; } template <class _InputIterator1, class _InputIterator2, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) -{ - return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, - __less<typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result) { + return std::__set_difference( + __first1, + __last1, + __first2, + __last2, + __result, + __less<typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>()).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_intersection.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_intersection.h index c4163fcd4c..837f9af01d 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_intersection.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/set_intersection.h @@ -11,8 +11,10 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,48 +22,76 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - while (__first1 != __last1 && __first2 != __last2) - { - if (__comp(*__first1, *__first2)) - ++__first1; - else - { - if (!__comp(*__first2, *__first1)) - { - *__result = *__first1; - ++__result; - ++__first1; - } - ++__first2; - } +template <class _InIter1, class _InIter2, class _OutIter> +struct __set_intersection_result { + _InIter1 in1; + _InIter2 in2; + _OutIter out; + + // need a constructor as C++03 aggregate init is hard + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 + __set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter) + : in1(std::move(__in_iter1)), in2(std::move(__in_iter2)), out(std::move(__out_iter)) {} +}; + +template < class _IterOper, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_intersection_result<_InIter1, _InIter2, _OutIter> +__set_intersection( + _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { + while (__first1 != __last1 && __first2 != __last2) { + if (__comp(*__first1, *__first2)) + ++__first1; + else { + if (!__comp(*__first2, *__first1)) { + *__result = *__first1; + ++__result; + ++__first1; + } + ++__first2; } - return __result; + } + + return __set_intersection_result<_InIter1, _InIter2, _OutIter>( + _IterOper::next(std::move(__first1), std::move(__last1)), + _IterOper::next(std::move(__first2), std::move(__last2)), + std::move(__result)); } template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__set_intersection<_StdIterOps, _Comp_ref>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __comp) + .out; } template <class _InputIterator1, class _InputIterator2, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) -{ - return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, - __less<typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result) { + return std::__set_intersection<_StdIterOps>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __less<typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>()) + .out; } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h index f7406a5170..76a1821573 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h @@ -17,6 +17,7 @@ #include <__bits> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> @@ -24,10 +25,6 @@ #include <climits> #include <memory> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -582,7 +579,7 @@ extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long dou template <class _RandomAccessIterator, class _Comp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); + std::__debug_randomize_range(__first, __last); using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort_heap.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort_heap.h index 3a63d744fc..261adedd0e 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort_heap.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort_heap.h @@ -14,6 +14,7 @@ #include <__algorithm/pop_heap.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <type_traits> // swap #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -23,29 +24,27 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 void -__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) - _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) + std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n); } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__sort_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::sort_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/stable_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/stable_sort.h index 22b0a64db6..e3479aad62 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/stable_sort.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/stable_sort.h @@ -15,6 +15,7 @@ #include <__algorithm/sort.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> #include <memory> #include <type_traits> @@ -199,33 +200,36 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __len = __last - __first; - pair<value_type*, ptrdiff_t> __buf(0, 0); - unique_ptr<value_type, __return_temporary_buffer> __h; - if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) - { +inline _LIBCPP_HIDE_FROM_ABI +void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + + difference_type __len = __last - __first; + pair<value_type*, ptrdiff_t> __buf(0, 0); + unique_ptr<value_type, __return_temporary_buffer> __h; + if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { // TODO: Remove the use of std::get_temporary_buffer _LIBCPP_SUPPRESS_DEPRECATED_PUSH - __buf = _VSTD::get_temporary_buffer<value_type>(__len); + __buf = std::get_temporary_buffer<value_type>(__len); _LIBCPP_SUPPRESS_DEPRECATED_POP - __h.reset(__buf.first); - } - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); + __h.reset(__buf.first); + } + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); +} + +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__stable_sort_impl(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/upper_bound.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/upper_bound.h index c6483607e3..3fc2548735 100644 --- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/upper_bound.h +++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/upper_bound.h @@ -24,7 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); @@ -33,7 +33,7 @@ __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); - if (__comp(__value_, *__m)) + if (__comp(__value, *__m)) __len = __l2; else { @@ -48,18 +48,18 @@ template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { - return _VSTD::__upper_bound<_Compare&>(__first, __last, __value_, __comp); + return _VSTD::__upper_bound<_Compare&>(__first, __last, __value, __comp); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return _VSTD::upper_bound(__first, __last, __value_, + return _VSTD::upper_bound(__first, __last, __value, __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); } |