183 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// UNSUPPORTED: c++03, c++11, c++14, c++1712 13// template<forward_iterator I, sentinel_for<I> S, class Proj = identity,14// indirect_binary_predicate<projected<I, Proj>,15// projected<I, Proj>> Pred = ranges::equal_to>16// constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});17// template<forward_range R, class Proj = identity,18// indirect_binary_predicate<projected<iterator_t<R>, Proj>,19// projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>20// constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});21 22#include <algorithm>23#include <array>24#include <cassert>25#include <cstddef>26#include <ranges>27 28#include "almost_satisfies_types.h"29#include "test_iterators.h"30 31template <class Iter, class Sent = Iter>32concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); };33 34struct NotComparable {};35 36static_assert(HasAdjacentFindIt<int*>);37static_assert(!HasAdjacentFindIt<ForwardIteratorNotDerivedFrom>);38static_assert(!HasAdjacentFindIt<ForwardIteratorNotIncrementable>);39static_assert(!HasAdjacentFindIt<int*, SentinelForNotSemiregular>);40static_assert(!HasAdjacentFindIt<int*, SentinelForNotWeaklyEqualityComparableWith>);41static_assert(!HasAdjacentFindIt<NotComparable*>);42 43template <class Range>44concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); };45 46static_assert(HasAdjacentFindR<UncheckedRange<int*>>);47static_assert(!HasAdjacentFindR<ForwardRangeNotDerivedFrom>);48static_assert(!HasAdjacentFindR<ForwardRangeNotIncrementable>);49static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelSemiregular>);50static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelEqualityComparableWith>);51static_assert(!HasAdjacentFindR<UncheckedRange<NotComparable>>);52 53template <std::size_t N>54struct Data {55 std::array<int, N> input;56 int expected;57};58 59template <class Iter, class Sent, std::size_t N>60constexpr void test(Data<N> d) {61 {62 std::same_as<Iter> decltype(auto) ret =63 std::ranges::adjacent_find(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));64 assert(base(ret) == d.input.data() + d.expected);65 }66 {67 auto range = std::ranges::subrange(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));68 std::same_as<Iter> decltype(auto) ret = std::ranges::adjacent_find(range);69 assert(base(ret) == d.input.data() + d.expected);70 }71}72 73template <class Iter, class Sent = Iter>74constexpr void test_iterators() {75 // simple test76 test<Iter, Sent, 4>({.input = {1, 2, 2, 4}, .expected = 1});77 // last is returned with no match78 test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .expected = 4});79 // first elements match80 test<Iter, Sent, 4>({.input = {1, 1, 3, 4}, .expected = 0});81 // the first match is returned82 test<Iter, Sent, 7>({.input = {1, 1, 3, 4, 4, 4, 4}, .expected = 0});83 // two element range works84 test<Iter, Sent, 2>({.input = {3, 3}, .expected = 0});85 // single element range works86 test<Iter, Sent, 1>({.input = {1}, .expected = 1});87 // empty range works88 test<Iter, Sent, 0>({.input = {}, .expected = 0});89}90 91constexpr bool test() {92 test_iterators<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();93 test_iterators<forward_iterator<int*>>();94 test_iterators<bidirectional_iterator<int*>>();95 test_iterators<random_access_iterator<int*>>();96 test_iterators<contiguous_iterator<int*>>();97 test_iterators<int*>();98 test_iterators<const int*>();99 100 { // check that ranges::dangling is returned101 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =102 std::ranges::adjacent_find(std::array{1, 2, 3, 4});103 }104 105 { // check that the complexity requirements are met with no match106 {107 int predicateCount = 0;108 auto pred = [&](int, int) { ++predicateCount; return false; };109 auto projectionCount = 0;110 auto proj = [&](int i) { ++projectionCount; return i; };111 int a[] = {1, 2, 3, 4, 5};112 auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);113 assert(ret == a + 5);114 assert(predicateCount == 4);115 assert(projectionCount == 8);116 }117 {118 int predicateCount = 0;119 auto pred = [&](int, int) { ++predicateCount; return false; };120 auto projectionCount = 0;121 auto proj = [&](int i) { ++projectionCount; return i; };122 int a[] = {1, 2, 3, 4, 5};123 auto ret = std::ranges::adjacent_find(a, pred, proj);124 assert(ret == a + 5);125 assert(predicateCount == 4);126 assert(projectionCount == 8);127 }128 }129 130 { // check that the complexity requirements are met with a match131 {132 int predicateCount = 0;133 auto pred = [&](int i, int j) { ++predicateCount; return i == j; };134 auto projectionCount = 0;135 auto proj = [&](int i) { ++projectionCount; return i; };136 int a[] = {1, 2, 4, 4, 5};137 auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);138 assert(ret == a + 2);139 assert(predicateCount == 3);140 assert(projectionCount == 6);141 }142 {143 int predicateCount = 0;144 auto pred = [&](int i, int j) { ++predicateCount; return i == j; };145 auto projectionCount = 0;146 auto proj = [&](int i) { ++projectionCount; return i; };147 int a[] = {1, 2, 4, 4, 5};148 auto ret = std::ranges::adjacent_find(a, pred, proj);149 assert(ret == a + 2);150 assert(predicateCount == 3);151 assert(projectionCount == 6);152 }153 }154 155 { // check that std::invoke is used156 struct S {157 constexpr S(int i_) : i(i_) {}158 constexpr bool compare(const S& j) const { return j.i == i; }159 constexpr const S& identity() const { return *this; }160 int i;161 };162 {163 S a[] = {1, 2, 3, 4};164 auto ret = std::ranges::adjacent_find(std::begin(a), std::end(a), &S::compare, &S::identity);165 assert(ret == a + 4);166 }167 {168 S a[] = {1, 2, 3, 4};169 auto ret = std::ranges::adjacent_find(a, &S::compare, &S::identity);170 assert(ret == a + 4);171 }172 }173 174 return true;175}176 177int main(int, char**) {178 test();179 static_assert(test());180 181 return 0;182}183