libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains.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, c++20
  12
  13 // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  14 //     requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
  15 //     constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});       // since C++23
  16
  17 // template<input_range R, class T, class Proj = identity>
  18 //     requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  19 //     constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});                 // since C++23
  20
  21 #include <algorithm>
  22 #include <array>
  23 #include <cassert>
  24 #include <list>
  25 #include <ranges>
  26 #include <string>
  27 #include <vector>
  28
  29 #include "almost_satisfies_types.h"
  30 #include "boolean_testable.h"
  31 #include "test_iterators.h"
  32
  33 struct NotEqualityComparable {};
  34
  35 template <class Iter, class Sent = Iter>
  36 concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); };
  37
  38 static_assert(HasContainsIt<int*>);
  39 static_assert(HasContainsIt<int*, int*>);
  40 static_assert(!HasContainsIt<NotEqualityComparable*>);
  41 static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>);
  42 static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>);
  43 static_assert(!HasContainsIt<InputIteratorNotInputOrOutputIterator>);
  44 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
  45 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
  46 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);
  47
  48 static_assert(!HasContainsIt<int*, int>);
  49 static_assert(!HasContainsIt<int, int*>);
  50
  51 template <class Range, class ValT>
  52 concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); };
  53
  54 static_assert(!HasContainsR<int, int>);
  55 static_assert(HasContainsR<int[1], int>);
  56 static_assert(!HasContainsR<NotEqualityComparable[1], NotEqualityComparable>);
  57 static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>);
  58 static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>);
  59 static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>);
  60 static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>);
  61 static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>);
  62
  63 template <class Iter, class Sent = Iter>
  64 constexpr void test_iterators() {
  65   using ValueT = std::iter_value_t<Iter>;
  66   { // simple tests
  67     ValueT a[] = {1, 2, 3, 4, 5, 6};
  68     {
  69       std::same_as<bool> decltype(auto) ret = std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3);
  70       assert(ret);
  71     }
  72     {
  73       auto whole                            = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
  74       std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole, 3);
  75       assert(ret);
  76     }
  77   }
  78
  79   { // check that a range with a single element works
  80     ValueT a[] = {32};
  81     {
  82       bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 1)), 32);
  83       assert(ret);
  84     }
  85     {
  86       auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 1)));
  87       bool ret   = std::ranges::contains(whole, 32);
  88       assert(ret);
  89     }
  90   }
  91
  92   { // check that an empty range works
  93     std::array<ValueT, 0> a = {};
  94     {
  95       bool ret = std::ranges::contains(Iter(a.data()), Sent(Iter(a.data())), 1);
  96       assert(!ret);
  97     }
  98     {
  99       auto whole = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data())));
 100       bool ret   = std::ranges::contains(whole, 1);
 101       assert(!ret);
 102     }
 103   }
 104
 105   { // check that the first element matches
 106     ValueT a[] = {32, 3, 2, 1, 0, 23, 21, 9, 40, 100};
 107     {
 108       bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 10)), 32);
 109       assert(ret);
 110     }
 111     {
 112       auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 10)));
 113       bool ret   = std::ranges::contains(whole, 32);
 114       assert(ret);
 115     }
 116   }
 117
 118   { // check that the last element matches
 119     ValueT a[] = {3, 22, 1, 43, 99, 0, 56, 100, 32};
 120     {
 121       bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 9)), 32);
 122       assert(ret);
 123     }
 124     {
 125       auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));
 126       bool ret   = std::ranges::contains(whole, 32);
 127       assert(ret);
 128     }
 129   }
 130
 131   { // no match
 132     ValueT a[] = {13, 1, 21, 4, 5};
 133     {
 134       bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10);
 135       assert(!ret);
 136     }
 137     {
 138       auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
 139       bool ret   = std::ranges::contains(whole, 10);
 140       assert(!ret);
 141     }
 142   }
 143
 144   { // check that the projections are used
 145     int a[] = {1, 9, 0, 13, 25};
 146     {
 147       bool ret = std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; });
 148       assert(ret);
 149     }
 150     {
 151       auto range = std::ranges::subrange(a, a + 5);
 152       bool ret   = std::ranges::contains(range, -13, [&](int i) { return i * -1; });
 153       assert(ret);
 154     }
 155   }
 156 }
 157
 158 constexpr bool test() {
 159   types::for_each(types::type_list<char, long long>{}, []<class T> {
 160     types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> {
 161       if constexpr (std::forward_iterator<Iter>)
 162         test_iterators<Iter>();
 163       test_iterators<Iter, sentinel_wrapper<Iter>>();
 164       test_iterators<Iter, sized_sentinel<Iter>>();
 165     });
 166   });
 167
 168   { // count invocations of the projection for contiguous iterators
 169     int a[]              = {1, 9, 0, 13, 25};
 170     int projection_count = 0;
 171     {
 172       bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) {
 173         ++projection_count;
 174         return i;
 175       });
 176       assert(ret);
 177       assert(projection_count == 3);
 178       projection_count = 0;
 179     }
 180     {
 181       bool ret = std::ranges::contains(a, 0, [&](int i) {
 182         ++projection_count;
 183         return i;
 184       });
 185       assert(ret);
 186       assert(projection_count == 3);
 187     }
 188   }
 189
 190   { // check invocations of the projection for std::string
 191     const std::string str{"hello world"};
 192     const std::string str1{"hi world"};
 193     int projection_count = 0;
 194     {
 195       std::string a[] = {str1, str1, str, str1, str1};
 196       auto whole =
 197           std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5)));
 198       bool ret = std::ranges::contains(whole.begin(), whole.end(), "hello world", [&](const std::string i) {
 199         ++projection_count;
 200         return i;
 201       });
 202       assert(ret);
 203       assert(projection_count == 3);
 204       projection_count = 0;
 205     }
 206     {
 207       std::string a[] = {str1, str1, str, str1, str1};
 208       auto whole =
 209           std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5)));
 210       bool ret = std::ranges::contains(whole, "hello world", [&](const std::string i) {
 211         ++projection_count;
 212         return i;
 213       });
 214       assert(ret);
 215       assert(projection_count == 3);
 216     }
 217   }
 218
 219   { // check invocations of the projection for non-contiguous iterators
 220     std::vector<bool> whole{false, false, true, false};
 221     int projection_count = 0;
 222     {
 223       bool ret = std::ranges::contains(whole.begin(), whole.end(), true, [&](bool b) {
 224         ++projection_count;
 225         return b;
 226       });
 227       assert(ret);
 228       assert(projection_count == 3);
 229       projection_count = 0;
 230     }
 231     {
 232       bool ret = std::ranges::contains(whole, true, [&](bool b) {
 233         ++projection_count;
 234         return b;
 235       });
 236       assert(ret);
 237       assert(projection_count == 3);
 238     }
 239   }
 240
 241   { // check invocations of the projection for views::transform
 242     int a[]              = {1, 2, 3, 4, 5};
 243     int projection_count = 0;
 244     auto square_number   = a | std::views::transform([](int x) { return x * x; });
 245     {
 246       bool ret = std::ranges::contains(square_number.begin(), square_number.end(), 16, [&](int i) {
 247         ++projection_count;
 248         return i;
 249       });
 250       assert(ret);
 251       assert(projection_count == 4);
 252       projection_count = 0;
 253     }
 254     {
 255       bool ret = std::ranges::contains(square_number, 16, [&](int i) {
 256         ++projection_count;
 257         return i;
 258       });
 259       assert(ret);
 260       assert(projection_count == 4);
 261     }
 262   }
 263
 264   return true;
 265 }
 266
 267 // test for non-contiguous containers
 268 bool test_nonconstexpr() {
 269   std::list<int> a     = {7, 5, 0, 16, 8};
 270   int projection_count = 0;
 271   {
 272     bool ret = std::ranges::contains(a.begin(), a.end(), 0, [&](int i) {
 273       ++projection_count;
 274       return i;
 275     });
 276     assert(ret);
 277     assert(projection_count == 3);
 278     projection_count = 0;
 279   }
 280   {
 281     bool ret = std::ranges::contains(a, 0, [&](int i) {
 282       ++projection_count;
 283       return i;
 284     });
 285     assert(ret);
 286     assert(projection_count == 3);
 287   }
 288
 289   return true;
 290 }
 291
 292 int main(int, char**) {
 293   test();
 294   static_assert(test());
 295
 296   assert(test_nonconstexpr());
 297
 298   return 0;
 299 }