libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.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 // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=20000000
  14 // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=70000000
  15
  16 // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  17 //   requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
  18 //   constexpr iter_difference_t<I>
  19 //     ranges::count(I first, S last, const T& value, Proj proj = {});
  20 // template<input_range R, class T, class Proj = identity>
  21 //   requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  22 //   constexpr range_difference_t<R>
  23 //     ranges::count(R&& r, const T& value, Proj proj = {});
  24
  25 #include <algorithm>
  26 #include <array>
  27 #include <cassert>
  28 #include <ranges>
  29 #include <vector>
  30
  31 #include "almost_satisfies_types.h"
  32 #include "test_iterators.h"
  33
  34 struct NotEqualityComparable {
  35   bool operator==(NotEqualityComparable&&) const;
  36   bool operator==(NotEqualityComparable&) const;
  37   bool operator==(const NotEqualityComparable&&) const;
  38 };
  39
  40 template <class It, class Sent = It>
  41 concept HasCountIt = requires(It it, Sent sent) { std::ranges::count(it, sent, *it); };
  42 static_assert(HasCountIt<int*>);
  43 static_assert(!HasCountIt<NotEqualityComparable*>);
  44 static_assert(!HasCountIt<InputIteratorNotDerivedFrom>);
  45 static_assert(!HasCountIt<InputIteratorNotIndirectlyReadable>);
  46 static_assert(!HasCountIt<InputIteratorNotInputOrOutputIterator>);
  47 static_assert(!HasCountIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
  48 static_assert(!HasCountIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
  49
  50 static_assert(!HasCountIt<int*, int>);
  51 static_assert(!HasCountIt<int, int*>);
  52
  53 template <class Range, class ValT>
  54 concept HasCountR = requires(Range r) { std::ranges::count(r, ValT{}); };
  55 static_assert(HasCountR<std::array<int, 1>, int>);
  56 static_assert(!HasCountR<int, int>);
  57 static_assert(!HasCountR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
  58 static_assert(!HasCountR<InputRangeNotDerivedFrom, int>);
  59 static_assert(!HasCountR<InputRangeNotIndirectlyReadable, int>);
  60 static_assert(!HasCountR<InputRangeNotInputOrOutputIterator, int>);
  61 static_assert(!HasCountR<InputRangeNotSentinelSemiregular, int>);
  62 static_assert(!HasCountR<InputRangeNotSentinelEqualityComparableWith, int>);
  63
  64 template <class It, class Sent = It>
  65 constexpr void test_iterators() {
  66   {
  67     // simple test
  68     {
  69       int a[] = {1, 2, 3, 4};
  70       std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(It(a), Sent(It(a + 4)), 3);
  71       assert(ret == 1);
  72     }
  73     {
  74       int a[] = {1, 2, 3, 4};
  75       auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
  76       std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(range, 3);
  77       assert(ret == 1);
  78     }
  79   }
  80
  81   {
  82     // check that an empty range works
  83     {
  84       std::array<int, 0> a = {};
  85       auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 1);
  86       assert(ret == 0);
  87     }
  88     {
  89       std::array<int, 0> a = {};
  90       auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
  91       auto ret = std::ranges::count(range, 1);
  92       assert(ret == 0);
  93     }
  94   }
  95
  96   {
  97     // check that a range with a single element works
  98     {
  99       std::array a = {2};
 100       auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 2);
 101       assert(ret == 1);
 102     }
 103     {
 104       std::array a = {2};
 105       auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
 106       auto ret = std::ranges::count(range, 2);
 107       assert(ret == 1);
 108     }
 109   }
 110
 111   {
 112     // check that 0 is returned with no match
 113     {
 114       std::array a = {1, 1, 1};
 115       auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 0);
 116       assert(ret == 0);
 117     }
 118     {
 119       std::array a = {1, 1, 1};
 120       auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
 121       auto ret = std::ranges::count(range, 0);
 122       assert(ret == 0);
 123     }
 124   }
 125
 126   {
 127     // check that more than one element is counted
 128     {
 129       std::array a = {3, 3, 4, 3, 3};
 130       auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 3);
 131       assert(ret == 4);
 132     }
 133     {
 134       std::array a = {3, 3, 4, 3, 3};
 135       auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
 136       auto ret = std::ranges::count(range, 3);
 137       assert(ret == 4);
 138     }
 139   }
 140
 141   {
 142     // check that all elements are counted
 143     {
 144       std::array a = {5, 5, 5, 5};
 145       auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 5);
 146       assert(ret == 4);
 147     }
 148     {
 149       std::array a = {5, 5, 5, 5};
 150       auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
 151       auto ret = std::ranges::count(range, 5);
 152       assert(ret == 4);
 153     }
 154   }
 155 }
 156
 157 constexpr bool test() {
 158   test_iterators<int*>();
 159   test_iterators<const int*>();
 160   test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
 161   test_iterators<bidirectional_iterator<int*>>();
 162   test_iterators<forward_iterator<int*>>();
 163   test_iterators<random_access_iterator<int*>>();
 164   test_iterators<contiguous_iterator<int*>>();
 165
 166   {
 167     // check that projections are used properly and that they are called with the iterator directly
 168     {
 169       int a[] = {1, 2, 3, 4};
 170       auto ret = std::ranges::count(a, a + 4, a + 3, [](int& i) { return &i; });
 171       assert(ret == 1);
 172     }
 173     {
 174       int a[] = {1, 2, 3, 4};
 175       auto ret = std::ranges::count(a, a + 3, [](int& i) { return &i; });
 176       assert(ret == 1);
 177     }
 178   }
 179
 180   {
 181     // check that std::invoke is used
 182     struct S { int i; };
 183     S a[] = { S{1}, S{3}, S{2} };
 184     std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(a, 4, &S::i);
 185     assert(ret == 0);
 186   }
 187
 188   {
 189     // count invocations of the projection
 190     {
 191       int a[] = {1, 2, 3, 4};
 192       int projection_count = 0;
 193       auto ret = std::ranges::count(a, a + 4, 2, [&](int i) { ++projection_count; return i; });
 194       assert(ret == 1);
 195       assert(projection_count == 4);
 196     }
 197     {
 198       int a[] = {1, 2, 3, 4};
 199       int projection_count = 0;
 200       auto ret = std::ranges::count(a, 2, [&](int i) { ++projection_count; return i; });
 201       assert(ret == 1);
 202       assert(projection_count == 4);
 203     }
 204   }
 205
 206   {
 207     // check that an immobile type works
 208     struct NonMovable {
 209       NonMovable(const NonMovable&) = delete;
 210       NonMovable(NonMovable&&) = delete;
 211       constexpr NonMovable(int i_) : i(i_) {}
 212       int i;
 213
 214       bool operator==(const NonMovable&) const = default;
 215     };
 216     {
 217       NonMovable a[] = {9, 8, 4, 3};
 218       auto ret = std::ranges::count(a, a + 4, NonMovable(8));
 219       assert(ret == 1);
 220     }
 221     {
 222       NonMovable a[] = {9, 8, 4, 3};
 223       auto ret = std::ranges::count(a, NonMovable(8));
 224       assert(ret == 1);
 225     }
 226   }
 227
 228   {
 229     // check that difference_type is used
 230     struct DiffTypeIterator {
 231       using difference_type = signed char;
 232       using value_type = int;
 233
 234       int* it = nullptr;
 235
 236       constexpr DiffTypeIterator() = default;
 237       constexpr DiffTypeIterator(int* i) : it(i) {}
 238
 239       constexpr int& operator*() const { return *it; }
 240       constexpr DiffTypeIterator& operator++() { ++it; return *this; }
 241       constexpr void operator++(int) { ++it; }
 242
 243       bool operator==(const DiffTypeIterator&) const = default;
 244     };
 245
 246     {
 247       int a[] = {5, 5, 4, 3, 2, 1};
 248       std::same_as<signed char> decltype(auto) ret =
 249           std::ranges::count(DiffTypeIterator(a), DiffTypeIterator(a + 6), 4);
 250       assert(ret == 1);
 251     }
 252     {
 253       int a[] = {5, 5, 4, 3, 2, 1};
 254       auto range = std::ranges::subrange(DiffTypeIterator(a), DiffTypeIterator(a + 6));
 255       std::same_as<signed char> decltype(auto) ret = std::ranges::count(range, 4);
 256       assert(ret == 1);
 257     }
 258   }
 259
 260   { // check that __bit_iterator optimizations work as expected
 261     std::vector<bool> vec(256 + 64);
 262     for (ptrdiff_t i = 0; i != 256; ++i) {
 263       for (size_t offset = 0; offset != 64; ++offset) {
 264         std::fill(vec.begin(), vec.end(), false);
 265         std::fill(vec.begin() + offset, vec.begin() + i + offset, true);
 266         assert(std::ranges::count(vec.begin() + offset, vec.begin() + offset + 256, true) == i);
 267         assert(std::ranges::count(vec.begin() + offset, vec.begin() + offset + 256, false) == 256 - i);
 268       }
 269     }
 270   }
 271
 272   return true;
 273 }
 274
 275 int main(int, char**) {
 276   test();
 277   static_assert(test());
 278
 279   return 0;
 280 }