libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges.remove.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<permutable 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 subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
  16 // template<forward_range R, class T, class Proj = identity>
  17 //   requires permutable<iterator_t<R>> &&
  18 //            indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  19 //   constexpr borrowed_subrange_t<R>
  20 //     ranges::remove(R&& r, const T& value, Proj proj = {});
  21
  22 #include <algorithm>
  23 #include <array>
  24 #include <cassert>
  25 #include <ranges>
  26
  27 #include "almost_satisfies_types.h"
  28 #include "boolean_testable.h"
  29 #include "test_iterators.h"
  30
  31 template <class Iter, class Sent = sentinel_wrapper<Iter>>
  32 concept HasRemoveIt = requires(Iter first, Sent last) { std::ranges::remove(first, last, 0); };
  33
  34 static_assert(HasRemoveIt<int*>);
  35 static_assert(!HasRemoveIt<PermutableNotForwardIterator>);
  36 static_assert(!HasRemoveIt<PermutableNotSwappable>);
  37 static_assert(!HasRemoveIt<int*, SentinelForNotSemiregular>);
  38 static_assert(!HasRemoveIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  39 static_assert(!HasRemoveIt<int**>); // not indirect_binary_prediacte
  40
  41 template <class Range>
  42 concept HasRemoveR = requires(Range range) { std::ranges::remove(range, 0); };
  43
  44 static_assert(HasRemoveR<UncheckedRange<int*>>);
  45 static_assert(!HasRemoveR<PermutableRangeNotForwardIterator>);
  46 static_assert(!HasRemoveR<PermutableRangeNotSwappable>);
  47 static_assert(!HasRemoveR<SentinelForNotSemiregular>);
  48 static_assert(!HasRemoveR<SentinelForNotWeaklyEqualityComparableWith>);
  49 static_assert(!HasRemoveR<UncheckedRange<int**>>); // not indirect_binary_prediacte
  50
  51 template <int N, int M>
  52 struct Data {
  53   std::array<int, N> input;
  54   std::array<int, M> expected;
  55   int val;
  56 };
  57
  58 template <class Iter, class Sent, int N, int M>
  59 constexpr void test(Data<N, M> d) {
  60   { // iterator overload
  61     auto input = d.input;
  62
  63     std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =
  64         std::ranges::remove(Iter(input.data()), Sent(Iter(input.data() + input.size())), d.val);
  65
  66     assert(base(ret.begin()) == input.data() + M);
  67     assert(base(ret.end()) == input.data() + N);
  68     assert(std::ranges::equal(input.begin(), base(ret.begin()), d.expected.begin(), d.expected.end()));
  69   }
  70
  71   { // range overload
  72     auto input = d.input;
  73     auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));
  74
  75     std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove(range, d.val);
  76
  77     assert(base(ret.begin()) == input.data() + M);
  78     assert(base(ret.end()) == input.data() + N);
  79     assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end()));
  80   }
  81 }
  82
  83 template <class Iter, class Sent>
  84 constexpr void tests() {
  85   // simple test
  86   test<Iter, Sent, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});
  87   // empty range
  88   test<Iter, Sent, 0, 0>({});
  89   // single element range - match
  90   test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .val = 1});
  91   // single element range - no match
  92   test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .val = 2});
  93   // two element range - same order
  94   test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});
  95   // two element range - reversed order
  96   test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});
  97   // all elements match
  98   test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});
  99   // the relative order of elements isn't changed
 100   test<Iter, Sent, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});
 101 }
 102
 103 template <class Iter>
 104 constexpr void test_sentinels() {
 105   tests<Iter, Iter>();
 106   tests<Iter, sentinel_wrapper<Iter>>();
 107   tests<Iter, sized_sentinel<Iter>>();
 108 }
 109
 110 constexpr void test_iterators() {
 111   test_sentinels<forward_iterator<int*>>();
 112   test_sentinels<bidirectional_iterator<int*>>();
 113   test_sentinels<random_access_iterator<int*>>();
 114   test_sentinels<contiguous_iterator<int*>>();
 115   test_sentinels<int*>();
 116 }
 117
 118 constexpr bool test() {
 119   test_iterators();
 120
 121   { // check that ranges::dangling is returned
 122     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
 123         std::ranges::remove(std::array{1, 2, 3, 4}, 1);
 124   }
 125
 126   { // check complexity requirements
 127     struct CompCounter {
 128       int* comp_count;
 129
 130       constexpr bool operator==(const CompCounter&) const {
 131         ++*comp_count;
 132         return false;
 133       }
 134     };
 135     {
 136       int proj_count = 0;
 137       auto proj      = [&](CompCounter i) {
 138         ++proj_count;
 139         return i;
 140       };
 141       int comp_count = 0;
 142
 143       CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};
 144       auto ret        = std::ranges::remove(std::begin(a), std::end(a), CompCounter{&comp_count}, proj);
 145       assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
 146       assert(comp_count == 4);
 147       assert(proj_count == 4);
 148     }
 149     {
 150       int proj_count = 0;
 151       auto proj      = [&](CompCounter i) {
 152         ++proj_count;
 153         return i;
 154       };
 155       int comp_count = 0;
 156
 157       CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};
 158       auto ret        = std::ranges::remove(a, CompCounter{&comp_count}, proj);
 159       assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
 160       assert(comp_count == 4);
 161       assert(proj_count == 4);
 162     }
 163   }
 164
 165   { // check that std::invoke is used
 166     struct S {
 167       constexpr S& identity() { return *this; }
 168       bool operator==(const S&) const = default;
 169     };
 170     {
 171       S a[4]   = {};
 172       auto ret = std::ranges::remove(std::begin(a), std::end(a), S{}, &S::identity);
 173       assert(ret.begin() == std::begin(a));
 174       assert(ret.end() == std::end(a));
 175     }
 176     {
 177       S a[4]   = {};
 178       auto ret = std::ranges::remove(a, S{}, &S::identity);
 179       assert(ret.begin() == std::begin(a));
 180       assert(ret.end() == std::end(a));
 181     }
 182   }
 183
 184   {
 185     // check that the implicit conversion to bool works
 186     {
 187       StrictComparable<int> a[] = {1, 2, 3, 4};
 188       auto ret                  = std::ranges::remove(a, a + 4, StrictComparable<int>{2});
 189       assert(ret.begin() == a + 3);
 190     }
 191     {
 192       StrictComparable<int> a[] = {1, 2, 3, 4};
 193       auto ret                  = std::ranges::remove(a, StrictComparable<int>{2});
 194       assert(ret.begin() == a + 3);
 195     }
 196   }
 197
 198   return true;
 199 }
 200
 201 int main(int, char**) {
 202   test();
 203   static_assert(test());
 204
 205   return 0;
 206 }