diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -66,6 +66,8 @@ __algorithm/pop_heap.h __algorithm/prev_permutation.h __algorithm/push_heap.h + __algorithm/ranges_count.h + __algorithm/ranges_count_if.h __algorithm/ranges_find.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h diff --git a/libcxx/include/__algorithm/ranges_count.h b/libcxx/include/__algorithm/ranges_count.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_count.h @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// 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_COUNT_H +#define _LIBCPP___ALGORITHM_RANGES_COUNT_H + +#include <__algorithm/ranges_count_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.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 __count { +struct __fn { + template _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](const auto& __e) { return __e == __value; }; + return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + range_difference_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](const auto& __e) { return __e == __value; }; + return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __count + +inline namespace __cpo { + inline constexpr auto count = __count::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_H diff --git a/libcxx/include/__algorithm/ranges_count_if.h b/libcxx/include/__algorithm/ranges_count_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_count_if.h @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// 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_COUNT_IF_H +#define _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +template +_LIBCPP_HIDE_FROM_ABI constexpr +auto __count_if_impl(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) { + iter_difference_t<_Ip> __counter(0); + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + ++__counter; + } + return __counter; +} + +namespace __count_if { +struct __fn { + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + range_difference_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __count_if + +inline namespace __cpo { + inline constexpr auto count_if = __count_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -802,6 +802,8 @@ #include <__algorithm/pop_heap.h> #include <__algorithm/prev_permutation.h> #include <__algorithm/push_heap.h> +#include <__algorithm/ranges_count.h> +#include <__algorithm/ranges_count_if.h> #include <__algorithm/ranges_find.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -294,6 +294,8 @@ module pop_heap { private header "__algorithm/pop_heap.h" } module prev_permutation { private header "__algorithm/prev_permutation.h" } module push_heap { private header "__algorithm/push_heap.h" } + module ranges_count { private header "__algorithm/ranges_count.h" } + module ranges_count_if { private header "__algorithm/ranges_count_if.h" } module ranges_find { private header "__algorithm/ranges_find.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} +#include <__algorithm/ranges_count.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}} +#include <__algorithm/ranges_count_if.h> diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp @@ -0,0 +1,156 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class T, class Proj = identity> +// requires indirect_binary_predicate, const T*> +// constexpr iter_difference_t +// ranges::count(I first, S last, const T& value, Proj proj = {}); +// template +// requires indirect_binary_predicate, Proj>, const T*> +// constexpr range_difference_t +// ranges::count(R&& r, const T& value, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +struct NotEqualityComparable {}; + +template +concept HasFindIt = requires(It it, Sent sent) { std::ranges::count(it, sent, *it); }; +static_assert(HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt); +static_assert(!HasFindIt, SentinelForNotSemiregular>); +static_assert(!HasFindIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasFindIt); +static_assert(!HasFindIt); + +template +concept HasFindR = requires(Range r) { std::ranges::count(r, ValT{}); }; +static_assert(HasFindR, int>); +static_assert(!HasFindR); +static_assert(!HasFindR, NotEqualityComparable>); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); +static_assert(!HasFindR); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::count(It(a), Sent(It(a + 4)), 4); + assert(ret == 1); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::count(range, 4); + assert(ret == 1); + } +} + +constexpr bool test() { + test_iterators(); + test_iterators(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { + // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::count(a, a + 4, a + 3, [](int& i) { return &i; }); + assert(ret == 1); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::count(a, a + 3, [](int& i) { return &i; }); + assert(ret == 1); + } + } + + { // check that 0 is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::count(a, a + 3, 0); + assert(ret == 0); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::count(a, 0); + assert(ret == 0); + } + } + + { + // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::count(a, 4, &S::i); + assert(ret == 0); + } + + { + // count invocations of the projection + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::count(a, a + 4, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == 1); + assert(projection_count == 4); + } + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::count(a, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == 1); + assert(projection_count == 4); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::count(a.begin(), a.end(), 1); + assert(ret == 0); + } + { + std::array a = {}; + auto ret = std::ranges::count(a, 1); + assert(ret == 0); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp @@ -0,0 +1,187 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr iter_difference_t +// ranges::count_if(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr range_difference_t +// ranges::count_if(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +struct Predicate { + bool operator()(int); +}; + +template +concept HasCountIfIt = requires(It it, Sent sent) { std::ranges::count_if(it, sent, Predicate{}); }; +static_assert(HasCountIfIt); +static_assert(!HasCountIfIt); +static_assert(!HasCountIfIt); +static_assert(!HasCountIfIt); +static_assert(!HasCountIfIt, SentinelForNotSemiregular>); +static_assert(!HasCountIfIt, InputRangeNotSentinelEqualityComparableWith>); + +static_assert(!HasCountIfIt); +static_assert(!HasCountIfIt); + +template +concept HasFindIfPred = requires(int* it, Pred pred) {std::ranges::count_if(it, it, pred); }; + +static_assert(!HasFindIfPred); +static_assert(!HasFindIfPred); + +template +concept HasCountIfR = requires(R r) { std::ranges::count_if(r, Predicate{}); }; +static_assert(HasCountIfR>); +static_assert(!HasCountIfR); +static_assert(!HasCountIfR); +static_assert(!HasCountIfR); +static_assert(!HasCountIfR); +static_assert(!HasCountIfR); +static_assert(!HasCountIfR); + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = + std::ranges::count_if(It(a), Sent(It(a + 4)), [](int x) mutable { return x == 4; }); + assert(ret == 1); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = + std::ranges::count_if(range, [](int x) mutable { return x == 4; }); + assert(ret == 1); + } +} + +constexpr bool test() { + test_iterators(); + test_iterators(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { + // check that projections are used properly and that they are called with the iterator directly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::count_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret == 1); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::count_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }); + assert(ret == 1); + } + } + + { + // check that std::invoke is used + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::count_if(a, [](int i){ return i == 0; }, &S::comp); + assert(ret == 3); + } + { + struct S { + int comp; + int other; + }; + S a[] = { {0, 0}, {0, 2}, {0, 1} }; + auto ret = std::ranges::count_if(a, a + 3, [](int i) { return i == 0; }, &S::comp); + assert(ret == 3); + } + } + + { + // check that 0 is returned with no match + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::count_if(a, a + 3, [](int) { return false; }); + assert(ret == 0); + } + { + int a[] = {1, 1, 1}; + auto ret = std::ranges::count_if(a, [](int){ return false; }); + assert(ret == 0); + } + } + + { + // count projection and predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::count_if(a, a + 4, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == 1); + assert(predicate_count == 4); + assert(projection_count == 4); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::count_if(a, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == 1); + assert(predicate_count == 4); + assert(projection_count == 4); + } + } + + { + // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::count_if(a.begin(), a.end(), [](int) { return true; }); + assert(ret == 0); + } + { + std::array a = {}; + auto ret = std::ranges::count_if(a, [](int) { return true; }); + assert(ret == 0); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}