237 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<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,14// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>15// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>16// constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,17// Pred pred = {},18// Proj1 proj1 = {}, Proj2 proj2 = {});19// template<input_range R1, forward_range R2,20// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>21// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>22// constexpr borrowed_iterator_t<R1>23// ranges::find_first_of(R1&& r1, R2&& r2,24// Pred pred = {},25// Proj1 proj1 = {}, Proj2 proj2 = {});26 27#include <algorithm>28#include <array>29#include <functional>30#include <ranges>31 32#include "almost_satisfies_types.h"33#include "test_iterators.h"34 35template <class Iter1, class Iter2 = int*, class Sent1 = Iter1, class Sent2 = Iter2>36concept HasFindFirstOfIt = requires(Iter1 iter1, Sent1 sent1, Iter2 iter2, Sent2 sent2) {37 std::ranges::find_first_of(iter1, sent1, iter2, sent2);38 };39 40static_assert(HasFindFirstOfIt<int*>);41static_assert(!HasFindFirstOfIt<InputIteratorNotDerivedFrom>);42static_assert(!HasFindFirstOfIt<InputIteratorNotIndirectlyReadable>);43static_assert(!HasFindFirstOfIt<InputIteratorNotInputOrOutputIterator>);44static_assert(!HasFindFirstOfIt<int*, ForwardIteratorNotDerivedFrom>);45static_assert(!HasFindFirstOfIt<int*, ForwardIteratorNotIncrementable>);46static_assert(!HasFindFirstOfIt<int*, int*, SentinelForNotSemiregular>);47static_assert(!HasFindFirstOfIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);48static_assert(!HasFindFirstOfIt<int*, int*, int*, SentinelForNotSemiregular>);49static_assert(!HasFindFirstOfIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);50static_assert(!HasFindFirstOfIt<int*, int**>); // not indirectly_comparable51 52template <class Range1, class Range2 = UncheckedRange<int*>>53concept HasFindFirstOfR = requires(Range1 range1, Range2 range2) {54 std::ranges::find_first_of(range1, range2);55 };56 57static_assert(HasFindFirstOfR<UncheckedRange<int*>>);58static_assert(!HasFindFirstOfR<InputRangeNotDerivedFrom>);59static_assert(!HasFindFirstOfR<InputRangeNotIndirectlyReadable>);60static_assert(!HasFindFirstOfR<InputRangeNotInputOrOutputIterator>);61static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);62static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);63static_assert(!HasFindFirstOfR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);64static_assert(!HasFindFirstOfR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);65static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);66static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);67static_assert(!HasFindFirstOfR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly_comparable68 69template <int N1, int N2>70struct Data {71 std::array<int, N1> input1;72 std::array<int, N2> input2;73 std::ptrdiff_t expected;74};75 76template <class Iter1, class Sent1, class Iter2, class Sent2, int N1, int N2>77constexpr void test(Data<N1, N2> d) {78 {79 std::same_as<Iter1> decltype(auto) ret =80 std::ranges::find_first_of(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())),81 Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));82 assert(base(ret) == d.input1.data() + d.expected);83 }84 {85 auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())));86 auto range2 = std::ranges::subrange(Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));87 std::same_as<Iter1> decltype(auto) ret = std::ranges::find_first_of(range1, range2);88 assert(base(ret) == d.input1.data() + d.expected);89 }90}91 92template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>93constexpr void test_iterators() {94 // simple test95 test<Iter1, Sent1, Iter2, Sent2, 4, 2>({.input1 = {1, 2, 3, 4}, .input2 = {2, 3}, .expected = 1});96 // other elements from input2 are checked97 test<Iter1, Sent1, Iter2, Sent2, 4, 2>({.input1 = {1, 2, 3, 4}, .input2 = {3, 2}, .expected = 1});98 // an empty second range returns last99 test<Iter1, Sent1, Iter2, Sent2, 4, 0>({.input1 = {1, 2, 3, 4}, .input2 = {}, .expected = 4});100 // check that an empty first range works101 test<Iter1, Sent1, Iter2, Sent2, 0, 1>({.input1 = {}, .input2 = {1}, .expected = 0});102 // check both ranges empty works103 test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = 0});104 // the first element is checked properly105 test<Iter1, Sent1, Iter2, Sent2, 5, 2>({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 5}, .expected = 0});106 // the last element is checked properly107 test<Iter1, Sent1, Iter2, Sent2, 5, 2>({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 6}, .expected = 4});108 // no match, one-past-the-end iterator should be returned109 test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 3, 5, 7}, .input2 = {0, 2, 4, 6}, .expected = 4});110 // input2 contains a single element111 test<Iter1, Sent1, Iter2, Sent2, 4, 1>({.input1 = {1, 3, 5, 7}, .input2 = {1}, .expected = 0});112}113 114template <class Iter1, class Sent1 = Iter1>115constexpr void test_iterators1() {116 test_iterators<Iter1, Sent1, forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();117 test_iterators<Iter1, Sent1, forward_iterator<int*>>();118 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();119 test_iterators<Iter1, Sent1, random_access_iterator<int*>>();120 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();121 test_iterators<Iter1, Sent1, int*>();122}123 124constexpr bool test() {125 test_iterators1<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();126 test_iterators1<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();127 test_iterators1<forward_iterator<int*>>();128 test_iterators1<bidirectional_iterator<int*>>();129 test_iterators1<random_access_iterator<int*>>();130 test_iterators1<contiguous_iterator<int*>>();131 test_iterators1<int*>();132 133 { // check that std::ranges::dangling is returned134 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =135 std::ranges::find_first_of(std::array {1}, std::array {1});136 }137 138 { // check that the predicate is used139 int a[] = {1, 2, 3, 4};140 int b[] = {2};141 {142 auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),143 std::begin(b), std::end(b),144 std::ranges::greater{});145 assert(ret == a + 2);146 }147 {148 auto ret = std::ranges::find_first_of(a, b, std::ranges::greater{});149 assert(ret == a + 2);150 }151 }152 153 { // check that the projections are used154 int a[] = {1, 2, 3, 4};155 int b[] = {4};156 {157 auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),158 std::begin(b), std::end(b), {},159 [](int i) { return i / 2; },160 [](int i) { return i - 3; });161 assert(ret == a + 1);162 }163 {164 auto ret = std::ranges::find_first_of(a, b, {}, [](int i) { return i / 2; }, [](int i) { return i - 3; });165 assert(ret == a + 1);166 }167 }168 169 { // check that std::invoke is used170 struct S1 {171 constexpr S1(int i_) : i(i_) {}172 constexpr bool compare(int j) const { return j == i; }173 constexpr const S1& identity() const { return *this; }174 int i;175 };176 struct S2 {177 constexpr S2(int i_) : i(i_) {}178 int i;179 };180 181 {182 S1 a[] = {1, 2, 3, 4};183 S2 b[] = {2, 3};184 auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),185 std::begin(b), std::end(b), &S1::compare, &S1::identity, &S2::i);186 assert(ret == a + 1);187 }188 {189 S1 a[] = {1, 2, 3, 4};190 S2 b[] = {2, 3};191 auto ret = std::ranges::find_first_of(a, b, &S1::compare, &S1::identity, &S2::i);192 assert(ret == a + 1);193 }194 }195 196 { // check that the complexity requirements are met197 int a[] = {1, 2, 3, 4};198 int b[] = {2, 3};199 {200 int predCount = 0;201 auto predCounter = [&](int, int) { ++predCount; return false; };202 int proj1Count = 0;203 auto proj1Counter = [&](int i) { ++proj1Count; return i; };204 int proj2Count = 0;205 auto proj2Counter = [&](int i) { ++proj2Count; return i; };206 auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),207 std::begin(b), std::end(b), predCounter, proj1Counter, proj2Counter);208 assert(ret == a + 4);209 assert(predCount <= 8);210 assert(proj1Count <= 8);211 assert(proj2Count <= 8);212 }213 {214 int predCount = 0;215 auto predCounter = [&](int, int) { ++predCount; return false; };216 int proj1Count = 0;217 auto proj1Counter = [&](int i) { ++proj1Count; return i; };218 int proj2Count = 0;219 auto proj2Counter = [&](int i) { ++proj2Count; return i; };220 auto ret = std::ranges::find_first_of(a, b, predCounter, proj1Counter, proj2Counter);221 assert(ret == a + 4);222 assert(predCount == 8);223 assert(proj1Count == 8);224 assert(proj2Count == 8);225 }226 }227 228 return true;229}230 231int main(int, char**) {232 test();233 static_assert(test());234 235 return 0;236}237