261 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++17, c++2012 13// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,14// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>15// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>16// constexpr bool ranges::starts_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},17// Proj1 proj1 = {}, Proj2 proj2 = {});18// template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,19// class Proj2 = identity>20// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>21// constexpr bool ranges::starts_with(R1&& r1, R2&& r2, Pred pred = {},22// Proj1 proj1 = {}, Proj2 proj2 = {});23 24#include <algorithm>25#include <array>26#include <ranges>27 28#include "almost_satisfies_types.h"29#include "test_iterators.h"30#include "type_algorithms.h"31 32template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>33concept HasStartsWithIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {34 std::ranges::starts_with(first1, last1, first2, last2);35};36 37static_assert(HasStartsWithIt<int*>);38static_assert(HasStartsWithIt<ForwardIteratorNotDerivedFrom>);39static_assert(HasStartsWithIt<ForwardIteratorNotIncrementable>);40static_assert(!HasStartsWithIt<int*, SentinelForNotSemiregular>);41static_assert(!HasStartsWithIt<int*, int*, int**>); // not indirectly comparable42static_assert(!HasStartsWithIt<int*, SentinelForNotWeaklyEqualityComparableWith>);43static_assert(HasStartsWithIt<int*, int*, ForwardIteratorNotDerivedFrom>);44static_assert(HasStartsWithIt<int*, int*, ForwardIteratorNotIncrementable>);45static_assert(!HasStartsWithIt<int*, int*, int*, SentinelForNotSemiregular>);46static_assert(!HasStartsWithIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);47 48template <class Range1, class Range2 = UncheckedRange<int*>>49concept HasStartsWithR = requires(Range1 range1, Range2 range2) { std::ranges::starts_with(range1, range2); };50 51static_assert(HasStartsWithR<UncheckedRange<int*>>);52static_assert(HasStartsWithR<ForwardRangeNotDerivedFrom>);53static_assert(!HasStartsWithR<ForwardIteratorNotIncrementable>);54static_assert(!HasStartsWithR<ForwardRangeNotSentinelSemiregular>);55static_assert(!HasStartsWithR<ForwardRangeNotSentinelEqualityComparableWith>);56static_assert(!HasStartsWithR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable57static_assert(HasStartsWithR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);58static_assert(HasStartsWithR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);59static_assert(!HasStartsWithR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);60static_assert(!HasStartsWithR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);61 62// clang-format off63template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2>64constexpr void test_iterators() {65 { // simple tests66 {67 int a[] = {1, 2, 3, 4, 5, 6};68 int p[] = {1, 2};69 std::same_as<bool> decltype(auto) ret =70 std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)));71 assert(ret);72 }73 {74 int a[] = {1, 2, 3, 4, 5, 6};75 int p[] = {1, 2};76 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));77 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));78 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);79 assert(ret);80 }81 }82 83 { // prefix doesn't match84 {85 int a[] = {1, 2, 3, 4, 5, 6};86 int p[] = {4, 5, 6};87 std::same_as<bool> decltype(auto) ret =88 std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3)));89 assert(!ret);90 }91 {92 int a[] = {1, 2, 3, 4, 5, 6};93 int p[] = {4, 5, 6};94 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));95 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));96 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);97 assert(!ret);98 }99 }100 101 { // range and prefix are identical102 {103 int a[] = {1, 2, 3, 4, 5, 6};104 int p[] = {1, 2, 3, 4, 5, 6};105 std::same_as<bool> decltype(auto) ret =106 std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 6)));107 assert(ret);108 }109 {110 int a[] = {1, 2, 3, 4, 5, 6};111 int p[] = {1, 2, 3, 4, 5, 6};112 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));113 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6)));114 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);115 assert(ret);116 }117 }118 119 { // prefix is longer than range120 {121 int a[] = {1, 2, 3, 4, 5, 6};122 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};123 std::same_as<bool> decltype(auto) ret =124 std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 8)));125 assert(!ret);126 }127 {128 int a[] = {1, 2, 3, 4, 5, 6};129 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};130 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));131 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));132 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);133 assert(!ret);134 }135 }136 137 { // prefix has zero length138 {139 int a[] = {1, 2, 3, 4, 5, 6};140 std::array<int, 0> p = {};141 std::same_as<bool> decltype(auto) ret =142 std::ranges::starts_with(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p.data()), Sent2(Iter2(p.data())));143 assert(ret);144 }145 {146 int a[] = {1, 2, 3, 4, 5, 6};147 std::array<int, 0> p = {};148 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));149 auto prefix = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));150 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);151 assert(ret);152 }153 }154 155 { // range has zero length156 {157 std::array<int, 0> a = {};158 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};159 std::same_as<bool> decltype(auto) ret =160 std::ranges::starts_with(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(p), Sent2(Iter2(p + 8)));161 assert(!ret);162 }163 {164 std::array<int, 0> a = {};165 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};166 auto whole = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));167 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));168 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix);169 assert(!ret);170 }171 }172 173 { // check that the predicate is used174 {175 int a[] = {11, 8, 3, 4, 0, 6};176 int p[] = {1, 12};177 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(178 Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)), [](int l, int r) { return l > r; });179 assert(!ret);180 }181 {182 int a[] = {11, 8, 3, 4, 0, 6};183 int p[] = {1, 12};184 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));185 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));186 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(whole, prefix, [](int l, int r) { return l > r; });187 assert(!ret);188 }189 }190 191 { // check that the projections are used192 {193 int a[] = {1, 3, 5, 1, 5, 6};194 int p[] = {2, 3, 4};195 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(196 Iter1(a),197 Sent1(Iter1(a + 6)),198 Iter2(p),199 Sent2(Iter2(p + 3)),200 {},201 [](int i) { return i + 3; },202 [](int i) { return i * 2; });203 assert(ret);204 }205 {206 int a[] = {1, 3, 5, 1, 5, 6};207 int p[] = {2, 3, 4};208 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));209 auto prefix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));210 std::same_as<bool> decltype(auto) ret = std::ranges::starts_with(211 whole, prefix, {}, [](int i) { return i + 3; }, [](int i) { return i * 2; });212 assert(ret);213 }214 }215}216 217constexpr bool test() {218 types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() {219 types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() {220 if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>)221 test_iterators<Iter1, Iter1, Iter2, Iter2>();222 if constexpr (std::forward_iterator<Iter2>)223 test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>();224 if constexpr (std::forward_iterator<Iter1>)225 test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>();226 test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>();227 });228 });229 230 { // check that std::invoke is used231 struct S {232 int i;233 234 constexpr S identity() { return *this; }235 236 constexpr bool compare(const S& s) { return i == s.i; }237 };238 {239 S a[] = {{1}, {2}, {3}, {4}};240 S p[] = {{1}, {2}};241 auto ret = std::ranges::starts_with(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity);242 assert(ret);243 }244 {245 S a[] = {{1}, {2}, {3}, {4}};246 S p[] = {{1}, {2}};247 auto ret = std::ranges::starts_with(a, p, &S::compare, &S::identity, &S::identity);248 assert(ret);249 }250 }251 252 return true;253}254 255int main(int, char**) {256 test();257 static_assert(test());258 259 return 0;260}261