192 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<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 "test_iterators.h"29 30template <class Iter, class Sent = sentinel_wrapper<Iter>>31concept HasRemoveIt = requires(Iter first, Sent last) { std::ranges::remove(first, last, 0); };32 33static_assert(HasRemoveIt<int*>);34static_assert(!HasRemoveIt<PermutableNotForwardIterator>);35static_assert(!HasRemoveIt<PermutableNotSwappable>);36static_assert(!HasRemoveIt<int*, SentinelForNotSemiregular>);37static_assert(!HasRemoveIt<int*, SentinelForNotWeaklyEqualityComparableWith>);38static_assert(!HasRemoveIt<int**>); // not indirect_binary_predicate39 40template <class Range>41concept HasRemoveR = requires(Range range) { std::ranges::remove(range, 0); };42 43static_assert(HasRemoveR<UncheckedRange<int*>>);44static_assert(!HasRemoveR<PermutableRangeNotForwardIterator>);45static_assert(!HasRemoveR<PermutableRangeNotSwappable>);46static_assert(!HasRemoveR<SentinelForNotSemiregular>);47static_assert(!HasRemoveR<SentinelForNotWeaklyEqualityComparableWith>);48static_assert(!HasRemoveR<UncheckedRange<int**>>); // not indirect_binary_predicate49 50template <int N, int M>51struct Data {52 std::array<int, N> input;53 std::array<int, M> expected;54 int val;55};56 57template <class Iter, class Sent, int N, int M>58constexpr void test(Data<N, M> d) {59 { // iterator overload60 auto input = d.input;61 62 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =63 std::ranges::remove(Iter(input.data()), Sent(Iter(input.data() + input.size())), d.val);64 65 assert(base(ret.begin()) == input.data() + M);66 assert(base(ret.end()) == input.data() + N);67 assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));68 }69 70 { // range overload71 auto input = d.input;72 auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));73 74 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove(range, d.val);75 76 assert(base(ret.begin()) == input.data() + M);77 assert(base(ret.end()) == input.data() + N);78 assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));79 }80}81 82template <class Iter, class Sent>83constexpr void tests() {84 // simple test85 test<Iter, Sent, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});86 // empty range87 test<Iter, Sent, 0, 0>({});88 // single element range - match89 test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .val = 1});90 // single element range - no match91 test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .val = 2});92 // two element range - same order93 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});94 // two element range - reversed order95 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});96 // all elements match97 test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});98 // the relative order of elements isn't changed99 test<Iter, Sent, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});100}101 102template <class Iter>103constexpr void test_sentinels() {104 tests<Iter, Iter>();105 tests<Iter, sentinel_wrapper<Iter>>();106 tests<Iter, sized_sentinel<Iter>>();107}108 109constexpr void test_iterators() {110 test_sentinels<forward_iterator<int*>>();111 test_sentinels<bidirectional_iterator<int*>>();112 test_sentinels<random_access_iterator<int*>>();113 test_sentinels<contiguous_iterator<int*>>();114 test_sentinels<int*>();115}116 117constexpr bool test() {118 test_iterators();119 120 { // check that ranges::dangling is returned121 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =122 std::ranges::remove(std::array{1, 2, 3, 4}, 1);123 }124 125 { // check complexity requirements126 struct CompCounter {127 int* comp_count;128 129 constexpr bool operator==(const CompCounter&) const {130 ++*comp_count;131 return false;132 }133 };134 {135 int proj_count = 0;136 auto proj = [&](CompCounter i) {137 ++proj_count;138 return i;139 };140 int comp_count = 0;141 142 CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};143 auto ret = std::ranges::remove(std::begin(a), std::end(a), CompCounter{&comp_count}, proj);144 assert(ret.begin() == std::end(a) && ret.end() == std::end(a));145 assert(comp_count == 4);146 assert(proj_count == 4);147 }148 {149 int proj_count = 0;150 auto proj = [&](CompCounter i) {151 ++proj_count;152 return i;153 };154 int comp_count = 0;155 156 CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};157 auto ret = std::ranges::remove(a, CompCounter{&comp_count}, proj);158 assert(ret.begin() == std::end(a) && ret.end() == std::end(a));159 assert(comp_count == 4);160 assert(proj_count == 4);161 }162 }163 164 { // check that std::invoke is used165 struct S {166 constexpr S& identity() { return *this; }167 bool operator==(const S&) const = default;168 };169 {170 S a[4] = {};171 auto ret = std::ranges::remove(std::begin(a), std::end(a), S{}, &S::identity);172 assert(ret.begin() == std::begin(a));173 assert(ret.end() == std::end(a));174 }175 {176 S a[4] = {};177 auto ret = std::ranges::remove(a, S{}, &S::identity);178 assert(ret.begin() == std::begin(a));179 assert(ret.end() == std::end(a));180 }181 }182 183 return true;184}185 186int main(int, char**) {187 test();188 static_assert(test());189 190 return 0;191}192