diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -1,4 +1,23 @@ set(files + __algorithm/adjacent_find.h + __algorithm/algorithm_functional.h + __algorithm/all_of.h + __algorithm/any_of.h + __algorithm/count.h + __algorithm/count_if.h + __algorithm/equal.h + __algorithm/find.h + __algorithm/find_end.h + __algorithm/find_if.h + __algorithm/find_if_not.h + __algorithm/find_first_of.h + __algorithm/for_each.h + __algorithm/for_each_n.h + __algorithm/is_permutation.h + __algorithm/mismatch.h + __algorithm/none_of.h + __algorithm/search.h + __algorithm/search_n.h __availability __bit_reference __bits @@ -10,6 +29,7 @@ __format/format_error.h __format/format_parse_context.h __function_like.h + __functional/__search.h __functional_03 __functional_base __functional_base_03 diff --git a/libcxx/include/__algorithm/adjacent_find.h b/libcxx/include/__algorithm/adjacent_find.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/adjacent_find.h @@ -0,0 +1,51 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_ADJACENT_FIND_H +#define _LIBCPP___ALGORITHM_ADJACENT_FIND_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { + if (__first != __last) { + _ForwardIterator __i = __first; + while (++__i != __last) { + if (__pred(*__first, *__i)) + return __first; + __first = __i; + } + } + return __last; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +adjacent_find(_ForwardIterator __first, _ForwardIterator __last) { + typedef typename iterator_traits<_ForwardIterator>::value_type __v; + return _VSTD::adjacent_find(__first, __last, __equal_to<__v>()); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_ADJACENT_FIND_H diff --git a/libcxx/include/__algorithm/algorithm_functional.h b/libcxx/include/__algorithm/algorithm_functional.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/algorithm_functional.h @@ -0,0 +1,191 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_ALGORITHM_FUNCTIONAL_H +#define _LIBCPP___ALGORITHM_ALGORITHM_FUNCTIONAL_H + +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +// I'd like to replace these with _VSTD::equal_to, but can't because that only works with C++14 and later. +template +struct __equal_to { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x == __y; + } + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const { + return __x == __y; + } + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const { + return __x == __y; + } + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const { + return __x == __y; + } +}; + +template +struct __equal_to<_T1, _T1> { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x == __y; + } +}; + +template +struct __equal_to { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x == __y; + } +}; + +template +struct __equal_to<_T1, const _T1> { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x == __y; + } +}; + +template +struct __less { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x < __y; + } + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const { + return __x < __y; + } + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const { + return __x < __y; + } + + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const { + return __x < __y; + } +}; + +template +struct __less<_T1, _T1> { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x < __y; + } +}; + +template +struct __less { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x < __y; + } +}; + +template +struct __less<_T1, const _T1> { + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const { + return __x < __y; + } +}; + +template +class __invert // invert the sense of a comparison +{ +private: + _Predicate __p_; + +public: + _LIBCPP_INLINE_VISIBILITY __invert() {} + + _LIBCPP_INLINE_VISIBILITY + explicit __invert(_Predicate __p) : __p_(__p) {} + + template + _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x) { + return !__p_(__x); + } + + template + _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) { + return __p_(__y, __x); + } +}; + +// Perform division by two quickly for positive integers (llvm.org/PR39129) + +template +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if::value, _Integral>::type +__half_positive(_Integral __value) { + return static_cast<_Integral>(static_cast::type>(__value) / 2); +} + +template +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if::value, _Tp>::type +__half_positive(_Tp __value) { + return __value / 2; +} + +#ifdef _LIBCPP_DEBUG + +template +struct __debug_less { + _Compare& __comp_; + _LIBCPP_CONSTEXPR_AFTER_CXX17 + __debug_less(_Compare& __c) : __comp_(__c) {} + + template + _LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator()(const _Tp& __x, const _Up& __y) { + bool __r = __comp_(__x, __y); + if (__r) + __do_compare_assert(0, __y, __x); + return __r; + } + + template + _LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator()(_Tp& __x, _Up& __y) { + bool __r = __comp_(__x, __y); + if (__r) + __do_compare_assert(0, __y, __x); + return __r; + } + + template + _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY decltype((void)declval<_Compare&>()(declval<_LHS&>(), + declval<_RHS&>())) + __do_compare_assert(int, _LHS& __l, _RHS& __r) { + _LIBCPP_ASSERT(!__comp_(__l, __r), "Comparator does not induce a strict weak ordering"); + } + + template + _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY void __do_compare_assert(long, _LHS&, _RHS&) {} +}; + +#endif // _LIBCPP_DEBUG + +template +struct __comp_ref_type { + // Pass the comparator by lvalue reference. Or in debug mode, using a + // debugging wrapper that stores a reference. +#ifndef _LIBCPP_DEBUG + typedef typename add_lvalue_reference<_Comp>::type type; +#else + typedef __debug_less<_Comp> type; +#endif +}; + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_ALGORITHM_FUNCTIONAL_H diff --git a/libcxx/include/__algorithm/all_of.h b/libcxx/include/__algorithm/all_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/all_of.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_ALL_OF_H +#define _LIBCPP___ALGORITHM_ALL_OF_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + for (; __first != __last; ++__first) + if (!__pred(*__first)) + return false; + return true; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_ALL_OF_H diff --git a/libcxx/include/__algorithm/any_of.h b/libcxx/include/__algorithm/any_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/any_of.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_ANY_OF_H +#define _LIBCPP___ALGORITHM_ANY_OF_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + for (; __first != __last; ++__first) + if (__pred(*__first)) + return true; + return false; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_ANY_OF_H diff --git a/libcxx/include/__algorithm/count.h b/libcxx/include/__algorithm/count.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/count.h @@ -0,0 +1,40 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_COUNT_H +#define _LIBCPP___ALGORITHM_COUNT_H + +#include <__config> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_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_) { + typename iterator_traits<_InputIterator>::difference_type __r(0); + for (; __first != __last; ++__first) + if (*__first == __value_) + ++__r; + return __r; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_COUNT_H diff --git a/libcxx/include/__algorithm/count_if.h b/libcxx/include/__algorithm/count_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/count_if.h @@ -0,0 +1,40 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_COUNT_IF_H +#define _LIBCPP___ALGORITHM_COUNT_IF_H + +#include <__config> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + typename iterator_traits<_InputIterator>::difference_type + count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + typename iterator_traits<_InputIterator>::difference_type __r(0); + for (; __first != __last; ++__first) + if (__pred(*__first)) + ++__r; + return __r; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_COUNT_IF_H diff --git a/libcxx/include/__algorithm/equal.h b/libcxx/include/__algorithm/equal.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/equal.h @@ -0,0 +1,90 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_EQUAL_H +#define _LIBCPP___ALGORITHM_EQUAL_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include // FIXME: replace with <__iterator/distance.h> when it lands + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { + for (; __first1 != __last1; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + return false; + return true; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { + typedef typename iterator_traits<_InputIterator1>::value_type __v1; + typedef typename iterator_traits<_InputIterator2>::value_type __v2; + return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>()); +} + +#if _LIBCPP_STD_VER > 11 +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, + _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag) { + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + return false; + return __first1 == __last1 && __first2 == __last2; +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, + random_access_iterator_tag) { + if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) + return false; + return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, + typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, __pred); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, + _BinaryPredicate __pred) { + return _VSTD::__equal::type>( + __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(), + typename iterator_traits<_InputIterator2>::iterator_category()); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + typedef typename iterator_traits<_InputIterator1>::value_type __v1; + typedef typename iterator_traits<_InputIterator2>::value_type __v2; + return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), + typename iterator_traits<_InputIterator1>::iterator_category(), + typename iterator_traits<_InputIterator2>::iterator_category()); +} +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_EQUAL_H diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/find.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FIND_H +#define _LIBCPP___ALGORITHM_FIND_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator +find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { + for (; __first != __last; ++__first) + if (*__first == __value_) + break; + return __first; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FIND_H diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/find_end.h @@ -0,0 +1,153 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FIND_END_OF_H +#define _LIBCPP___ALGORITHM_FIND_END_OF_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, + forward_iterator_tag) { + // modeled after search algorithm + _ForwardIterator1 __r = __last1; // __last1 is the "default" answer + if (__first2 == __last2) + return __r; + while (true) { + while (true) { + if (__first1 == __last1) // if source exhausted return last correct answer + return __r; // (or __last1 if never found) + if (__pred(*__first1, *__first2)) + break; + ++__first1; + } + // *__first1 matches *__first2, now match elements after here + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; + while (true) { + if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one + __r = __first1; + ++__first1; + break; + } + if (++__m1 == __last1) // Source exhausted, return last answer + return __r; + if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first + { + ++__first1; + break; + } // else there is a match, check next elements + } + } +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( + _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, + _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { + // modeled after search algorithm (in reverse) + if (__first2 == __last2) + return __last1; // Everything matches an empty sequence + _BidirectionalIterator1 __l1 = __last1; + _BidirectionalIterator2 __l2 = __last2; + --__l2; + while (true) { + // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks + while (true) { + if (__first1 == __l1) // return __last1 if no element matches *__first2 + return __last1; + if (__pred(*--__l1, *__l2)) + break; + } + // *__l1 matches *__l2, now match elements before here + _BidirectionalIterator1 __m1 = __l1; + _BidirectionalIterator2 __m2 = __l2; + while (true) { + if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) + return __m1; + if (__m1 == __first1) // Otherwise if source exhaused, pattern not found + return __last1; + if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 + { + break; + } // else there is a match, check next elements + } + } +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( + _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { + // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern + typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; + if (__len2 == 0) + return __last1; + typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; + if (__len1 < __len2) + return __last1; + const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here + _RandomAccessIterator1 __l1 = __last1; + _RandomAccessIterator2 __l2 = __last2; + --__l2; + while (true) { + while (true) { + if (__s == __l1) + return __last1; + if (__pred(*--__l1, *__l2)) + break; + } + _RandomAccessIterator1 __m1 = __l1; + _RandomAccessIterator2 __m2 = __l2; + while (true) { + if (__m2 == __first2) + return __m1; + // no need to check range on __m1 because __s guarantees we have enough source + if (!__pred(*--__m1, *--__m2)) { + break; + } + } + } +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return _VSTD::__find_end::type>( + __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FIND_END_OF_H diff --git a/libcxx/include/__algorithm/find_first_of.h b/libcxx/include/__algorithm/find_first_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/find_first_of.h @@ -0,0 +1,57 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FIND_FIRST_OF_H +#define _LIBCPP___ALGORITHM_FIND_FIRST_OF_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1 __find_first_of_ce(_ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _BinaryPredicate __pred) { + for (; __first1 != __last1; ++__first1) + for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) + if (__pred(*__first1, *__j)) + return __first1; + return __last1; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _BinaryPredicate __pred) { + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 find_first_of( + _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FIND_FIRST_OF_H diff --git a/libcxx/include/__algorithm/find_if.h b/libcxx/include/__algorithm/find_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/find_if.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FIND_IF_H +#define _LIBCPP___ALGORITHM_FIND_IF_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator +find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + for (; __first != __last; ++__first) + if (__pred(*__first)) + break; + return __first; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FIND_IF_H diff --git a/libcxx/include/__algorithm/find_if_not.h b/libcxx/include/__algorithm/find_if_not.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/find_if_not.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FIND_IF_NOT_H +#define _LIBCPP___ALGORITHM_FIND_IF_NOT_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator +find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + for (; __first != __last; ++__first) + if (!__pred(*__first)) + break; + return __first; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FIND_IF_NOT_H diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/for_each.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FOR_EACH_H +#define _LIBCPP___ALGORITHM_FOR_EACH_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _Function for_each(_InputIterator __first, + _InputIterator __last, + _Function __f) { + for (; __first != __last; ++__first) + __f(*__first); + return __f; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FOR_EACH_H diff --git a/libcxx/include/__algorithm/for_each_n.h b/libcxx/include/__algorithm/for_each_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/for_each_n.h @@ -0,0 +1,47 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_FOR_EACH_N_H +#define _LIBCPP___ALGORITHM_FOR_EACH_N_H + +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 14 + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator for_each_n(_InputIterator __first, + _Size __orig_n, + _Function __f) { + typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; + _IntegralSize __n = __orig_n; + while (__n > 0) { + __f(*__first); + ++__first; + --__n; + } + return __first; +} + +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_FOR_EACH_N_H diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/is_permutation.h @@ -0,0 +1,168 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_IS_PERMUTATION_H +#define _LIBCPP___ALGORITHM_IS_PERMUTATION_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include // FIXME: replace with <__iterator/distance.h> when it lands + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _BinaryPredicate __pred) { + // shorten sequences as much as possible by lopping of any equal prefix + for (; __first1 != __last1; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + break; + if (__first1 == __last1) + return true; + + // __first1 != __last1 && *__first1 != *__first2 + typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; + _D1 __l1 = _VSTD::distance(__first1, __last1); + if (__l1 == _D1(1)) + return false; + _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); + // For each element in [f1, l1) see if there are the same number of + // equal elements in [f2, l2) + for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { + // Have we already counted the number of *__i in [f1, l1)? + _ForwardIterator1 __match = __first1; + for (; __match != __i; ++__match) + if (__pred(*__match, *__i)) + break; + if (__match == __i) { + // Count number of *__i in [f2, l2) + _D1 __c2 = 0; + for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) + if (__pred(*__i, *__j)) + ++__c2; + if (__c2 == 0) + return false; + // Count number of *__i in [__i, l1) (we can start with 1) + _D1 __c1 = 1; + for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) + if (__pred(*__i, *__j)) + ++__c1; + if (__c1 != __c2) + return false; + } + } + return true; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); +} + +#if _LIBCPP_STD_VER > 11 +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { + // shorten sequences as much as possible by lopping of any equal prefix + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + break; + if (__first1 == __last1) + return __first2 == __last2; + else if (__first2 == __last2) + return false; + + typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; + _D1 __l1 = _VSTD::distance(__first1, __last1); + + typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; + _D2 __l2 = _VSTD::distance(__first2, __last2); + if (__l1 != __l2) + return false; + + // For each element in [f1, l1) see if there are the same number of + // equal elements in [f2, l2) + for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { + // Have we already counted the number of *__i in [f1, l1)? + _ForwardIterator1 __match = __first1; + for (; __match != __i; ++__match) + if (__pred(*__match, *__i)) + break; + if (__match == __i) { + // Count number of *__i in [f2, l2) + _D1 __c2 = 0; + for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) + if (__pred(*__i, *__j)) + ++__c2; + if (__c2 == 0) + return false; + // Count number of *__i in [__i, l1) (we can start with 1) + _D1 __c1 = 1; + for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) + if (__pred(*__i, *__j)) + ++__c1; + if (__c1 != __c2) + return false; + } + } + return true; +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, + _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, + _BinaryPredicate __pred, random_access_iterator_tag, + random_access_iterator_tag) { + if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) + return false; + return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, + typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, + __pred); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _BinaryPredicate __pred) { + return _VSTD::__is_permutation::type>( + __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); +} +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H diff --git a/libcxx/include/__algorithm/mismatch.h b/libcxx/include/__algorithm/mismatch.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/mismatch.h @@ -0,0 +1,72 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_MISMATCH_H +#define _LIBCPP___ALGORITHM_MISMATCH_H + +#include <__algorithm/algorithm_functional.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY + _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { + for (; __first1 != __last1; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + break; + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY + _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { + typedef typename iterator_traits<_InputIterator1>::value_type __v1; + typedef typename iterator_traits<_InputIterator2>::value_type __v2; + return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>()); +} + +#if _LIBCPP_STD_VER > 11 +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY + _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, + _BinaryPredicate __pred) { + for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) + if (!__pred(*__first1, *__first2)) + break; + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY + _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + typedef typename iterator_traits<_InputIterator1>::value_type __v1; + typedef typename iterator_traits<_InputIterator2>::value_type __v2; + return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +} +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_MISMATCH_H diff --git a/libcxx/include/__algorithm/none_of.h b/libcxx/include/__algorithm/none_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/none_of.h @@ -0,0 +1,37 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_NONE_OF_H +#define _LIBCPP___ALGORITHM_NONE_OF_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { + for (; __first != __last; ++__first) + if (__pred(*__first)) + return false; + return true; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_NONE_OF_H diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/search.h @@ -0,0 +1,59 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_H +#define _LIBCPP___ALGORITHM_SEARCH_H + +#include <__config> +#include <__functional/__search.h> +#include <__iterator/iterator_traits.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return _VSTD::__search::type>( + __first1, __last1, __first2, __last2, __pred, + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()) + .first; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +} + +#if _LIBCPP_STD_VER > 14 +template +_LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) { + return __s(__f, __l).first; +} + +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_SEARCH_H diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/search_n.h @@ -0,0 +1,115 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_N_H +#define _LIBCPP___ALGORITHM_SEARCH_N_H + +#include <__config> +#include <__iterator/iterator_traits.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, const _Tp& __value_, _BinaryPredicate __pred, + forward_iterator_tag) { + if (__count <= 0) + return __first; + while (true) { + // Find first element in sequence that matchs __value_, with a mininum of loop checks + while (true) { + if (__first == __last) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value_)) + break; + ++__first; + } + // *__first matches __value_, now match elements after here + _ForwardIterator __m = __first; + _Size __c(0); + while (true) { + if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) + return __first; + if (++__m == __last) // Otherwise if source exhaused, pattern not found + return __last; + if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + { + __first = __m; + ++__first; + break; + } // else there is a match, check next elements + } + } +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, + _RandomAccessIterator __last, _Size __count, + const _Tp& __value_, _BinaryPredicate __pred, + random_access_iterator_tag) { + if (__count <= 0) + return __first; + _Size __len = static_cast<_Size>(__last - __first); + if (__len < __count) + return __last; + const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here + while (true) { + // Find first element in sequence that matchs __value_, with a mininum of loop checks + while (true) { + if (__first >= __s) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value_)) + break; + ++__first; + } + // *__first matches __value_, now match elements after here + _RandomAccessIterator __m = __first; + _Size __c(0); + while (true) { + if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) + return __first; + ++__m; // no need to check range on __m because __s guarantees we have enough source + if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + { + __first = __m; + ++__first; + break; + } // else there is a match, check next elements + } + } +} + +template +_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) { + return _VSTD::__search_n::type>( + __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, + typename iterator_traits<_ForwardIterator>::iterator_category()); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { + typedef typename iterator_traits<_ForwardIterator>::value_type __v; + return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_SEARCH_N_H diff --git a/libcxx/include/__functional/__search.h b/libcxx/include/__functional/__search.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__functional/__search.h @@ -0,0 +1,102 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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___FUNCTIONAL___SEARCH_H +#define _LIBCPP___FUNCTIONAL___SEARCH_H + +#include <__config> +#include <__iterator/iterator_traits.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +pair<_ForwardIterator1, _ForwardIterator1> + _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { + if (__first2 == __last2) + return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence + while (true) { + // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks + while (true) { + if (__first1 == __last1) // return __last1 if no element matches *__first2 + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) + break; + ++__first1; + } + // *__first1 matches *__first2, now match elements after here + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; + while (true) { + if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) + return _VSTD::make_pair(__first1, __m1); + if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found + return _VSTD::make_pair(__last1, __last1); + if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 + { + ++__first1; + break; + } // else there is a match, check next elements + } + } +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> +__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, + random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; + typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; + // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern + const _D2 __len2 = __last2 - __first2; + if (__len2 == 0) + return _VSTD::make_pair(__first1, __first1); + const _D1 __len1 = __last1 - __first1; + if (__len1 < __len2) + return _VSTD::make_pair(__last1, __last1); + const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here + + while (true) { + while (true) { + if (__first1 == __s) + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) + break; + ++__first1; + } + + _RandomAccessIterator1 __m1 = __first1; + _RandomAccessIterator2 __m2 = __first2; + while (true) { + if (++__m2 == __last2) + return _VSTD::make_pair(__first1, __first1 + __len2); + ++__m1; // no need to check range on __m1 because __s guarantees we have enough source + if (!__pred(*__m1, *__m2)) { + ++__first1; + break; + } + } + } +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___FUNCTIONAL___SEARCH_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -645,12 +645,32 @@ */ +#include <__algorithm/adjacent_find.h> +#include <__algorithm/all_of.h> +#include <__algorithm/any_of.h> +#include <__algorithm/count.h> +#include <__algorithm/count_if.h> +#include <__algorithm/equal.h> +#include <__algorithm/find.h> +#include <__algorithm/find_end.h> +#include <__algorithm/find_if.h> +#include <__algorithm/find_if_not.h> +#include <__algorithm/find_first_of.h> +#include <__algorithm/for_each.h> +#include <__algorithm/for_each_n.h> +#include <__algorithm/is_permutation.h> +#include <__algorithm/mismatch.h> +#include <__algorithm/none_of.h> +#include <__algorithm/search.h> +#include <__algorithm/search_n.h> #include <__config> #include <__bits> // __libcpp_clz #include #include #include #include +#include // needed to provide swap_ranges. +#include #include #include #include @@ -669,976 +689,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD -// I'd like to replace these with _VSTD::equal_to, but can't because: -// * That only works with C++14 and later, and -// * We haven't included here. -template -struct __equal_to -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;} -}; - -template -struct __equal_to<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template -struct __equal_to -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template -struct __equal_to<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -class __invert // invert the sense of a comparison -{ -private: - _Predicate __p_; -public: - _LIBCPP_INLINE_VISIBILITY __invert() {} - - _LIBCPP_INLINE_VISIBILITY - explicit __invert(_Predicate __p) : __p_(__p) {} - - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x) {return !__p_(__x);} - - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} -}; - -// Perform division by two quickly for positive integers (llvm.org/PR39129) - -template -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -typename enable_if -< - is_integral<_Integral>::value, - _Integral ->::type -__half_positive(_Integral __value) -{ - return static_cast<_Integral>(static_cast::type>(__value) / 2); -} - -template -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -typename enable_if -< - !is_integral<_Tp>::value, - _Tp ->::type -__half_positive(_Tp __value) -{ - return __value / 2; -} - -#ifdef _LIBCPP_DEBUG - -template -struct __debug_less -{ - _Compare &__comp_; - _LIBCPP_CONSTEXPR_AFTER_CXX17 - __debug_less(_Compare& __c) : __comp_(__c) {} - - template - _LIBCPP_CONSTEXPR_AFTER_CXX17 - bool operator()(const _Tp& __x, const _Up& __y) - { - bool __r = __comp_(__x, __y); - if (__r) - __do_compare_assert(0, __y, __x); - return __r; - } - - template - _LIBCPP_CONSTEXPR_AFTER_CXX17 - bool operator()(_Tp& __x, _Up& __y) - { - bool __r = __comp_(__x, __y); - if (__r) - __do_compare_assert(0, __y, __x); - return __r; - } - - template - _LIBCPP_CONSTEXPR_AFTER_CXX17 - inline _LIBCPP_INLINE_VISIBILITY - decltype((void)declval<_Compare&>()( - declval<_LHS &>(), declval<_RHS &>())) - __do_compare_assert(int, _LHS & __l, _RHS & __r) { - _LIBCPP_ASSERT(!__comp_(__l, __r), - "Comparator does not induce a strict weak ordering"); - } - - template - _LIBCPP_CONSTEXPR_AFTER_CXX17 - inline _LIBCPP_INLINE_VISIBILITY - void __do_compare_assert(long, _LHS &, _RHS &) {} -}; - -#endif // _LIBCPP_DEBUG - -template -struct __comp_ref_type { - // Pass the comparator by lvalue reference. Or in debug mode, using a - // debugging wrapper that stores a reference. -#ifndef _LIBCPP_DEBUG - typedef typename add_lvalue_reference<_Comp>::type type; -#else - typedef __debug_less<_Comp> type; -#endif -}; - -// all_of - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (!__pred(*__first)) - return false; - return true; -} - -// any_of - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - return true; - return false; -} - -// none_of - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - return false; - return true; -} - -// for_each - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_Function -for_each(_InputIterator __first, _InputIterator __last, _Function __f) -{ - for (; __first != __last; ++__first) - __f(*__first); - return __f; -} - -#if _LIBCPP_STD_VER > 14 -// for_each_n - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_InputIterator -for_each_n(_InputIterator __first, _Size __orig_n, _Function __f) -{ - typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; - _IntegralSize __n = __orig_n; - while (__n > 0) - { - __f(*__first); - ++__first; - --__n; - } - return __first; -} -#endif - -// find - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_InputIterator -find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) -{ - for (; __first != __last; ++__first) - if (*__first == __value_) - break; - return __first; -} - -// find_if - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_InputIterator -find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - break; - return __first; -} - -// find_if_not - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_InputIterator -find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (!__pred(*__first)) - break; - return __first; -} - -// find_end - -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, - forward_iterator_tag, forward_iterator_tag) -{ - // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer - if (__first2 == __last2) - return __r; - while (true) - { - while (true) - { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) - break; - ++__first1; - } - // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; - while (true) - { - if (++__m2 == __last2) - { // Pattern exhaused, record answer and search for another one - __r = __first1; - ++__first1; - break; - } - if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first - { - ++__first1; - break; - } // else there is a match, check next elements - } - } -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 -__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, - _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred, - bidirectional_iterator_tag, bidirectional_iterator_tag) -{ - // modeled after search algorithm (in reverse) - if (__first2 == __last2) - return __last1; // Everything matches an empty sequence - _BidirectionalIterator1 __l1 = __last1; - _BidirectionalIterator2 __l2 = __last2; - --__l2; - while (true) - { - // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks - while (true) - { - if (__first1 == __l1) // return __last1 if no element matches *__first2 - return __last1; - if (__pred(*--__l1, *__l2)) - break; - } - // *__l1 matches *__l2, now match elements before here - _BidirectionalIterator1 __m1 = __l1; - _BidirectionalIterator2 __m2 = __l2; - while (true) - { - if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) - return __m1; - if (__m1 == __first1) // Otherwise if source exhaused, pattern not found - return __last1; - if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 - { - break; - } // else there is a match, check next elements - } - } -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 -__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag) -{ - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; - if (__len2 == 0) - return __last1; - typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; - if (__len1 < __len2) - return __last1; - const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; - --__l2; - while (true) - { - while (true) - { - if (__s == __l1) - return __last1; - if (__pred(*--__l1, *__l2)) - break; - } - _RandomAccessIterator1 __m1 = __l1; - _RandomAccessIterator2 __m2 = __l2; - while (true) - { - if (__m2 == __first2) - return __m1; - // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*--__m1, *--__m2)) - { - break; - } - } - } -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - return _VSTD::__find_end::type> - (__first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} - -// find_first_of - -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1 -__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - for (; __first1 != __last1; ++__first1) - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) - if (__pred(*__first1, *__j)) - return __first1; - return __last1; -} - - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} - -// adjacent_find - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) -{ - if (__first != __last) - { - _ForwardIterator __i = __first; - while (++__i != __last) - { - if (__pred(*__first, *__i)) - return __first; - __first = __i; - } - } - return __last; -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -adjacent_find(_ForwardIterator __first, _ForwardIterator __last) -{ - typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::adjacent_find(__first, __last, __equal_to<__v>()); -} - -// count - -template -_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_) -{ - typename iterator_traits<_InputIterator>::difference_type __r(0); - for (; __first != __last; ++__first) - if (*__first == __value_) - ++__r; - return __r; -} - -// count_if - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -typename iterator_traits<_InputIterator>::difference_type -count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - typename iterator_traits<_InputIterator>::difference_type __r(0); - for (; __first != __last; ++__first) - if (__pred(*__first)) - ++__r; - return __r; -} - -// mismatch - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -pair<_InputIterator1, _InputIterator2> -mismatch(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _BinaryPredicate __pred) -{ - for (; __first1 != __last1; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - break; - return pair<_InputIterator1, _InputIterator2>(__first1, __first2); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -pair<_InputIterator1, _InputIterator2> -mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) -{ - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>()); -} - -#if _LIBCPP_STD_VER > 11 -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -pair<_InputIterator1, _InputIterator2> -mismatch(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _BinaryPredicate __pred) -{ - for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - break; - return pair<_InputIterator1, _InputIterator2>(__first1, __first2); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -pair<_InputIterator1, _InputIterator2> -mismatch(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2) -{ - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} -#endif - -// equal - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) -{ - for (; __first1 != __last1; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - return false; - return true; -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) -{ - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>()); -} - -#if _LIBCPP_STD_VER > 11 -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -__equal(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, - input_iterator_tag, input_iterator_tag ) -{ - for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - return false; - return __first1 == __last1 && __first2 == __last2; -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag ) -{ - if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) - return false; - return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, - typename add_lvalue_reference<_BinaryPredicate>::type> - (__first1, __last1, __first2, __pred ); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred ) -{ - return _VSTD::__equal::type> - (__first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_InputIterator1>::iterator_category(), - typename iterator_traits<_InputIterator2>::iterator_category()); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2) -{ - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), - typename iterator_traits<_InputIterator1>::iterator_category(), - typename iterator_traits<_InputIterator2>::iterator_category()); -} -#endif - -// is_permutation - -template -_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _BinaryPredicate __pred) -{ -// shorten sequences as much as possible by lopping of any equal prefix - for (; __first1 != __last1; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - break; - if (__first1 == __last1) - return true; - -// __first1 != __last1 && *__first1 != *__first2 - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); - if (__l1 == _D1(1)) - return false; - _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); - // For each element in [f1, l1) see if there are the same number of - // equal elements in [f2, l2) - for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) - { - // Have we already counted the number of *__i in [f1, l1)? - _ForwardIterator1 __match = __first1; - for (; __match != __i; ++__match) - if (__pred(*__match, *__i)) - break; - if (__match == __i) { - // Count number of *__i in [f2, l2) - _D1 __c2 = 0; - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) - if (__pred(*__i, *__j)) - ++__c2; - if (__c2 == 0) - return false; - // Count number of *__i in [__i, l1) (we can start with 1) - _D1 __c1 = 1; - for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) - if (__pred(*__i, *__j)) - ++__c1; - if (__c1 != __c2) - return false; - } - } - return true; -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); -} - -#if _LIBCPP_STD_VER > 11 -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, - forward_iterator_tag, forward_iterator_tag ) -{ -// shorten sequences as much as possible by lopping of any equal prefix - for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) - if (!__pred(*__first1, *__first2)) - break; - if (__first1 == __last1) - return __first2 == __last2; - else if (__first2 == __last2) - return false; - - typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; - _D1 __l1 = _VSTD::distance(__first1, __last1); - - typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; - _D2 __l2 = _VSTD::distance(__first2, __last2); - if (__l1 != __l2) - return false; - - // For each element in [f1, l1) see if there are the same number of - // equal elements in [f2, l2) - for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) - { - // Have we already counted the number of *__i in [f1, l1)? - _ForwardIterator1 __match = __first1; - for (; __match != __i; ++__match) - if (__pred(*__match, *__i)) - break; - if (__match == __i) { - // Count number of *__i in [f2, l2) - _D1 __c2 = 0; - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) - if (__pred(*__i, *__j)) - ++__c2; - if (__c2 == 0) - return false; - // Count number of *__i in [__i, l1) (we can start with 1) - _D1 __c1 = 1; - for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) - if (__pred(*__i, *__j)) - ++__c1; - if (__c1 != __c2) - return false; - } - } - return true; -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, - _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, - _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag ) -{ - if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) - return false; - return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, - typename add_lvalue_reference<_BinaryPredicate>::type> - (__first1, __last1, __first2, __pred ); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred ) -{ - return _VSTD::__is_permutation::type> - (__first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, - __equal_to<__v1, __v2>(), - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); -} -#endif - -// search -// __search is in - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - return _VSTD::__search::type> - (__first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()) - .first; -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} - - -#if _LIBCPP_STD_VER > 14 -template -_LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) -{ return __s(__f, __l).first; } -#endif - -// search_n - -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -__search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag) -{ - if (__count <= 0) - return __first; - while (true) - { - // Find first element in sequence that matchs __value_, with a mininum of loop checks - while (true) - { - if (__first == __last) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) - break; - ++__first; - } - // *__first matches __value_, now match elements after here - _ForwardIterator __m = __first; - _Size __c(0); - while (true) - { - if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - if (++__m == __last) // Otherwise if source exhaused, pattern not found - return __last; - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first - { - __first = __m; - ++__first; - break; - } // else there is a match, check next elements - } - } -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator -__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag) -{ - if (__count <= 0) - return __first; - _Size __len = static_cast<_Size>(__last - __first); - if (__len < __count) - return __last; - const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here - while (true) - { - // Find first element in sequence that matchs __value_, with a mininum of loop checks - while (true) - { - if (__first >= __s) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) - break; - ++__first; - } - // *__first matches __value_, now match elements after here - _RandomAccessIterator __m = __first; - _Size __c(0); - while (true) - { - if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - ++__m; // no need to check range on __m because __s guarantees we have enough source - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first - { - __first = __m; - ++__first; - break; - } // else there is a match, check next elements - } - } -} - -template -_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) -{ - return _VSTD::__search_n::type> - (__first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, - typename iterator_traits<_ForwardIterator>::iterator_category()); -} - -template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) -{ - typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), - __value_, __equal_to<__v, _Tp>()); -} - // __unwrap_iter, __rewrap_iter // The job of __unwrap_iter is to lower contiguous iterators (such as diff --git a/libcxx/include/experimental/functional b/libcxx/include/experimental/functional --- a/libcxx/include/experimental/functional +++ b/libcxx/include/experimental/functional @@ -86,6 +86,7 @@ */ +#include <__functional/__search.h> #include #include #include diff --git a/libcxx/include/functional b/libcxx/include/functional --- a/libcxx/include/functional +++ b/libcxx/include/functional @@ -509,6 +509,7 @@ #include <__config> #include <__debug> #include <__functional_base> +#include <__functional/__search.h> #include #include #include @@ -3110,88 +3111,6 @@ // struct hash in -template -pair<_ForwardIterator1, _ForwardIterator1> _LIBCPP_CONSTEXPR_AFTER_CXX11 -__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, - forward_iterator_tag, forward_iterator_tag) -{ - if (__first2 == __last2) - return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence - while (true) - { - // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks - while (true) - { - if (__first1 == __last1) // return __last1 if no element matches *__first2 - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) - break; - ++__first1; - } - // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; - while (true) - { - if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return _VSTD::make_pair(__first1, __m1); - if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found - return _VSTD::make_pair(__last1, __last1); - if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 - { - ++__first1; - break; - } // else there is a match, check next elements - } - } -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_RandomAccessIterator1, _RandomAccessIterator1> -__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag) -{ - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - const _D2 __len2 = __last2 - __first2; - if (__len2 == 0) - return _VSTD::make_pair(__first1, __first1); - const _D1 __len1 = __last1 - __first1; - if (__len1 < __len2) - return _VSTD::make_pair(__last1, __last1); - const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here - - while (true) - { - while (true) - { - if (__first1 == __s) - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) - break; - ++__first1; - } - - _RandomAccessIterator1 __m1 = __first1; - _RandomAccessIterator2 __m2 = __first2; - while (true) - { - if (++__m2 == __last2) - return _VSTD::make_pair(__first1, __first1 + __len2); - ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*__m1, *__m2)) - { - ++__first1; - break; - } - } - } -} - #if _LIBCPP_STD_VER > 14 // default searcher diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -217,6 +217,10 @@ header "algorithm" export initializer_list export * + umbrella "__algorithm" + explicit module * { + export * + } } module any { header "any" @@ -307,6 +311,7 @@ } module functional { header "functional" + umbrella "__functional" export * } module future { @@ -346,6 +351,10 @@ module iterator { header "iterator" export * + umbrella "__iterator" + explicit module * { + export * + } } module latch { requires cplusplus14 @@ -415,6 +424,10 @@ export initializer_list export iterator export * + umbrella "__ranges" + explicit module * { + export * + } } module ratio { header "ratio" diff --git a/libcxx/include/regex b/libcxx/include/regex --- a/libcxx/include/regex +++ b/libcxx/include/regex @@ -764,6 +764,7 @@ #include <__config> #include <__debug> +#include <__functional/__search.h> #include <__locale> #include #include diff --git a/libcxx/test/std/containers/sequences/array/compare.fail.cpp b/libcxx/test/std/containers/sequences/array/compare.fail.cpp --- a/libcxx/test/std/containers/sequences/array/compare.fail.cpp +++ b/libcxx/test/std/containers/sequences/array/compare.fail.cpp @@ -50,7 +50,7 @@ typedef NoCompare<0> T; typedef std::array C; C c1 = {{}}; - // expected-error@algorithm:* 2 {{invalid operands to binary expression}} + // expected-error@*:* 2 {{invalid operands to binary expression}} TEST_IGNORE_NODISCARD (c1 == c1); TEST_IGNORE_NODISCARD (c1 < c1); } @@ -58,7 +58,7 @@ typedef NoCompare<1> T; typedef std::array C; C c1 = {{}}; - // expected-error@algorithm:* 2 {{invalid operands to binary expression}} + // expected-error@*:* 2 {{invalid operands to binary expression}} TEST_IGNORE_NODISCARD (c1 != c1); TEST_IGNORE_NODISCARD (c1 > c1); } @@ -66,7 +66,7 @@ typedef NoCompare<2> T; typedef std::array C; C c1 = {{}}; - // expected-error@algorithm:* 2 {{invalid operands to binary expression}} + // expected-error@*:* 2 {{invalid operands to binary expression}} TEST_IGNORE_NODISCARD (c1 == c1); TEST_IGNORE_NODISCARD (c1 < c1); }