libcxx/test/std/algorithms/alg.nonmodifying/alg.adjacent.find/ranges.adjacent_find.pass.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // <algorithm>
  10
  11 // UNSUPPORTED: c++03, c++11, c++14, c++17
  12
  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 "boolean_testable.h"
  30 #include "test_iterators.h"
  31
  32 template <class Iter, class Sent = Iter>
  33 concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); };
  34
  35 struct NotComparable {};
  36
  37 static_assert(HasAdjacentFindIt<int*>);
  38 static_assert(!HasAdjacentFindIt<ForwardIteratorNotDerivedFrom>);
  39 static_assert(!HasAdjacentFindIt<ForwardIteratorNotIncrementable>);
  40 static_assert(!HasAdjacentFindIt<int*, SentinelForNotSemiregular>);
  41 static_assert(!HasAdjacentFindIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  42 static_assert(!HasAdjacentFindIt<NotComparable*>);
  43
  44 template <class Range>
  45 concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); };
  46
  47 static_assert(HasAdjacentFindR<UncheckedRange<int*>>);
  48 static_assert(!HasAdjacentFindR<ForwardRangeNotDerivedFrom>);
  49 static_assert(!HasAdjacentFindR<ForwardRangeNotIncrementable>);
  50 static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelSemiregular>);
  51 static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelEqualityComparableWith>);
  52 static_assert(!HasAdjacentFindR<UncheckedRange<NotComparable>>);
  53
  54 template <std::size_t N>
  55 struct Data {
  56   std::array<int, N> input;
  57   int expected;
  58 };
  59
  60 template <class Iter, class Sent, std::size_t N>
  61 constexpr void test(Data<N> d) {
  62   {
  63     std::same_as<Iter> decltype(auto) ret =
  64         std::ranges::adjacent_find(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));
  65     assert(base(ret) == d.input.data() + d.expected);
  66   }
  67   {
  68     auto range = std::ranges::subrange(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));
  69     std::same_as<Iter> decltype(auto) ret = std::ranges::adjacent_find(range);
  70     assert(base(ret) == d.input.data() + d.expected);
  71   }
  72 }
  73
  74 template <class Iter, class Sent = Iter>
  75 constexpr void test_iterators() {
  76   // simple test
  77   test<Iter, Sent, 4>({.input = {1, 2, 2, 4}, .expected = 1});
  78   // last is returned with no match
  79   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .expected = 4});
  80   // first elements match
  81   test<Iter, Sent, 4>({.input = {1, 1, 3, 4}, .expected = 0});
  82   // the first match is returned
  83   test<Iter, Sent, 7>({.input = {1, 1, 3, 4, 4, 4, 4}, .expected = 0});
  84   // two element range works
  85   test<Iter, Sent, 2>({.input = {3, 3}, .expected = 0});
  86   // single element range works
  87   test<Iter, Sent, 1>({.input = {1}, .expected = 1});
  88   // empty range works
  89   test<Iter, Sent, 0>({.input = {}, .expected = 0});
  90 }
  91
  92 constexpr bool test() {
  93   test_iterators<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
  94   test_iterators<forward_iterator<int*>>();
  95   test_iterators<bidirectional_iterator<int*>>();
  96   test_iterators<random_access_iterator<int*>>();
  97   test_iterators<contiguous_iterator<int*>>();
  98   test_iterators<int*>();
  99   test_iterators<const int*>();
 100
 101   { // check that ranges::dangling is returned
 102     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
 103         std::ranges::adjacent_find(std::array{1, 2, 3, 4});
 104   }
 105
 106   { // check that the complexity requirements are met with no match
 107     {
 108       int predicateCount = 0;
 109       auto pred = [&](int, int) { ++predicateCount; return false; };
 110       auto projectionCount = 0;
 111       auto proj = [&](int i) { ++projectionCount; return i; };
 112       int a[] = {1, 2, 3, 4, 5};
 113       auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);
 114       assert(ret == a + 5);
 115       assert(predicateCount == 4);
 116       assert(projectionCount == 8);
 117     }
 118     {
 119       int predicateCount = 0;
 120       auto pred = [&](int, int) { ++predicateCount; return false; };
 121       auto projectionCount = 0;
 122       auto proj = [&](int i) { ++projectionCount; return i; };
 123       int a[] = {1, 2, 3, 4, 5};
 124       auto ret = std::ranges::adjacent_find(a, pred, proj);
 125       assert(ret == a + 5);
 126       assert(predicateCount == 4);
 127       assert(projectionCount == 8);
 128     }
 129   }
 130
 131   { // check that the complexity requirements are met with a match
 132     {
 133       int predicateCount = 0;
 134       auto pred = [&](int i, int j) { ++predicateCount; return i == j; };
 135       auto projectionCount = 0;
 136       auto proj = [&](int i) { ++projectionCount; return i; };
 137       int a[] = {1, 2, 4, 4, 5};
 138       auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);
 139       assert(ret == a + 2);
 140       assert(predicateCount == 3);
 141       assert(projectionCount == 6);
 142     }
 143     {
 144       int predicateCount = 0;
 145       auto pred = [&](int i, int j) { ++predicateCount; return i == j; };
 146       auto projectionCount = 0;
 147       auto proj = [&](int i) { ++projectionCount; return i; };
 148       int a[] = {1, 2, 4, 4, 5};
 149       auto ret = std::ranges::adjacent_find(a, pred, proj);
 150       assert(ret == a + 2);
 151       assert(predicateCount == 3);
 152       assert(projectionCount == 6);
 153     }
 154   }
 155
 156   { // check that std::invoke is used
 157     struct S {
 158       constexpr S(int i_) : i(i_) {}
 159       constexpr bool compare(const S& j) const { return j.i == i; }
 160       constexpr const S& identity() const { return *this; }
 161       int i;
 162     };
 163     {
 164       S a[] = {1, 2, 3, 4};
 165       auto ret = std::ranges::adjacent_find(std::begin(a), std::end(a), &S::compare, &S::identity);
 166       assert(ret == a + 4);
 167     }
 168     {
 169       S a[] = {1, 2, 3, 4};
 170       auto ret = std::ranges::adjacent_find(a, &S::compare, &S::identity);
 171       assert(ret == a + 4);
 172     }
 173   }
 174
 175   { // check that the implicit conversion to bool works
 176     {
 177       int a[] = {1, 2, 2, 4};
 178       auto ret = std::ranges::adjacent_find(a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; });
 179       assert(ret == a + 1);
 180     }
 181     {
 182       int a[] = {1, 2, 2, 4};
 183       auto ret = std::ranges::adjacent_find(a, [](int i, int j) { return BooleanTestable{i == j}; });
 184       assert(ret == a + 1);
 185     }
 186   }
 187
 188   return true;
 189 }
 190
 191 int main(int, char**) {
 192   test();
 193   static_assert(test());
 194
 195   return 0;
 196 }