diff options
Diffstat (limited to 'chromium/base/util/ranges')
| -rw-r--r-- | chromium/base/util/ranges/BUILD.gn | 26 | ||||
| -rw-r--r-- | chromium/base/util/ranges/OWNERS | 2 | ||||
| -rw-r--r-- | chromium/base/util/ranges/README.md | 146 | ||||
| -rw-r--r-- | chromium/base/util/ranges/algorithm.h | 1352 | ||||
| -rw-r--r-- | chromium/base/util/ranges/algorithm_unittest.cc | 398 | ||||
| -rw-r--r-- | chromium/base/util/ranges/functional.h | 71 | ||||
| -rw-r--r-- | chromium/base/util/ranges/functional_unittest.cc | 52 | ||||
| -rw-r--r-- | chromium/base/util/ranges/iterator.h | 40 | ||||
| -rw-r--r-- | chromium/base/util/ranges/iterator_unittest.cc | 49 |
9 files changed, 2136 insertions, 0 deletions
diff --git a/chromium/base/util/ranges/BUILD.gn b/chromium/base/util/ranges/BUILD.gn new file mode 100644 index 00000000000..455c47d6877 --- /dev/null +++ b/chromium/base/util/ranges/BUILD.gn @@ -0,0 +1,26 @@ +# Copyright 2020 The Chromium Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. + +source_set("ranges") { + sources = [ + "algorithm.h", + "functional.h", + "iterator.h", + ] +} + +source_set("unittests") { + testonly = true + sources = [ + "algorithm_unittest.cc", + "functional_unittest.cc", + "iterator_unittest.cc", + ] + + deps = [ + ":ranges", + "//testing/gmock", + "//testing/gtest", + ] +} diff --git a/chromium/base/util/ranges/OWNERS b/chromium/base/util/ranges/OWNERS new file mode 100644 index 00000000000..766efe6c4af --- /dev/null +++ b/chromium/base/util/ranges/OWNERS @@ -0,0 +1,2 @@ +jdoerrie@chromium.org +pkasting@chromium.org diff --git a/chromium/base/util/ranges/README.md b/chromium/base/util/ranges/README.md new file mode 100644 index 00000000000..141a734defe --- /dev/null +++ b/chromium/base/util/ranges/README.md @@ -0,0 +1,146 @@ +# `util::ranges` + +This directory aims to implement a C++14 version of the new `std::ranges` +algorithms that were introduced in C++20. These implementations are added to the +`::util::ranges` namespace, and callers can access them by including +[`base/util/ranges/algorithm.h`](https://source.chromium.org/chromium/chromium/src/+/master:base/util/ranges/algorithm.h). + +## Similarities with C++20: + +### Automatically deducing `begin()` and `end()` +As probably one of the most important changes for readability and usability, all +algorithms in `util::ranges` have overloads for ranges of elements, which allow +callers to no longer specify `begin()` and `end()` iterators themselves. + +Before: +```c++ +bool HasEvens(const std::vector<int>& vec) { + return std::any_of(vec.begin(), vec.end(), [](int i) { return i % 2 == 0; }); +} +``` + +After: +```c++ +bool HasEvens(const std::vector<int>& vec) { + return util::ranges::any_of(vec, [](int i) { return i % 2 == 0; }); +} +``` + +Furthermore, these overloads also support binding to temporaries, so that +applying algorithms to return values is easier: + +```c++ +std::vector<int> GetNums(); +``` + +Before: + +```c++ +bool HasEvens() { + std::vector<int> nums = GetNums(); + return std::any_of(nums.begin(), nums.end(), + [](int i) { return i % 2 == 0; }); +} +``` + +After: +```c++ +bool HasEvens() { + return util::ranges::any_of(GetNums(), [](int i) { return i % 2 == 0; }); +} +``` + +### Support for Projections +In addition to supporting automatically deducing the `begin()` and `end()` +iterator for ranges, the `util::ranges::` algorithms also support projections, +that can be applied to arguments prior to passing it to supplied transformations +or predicates. This is especially useful when ordering a collection of classes +by a specific data member of the class. Example: + +Before: +```cpp +std::sort(suggestions->begin(), suggestions->end(), + [](const autofill::Suggestion& a, const autofill::Suggestion& b) { + return a.match < b.match; + }); +``` + +After: +```cpp +util::ranges::sort(*suggestions, /*comp=*/{}, &autofill::Suggestion::match); +``` + +Anything that is callable can be used as a projection. This includes +`FunctionObjects` like function pointers or functors, but also pointers to +member function and pointers to data members, as shown above. When not specified +a projection defaults to `util::ranges::identity`, which simply perfectly +forwards its argument. + +Projections are supported in both range and iterator-pair overloads of the +`util::ranges::` algorithms, for example `util::ranges::all_of` has the +following signatures: + +```cpp +template <typename InputIterator, typename Pred, typename Proj = identity> +bool all_of(InputIterator first, InputIterator last, Pred pred, Proj proj = {}); + +template <typename Range, typename Pred, typename Proj = identity> +bool all_of(Range&& range, Pred pred, Proj proj = {}); +``` + +## Differences from C++20: +To simplify the implementation of the `util::ranges::` algorithms, they dispatch +to the `std::` algorithms found in C++14. This leads to the following list of +differences from C++20. Since most of these differences are differences in the +library and not in the language, they could be addressed in the future by adding +corresponding implementations. + +### Lack of Constraints +Due to the lack of support for concepts in the language, the algorithms in +`util::ranges` do not have the constraints that are present on the algorithms in +`std::ranges`. Instead, they support any type, much like C++14's `std::` +algorithms. In the future this might be addressed by adding corresponding +constraints via SFINAE, should the need arise. + +### Lack of Range Primitives +Due to C++14's lack of `std::ranges` concepts like sentinels and other range +primitives, algorithms taking a `[first, last)` pair rather than a complete +range, do not support different types for `first` and `last`. Since they rely on +C++14's implementation, the type must be the same. This could be addressed in +the future by implementing support for sentinel types ourselves. + +### Lack of `constexpr` +The `util::ranges` algorithms can only be used in a `constexpr` context when +they call underlying `std::` algorithms that are themselves `constexpr`. Before +C++20, only `std::min`, `std::max` and `std::minmax` are annotated +appropriately, so code like `constexpr bool foo = util::ranges::any_of(...);` +will fail because the compiler will not find a `constexpr std::any_of`. This +could be addressed by either upgrading Chromium's STL to C++20, or implementing +`constexpr` versions of some of these algorithms ourselves. + +### Lack of post C++14 algorithms +Since all algorithms in `util::ranges` dispatch to their C++14 equivalent, +`std::` algorithms that are not present in C++14 have no implementation in +`util::ranges`. This list of algorithms includes the following: + +- [`std::for_each_n`](https://en.cppreference.com/w/cpp/algorithm/for_each_n) (added in C++17) +- [`std::sample`](https://en.cppreference.com/w/cpp/algorithm/sample) (added in C++17) +- [`std::clamp`](https://en.cppreference.com/w/cpp/algorithm/clamp) (added in C++17) + +### Return Types +Some of the algorithms in `std::ranges::` have different return types than their +equivalent in `std::`. For example, while `std::for_each` returns the passed-in +`Function`, `std::ranges::for_each` returns a `std::ranges::for_each_result`, +consisting of the `last` iterator and the function. + +In the cases where the return type differs, `util::ranges::` algorithms will +continue to return the old return type. + +### No blocking of ADL +The algorithms defined in `std::ranges` are not found by ADL, and inhibit ADL +when found by [unqualified name lookup][1]. This is done to be able to enforce +the constraints specified by those algorithms and commonly implemented by using +function objects instead of regular functions. Since we don't support +constrained algorithms yet, we don't implement the blocking of ADL either. + +[1]: https://wg21.link/algorithms.requirements#2 diff --git a/chromium/base/util/ranges/algorithm.h b/chromium/base/util/ranges/algorithm.h new file mode 100644 index 00000000000..4f9c1a6e745 --- /dev/null +++ b/chromium/base/util/ranges/algorithm.h @@ -0,0 +1,1352 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef BASE_UTIL_RANGES_ALGORITHM_H_ +#define BASE_UTIL_RANGES_ALGORITHM_H_ + +#include <algorithm> +#include <iterator> +#include <utility> + +#include "base/util/ranges/functional.h" +#include "base/util/ranges/iterator.h" + +namespace util { +namespace ranges { + +namespace internal { + +// Returns a transformed version of the unary predicate `pred` applying `proj` +// to its argument before invoking `pred` on it. +// Ensures that the return type of `invoke(pred, ...)` is convertible to bool. +template <typename Pred, typename Proj> +constexpr auto ProjectedUnaryPredicate(Pred& pred, Proj& proj) noexcept { + return [&pred, &proj](auto&& arg) -> bool { + return invoke(pred, invoke(proj, std::forward<decltype(arg)>(arg))); + }; +} + +// Returns a transformed version of the binary predicate `pred` applying `proj1` +// and `proj2` to its arguments before invoking `pred` on them. +// Ensures that the return type of `invoke(pred, ...)` is convertible to bool. +template <typename Pred, typename Proj1, typename Proj2> +constexpr auto ProjectedBinaryPredicate(Pred& pred, + Proj1& proj1, + Proj2& proj2) noexcept { + return [&pred, &proj1, &proj2](auto&& lhs, auto&& rhs) -> bool { + return invoke(pred, invoke(proj1, std::forward<decltype(lhs)>(lhs)), + invoke(proj2, std::forward<decltype(rhs)>(rhs))); + }; +} + +// This alias is used below to restrict iterator based APIs to types for which +// `iterator_category` is defined. This is required in situations where +// otherwise an undesired overload would be chosen, e.g. copy_if. In spirit this +// is similar to C++20's std::input_or_output_iterator, a concept that each +// iterator should satisfy. +template <typename Iter> +using iterator_category_t = + typename std::iterator_traits<Iter>::iterator_category; + +} // namespace internal + +// [alg.nonmodifying] Non-modifying sequence operations +// Reference: https://wg21.link/alg.nonmodifying + +// [alg.all.of] All of +// Reference: https://wg21.link/alg.all.of + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `false` if `E(i)` is `false` for some iterator `i` in the range +// `[first, last)`, and `true` otherwise. +// +// Complexity: At most `last - first` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr bool all_of(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::all_of(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `false` if `E(i)` is `false` for some iterator `i` in `range`, and +// `true` otherwise. +// +// Complexity: At most `size(range)` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr bool all_of(Range&& range, Pred pred, Proj proj = {}) { + return ranges::all_of(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [alg.any.of] Any of +// Reference: https://wg21.link/alg.any.of + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `true` if `E(i)` is `true` for some iterator `i` in the range +// `[first, last)`, and `false` otherwise. +// +// Complexity: At most `last - first` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr bool any_of(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::any_of(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `true` if `E(i)` is `true` for some iterator `i` in `range`, and +// `false` otherwise. +// +// Complexity: At most `size(range)` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr bool any_of(Range&& range, Pred pred, Proj proj = {}) { + return ranges::any_of(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [alg.none.of] None of +// Reference: https://wg21.link/alg.none.of + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `false` if `E(i)` is `true` for some iterator `i` in the range +// `[first, last)`, and `true` otherwise. +// +// Complexity: At most `last - first` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr bool none_of(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::none_of(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `invoke(pred, invoke(proj, *i))`. +// +// Returns: `false` if `E(i)` is `true` for some iterator `i` in `range`, and +// `true` otherwise. +// +// Complexity: At most `size(range)` applications of the predicate and any +// projection. +// +// Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr bool none_of(Range&& range, Pred pred, Proj proj = {}) { + return ranges::none_of(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [alg.foreach] For each +// Reference: https://wg21.link/alg.foreach + +// Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the +// range `[first, last)`, starting from `first` and proceeding to `last - 1`. +// +// Returns: `f` +// Note: std::ranges::for_each(I first,...) returns a for_each_result, rather +// than an invocable. For simplicitly we match std::for_each's return type +// instead. +// +// Complexity: Applies `f` and `proj` exactly `last - first` times. +// +// Remarks: If `f` returns a result, the result is ignored. +// +// Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(I +template <typename InputIterator, + typename Fun, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto for_each(InputIterator first, + InputIterator last, + Fun f, + Proj proj = {}) { + std::for_each(first, last, [&f, &proj](auto&& arg) { + return invoke(f, invoke(proj, std::forward<decltype(arg)>(arg))); + }); + + return f; +} + +// Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the +// range `range`, starting from `begin(range)` and proceeding to `end(range) - +// 1`. +// +// Returns: `f` +// Note: std::ranges::for_each(R&& r,...) returns a for_each_result, rather +// than an invocable. For simplicitly we match std::for_each's return type +// instead. +// +// Complexity: Applies `f` and `proj` exactly `size(range)` times. +// +// Remarks: If `f` returns a result, the result is ignored. +// +// Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(R +template <typename Range, typename Fun, typename Proj = identity> +constexpr auto for_each(Range&& range, Fun f, Proj proj = {}) { + return ranges::for_each(ranges::begin(range), ranges::end(range), + std::move(f), std::move(proj)); +} + +// [alg.find] Find +// Reference: https://wg21.link/alg.find + +// Let `E(i)` be `bool(invoke(proj, *i) == value)`. +// +// Returns: The first iterator `i` in the range `[first, last)` for which `E(i)` +// is `true`. Returns `last` if no such iterator is found. +// +// Complexity: At most `last - first` applications of the corresponding +// predicate and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find(I +template <typename InputIterator, + typename T, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto find(InputIterator first, + InputIterator last, + const T& value, + Proj proj = {}) { + // Note: In order to be able to apply `proj` to each element in [first, last) + // we are dispatching to std::find_if instead of std::find. + return std::find_if(first, last, [&proj, &value](auto&& lhs) { + return invoke(proj, std::forward<decltype(lhs)>(lhs)) == value; + }); +} + +// Let `E(i)` be `bool(invoke(proj, *i) == value)`. +// +// Returns: The first iterator `i` in `range` for which `E(i)` is `true`. +// Returns `end(range)` if no such iterator is found. +// +// Complexity: At most `size(range)` applications of the corresponding predicate +// and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find(R +template <typename Range, typename T, typename Proj = identity> +constexpr auto find(Range&& range, const T& value, Proj proj = {}) { + return ranges::find(ranges::begin(range), ranges::end(range), value, + std::move(proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`. +// +// Returns: The first iterator `i` in the range `[first, last)` for which `E(i)` +// is `true`. Returns `last` if no such iterator is found. +// +// Complexity: At most `last - first` applications of the corresponding +// predicate and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto find_if(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::find_if(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`. +// +// Returns: The first iterator `i` in `range` for which `E(i)` is `true`. +// Returns `end(range)` if no such iterator is found. +// +// Complexity: At most `size(range)` applications of the corresponding predicate +// and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr auto find_if(Range&& range, Pred pred, Proj proj = {}) { + return ranges::find_if(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`. +// +// Returns: The first iterator `i` in the range `[first, last)` for which `E(i)` +// is `true`. Returns `last` if no such iterator is found. +// +// Complexity: At most `last - first` applications of the corresponding +// predicate and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto find_if_not(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::find_if_not(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`. +// +// Returns: The first iterator `i` in `range` for which `E(i)` is `true`. +// Returns `end(range)` if no such iterator is found. +// +// Complexity: At most `size(range)` applications of the corresponding predicate +// and any projection. +// +// Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr auto find_if_not(Range&& range, Pred pred, Proj proj = {}) { + return ranges::find_if_not(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [alg.find.end] Find end +// Reference: https://wg21.link/alg.find.end + +// Let: +// - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)), +// invoke(proj2, *(first2 + n)))` +// +// - `i` be `last1` if `[first2, last2)` is empty, or if +// `(last2 - first2) > (last1 - first1)` is `true`, or if there is no iterator +// in the range `[first1, last1 - (last2 - first2))` such that for every +// non-negative integer `n < (last2 - first2)`, `E(i,n)` is `true`. Otherwise +// `i` is the last such iterator in `[first1, last1 - (last2 - first2))`. +// +// Returns: `i` +// Note: std::ranges::find_end(I1 first1,...) returns a range, rather than an +// iterator. For simplicitly we match std::find_end's return type instead. +// +// Complexity: +// At most `(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)` +// applications of the corresponding predicate and any projections. +// +// Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr auto find_end(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return std::find_end(first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj1, proj2)); +} + +// Let: +// - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)), +// invoke(proj2, *(first2 + n)))` +// +// - `i` be `end(range1)` if `range2` is empty, or if +// `size(range2) > size(range1)` is `true`, or if there is no iterator in the +// range `[begin(range1), end(range1) - size(range2))` such that for every +// non-negative integer `n < size(range2)`, `E(i,n)` is `true`. Otherwise `i` +// is the last such iterator in `[begin(range1), end(range1) - size(range2))`. +// +// Returns: `i` +// Note: std::ranges::find_end(R1&& r1,...) returns a range, rather than an +// iterator. For simplicitly we match std::find_end's return type instead. +// +// Complexity: At most `size(range2) * (size(range1) - size(range2) + 1)` +// applications of the corresponding predicate and any projections. +// +// Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity> +constexpr auto find_end(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return ranges::find_end(ranges::begin(range1), ranges::end(range1), + ranges::begin(range2), ranges::end(range2), + std::move(pred), std::move(proj1), std::move(proj2)); +} + +// [alg.find.first.of] Find first +// Reference: https://wg21.link/alg.find.first.of + +// Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`. +// +// Effects: Finds an element that matches one of a set of values. +// +// Returns: The first iterator `i` in the range `[first1, last1)` such that for +// some iterator `j` in the range `[first2, last2)` `E(i,j)` holds. Returns +// `last1` if `[first2, last2)` is empty or if no such iterator is found. +// +// Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the +// corresponding predicate and any projections. +// +// Reference: +// https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr auto find_first_of(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return std::find_first_of( + first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj1, proj2)); +} + +// Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`. +// +// Effects: Finds an element that matches one of a set of values. +// +// Returns: The first iterator `i` in `range1` such that for some iterator `j` +// in `range2` `E(i,j)` holds. Returns `end(range1)` if `range2` is empty or if +// no such iterator is found. +// +// Complexity: At most `size(range1) * size(range2)` applications of the +// corresponding predicate and any projections. +// +// Reference: +// https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity> +constexpr auto find_first_of(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return ranges::find_first_of( + ranges::begin(range1), ranges::end(range1), ranges::begin(range2), + ranges::end(range2), std::move(pred), std::move(proj1), std::move(proj2)); +} + +// [alg.adjacent.find] Adjacent find +// Reference: https://wg21.link/alg.adjacent.find + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`. +// +// Returns: The first iterator `i` such that both `i` and `i + 1` are in the +// range `[first, last)` for which `E(i)` holds. Returns `last` if no such +// iterator is found. +// +// Complexity: Exactly `min((i - first) + 1, (last - first) - 1)` applications +// of the corresponding predicate, where `i` is `adjacent_find`'s return value. +// +// Reference: +// https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(I +template <typename ForwardIterator, + typename Pred = ranges::equal_to, + typename Proj = identity, + typename = internal::iterator_category_t<ForwardIterator>> +constexpr auto adjacent_find(ForwardIterator first, + ForwardIterator last, + Pred pred = {}, + Proj proj = {}) { + return std::adjacent_find( + first, last, internal::ProjectedBinaryPredicate(pred, proj, proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`. +// +// Returns: The first iterator `i` such that both `i` and `i + 1` are in the +// range `range` for which `E(i)` holds. Returns `end(range)` if no such +// iterator is found. +// +// Complexity: Exactly `min((i - begin(range)) + 1, size(range) - 1)` +// applications of the corresponding predicate, where `i` is `adjacent_find`'s +// return value. +// +// Reference: +// https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(R +template <typename Range, + typename Pred = ranges::equal_to, + typename Proj = identity> +constexpr auto adjacent_find(Range&& range, Pred pred = {}, Proj proj = {}) { + return ranges::adjacent_find(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [alg.count] Count +// Reference: https://wg21.link/alg.count + +// Let `E(i)` be `invoke(proj, *i) == value`. +// +// Effects: Returns the number of iterators `i` in the range `[first, last)` for +// which `E(i)` holds. +// +// Complexity: Exactly `last - first` applications of the corresponding +// predicate and any projection. +// +// Reference: https://wg21.link/alg.count#:~:text=ranges::count(I +template <typename InputIterator, + typename T, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto count(InputIterator first, + InputIterator last, + const T& value, + Proj proj = {}) { + // Note: In order to be able to apply `proj` to each element in [first, last) + // we are dispatching to std::count_if instead of std::count. + return std::count_if(first, last, [&proj, &value](auto&& lhs) { + return invoke(proj, std::forward<decltype(lhs)>(lhs)) == value; + }); +} + +// Let `E(i)` be `invoke(proj, *i) == value`. +// +// Effects: Returns the number of iterators `i` in `range` for which `E(i)` +// holds. +// +// Complexity: Exactly `size(range)` applications of the corresponding predicate +// and any projection. +// +// Reference: https://wg21.link/alg.count#:~:text=ranges::count(R +template <typename Range, typename T, typename Proj = identity> +constexpr auto count(Range&& range, const T& value, Proj proj = {}) { + return ranges::count(ranges::begin(range), ranges::end(range), value, + std::move(proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`. +// +// Effects: Returns the number of iterators `i` in the range `[first, last)` for +// which `E(i)` holds. +// +// Complexity: Exactly `last - first` applications of the corresponding +// predicate and any projection. +// +// Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(I +template <typename InputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>> +constexpr auto count_if(InputIterator first, + InputIterator last, + Pred pred, + Proj proj = {}) { + return std::count_if(first, last, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`. +// +// Effects: Returns the number of iterators `i` in `range` for which `E(i)` +// holds. +// +// Complexity: Exactly `size(range)` applications of the corresponding predicate +// and any projection. +// +// Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(R +template <typename Range, typename Pred, typename Proj = identity> +constexpr auto count_if(Range&& range, Pred pred, Proj proj = {}) { + return ranges::count_if(ranges::begin(range), ranges::end(range), + std::move(pred), std::move(proj)); +} + +// [mismatch] Mismatch +// Reference: https://wg21.link/mismatch + +// Let `E(n)` be `!invoke(pred, invoke(proj1, *(first1 + n)), +// invoke(proj2, *(first2 + n)))`. +// +// Let `N` be `min(last1 - first1, last2 - first2)`. +// +// Returns: `{ first1 + n, first2 + n }`, where `n` is the smallest integer in +// `[0, N)` such that `E(n)` holds, or `N` if no such integer exists. +// +// Complexity: At most `N` applications of the corresponding predicate and any +// projections. +// +// Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr auto mismatch(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return std::mismatch(first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj1, proj2)); +} + +// Let `E(n)` be `!invoke(pred, invoke(proj1, *(begin(range1) + n)), +// invoke(proj2, *(begin(range2) + n)))`. +// +// Let `N` be `min(size(range1), size(range2))`. +// +// Returns: `{ begin(range1) + n, begin(range2) + n }`, where `n` is the +// smallest integer in `[0, N)` such that `E(n)` holds, or `N` if no such +// integer exists. +// +// Complexity: At most `N` applications of the corresponding predicate and any +// projections. +// +// Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity> +constexpr auto mismatch(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return ranges::mismatch(ranges::begin(range1), ranges::end(range1), + ranges::begin(range2), ranges::end(range2), + std::move(pred), std::move(proj1), std::move(proj2)); +} + +// [alg.equal] Equal +// Reference: https://wg21.link/alg.equal + +// Let `E(i)` be +// `invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))`. +// +// Returns: If `last1 - first1 != last2 - first2`, return `false.` Otherwise +// return `true` if `E(i)` holds for every iterator `i` in the range `[first1, +// last1)`. Otherwise, returns `false`. +// +// Complexity: If the types of `first1`, `last1`, `first2`, and `last2` meet the +// `RandomAccessIterator` requirements and `last1 - first1 != last2 - first2`, +// then no applications of the corresponding predicate and each projection; +// otherwise, at most `min(last1 - first1, last2 - first2)` applications of the +// corresponding predicate and any projections. +// +// Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr bool equal(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return std::equal(first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj1, proj2)); +} + +// Let `E(i)` be +// `invoke(pred, invoke(proj1, *i), +// invoke(proj2, *(begin(range2) + (i - begin(range1)))))`. +// +// Returns: If `size(range1) != size(range2)`, return `false.` Otherwise return +// `true` if `E(i)` holds for every iterator `i` in `range1`. Otherwise, returns +// `false`. +// +// Complexity: If the types of `begin(range1)`, `end(range1)`, `begin(range2)`, +// and `end(range2)` meet the `RandomAccessIterator` requirements and +// `size(range1) != size(range2)`, then no applications of the corresponding +// predicate and each projection; +// otherwise, at most `min(size(range1), size(range2))` applications of the +// corresponding predicate and any projections. +// +// Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity> +constexpr bool equal(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return ranges::equal(ranges::begin(range1), ranges::end(range1), + ranges::begin(range2), ranges::end(range2), + std::move(pred), std::move(proj1), std::move(proj2)); +} + +// [alg.is.permutation] Is permutation +// Reference: https://wg21.link/alg.is.permutation + +// Returns: If `last1 - first1 != last2 - first2`, return `false`. Otherwise +// return `true` if there exists a permutation of the elements in the range +// `[first2, last2)`, bounded by `[pfirst, plast)`, such that +// `ranges::equal(first1, last1, pfirst, plast, pred, proj, proj)` returns +// `true`; otherwise, returns `false`. +// +// Complexity: No applications of the corresponding predicate if +// ForwardIterator1 and ForwardIterator2 meet the requirements of random access +// iterators and `last1 - first1 != last2 - first2`. Otherwise, exactly +// `last1 - first1` applications of the corresponding predicate and projections +// if `ranges::equal(first1, last1, first2, last2, pred, proj, proj)` would +// return true; +// otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`. +// +// Note: While std::ranges::is_permutation supports different projections for +// the first and second range, this is currently not supported due to +// dispatching to std::is_permutation, which demands that `pred` is an +// equivalence relation. +// TODO(https://crbug.com/1071094): Consider supporing different projections in +// the future. +// +// Reference: +// https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr bool is_permutation(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj proj = {}) { + return std::is_permutation( + first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj, proj)); +} + +// Returns: If `size(range1) != size(range2)`, return `false`. Otherwise return +// `true` if there exists a permutation of the elements in `range2`, bounded by +// `[pbegin, pend)`, such that +// `ranges::equal(range1, [pbegin, pend), pred, proj, proj)` returns `true`; +// otherwise, returns `false`. +// +// Complexity: No applications of the corresponding predicate if Range1 and +// Range2 meet the requirements of random access ranges and +// `size(range1) != size(range2)`. Otherwise, exactly `size(range1)` +// applications of the corresponding predicate and projections if +// `ranges::equal(range1, range2, pred, proj, proj)` would return true; +// otherwise, at worst `O(N^2)`, where `N` has the value `size(range1)`. +// +// Note: While std::ranges::is_permutation supports different projections for +// the first and second range, this is currently not supported due to +// dispatching to std::is_permutation, which demands that `pred` is an +// equivalence relation. +// TODO(https://crbug.com/1071094): Consider supporing different projections in +// the future. +// +// Reference: +// https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj = identity> +constexpr bool is_permutation(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj proj = {}) { + return ranges::is_permutation(ranges::begin(range1), ranges::end(range1), + ranges::begin(range2), ranges::end(range2), + std::move(pred), std::move(proj)); +} + +// [alg.search] Search +// Reference: https://wg21.link/alg.search + +// Returns: `i`, where `i` is the first iterator in the range +// `[first1, last1 - (last2 - first2))` such that for every non-negative integer +// `n` less than `last2 - first2` the condition +// `bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))` +// is `true`. +// Returns `last1` if no such iterator exists. +// Note: std::ranges::search(I1 first1,...) returns a range, rather than an +// iterator. For simplicitly we match std::search's return type instead. +// +// Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the +// corresponding predicate and projections. +// +// Reference: https://wg21.link/alg.search#:~:text=ranges::search(I1 +template <typename ForwardIterator1, + typename ForwardIterator2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity, + typename = internal::iterator_category_t<ForwardIterator1>, + typename = internal::iterator_category_t<ForwardIterator2>> +constexpr auto search(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return std::search(first1, last1, first2, last2, + internal::ProjectedBinaryPredicate(pred, proj1, proj2)); +} + +// Returns: `i`, where `i` is the first iterator in the range +// `[begin(range1), end(range1) - size(range2))` such that for every +// non-negative integer `n` less than `size(range2)` the condition +// `bool(invoke(pred, invoke(proj1, *(i + n)), +// invoke(proj2, *(begin(range2) + n))))` is `true`. +// Returns `end(range1)` if no such iterator exists. +// Note: std::ranges::search(R1&& r1,...) returns a range, rather than an +// iterator. For simplicitly we match std::search's return type instead. +// +// Complexity: At most `size(range1) * size(range2)` applications of the +// corresponding predicate and projections. +// +// Reference: https://wg21.link/alg.search#:~:text=ranges::search(R1 +template <typename Range1, + typename Range2, + typename Pred = ranges::equal_to, + typename Proj1 = identity, + typename Proj2 = identity> +constexpr auto search(Range1&& range1, + Range2&& range2, + Pred pred = {}, + Proj1 proj1 = {}, + Proj2 proj2 = {}) { + return ranges::search(ranges::begin(range1), ranges::end(range1), + ranges::begin(range2), ranges::end(range2), + std::move(pred), std::move(proj1), std::move(proj2)); +} + +// Mandates: The type `Size` is convertible to an integral type. +// +// Returns: `i` where `i` is the first iterator in the range +// `[first, last - count)` such that for every non-negative integer `n` less +// than `count`, the following condition holds: +// `invoke(pred, invoke(proj, *(i + n)), value)`. +// Returns `last` if no such iterator is found. +// Note: std::ranges::search_n(I1 first1,...) returns a range, rather than an +// iterator. For simplicitly we match std::search_n's return type instead. +// +// Complexity: At most `last - first` applications of the corresponding +// predicate and projection. +// +// Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(I +template <typename ForwardIterator, + typename Size, + typename T, + typename Pred = ranges::equal_to, + typename Proj = identity, + typename = internal::iterator_category_t<ForwardIterator>> +constexpr auto search_n(ForwardIterator first, + ForwardIterator last, + Size count, + const T& value, + Pred pred = {}, + Proj proj = {}) { + // The second arg is guaranteed to be `value`, so we'll simply apply the + // identity projection. + identity value_proj; + return std::search_n( + first, last, count, value, + internal::ProjectedBinaryPredicate(pred, proj, value_proj)); +} + +// Mandates: The type `Size` is convertible to an integral type. +// +// Returns: `i` where `i` is the first iterator in the range +// `[begin(range), end(range) - count)` such that for every non-negative integer +// `n` less than `count`, the following condition holds: +// `invoke(pred, invoke(proj, *(i + n)), value)`. +// Returns `end(arnge)` if no such iterator is found. +// Note: std::ranges::search_n(R1&& r1,...) returns a range, rather than an +// iterator. For simplicitly we match std::search_n's return type instead. +// +// Complexity: At most `size(range)` applications of the corresponding predicate +// and projection. +// +// Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(R +template <typename Range, + typename Size, + typename T, + typename Pred = ranges::equal_to, + typename Proj = identity> +constexpr auto search_n(Range&& range, + Size count, + const T& value, + Pred pred = {}, + Proj proj = {}) { + return ranges::search_n(ranges::begin(range), ranges::end(range), count, + value, std::move(pred), std::move(proj)); +} + +// [alg.modifying.operations] Mutating sequence operations +// Reference: https://wg21.link/alg.modifying.operations + +// [alg.copy] Copy +// Reference: https://wg21.link/alg.copy + +// Let N be `last - first`. +// +// Preconditions: `result` is not in the range `[first, last)`. +// +// Effects: Copies elements in the range `[first, last)` into the range +// `[result, result + N)` starting from `first` and proceeding to `last`. For +// each non-negative integer `n < N` , performs `*(result + n) = *(first + n)`. +// +// Returns: `result + N` +// +// Complexity: Exactly `N` assignments. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(I +template <typename InputIterator, + typename OutputIterator, + typename = internal::iterator_category_t<InputIterator>, + typename = internal::iterator_category_t<OutputIterator>> +constexpr auto copy(InputIterator first, + InputIterator last, + OutputIterator result) { + return std::copy(first, last, result); +} + +// Let N be `size(range)`. +// +// Preconditions: `result` is not in `range`. +// +// Effects: Copies elements in `range` into the range `[result, result + N)` +// starting from `begin(range)` and proceeding to `end(range)`. For each +// non-negative integer `n < N` , performs +// *(result + n) = *(begin(range) + n)`. +// +// Returns: `result + N` +// +// Complexity: Exactly `N` assignments. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(R +template <typename Range, + typename OutputIterator, + typename = internal::iterator_category_t<OutputIterator>> +constexpr auto copy(Range&& range, OutputIterator result) { + return ranges::copy(ranges::begin(range), ranges::end(range), result); +} + +// Let `N` be `max(0, n)`. +// +// Mandates: The type `Size` is convertible to an integral type. +// +// Effects: For each non-negative integer `i < N`, performs +// `*(result + i) = *(first + i)`. +// +// Returns: `result + N` +// +// Complexity: Exactly `N` assignments. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_n +template <typename InputIterator, + typename Size, + typename OutputIterator, + typename = internal::iterator_category_t<InputIterator>, + typename = internal::iterator_category_t<OutputIterator>> +constexpr auto copy_n(InputIterator first, Size n, OutputIterator result) { + return std::copy_n(first, n, result); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number +// of iterators `i` in the range `[first, last)` for which the condition `E(i)` +// holds. +// +// Preconditions: The ranges `[first, last)` and +// `[result, result + (last - first))` do not overlap. +// +// Effects: Copies all of the elements referred to by the iterator `i` in the +// range `[first, last)` for which `E(i)` is true. +// +// Returns: `result + N` +// +// Complexity: Exactly `last - first` applications of the corresponding +// predicate and any projection. +// +// Remarks: Stable. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(I +template <typename InputIterator, + typename OutputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<InputIterator>, + typename = internal::iterator_category_t<OutputIterator>> +constexpr auto copy_if(InputIterator first, + InputIterator last, + OutputIterator result, + Pred pred, + Proj proj = {}) { + return std::copy_if(first, last, result, + internal::ProjectedUnaryPredicate(pred, proj)); +} + +// Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number +// of iterators `i` in `range` for which the condition `E(i)` holds. +// +// Preconditions: `range` and `[result, result + size(range))` do not overlap. +// +// Effects: Copies all of the elements referred to by the iterator `i` in +// `range` for which `E(i)` is true. +// +// Returns: `result + N` +// +// Complexity: Exactly `size(range)` applications of the corresponding predicate +// and any projection. +// +// Remarks: Stable. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(R +template <typename Range, + typename OutputIterator, + typename Pred, + typename Proj = identity, + typename = internal::iterator_category_t<OutputIterator>> +constexpr auto copy_if(Range&& range, + OutputIterator result, + Pred pred, + Proj proj = {}) { + return ranges::copy_if(ranges::begin(range), ranges::end(range), result, + std::move(pred), std::move(proj)); +} + +// Let `N` be `last - first`. +// +// Preconditions: `result` is not in the range `(first, last]`. +// +// Effects: Copies elements in the range `[first, last)` into the range +// `[result - N, result)` starting from `last - 1` and proceeding to `first`. +// For each positive integer `n ≤ N`, performs `*(result - n) = *(last - n)`. +// +// Returns: `result - N` +// +// Complexity: Exactly `N` assignments. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(I +template <typename BidirectionalIterator1, + typename BidirectionalIterator2, + typename = internal::iterator_category_t<BidirectionalIterator1>, + typename = internal::iterator_category_t<BidirectionalIterator2>> +constexpr auto copy_backward(BidirectionalIterator1 first, + BidirectionalIterator1 last, + BidirectionalIterator2 result) { + return std::copy_backward(first, last, result); +} + +// Let `N` be `size(range)`. +// +// Preconditions: `result` is not in the range `(begin(range), end(range)]`. +// +// Effects: Copies elements in `range` into the range `[result - N, result)` +// starting from `end(range) - 1` and proceeding to `begin(range)`. For each +// positive integer `n ≤ N`, performs `*(result - n) = *(end(range) - n)`. +// +// Returns: `result - N` +// +// Complexity: Exactly `N` assignments. +// +// Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(I +template <typename Range, + typename BidirectionalIterator, + typename = internal::iterator_category_t<BidirectionalIterator>> +constexpr auto copy_backward(Range&& range, BidirectionalIterator result) { + return ranges::copy_backward(ranges::begin(range), ranges::end(range), + result); +} + +// [alg.move] Move +// Reference: https://wg21.link/alg.move + +// TODO(crbug.com/1071094): Implement. + +// [alg.swap] Swap +// Reference: https://wg21.link/alg.swap + +// TODO(crbug.com/1071094): Implement. + +// [alg.transform] Transform +// Reference: https://wg21.link/alg.transform + +// TODO(crbug.com/1071094): Implement. + +// [alg.replace] Replace +// Reference: https://wg21.link/alg.replace + +// TODO(crbug.com/1071094): Implement. + +// [alg.fill] Fill +// Reference: https://wg21.link/alg.fill + +// TODO(crbug.com/1071094): Implement. + +// [alg.generate] Generate +// Reference: https://wg21.link/alg.generate + +// TODO(crbug.com/1071094): Implement. + +// [alg.remove] Remove +// Reference: https://wg21.link/alg.remove + +// TODO(crbug.com/1071094): Implement. + +// [alg.unique] Unique +// Reference: https://wg21.link/alg.unique + +// TODO(crbug.com/1071094): Implement. + +// [alg.reverse] Reverse +// Reference: https://wg21.link/alg.reverse + +// TODO(crbug.com/1071094): Implement. + +// [alg.rotate] Rotate +// Reference: https://wg21.link/alg.rotate + +// TODO(crbug.com/1071094): Implement. + +// [alg.random.shuffle] Shuffle +// Reference: https://wg21.link/alg.random.shuffle + +// TODO(crbug.com/1071094): Implement. + +// [alg.nonmodifying] Sorting and related operations +// Reference: https://wg21.link/alg.sorting + +// [alg.sort] Sorting +// Reference: https://wg21.link/alg.sort + +// [sort] sort +// Reference: https://wg21.link/sort + +// TODO(crbug.com/1071094): Implement. + +// [stable.sort] stable_sort +// Reference: https://wg21.link/stable.sort + +// TODO(crbug.com/1071094): Implement. + +// [partial.sort] partial_sort +// Reference: https://wg21.link/partial.sort + +// TODO(crbug.com/1071094): Implement. + +// [partial.sort.copy] partial_sort_copy +// Reference: https://wg21.link/partial.sort.copy + +// TODO(crbug.com/1071094): Implement. + +// [is.sorted] is_sorted +// Reference: https://wg21.link/is.sorted + +// TODO(crbug.com/1071094): Implement. + +// [alg.nth.element] Nth element +// Reference: https://wg21.link/alg.nth.element + +// TODO(crbug.com/1071094): Implement. + +// [alg.binary.search] Binary search +// Reference: https://wg21.link/alg.binary.search + +// [lower.bound] lower_bound +// Reference: https://wg21.link/lower.bound + +// Preconditions: The elements `e` of `[first, last)` are partitioned with +// respect to the expression `bool(invoke(comp, invoke(proj, e), value))`. +// +// Returns: The furthermost iterator `i` in the range `[first, last]` such that +// for every iterator `j` in the range `[first, i)`, +// `bool(invoke(comp, invoke(proj, *j), value))` is true. +// +// Complexity: At most `log(last - first) + O(1)` comparisons and projections. +// +// Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(I +template <typename ForwardIterator, + typename T, + typename Proj = identity, + typename Comp = ranges::less, + typename = internal::iterator_category_t<ForwardIterator>> +constexpr auto lower_bound(ForwardIterator first, + ForwardIterator last, + const T& value, + Comp comp = {}, + Proj proj = {}) { + // The second arg is guaranteed to be `value`, so we'll simply apply the + // identity projection. + identity value_proj; + return std::lower_bound( + first, last, value, + internal::ProjectedBinaryPredicate(comp, proj, value_proj)); +} + +// Preconditions: The elements `e` of `[first, last)` are partitioned with +// respect to the expression `bool(invoke(comp, invoke(proj, e), value))`. +// +// Returns: The furthermost iterator `i` in the range +// `[begin(range), end(range)]` such that for every iterator `j` in the range +// `[begin(range), i)`, `bool(invoke(comp, invoke(proj, *j), value))` is true. +// +// Complexity: At most `log(size(range)) + O(1)` comparisons and projections. +// +// Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(R +template <typename Range, + typename T, + typename Proj = identity, + typename Comp = ranges::less> +constexpr auto lower_bound(Range&& range, + const T& value, + Comp comp = {}, + Proj proj = {}) { + return ranges::lower_bound(ranges::begin(range), ranges::end(range), value, + std::move(comp), std::move(proj)); +} + +// [upper.bound] upper_bound +// Reference: https://wg21.link/upper.bound + +// TODO(crbug.com/1071094): Implement. + +// [equal.range] equal_range +// Reference: https://wg21.link/equal.range + +// TODO(crbug.com/1071094): Implement. + +// [binary.search] binary_search +// Reference: https://wg21.link/binary.search + +// TODO(crbug.com/1071094): Implement. + +// [alg.partitions] Partitions +// Reference: https://wg21.link/alg.partitions + +// TODO(crbug.com/1071094): Implement. + +// [alg.merge] Merge +// Reference: https://wg21.link/alg.merge + +// TODO(crbug.com/1071094): Implement. + +// [alg.set.operations] Set operations on sorted structures +// Reference: https://wg21.link/alg.set.operations + +// [includes] includes +// Reference: https://wg21.link/includes + +// TODO(crbug.com/1071094): Implement. + +// [set.union] set_union +// Reference: https://wg21.link/set.union + +// TODO(crbug.com/1071094): Implement. + +// [set.intersection] set_intersection +// Reference: https://wg21.link/set.intersection + +// TODO(crbug.com/1071094): Implement. + +// [set.difference] set_difference +// Reference: https://wg21.link/set.difference + +// TODO(crbug.com/1071094): Implement. + +// [set.symmetric.difference] set_symmetric_difference +// Reference: https://wg21.link/set.symmetric.difference + +// TODO(crbug.com/1071094): Implement. + +// [alg.heap.operations] Heap operations +// Reference: https://wg21.link/alg.heap.operations + +// [push.heap] push_heap +// Reference: https://wg21.link/push.heap + +// TODO(crbug.com/1071094): Implement. + +// [pop.heap] pop_heap +// Reference: https://wg21.link/pop.heap + +// TODO(crbug.com/1071094): Implement. + +// [make.heap] make_heap +// Reference: https://wg21.link/make.heap + +// TODO(crbug.com/1071094): Implement. + +// [sort.heap] sort_heap +// Reference: https://wg21.link/sort.heap + +// TODO(crbug.com/1071094): Implement. + +// [is.heap] is_heap +// Reference: https://wg21.link/is.heap + +// TODO(crbug.com/1071094): Implement. + +// [alg.min.max] Minimum and maximum +// Reference: https://wg21.link/alg.min.max + +// TODO(crbug.com/1071094): Implement. + +// [alg.lex.comparison] Lexicographical comparison +// Reference: https://wg21.link/alg.lex.comparison + +// TODO(crbug.com/1071094): Implement. + +// [alg.permutation.generators] Permutation generators +// Reference: https://wg21.link/alg.permutation.generators + +// TODO(crbug.com/1071094): Implement. + +} // namespace ranges + +} // namespace util + +#endif // BASE_UTIL_RANGES_ALGORITHM_H_ diff --git a/chromium/base/util/ranges/algorithm_unittest.cc b/chromium/base/util/ranges/algorithm_unittest.cc new file mode 100644 index 00000000000..8b424a506b9 --- /dev/null +++ b/chromium/base/util/ranges/algorithm_unittest.cc @@ -0,0 +1,398 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "base/util/ranges/algorithm.h" + +#include <algorithm> +#include <utility> + +#include "base/util/ranges/functional.h" +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" + +using ::testing::ElementsAre; +using ::testing::Field; + +namespace util { + +namespace { + +struct Int { + int value = 0; +}; + +} // namespace + +TEST(RangesTest, AllOf) { + auto is_non_zero = [](int i) { return i != 0; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_TRUE(ranges::all_of(array + 1, array + 6, is_non_zero)); + EXPECT_FALSE(ranges::all_of(array, is_non_zero)); + + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_TRUE(ranges::all_of(values + 1, ranges::end(values), is_non_zero, + &Int::value)); + EXPECT_FALSE(ranges::all_of(values, is_non_zero, &Int::value)); +} + +TEST(RangesTest, AnyOf) { + auto is_even = [](int i) { return i % 2 == 0; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_FALSE(ranges::any_of(array + 5, array + 6, is_even)); + EXPECT_TRUE(ranges::any_of(array, is_even)); + + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_FALSE( + ranges::any_of(values + 3, ranges::end(values), is_even, &Int::value)); + EXPECT_TRUE(ranges::any_of(values, is_even, &Int::value)); +} + +TEST(RangesTest, NoneOf) { + auto is_zero = [](int i) { return i == 0; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_TRUE(ranges::none_of(array + 1, array + 6, is_zero)); + EXPECT_FALSE(ranges::none_of(array, is_zero)); + + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_TRUE( + ranges::none_of(values + 1, ranges::end(values), is_zero, &Int::value)); + EXPECT_FALSE(ranges::none_of(values, is_zero, &Int::value)); +} + +TEST(RangesTest, ForEach) { + auto times_two = [](int& i) { i *= 2; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + ranges::for_each(array, array + 3, times_two); + EXPECT_THAT(array, ElementsAre(0, 2, 4, 3, 4, 5)); + + ranges::for_each(array + 3, array + 6, times_two); + EXPECT_THAT(array, ElementsAre(0, 2, 4, 6, 8, 10)); + + EXPECT_EQ(times_two, ranges::for_each(array, times_two)); + EXPECT_THAT(array, ElementsAre(0, 4, 8, 12, 16, 20)); + + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_EQ(times_two, ranges::for_each(values, times_two, &Int::value)); + EXPECT_THAT(values, + ElementsAre(Field(&Int::value, 0), Field(&Int::value, 4), + Field(&Int::value, 8), Field(&Int::value, 10))); +} + +TEST(RangesTest, Find) { + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_EQ(array + 6, ranges::find(array + 1, array + 6, 0)); + EXPECT_EQ(array, ranges::find(array, 0)); + + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_EQ(values, ranges::find(values, values, 0, &Int::value)); + EXPECT_EQ(ranges::end(values), ranges::find(values, 3, &Int::value)); +} + +TEST(RangesTest, FindIf) { + auto is_at_least_5 = [](int i) { return i >= 5; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_EQ(array + 5, ranges::find_if(array, array + 5, is_at_least_5)); + EXPECT_EQ(array + 5, ranges::find_if(array, is_at_least_5)); + + auto is_odd = [](int i) { return i % 2 == 1; }; + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_EQ(values + 3, + ranges::find_if(values, values + 3, is_odd, &Int::value)); + EXPECT_EQ(values + 3, ranges::find_if(values, is_odd, &Int::value)); +} + +TEST(RangesTest, FindIfNot) { + auto is_less_than_5 = [](int i) { return i < 5; }; + int array[] = {0, 1, 2, 3, 4, 5}; + + EXPECT_EQ(array + 5, ranges::find_if_not(array, array + 5, is_less_than_5)); + EXPECT_EQ(array + 5, ranges::find_if_not(array, is_less_than_5)); + + auto is_even = [](int i) { return i % 2 == 0; }; + Int values[] = {{0}, {2}, {4}, {5}}; + EXPECT_EQ(values + 3, + ranges::find_if_not(values, values + 3, is_even, &Int::value)); + EXPECT_EQ(values + 3, ranges::find_if_not(values, is_even, &Int::value)); +} + +TEST(RangesTest, FindEnd) { + int array1[] = {0, 1, 2}; + int array2[] = {4, 5, 6}; + int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, + 0, 1, 2, 3, 0, 1, 2, 0, 1, 0}; + + EXPECT_EQ(array3 + 15, ranges::find_end(array3, ranges::end(array3), array1, + ranges::end(array1))); + EXPECT_EQ(ranges::end(array3), ranges::find_end(array3, ranges::end(array3), + array2, ranges::end(array2))); + EXPECT_EQ(array3 + 4, + ranges::find_end(array3, ranges::end(array3), array2, array2 + 2)); + + Int ints1[] = {{0}, {1}, {2}}; + Int ints2[] = {{4}, {5}, {6}}; + + EXPECT_EQ(array3 + 15, ranges::find_end(array3, ints1, ranges::equal_to{}, + identity{}, &Int::value)); + EXPECT_EQ(ranges::end(array3), + ranges::find_end(array3, ints2, ranges::equal_to{}, identity{}, + &Int::value)); +} + +TEST(RangesTest, FindFirstOf) { + int array1[] = {1, 2, 3}; + int array2[] = {7, 8, 9}; + int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3}; + + EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ranges::end(array3), + array1, ranges::end(array1))); + EXPECT_EQ(ranges::end(array3), + ranges::find_first_of(array3, ranges::end(array3), array2, + ranges::end(array2))); + Int ints1[] = {{1}, {2}, {3}}; + Int ints2[] = {{7}, {8}, {9}}; + + EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ints1, ranges::equal_to{}, + identity{}, &Int::value)); + EXPECT_EQ(ranges::end(array3), + ranges::find_first_of(array3, ints2, ranges::equal_to{}, identity{}, + &Int::value)); +} + +TEST(RangesTest, AdjacentFind) { + int array[] = {1, 2, 3, 3}; + EXPECT_EQ(array + 2, ranges::adjacent_find(array, ranges::end(array))); + EXPECT_EQ(array, + ranges::adjacent_find(array, ranges::end(array), ranges::less{})); + + Int ints[] = {{6}, {6}, {5}, {4}}; + EXPECT_EQ(ints, ranges::adjacent_find(ints, ranges::equal_to{}, &Int::value)); + EXPECT_EQ(ranges::end(ints), + ranges::adjacent_find(ints, ranges::less{}, &Int::value)); +} + +TEST(RangesTest, Count) { + int array[] = {1, 2, 3, 3}; + EXPECT_EQ(1, ranges::count(array, array + 4, 1)); + EXPECT_EQ(1, ranges::count(array, array + 4, 2)); + EXPECT_EQ(1, ranges::count(array, array + 3, 3)); + EXPECT_EQ(2, ranges::count(array, array + 4, 3)); + + Int ints[] = {{1}, {2}, {3}, {3}}; + EXPECT_EQ(1, ranges::count(ints, 1, &Int::value)); + EXPECT_EQ(1, ranges::count(ints, 2, &Int::value)); + EXPECT_EQ(2, ranges::count(ints, 3, &Int::value)); +} + +TEST(RangesTest, CountIf) { + auto is_even = [](int i) { return i % 2 == 0; }; + int array[] = {1, 2, 3, 3}; + EXPECT_EQ(0, ranges::count_if(array, array + 1, is_even)); + EXPECT_EQ(1, ranges::count_if(array, array + 2, is_even)); + EXPECT_EQ(1, ranges::count_if(array, array + 3, is_even)); + EXPECT_EQ(1, ranges::count_if(array, array + 4, is_even)); + + auto is_odd = [](int i) { return i % 2 == 1; }; + Int ints[] = {{1}, {2}, {3}, {3}}; + EXPECT_EQ(1, ranges::count_if(ints, is_even, &Int::value)); + EXPECT_EQ(3, ranges::count_if(ints, is_odd, &Int::value)); +} + +TEST(RangesTest, Mismatch) { + int array1[] = {1, 3, 6, 7}; + int array2[] = {1, 3}; + int array3[] = {1, 3, 5, 7}; + EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2), + ranges::mismatch(array1, array1 + 4, array2, array2 + 2)); + EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2), + ranges::mismatch(array1, array1 + 4, array3, array3 + 4)); + + EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2), + ranges::mismatch(array1, array2)); + EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2), + ranges::mismatch(array1, array3)); +} + +TEST(RangesTest, Equal) { + int array1[] = {1, 3, 6, 7}; + int array2[] = {1, 3, 5, 7}; + EXPECT_TRUE(ranges::equal(array1, array1 + 2, array2, array2 + 2)); + EXPECT_FALSE(ranges::equal(array1, array1 + 4, array2, array2 + 4)); + EXPECT_FALSE(ranges::equal(array1, array1 + 2, array2, array2 + 3)); + + Int ints[] = {{1}, {3}, {5}, {7}}; + EXPECT_TRUE(ranges::equal(ints, array2, + [](Int lhs, int rhs) { return lhs.value == rhs; })); + EXPECT_TRUE( + ranges::equal(array2, ints, ranges::equal_to{}, identity{}, &Int::value)); +} + +TEST(RangesTest, IsPermutation) { + int array1[] = {1, 3, 6, 7}; + int array2[] = {7, 3, 1, 6}; + int array3[] = {1, 3, 5, 7}; + + EXPECT_TRUE(ranges::is_permutation(array1, array1 + 4, array2, array2 + 4)); + EXPECT_FALSE(ranges::is_permutation(array1, array1 + 4, array3, array3 + 4)); + + EXPECT_TRUE(ranges::is_permutation(array1, array2)); + EXPECT_FALSE(ranges::is_permutation(array1, array3)); + + Int ints1[] = {{1}, {3}, {5}, {7}}; + Int ints2[] = {{1}, {5}, {3}, {7}}; + EXPECT_TRUE(ranges::is_permutation( + ints1, ints2, [](Int lhs, Int rhs) { return lhs.value == rhs.value; })); + + EXPECT_TRUE( + ranges::is_permutation(ints1, ints2, ranges::equal_to{}, &Int::value)); +} + +TEST(RangesTest, Search) { + int array1[] = {0, 1, 2, 3}; + int array2[] = {0, 1, 5, 3}; + int array3[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + + EXPECT_EQ(array3 + 3, + ranges::search(array3, array3 + 12, array1, array1 + 4)); + EXPECT_EQ(array3 + 12, + ranges::search(array3, array3 + 12, array2, array2 + 4)); + + EXPECT_EQ(array3 + 3, ranges::search(array3, array1)); + EXPECT_EQ(array3 + 12, ranges::search(array3, array2)); + + Int ints1[] = {{0}, {1}, {2}, {3}}; + Int ints2[] = {{0}, {1}, {5}, {3}}; + + EXPECT_EQ(ints1 + 4, ranges::search(ints1, ints2, ranges::equal_to{}, + &Int::value, &Int::value)); + + EXPECT_EQ(array3 + 3, ranges::search(array3, ints1, {}, {}, &Int::value)); + EXPECT_EQ(array3 + 12, ranges::search(array3, ints2, {}, {}, &Int::value)); +} + +TEST(RangesTest, SearchN) { + int array[] = {0, 0, 1, 1, 2, 2}; + + EXPECT_EQ(array, ranges::search_n(array, array + 6, 1, 0)); + EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 1, 1)); + EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 1, 2)); + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 1, 3)); + + EXPECT_EQ(array, ranges::search_n(array, array + 6, 2, 0)); + EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 2, 1)); + EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 2, 2)); + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 2, 3)); + + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 0)); + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 1)); + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 2)); + EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 3)); + + Int ints[] = {{0}, {0}, {1}, {1}, {2}, {2}}; + EXPECT_EQ(ints, ranges::search_n(ints, 1, 0, {}, &Int::value)); + EXPECT_EQ(ints + 2, ranges::search_n(ints, 1, 1, {}, &Int::value)); + EXPECT_EQ(ints + 4, ranges::search_n(ints, 1, 2, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::search_n(ints, 1, 3, {}, &Int::value)); + + EXPECT_EQ(ints, ranges::search_n(ints, 2, 0, {}, &Int::value)); + EXPECT_EQ(ints + 2, ranges::search_n(ints, 2, 1, {}, &Int::value)); + EXPECT_EQ(ints + 4, ranges::search_n(ints, 2, 2, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::search_n(ints, 2, 3, {}, &Int::value)); + + EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 0, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 1, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 2, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 3, {}, &Int::value)); +} + +TEST(RangesTest, Copy) { + int input[] = {1, 2, 3, 4, 5}; + int output[] = {6, 6, 6, 6, 6, 6, 6}; + auto equals_six = [](int i) { return i == 6; }; + + EXPECT_EQ(output + 3, ranges::copy(input, input + 3, output)); + EXPECT_TRUE(std::equal(input, input + 3, output, output + 3)); + EXPECT_TRUE(std::all_of(output + 3, output + 7, equals_six)); + + EXPECT_EQ(output + 5, ranges::copy(input, output)); + EXPECT_TRUE(std::equal(input, input + 5, output, output + 5)); + EXPECT_TRUE(std::all_of(output + 5, output + 7, equals_six)); +} + +TEST(RangesTest, CopyN) { + int input[] = {1, 2, 3, 4, 5}; + int output[] = {6, 6, 6, 6, 6, 6, 6}; + auto equals_six = [](int i) { return i == 6; }; + + EXPECT_EQ(output + 4, ranges::copy_n(input, 4, output)); + EXPECT_TRUE(std::equal(input, input + 4, output, output + 4)); + EXPECT_TRUE(std::all_of(output + 4, output + 7, equals_six)); +} + +TEST(RangesTest, CopyIf) { + int input[] = {2, 4, 6, 8, 6}; + int output[] = {0, 0, 0, 0, 0, 0}; + auto equals_six = [](int i) { return i == 6; }; + auto equals_zero = [](int i) { return i == 0; }; + + EXPECT_EQ(output + 1, ranges::copy_if(input, input + 4, output, equals_six)); + EXPECT_TRUE(std::all_of(output, output + 1, equals_six)); + EXPECT_TRUE(std::all_of(output + 1, output + 6, equals_zero)); + + Int ints_in[] = {{2}, {4}, {6}, {8}, {6}}; + Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}}; + EXPECT_EQ(ints_out + 2, + ranges::copy_if(ints_in, ints_out, equals_six, &Int::value)); + + EXPECT_TRUE(ranges::all_of(ints_out, ints_out + 2, equals_six, &Int::value)); + EXPECT_TRUE( + ranges::all_of(ints_out + 2, ints_out + 6, equals_zero, &Int::value)); +} + +TEST(RangesTest, CopyBackward) { + int input[] = {2, 4, 6, 8, 6}; + int output[] = {0, 0, 0, 0, 0, 0}; + + EXPECT_EQ(output + 1, ranges::copy_backward(input, input + 5, output + 6)); + EXPECT_THAT(output, ElementsAre(0, 2, 4, 6, 8, 6)); + + Int ints_in[] = {{2}, {4}, {6}, {8}, {6}}; + Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}}; + + EXPECT_EQ(ints_out, ranges::copy_backward(ints_in, ints_out + 5)); + EXPECT_TRUE(std::equal(ints_in, ints_in + 5, ints_out, ints_out + 5, + [](Int i, Int j) { return i.value == j.value; })); +} + +TEST(RangesTest, LowerBound) { + int array[] = {0, 0, 1, 1, 2, 2}; + + EXPECT_EQ(array, ranges::lower_bound(array, array + 6, -1)); + EXPECT_EQ(array, ranges::lower_bound(array, array + 6, 0)); + EXPECT_EQ(array + 2, ranges::lower_bound(array, array + 6, 1)); + EXPECT_EQ(array + 4, ranges::lower_bound(array, array + 6, 2)); + EXPECT_EQ(array + 6, ranges::lower_bound(array, array + 6, 3)); + + Int ints[] = {{0}, {0}, {1}, {1}, {2}, {2}}; + + EXPECT_EQ(ints, ranges::lower_bound(ints, -1, {}, &Int::value)); + EXPECT_EQ(ints, ranges::lower_bound(ints, 0, {}, &Int::value)); + EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, {}, &Int::value)); + EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 2, {}, &Int::value)); + EXPECT_EQ(ints + 6, ranges::lower_bound(ints, 3, {}, &Int::value)); + + const auto proj = [](const auto& i) { return 2 - i.value; }; + EXPECT_EQ(ints, ranges::lower_bound(ints, 3, ranges::greater{}, proj)); + EXPECT_EQ(ints, ranges::lower_bound(ints, 2, ranges::greater{}, proj)); + EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, ranges::greater{}, proj)); + EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 0, ranges::greater{}, proj)); + EXPECT_EQ(ints + 6, ranges::lower_bound(ints, -1, ranges::greater{}, proj)); +} + +} // namespace util diff --git a/chromium/base/util/ranges/functional.h b/chromium/base/util/ranges/functional.h new file mode 100644 index 00000000000..9d31a71a891 --- /dev/null +++ b/chromium/base/util/ranges/functional.h @@ -0,0 +1,71 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef BASE_UTIL_RANGES_FUNCTIONAL_H_ +#define BASE_UTIL_RANGES_FUNCTIONAL_H_ + +#include <functional> +#include <type_traits> +#include <utility> + +namespace util { + +// Implementation of C++20's std::identity. +// +// Reference: +// - https://en.cppreference.com/w/cpp/utility/functional/identity +// - https://wg21.link/func.identity +struct identity { + template <typename T> + constexpr T&& operator()(T&& t) const noexcept { + return std::forward<T>(t); + } + + using is_transparent = void; +}; + +// Minimal implementation of C++17's std::invoke. Based on implementation +// referenced in original std::invoke proposal. +// +// Note: Unlike C++20's std::invoke this implementation is not constexpr. A +// constexpr version can be added in the future, but it won't be as concise, +// since std::mem_fn is not constexpr prior to C++20. +// +// References: +// - https://wg21.link/n4169#implementability +// - https://en.cppreference.com/w/cpp/utility/functional/invoke +// - https://wg21.link/func.invoke +template <typename Functor, + typename... Args, + std::enable_if_t< + std::is_member_pointer<std::decay_t<Functor>>::value>* = nullptr> +decltype(auto) invoke(Functor&& f, Args&&... args) { + return std::mem_fn(f)(std::forward<Args>(args)...); +} + +template <typename Functor, + typename... Args, + std::enable_if_t< + !std::is_member_pointer<std::decay_t<Functor>>::value>* = nullptr> +decltype(auto) invoke(Functor&& f, Args&&... args) { + return std::forward<Functor>(f)(std::forward<Args>(args)...); +} + +// Simplified implementations of C++20's std::ranges comparison function +// objects. As opposed to the std::ranges implementation, these versions do not +// constrain the passed-in types. +// +// Reference: https://wg21.link/range.cmp +namespace ranges { +using equal_to = std::equal_to<>; +using not_equal_to = std::not_equal_to<>; +using greater = std::greater<>; +using less = std::less<>; +using greater_equal = std::greater_equal<>; +using less_equal = std::less_equal<>; +} // namespace ranges + +} // namespace util + +#endif // BASE_UTIL_RANGES_FUNCTIONAL_H_ diff --git a/chromium/base/util/ranges/functional_unittest.cc b/chromium/base/util/ranges/functional_unittest.cc new file mode 100644 index 00000000000..c3fe5487aa7 --- /dev/null +++ b/chromium/base/util/ranges/functional_unittest.cc @@ -0,0 +1,52 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "base/util/ranges/functional.h" + +#include <vector> + +#include "testing/gtest/include/gtest/gtest.h" + +namespace util { + +TEST(RangesTest, Identity) { + static constexpr identity id; + + std::vector<int> v; + EXPECT_EQ(&v, &id(v)); + + constexpr int arr = {0}; + static_assert(arr == id(arr), ""); +} + +TEST(RangesTest, Invoke) { + struct S { + int data_member = 123; + + int member_function() { return 42; } + }; + + S s; + EXPECT_EQ(123, invoke(&S::data_member, s)); + EXPECT_EQ(42, invoke(&S::member_function, s)); + + auto add_functor = [](int i, int j) { return i + j; }; + EXPECT_EQ(3, invoke(add_functor, 1, 2)); +} + +TEST(RangesTest, EqualTo) { + ranges::equal_to eq; + EXPECT_TRUE(eq(0, 0)); + EXPECT_FALSE(eq(0, 1)); + EXPECT_FALSE(eq(1, 0)); +} + +TEST(RangesTest, Less) { + ranges::less lt; + EXPECT_FALSE(lt(0, 0)); + EXPECT_TRUE(lt(0, 1)); + EXPECT_FALSE(lt(1, 0)); +} + +} // namespace util diff --git a/chromium/base/util/ranges/iterator.h b/chromium/base/util/ranges/iterator.h new file mode 100644 index 00000000000..daaedbc285b --- /dev/null +++ b/chromium/base/util/ranges/iterator.h @@ -0,0 +1,40 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef BASE_UTIL_RANGES_ITERATOR_H_ +#define BASE_UTIL_RANGES_ITERATOR_H_ + +#include <iterator> + +namespace util { +namespace ranges { + +// Simplified implementation of C++20's std::ranges::begin. +// As opposed to std::ranges::begin, this implementation does not prefer a +// member begin() over a free standing begin(), does not check whether begin() +// returns an iterator, does not inhibit ADL and is not constexpr. +// +// Reference: https://wg21.link/range.access.begin +template <typename Range> +decltype(auto) begin(Range&& range) { + using std::begin; + return begin(std::forward<Range>(range)); +} + +// Simplified implementation of C++20's std::ranges::end. +// As opposed to std::ranges::end, this implementation does not prefer a +// member end() over a free standing end(), does not check whether end() +// returns an iterator, does not inhibit ADL and is not constexpr. +// +// Reference: - https://wg21.link/range.access.end +template <typename Range> +decltype(auto) end(Range&& range) { + using std::end; + return end(std::forward<Range>(range)); +} + +} // namespace ranges +} // namespace util + +#endif // BASE_UTIL_RANGES_ITERATOR_H_ diff --git a/chromium/base/util/ranges/iterator_unittest.cc b/chromium/base/util/ranges/iterator_unittest.cc new file mode 100644 index 00000000000..d20391720cc --- /dev/null +++ b/chromium/base/util/ranges/iterator_unittest.cc @@ -0,0 +1,49 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "base/util/ranges/iterator.h" + +#include <vector> + +#include "testing/gtest/include/gtest/gtest.h" + +namespace util { + +namespace { + +struct S { + std::vector<int> v; +}; + +auto begin(const S& s) { + return s.v.begin(); +} + +auto end(const S& s) { + return s.v.end(); +} + +} // namespace + +TEST(RangesTest, Begin) { + std::vector<int> vec; + int arr[1]{}; + S s; + + EXPECT_EQ(vec.begin(), ranges::begin(vec)); + EXPECT_EQ(arr, ranges::begin(arr)); + EXPECT_EQ(s.v.begin(), ranges::begin(s)); +} + +TEST(RangesTest, End) { + std::vector<int> vec; + int arr[1]{}; + S s; + + EXPECT_EQ(vec.end(), ranges::end(vec)); + EXPECT_EQ(arr + 1, ranges::end(arr)); + EXPECT_EQ(s.v.end(), ranges::end(s)); +} + +} // namespace util |