| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // <algorithm> |
| |
| // UNSUPPORTED: c++03, c++11, c++14, c++17 |
| |
| // template<forward_iterator I, sentinel_for<I> S, class Proj = identity, |
| // indirect_binary_predicate<projected<I, Proj>, |
| // projected<I, Proj>> Pred = ranges::equal_to> |
| // constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); |
| // template<forward_range R, class Proj = identity, |
| // indirect_binary_predicate<projected<iterator_t<R>, Proj>, |
| // projected<iterator_t<R>, Proj>> Pred = ranges::equal_to> |
| // constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); |
| |
| #include <algorithm> |
| #include <array> |
| #include <cassert> |
| #include <cstddef> |
| #include <ranges> |
| |
| #include "almost_satisfies_types.h" |
| #include "boolean_testable.h" |
| #include "test_iterators.h" |
| |
| template <class Iter, class Sent = Iter> |
| concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); }; |
| |
| struct NotComparable {}; |
| |
| static_assert(HasAdjacentFindIt<int*>); |
| static_assert(!HasAdjacentFindIt<ForwardIteratorNotDerivedFrom>); |
| static_assert(!HasAdjacentFindIt<ForwardIteratorNotIncrementable>); |
| static_assert(!HasAdjacentFindIt<int*, SentinelForNotSemiregular>); |
| static_assert(!HasAdjacentFindIt<int*, SentinelForNotWeaklyEqualityComparableWith>); |
| static_assert(!HasAdjacentFindIt<NotComparable*>); |
| |
| template <class Range> |
| concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); }; |
| |
| static_assert(HasAdjacentFindR<UncheckedRange<int*>>); |
| static_assert(!HasAdjacentFindR<ForwardRangeNotDerivedFrom>); |
| static_assert(!HasAdjacentFindR<ForwardRangeNotIncrementable>); |
| static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelSemiregular>); |
| static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelEqualityComparableWith>); |
| static_assert(!HasAdjacentFindR<UncheckedRange<NotComparable>>); |
| |
| template <std::size_t N> |
| struct Data { |
| std::array<int, N> input; |
| int expected; |
| }; |
| |
| template <class Iter, class Sent, std::size_t N> |
| constexpr void test(Data<N> d) { |
| { |
| std::same_as<Iter> decltype(auto) ret = |
| std::ranges::adjacent_find(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size()))); |
| assert(base(ret) == d.input.data() + d.expected); |
| } |
| { |
| auto range = std::ranges::subrange(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size()))); |
| std::same_as<Iter> decltype(auto) ret = std::ranges::adjacent_find(range); |
| assert(base(ret) == d.input.data() + d.expected); |
| } |
| } |
| |
| template <class Iter, class Sent = Iter> |
| constexpr void test_iterators() { |
| // simple test |
| test<Iter, Sent, 4>({.input = {1, 2, 2, 4}, .expected = 1}); |
| // last is returned with no match |
| test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .expected = 4}); |
| // first elements match |
| test<Iter, Sent, 4>({.input = {1, 1, 3, 4}, .expected = 0}); |
| // the first match is returned |
| test<Iter, Sent, 7>({.input = {1, 1, 3, 4, 4, 4, 4}, .expected = 0}); |
| // two element range works |
| test<Iter, Sent, 2>({.input = {3, 3}, .expected = 0}); |
| // single element range works |
| test<Iter, Sent, 1>({.input = {1}, .expected = 1}); |
| // empty range works |
| test<Iter, Sent, 0>({.input = {}, .expected = 0}); |
| } |
| |
| constexpr bool test() { |
| test_iterators<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>(); |
| test_iterators<forward_iterator<int*>>(); |
| test_iterators<bidirectional_iterator<int*>>(); |
| test_iterators<random_access_iterator<int*>>(); |
| test_iterators<contiguous_iterator<int*>>(); |
| test_iterators<int*>(); |
| test_iterators<const int*>(); |
| |
| { // check that ranges::dangling is returned |
| [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret = |
| std::ranges::adjacent_find(std::array{1, 2, 3, 4}); |
| } |
| |
| { // check that the complexity requirements are met with no match |
| { |
| int predicateCount = 0; |
| auto pred = [&](int, int) { ++predicateCount; return false; }; |
| auto projectionCount = 0; |
| auto proj = [&](int i) { ++projectionCount; return i; }; |
| int a[] = {1, 2, 3, 4, 5}; |
| auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj); |
| assert(ret == a + 5); |
| assert(predicateCount == 4); |
| assert(projectionCount == 8); |
| } |
| { |
| int predicateCount = 0; |
| auto pred = [&](int, int) { ++predicateCount; return false; }; |
| auto projectionCount = 0; |
| auto proj = [&](int i) { ++projectionCount; return i; }; |
| int a[] = {1, 2, 3, 4, 5}; |
| auto ret = std::ranges::adjacent_find(a, pred, proj); |
| assert(ret == a + 5); |
| assert(predicateCount == 4); |
| assert(projectionCount == 8); |
| } |
| } |
| |
| { // check that the complexity requirements are met with a match |
| { |
| int predicateCount = 0; |
| auto pred = [&](int i, int j) { ++predicateCount; return i == j; }; |
| auto projectionCount = 0; |
| auto proj = [&](int i) { ++projectionCount; return i; }; |
| int a[] = {1, 2, 4, 4, 5}; |
| auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj); |
| assert(ret == a + 2); |
| assert(predicateCount == 3); |
| assert(projectionCount == 6); |
| } |
| { |
| int predicateCount = 0; |
| auto pred = [&](int i, int j) { ++predicateCount; return i == j; }; |
| auto projectionCount = 0; |
| auto proj = [&](int i) { ++projectionCount; return i; }; |
| int a[] = {1, 2, 4, 4, 5}; |
| auto ret = std::ranges::adjacent_find(a, pred, proj); |
| assert(ret == a + 2); |
| assert(predicateCount == 3); |
| assert(projectionCount == 6); |
| } |
| } |
| |
| { // check that std::invoke is used |
| struct S { |
| constexpr S(int i_) : i(i_) {} |
| constexpr bool compare(const S& j) const { return j.i == i; } |
| constexpr const S& identity() const { return *this; } |
| int i; |
| }; |
| { |
| S a[] = {1, 2, 3, 4}; |
| auto ret = std::ranges::adjacent_find(std::begin(a), std::end(a), &S::compare, &S::identity); |
| assert(ret == a + 4); |
| } |
| { |
| S a[] = {1, 2, 3, 4}; |
| auto ret = std::ranges::adjacent_find(a, &S::compare, &S::identity); |
| assert(ret == a + 4); |
| } |
| } |
| |
| { // check that the implicit conversion to bool works |
| { |
| int a[] = {1, 2, 2, 4}; |
| auto ret = std::ranges::adjacent_find(a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; }); |
| assert(ret == a + 1); |
| } |
| { |
| int a[] = {1, 2, 2, 4}; |
| auto ret = std::ranges::adjacent_find(a, [](int i, int j) { return BooleanTestable{i == j}; }); |
| assert(ret == a + 1); |
| } |
| } |
| |
| return true; |
| } |
| |
| int main(int, char**) { |
| test(); |
| static_assert(test()); |
| |
| return 0; |
| } |