algorithm_unittest.cc 62 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731
  1. // Copyright 2020 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/ranges/algorithm.h"
  5. #include <algorithm>
  6. #include <functional>
  7. #include <initializer_list>
  8. #include <iterator>
  9. #include <random>
  10. #include <utility>
  11. #include "base/ranges/functional.h"
  12. #include "testing/gmock/include/gmock/gmock.h"
  13. #include "testing/gtest/include/gtest/gtest.h"
  14. using ::testing::ElementsAre;
  15. using ::testing::Field;
  16. using ::testing::Ge;
  17. using ::testing::Gt;
  18. using ::testing::Le;
  19. using ::testing::Lt;
  20. using ::testing::Pair;
  21. namespace base {
  22. namespace {
  23. // A macro to work around the fact that lambdas are not constexpr in C++14.
  24. // This will define an unnamed struct with a constexpr call operator, similarly
  25. // to how lambdas behave in C++17+.
  26. // Note that this does not support capture groups, so all lambdas defined like
  27. // this must be stateless.
  28. // Example Usage: `CONSTEXPR_LAMBDA((int i, int j) { return i + j; }) lambda;`
  29. // TODO(crbug.com/752720): Remove once we have constexpr lambdas for real.
  30. #define CONSTEXPR_LAMBDA(fun) \
  31. constexpr struct { constexpr bool operator() fun }
  32. struct Int {
  33. constexpr Int() = default;
  34. constexpr Int(int value) : value(value) {}
  35. int value = 0;
  36. };
  37. constexpr bool operator==(Int lhs, Int rhs) {
  38. return lhs.value == rhs.value;
  39. }
  40. constexpr bool operator<(Int lhs, Int rhs) {
  41. return lhs.value < rhs.value;
  42. }
  43. constexpr bool operator>(Int lhs, Int rhs) {
  44. return lhs.value > rhs.value;
  45. }
  46. constexpr bool operator<=(Int lhs, Int rhs) {
  47. return lhs.value <= rhs.value;
  48. }
  49. constexpr bool operator>=(Int lhs, Int rhs) {
  50. return lhs.value >= rhs.value;
  51. }
  52. // Move-only int that clears `value` when moving out.
  53. struct MoveOnlyInt {
  54. MoveOnlyInt(int value) : value(value) {}
  55. MoveOnlyInt(MoveOnlyInt&& other) : value(std::exchange(other.value, 0)) {}
  56. MoveOnlyInt& operator=(MoveOnlyInt&& other) {
  57. value = std::exchange(other.value, 0);
  58. return *this;
  59. }
  60. int value = 0;
  61. };
  62. constexpr bool is_even(int i) {
  63. return i % 2 == 0;
  64. }
  65. bool is_odd(int i) {
  66. return i % 2 == 1;
  67. }
  68. template <typename Iter>
  69. auto make_vector(Iter begin, Iter end) {
  70. using T = typename std::iterator_traits<Iter>::value_type;
  71. return std::vector<T>(begin, end);
  72. }
  73. } // namespace
  74. TEST(RangesTest, AllOf) {
  75. // Note: Lambdas don't have a constexpr call operator prior to C++17, thus we
  76. // are providing our own anonyomous struct here.
  77. constexpr struct {
  78. constexpr bool operator()(int i) { return i != 0; }
  79. } is_non_zero;
  80. constexpr int array[] = {0, 1, 2, 3, 4, 5};
  81. static_assert(ranges::all_of(array + 1, array + 6, is_non_zero), "");
  82. static_assert(!ranges::all_of(array, is_non_zero), "");
  83. constexpr Int values[] = {0, 2, 4, 5};
  84. static_assert(
  85. ranges::all_of(values + 1, ranges::end(values), is_non_zero, &Int::value),
  86. "");
  87. static_assert(!ranges::all_of(values, is_non_zero, &Int::value), "");
  88. }
  89. TEST(RangesTest, AnyOf) {
  90. constexpr int array[] = {0, 1, 2, 3, 4, 5};
  91. static_assert(!ranges::any_of(array + 5, array + 6, is_even), "");
  92. static_assert(ranges::any_of(array, is_even), "");
  93. constexpr Int values[] = {{0}, {2}, {4}, {5}};
  94. static_assert(
  95. !ranges::any_of(values + 3, ranges::end(values), is_even, &Int::value),
  96. "");
  97. static_assert(ranges::any_of(values, is_even, &Int::value), "");
  98. }
  99. TEST(RangesTest, NoneOf) {
  100. // Note: Lambdas don't have a constexpr call operator prior to C++17, thus we
  101. // are providing our own anonyomous struct here.
  102. constexpr struct {
  103. constexpr bool operator()(int i) { return i == 0; }
  104. } is_zero;
  105. constexpr int array[] = {0, 1, 2, 3, 4, 5};
  106. static_assert(ranges::none_of(array + 1, array + 6, is_zero), "");
  107. static_assert(!ranges::none_of(array, is_zero), "");
  108. constexpr Int values[] = {{0}, {2}, {4}, {5}};
  109. static_assert(
  110. ranges::none_of(values + 1, ranges::end(values), is_zero, &Int::value),
  111. "");
  112. static_assert(!ranges::none_of(values, is_zero, &Int::value), "");
  113. }
  114. TEST(RangesTest, ForEach) {
  115. auto times_two = [](int& i) { i *= 2; };
  116. int array[] = {0, 1, 2, 3, 4, 5};
  117. auto result = ranges::for_each(array, array + 3, times_two);
  118. EXPECT_EQ(result.in, array + 3);
  119. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  120. // EXPECT_EQ.
  121. EXPECT_TRUE(result.fun == times_two);
  122. EXPECT_THAT(array, ElementsAre(0, 2, 4, 3, 4, 5));
  123. ranges::for_each(array + 3, array + 6, times_two);
  124. EXPECT_EQ(result.in, array + 3);
  125. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  126. // EXPECT_EQ.
  127. EXPECT_TRUE(result.fun == times_two);
  128. EXPECT_THAT(array, ElementsAre(0, 2, 4, 6, 8, 10));
  129. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  130. // EXPECT_EQ.
  131. EXPECT_TRUE(times_two == ranges::for_each(array, times_two).fun);
  132. EXPECT_THAT(array, ElementsAre(0, 4, 8, 12, 16, 20));
  133. Int values[] = {0, 2, 4, 5};
  134. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  135. // EXPECT_EQ.
  136. EXPECT_TRUE(times_two ==
  137. ranges::for_each(values, times_two, &Int::value).fun);
  138. EXPECT_THAT(values,
  139. ElementsAre(Field(&Int::value, 0), Field(&Int::value, 4),
  140. Field(&Int::value, 8), Field(&Int::value, 10)));
  141. }
  142. TEST(RangesTest, ForEachN) {
  143. auto times_two = [](int& i) { i *= 2; };
  144. int array[] = {0, 1, 2, 3, 4, 5};
  145. auto result = ranges::for_each_n(array, 3, times_two);
  146. EXPECT_EQ(result.in, array + 3);
  147. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  148. // EXPECT_EQ.
  149. EXPECT_TRUE(result.fun == times_two);
  150. EXPECT_THAT(array, ElementsAre(0, 2, 4, 3, 4, 5));
  151. Int values[] = {0, 2, 4, 5};
  152. // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
  153. // EXPECT_EQ.
  154. EXPECT_TRUE(times_two ==
  155. ranges::for_each_n(values, 4, times_two, &Int::value).fun);
  156. EXPECT_THAT(values,
  157. ElementsAre(Field(&Int::value, 0), Field(&Int::value, 4),
  158. Field(&Int::value, 8), Field(&Int::value, 10)));
  159. }
  160. TEST(RangesTest, Find) {
  161. constexpr int array[] = {0, 1, 2, 3, 4, 5};
  162. static_assert(array + 6 == ranges::find(array + 1, array + 6, 0), "");
  163. static_assert(array == ranges::find(array, 0), "");
  164. constexpr Int values[] = {{0}, {2}, {4}, {5}};
  165. static_assert(values == ranges::find(values, values, 0, &Int::value), "");
  166. static_assert(ranges::end(values) == ranges::find(values, 3, &Int::value),
  167. "");
  168. }
  169. TEST(RangesTest, FindIf) {
  170. auto is_at_least_5 = [](int i) { return i >= 5; };
  171. int array[] = {0, 1, 2, 3, 4, 5};
  172. EXPECT_EQ(array + 5, ranges::find_if(array, array + 5, is_at_least_5));
  173. EXPECT_EQ(array + 5, ranges::find_if(array, is_at_least_5));
  174. Int values[] = {{0}, {2}, {4}, {5}};
  175. EXPECT_EQ(values + 3,
  176. ranges::find_if(values, values + 3, is_odd, &Int::value));
  177. EXPECT_EQ(values + 3, ranges::find_if(values, is_odd, &Int::value));
  178. }
  179. TEST(RangesTest, FindIfNot) {
  180. auto is_less_than_5 = [](int i) { return i < 5; };
  181. int array[] = {0, 1, 2, 3, 4, 5};
  182. EXPECT_EQ(array + 5, ranges::find_if_not(array, array + 5, is_less_than_5));
  183. EXPECT_EQ(array + 5, ranges::find_if_not(array, is_less_than_5));
  184. Int values[] = {{0}, {2}, {4}, {5}};
  185. EXPECT_EQ(values + 3,
  186. ranges::find_if_not(values, values + 3, is_even, &Int::value));
  187. EXPECT_EQ(values + 3, ranges::find_if_not(values, is_even, &Int::value));
  188. }
  189. TEST(RangesTest, FindEnd) {
  190. int array1[] = {0, 1, 2};
  191. int array2[] = {4, 5, 6};
  192. int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4,
  193. 0, 1, 2, 3, 0, 1, 2, 0, 1, 0};
  194. EXPECT_EQ(array3 + 15, ranges::find_end(array3, ranges::end(array3), array1,
  195. ranges::end(array1)));
  196. EXPECT_EQ(ranges::end(array3), ranges::find_end(array3, ranges::end(array3),
  197. array2, ranges::end(array2)));
  198. EXPECT_EQ(array3 + 4,
  199. ranges::find_end(array3, ranges::end(array3), array2, array2 + 2));
  200. Int ints1[] = {{0}, {1}, {2}};
  201. Int ints2[] = {{4}, {5}, {6}};
  202. EXPECT_EQ(array3 + 15, ranges::find_end(array3, ints1, ranges::equal_to{},
  203. identity{}, &Int::value));
  204. EXPECT_EQ(ranges::end(array3),
  205. ranges::find_end(array3, ints2, ranges::equal_to{}, identity{},
  206. &Int::value));
  207. }
  208. TEST(RangesTest, FindFirstOf) {
  209. int array1[] = {1, 2, 3};
  210. int array2[] = {7, 8, 9};
  211. int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3};
  212. EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ranges::end(array3),
  213. array1, ranges::end(array1)));
  214. EXPECT_EQ(ranges::end(array3),
  215. ranges::find_first_of(array3, ranges::end(array3), array2,
  216. ranges::end(array2)));
  217. Int ints1[] = {{1}, {2}, {3}};
  218. Int ints2[] = {{7}, {8}, {9}};
  219. EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ints1, ranges::equal_to{},
  220. identity{}, &Int::value));
  221. EXPECT_EQ(ranges::end(array3),
  222. ranges::find_first_of(array3, ints2, ranges::equal_to{}, identity{},
  223. &Int::value));
  224. }
  225. TEST(RangesTest, AdjacentFind) {
  226. constexpr int array[] = {1, 2, 3, 3};
  227. static_assert(array + 2 == ranges::adjacent_find(array, ranges::end(array)),
  228. "");
  229. static_assert(
  230. array == ranges::adjacent_find(array, ranges::end(array), ranges::less{}),
  231. "");
  232. constexpr Int ints[] = {{6}, {6}, {5}, {4}};
  233. static_assert(
  234. ints == ranges::adjacent_find(ints, ranges::equal_to{}, &Int::value), "");
  235. static_assert(ranges::end(ints) ==
  236. ranges::adjacent_find(ints, ranges::less{}, &Int::value),
  237. "");
  238. }
  239. TEST(RangesTest, Count) {
  240. int array[] = {1, 2, 3, 3};
  241. EXPECT_EQ(1, ranges::count(array, array + 4, 1));
  242. EXPECT_EQ(1, ranges::count(array, array + 4, 2));
  243. EXPECT_EQ(1, ranges::count(array, array + 3, 3));
  244. EXPECT_EQ(2, ranges::count(array, array + 4, 3));
  245. Int ints[] = {{1}, {2}, {3}, {3}};
  246. EXPECT_EQ(1, ranges::count(ints, 1, &Int::value));
  247. EXPECT_EQ(1, ranges::count(ints, 2, &Int::value));
  248. EXPECT_EQ(2, ranges::count(ints, 3, &Int::value));
  249. }
  250. TEST(RangesTest, CountIf) {
  251. int array[] = {1, 2, 3, 3};
  252. EXPECT_EQ(0, ranges::count_if(array, array + 1, is_even));
  253. EXPECT_EQ(1, ranges::count_if(array, array + 2, is_even));
  254. EXPECT_EQ(1, ranges::count_if(array, array + 3, is_even));
  255. EXPECT_EQ(1, ranges::count_if(array, array + 4, is_even));
  256. Int ints[] = {{1}, {2}, {3}, {3}};
  257. EXPECT_EQ(1, ranges::count_if(ints, is_even, &Int::value));
  258. EXPECT_EQ(3, ranges::count_if(ints, is_odd, &Int::value));
  259. }
  260. TEST(RangesTest, Mismatch) {
  261. int array1[] = {1, 3, 6, 7};
  262. int array2[] = {1, 3};
  263. int array3[] = {1, 3, 5, 7};
  264. EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2),
  265. ranges::mismatch(array1, array1 + 4, array2, array2 + 2));
  266. EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2),
  267. ranges::mismatch(array1, array1 + 4, array3, array3 + 4));
  268. EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2),
  269. ranges::mismatch(array1, array2));
  270. EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2),
  271. ranges::mismatch(array1, array3));
  272. }
  273. TEST(RangesTest, Equal) {
  274. static constexpr int array1[] = {1, 3, 6, 7};
  275. static constexpr int array2[] = {1, 3, 5, 7};
  276. static_assert(ranges::equal(array1, array1 + 2, array2, array2 + 2), "");
  277. EXPECT_TRUE(ranges::equal(array1, array1 + 2, array2, array2 + 2));
  278. static_assert(!ranges::equal(array1, array1 + 4, array2, array2 + 4), "");
  279. EXPECT_FALSE(ranges::equal(array1, array1 + 4, array2, array2 + 4));
  280. static_assert(!ranges::equal(array1, array1 + 2, array2, array2 + 3), "");
  281. EXPECT_FALSE(ranges::equal(array1, array1 + 2, array2, array2 + 3));
  282. static constexpr Int ints[] = {{1}, {3}, {5}, {7}};
  283. CONSTEXPR_LAMBDA((Int lhs, int rhs) { return lhs.value == rhs; }) lambda;
  284. static_assert(ranges::equal(ints, array2, lambda), "");
  285. EXPECT_TRUE(ranges::equal(ints, array2, lambda));
  286. static_assert(
  287. ranges::equal(array2, ints, ranges::equal_to{}, identity{}, &Int::value),
  288. "");
  289. EXPECT_TRUE(
  290. ranges::equal(array2, ints, ranges::equal_to{}, identity{}, &Int::value));
  291. }
  292. TEST(RangesTest, IsPermutation) {
  293. int array1[] = {1, 3, 6, 7};
  294. int array2[] = {7, 3, 1, 6};
  295. int array3[] = {1, 3, 5, 7};
  296. EXPECT_TRUE(ranges::is_permutation(array1, array1 + 4, array2, array2 + 4));
  297. EXPECT_FALSE(ranges::is_permutation(array1, array1 + 4, array3, array3 + 4));
  298. EXPECT_TRUE(ranges::is_permutation(array1, array2));
  299. EXPECT_FALSE(ranges::is_permutation(array1, array3));
  300. Int ints1[] = {{1}, {3}, {5}, {7}};
  301. Int ints2[] = {{1}, {5}, {3}, {7}};
  302. EXPECT_TRUE(ranges::is_permutation(
  303. ints1, ints2, [](Int lhs, Int rhs) { return lhs.value == rhs.value; }));
  304. EXPECT_TRUE(
  305. ranges::is_permutation(ints1, ints2, ranges::equal_to{}, &Int::value));
  306. EXPECT_FALSE(ranges::is_permutation(array1, ints2, ranges::equal_to{}, {},
  307. &Int::value));
  308. EXPECT_TRUE(ranges::is_permutation(array3, ints2, ranges::equal_to{}, {},
  309. &Int::value));
  310. }
  311. TEST(RangesTest, Search) {
  312. int array1[] = {0, 1, 2, 3};
  313. int array2[] = {0, 1, 5, 3};
  314. int array3[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
  315. EXPECT_EQ(array3 + 3,
  316. ranges::search(array3, array3 + 12, array1, array1 + 4));
  317. EXPECT_EQ(array3 + 12,
  318. ranges::search(array3, array3 + 12, array2, array2 + 4));
  319. EXPECT_EQ(array3 + 3, ranges::search(array3, array1));
  320. EXPECT_EQ(array3 + 12, ranges::search(array3, array2));
  321. Int ints1[] = {{0}, {1}, {2}, {3}};
  322. Int ints2[] = {{0}, {1}, {5}, {3}};
  323. EXPECT_EQ(ints1 + 4, ranges::search(ints1, ints2, ranges::equal_to{},
  324. &Int::value, &Int::value));
  325. EXPECT_EQ(array3 + 3, ranges::search(array3, ints1, {}, {}, &Int::value));
  326. EXPECT_EQ(array3 + 12, ranges::search(array3, ints2, {}, {}, &Int::value));
  327. }
  328. TEST(RangesTest, SearchN) {
  329. int array[] = {0, 0, 1, 1, 2, 2};
  330. EXPECT_EQ(array, ranges::search_n(array, array + 6, 1, 0));
  331. EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 1, 1));
  332. EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 1, 2));
  333. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 1, 3));
  334. EXPECT_EQ(array, ranges::search_n(array, array + 6, 2, 0));
  335. EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 2, 1));
  336. EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 2, 2));
  337. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 2, 3));
  338. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 0));
  339. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 1));
  340. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 2));
  341. EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 3));
  342. Int ints[] = {{0}, {0}, {1}, {1}, {2}, {2}};
  343. EXPECT_EQ(ints, ranges::search_n(ints, 1, 0, {}, &Int::value));
  344. EXPECT_EQ(ints + 2, ranges::search_n(ints, 1, 1, {}, &Int::value));
  345. EXPECT_EQ(ints + 4, ranges::search_n(ints, 1, 2, {}, &Int::value));
  346. EXPECT_EQ(ints + 6, ranges::search_n(ints, 1, 3, {}, &Int::value));
  347. EXPECT_EQ(ints, ranges::search_n(ints, 2, 0, {}, &Int::value));
  348. EXPECT_EQ(ints + 2, ranges::search_n(ints, 2, 1, {}, &Int::value));
  349. EXPECT_EQ(ints + 4, ranges::search_n(ints, 2, 2, {}, &Int::value));
  350. EXPECT_EQ(ints + 6, ranges::search_n(ints, 2, 3, {}, &Int::value));
  351. EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 0, {}, &Int::value));
  352. EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 1, {}, &Int::value));
  353. EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 2, {}, &Int::value));
  354. EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 3, {}, &Int::value));
  355. }
  356. TEST(RangesTest, Copy) {
  357. int input[] = {1, 2, 3, 4, 5};
  358. int output[] = {6, 6, 6, 6, 6, 6, 6};
  359. auto equals_six = [](int i) { return i == 6; };
  360. EXPECT_EQ(output + 3, ranges::copy(input, input + 3, output));
  361. EXPECT_TRUE(std::equal(input, input + 3, output, output + 3));
  362. EXPECT_TRUE(std::all_of(output + 3, output + 7, equals_six));
  363. EXPECT_EQ(output + 5, ranges::copy(input, output));
  364. EXPECT_TRUE(std::equal(input, input + 5, output, output + 5));
  365. EXPECT_TRUE(std::all_of(output + 5, output + 7, equals_six));
  366. }
  367. TEST(RangesTest, CopyN) {
  368. int input[] = {1, 2, 3, 4, 5};
  369. int output[] = {6, 6, 6, 6, 6, 6, 6};
  370. auto equals_six = [](int i) { return i == 6; };
  371. EXPECT_EQ(output + 4, ranges::copy_n(input, 4, output));
  372. EXPECT_TRUE(std::equal(input, input + 4, output, output + 4));
  373. EXPECT_TRUE(std::all_of(output + 4, output + 7, equals_six));
  374. }
  375. TEST(RangesTest, CopyIf) {
  376. int input[] = {2, 4, 6, 8, 6};
  377. int output[] = {0, 0, 0, 0, 0, 0};
  378. auto equals_six = [](int i) { return i == 6; };
  379. auto equals_zero = [](int i) { return i == 0; };
  380. EXPECT_EQ(output + 1, ranges::copy_if(input, input + 4, output, equals_six));
  381. EXPECT_TRUE(std::all_of(output, output + 1, equals_six));
  382. EXPECT_TRUE(std::all_of(output + 1, output + 6, equals_zero));
  383. Int ints_in[] = {{2}, {4}, {6}, {8}, {6}};
  384. Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}};
  385. EXPECT_EQ(ints_out + 2,
  386. ranges::copy_if(ints_in, ints_out, equals_six, &Int::value));
  387. EXPECT_TRUE(ranges::all_of(ints_out, ints_out + 2, equals_six, &Int::value));
  388. EXPECT_TRUE(
  389. ranges::all_of(ints_out + 2, ints_out + 6, equals_zero, &Int::value));
  390. }
  391. TEST(RangesTest, CopyBackward) {
  392. int input[] = {2, 4, 6, 8, 6};
  393. int output[] = {0, 0, 0, 0, 0, 0};
  394. EXPECT_EQ(output + 1, ranges::copy_backward(input, input + 5, output + 6));
  395. EXPECT_THAT(output, ElementsAre(0, 2, 4, 6, 8, 6));
  396. Int ints_in[] = {{2}, {4}, {6}, {8}, {6}};
  397. Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}};
  398. EXPECT_EQ(ints_out, ranges::copy_backward(ints_in, ints_out + 5));
  399. EXPECT_TRUE(std::equal(ints_in, ints_in + 5, ints_out, ints_out + 5,
  400. [](Int i, Int j) { return i.value == j.value; }));
  401. }
  402. TEST(RangesTest, Move) {
  403. MoveOnlyInt input[] = {6, 6, 6, 6, 6};
  404. MoveOnlyInt output[] = {0, 0, 0, 0, 0};
  405. auto equals_zero = [](const auto& i) { return i.value == 0; };
  406. auto equals_six = [](const auto& i) { return i.value == 6; };
  407. EXPECT_EQ(output + 3, ranges::move(input, input + 3, output));
  408. EXPECT_TRUE(std::all_of(input, input + 3, equals_zero));
  409. EXPECT_TRUE(std::all_of(input + 3, input + 5, equals_six));
  410. EXPECT_TRUE(std::all_of(output, output + 3, equals_six));
  411. EXPECT_TRUE(std::all_of(output + 3, output + 5, equals_zero));
  412. for (auto& in : input)
  413. in = 6;
  414. EXPECT_EQ(output + 5, ranges::move(input, output));
  415. EXPECT_TRUE(ranges::all_of(input, equals_zero));
  416. EXPECT_TRUE(ranges::all_of(output, equals_six));
  417. }
  418. TEST(RangesTest, MoveBackward) {
  419. MoveOnlyInt input[] = {6, 6, 6, 6, 6};
  420. MoveOnlyInt output[] = {0, 0, 0, 0, 0};
  421. auto equals_zero = [](const auto& i) { return i.value == 0; };
  422. auto equals_six = [](const auto& i) { return i.value == 6; };
  423. EXPECT_EQ(output + 2, ranges::move_backward(input, input + 3, output + 5));
  424. EXPECT_TRUE(std::all_of(input, input + 3, equals_zero));
  425. EXPECT_TRUE(std::all_of(input + 3, input + 5, equals_six));
  426. EXPECT_TRUE(std::all_of(output, output + 2, equals_zero));
  427. EXPECT_TRUE(std::all_of(output + 2, output + 5, equals_six));
  428. for (auto& in : input)
  429. in = 6;
  430. EXPECT_EQ(output, ranges::move_backward(input, output + 5));
  431. EXPECT_TRUE(ranges::all_of(input, equals_zero));
  432. EXPECT_TRUE(ranges::all_of(output, equals_six));
  433. }
  434. TEST(RangesTest, SwapRanges) {
  435. int ints1[] = {0, 0, 0, 0, 0};
  436. int ints2[] = {6, 6, 6, 6, 6};
  437. // Test that swap_ranges does not exceed `last2`.
  438. EXPECT_EQ(ints2 + 3, ranges::swap_ranges(ints1, ints1 + 5, ints2, ints2 + 3));
  439. EXPECT_THAT(ints1, ElementsAre(6, 6, 6, 0, 0));
  440. EXPECT_THAT(ints2, ElementsAre(0, 0, 0, 6, 6));
  441. // Test that swap_ranges does not exceed `last1`.
  442. EXPECT_EQ(ints2 + 3, ranges::swap_ranges(ints1, ints1 + 3, ints2, ints2 + 5));
  443. EXPECT_THAT(ints1, ElementsAre(0, 0, 0, 0, 0));
  444. EXPECT_THAT(ints2, ElementsAre(6, 6, 6, 6, 6));
  445. EXPECT_EQ(ints2 + 5,
  446. ranges::swap_ranges(ints1 + 3, ints1 + 5, ints2 + 3, ints2 + 5));
  447. EXPECT_THAT(ints1, ElementsAre(0, 0, 0, 6, 6));
  448. EXPECT_THAT(ints2, ElementsAre(6, 6, 6, 0, 0));
  449. EXPECT_EQ(ints2 + 5, ranges::swap_ranges(ints1, ints2));
  450. EXPECT_THAT(ints1, ElementsAre(6, 6, 6, 0, 0));
  451. EXPECT_THAT(ints2, ElementsAre(0, 0, 0, 6, 6));
  452. }
  453. TEST(RangesTest, UnaryTransform) {
  454. int input[] = {1, 2, 3, 4, 5};
  455. auto plus_1 = [](int i) { return i + 1; };
  456. auto times_2 = [](int i) { return i * 2; };
  457. EXPECT_EQ(input + 4,
  458. ranges::transform(input + 1, input + 4, input + 1, plus_1));
  459. EXPECT_THAT(input, ElementsAre(1, 3, 4, 5, 5));
  460. int output[] = {0, 0, 0, 0, 0};
  461. EXPECT_EQ(output + 3,
  462. ranges::transform(input + 1, input + 4, output, times_2));
  463. EXPECT_THAT(output, ElementsAre(6, 8, 10, 0, 0));
  464. Int values[] = {{0}, {2}, {4}, {5}};
  465. EXPECT_EQ(values + 4,
  466. ranges::transform(values, values, times_2, &Int::value));
  467. EXPECT_THAT(values, ElementsAre(Int{0}, Int{4}, Int{8}, Int{10}));
  468. }
  469. TEST(RangesTest, BinaryTransform) {
  470. int input[] = {1, 2, 3, 4, 5};
  471. int output[] = {0, 0, 0, 0, 0};
  472. EXPECT_EQ(output + 2, ranges::transform(input, input + 2, input + 3,
  473. input + 5, output, std::plus<>{}));
  474. EXPECT_THAT(output, ElementsAre(5, 7, 0, 0, 0));
  475. EXPECT_EQ(output + 5,
  476. ranges::transform(input, input, output, std::multiplies<>{}));
  477. EXPECT_THAT(output, ElementsAre(1, 4, 9, 16, 25));
  478. Int values[] = {{0}, {2}, {4}, {5}};
  479. EXPECT_EQ(values + 4,
  480. ranges::transform(values, values, values, std::minus<>{},
  481. &Int::value, &Int::value));
  482. EXPECT_THAT(values, ElementsAre(Int{0}, Int{0}, Int{0}, Int{0}));
  483. }
  484. TEST(RangesTest, Replace) {
  485. int input[] = {0, 0, 0, 0, 0};
  486. EXPECT_EQ(input + 2, ranges::replace(input, input + 2, 0, 2));
  487. EXPECT_THAT(input, ElementsAre(2, 2, 0, 0, 0));
  488. EXPECT_EQ(input + 5, ranges::replace(input, 0, 3));
  489. EXPECT_THAT(input, ElementsAre(2, 2, 3, 3, 3));
  490. }
  491. TEST(RangesTest, ReplaceIf) {
  492. int input[] = {0, 1, 2, 3, 4};
  493. EXPECT_EQ(input + 3, ranges::replace_if(input, input + 3, is_even, 9));
  494. EXPECT_THAT(input, ElementsAre(9, 1, 9, 3, 4));
  495. EXPECT_EQ(input + 5, ranges::replace_if(input, is_odd, 0));
  496. EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 4));
  497. Int ints[] = {0, 0, 1, 1, 0};
  498. EXPECT_EQ(ints + 5, ranges::replace_if(ints, is_odd, 3, &Int::value));
  499. EXPECT_THAT(ints, ElementsAre(0, 0, 3, 3, 0));
  500. }
  501. TEST(RangesTest, ReplaceCopy) {
  502. int input[] = {0, 0, 0, 0, 0};
  503. int output[] = {1, 1, 1, 1, 1};
  504. EXPECT_EQ(input + 2, ranges::replace_copy(input, input + 2, output, 0, 2));
  505. EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 0));
  506. EXPECT_THAT(output, ElementsAre(2, 2, 1, 1, 1));
  507. EXPECT_EQ(input + 5, ranges::replace_copy(input, output, 0, 3));
  508. EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 0));
  509. EXPECT_THAT(output, ElementsAre(3, 3, 3, 3, 3));
  510. }
  511. TEST(RangesTest, ReplaceCopyIf) {
  512. Int input[] = {0, 1, 2, 3, 4};
  513. Int output[] = {0, 0, 0, 0, 0};
  514. EXPECT_EQ(output + 3, ranges::replace_copy_if(input, input + 3, output,
  515. is_even, 9, &Int::value));
  516. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  517. EXPECT_THAT(output, ElementsAre(9, 1, 9, 0, 0));
  518. EXPECT_EQ(output + 5,
  519. ranges::replace_copy_if(input, output, is_odd, 0, &Int::value));
  520. EXPECT_THAT(output, ElementsAre(0, 0, 2, 0, 4));
  521. }
  522. TEST(RangesTest, Fill) {
  523. int input[] = {1, 2, 3, 4, 5};
  524. EXPECT_EQ(input + 3, ranges::fill(input, input + 3, 0));
  525. EXPECT_THAT(input, ElementsAre(0, 0, 0, 4, 5));
  526. EXPECT_EQ(input + 5, ranges::fill(input, 1));
  527. EXPECT_THAT(input, ElementsAre(1, 1, 1, 1, 1));
  528. }
  529. TEST(RangesTest, FillN) {
  530. int input[] = {0, 0, 0, 0, 0};
  531. EXPECT_EQ(input + 5, ranges::fill_n(input, 5, 5));
  532. EXPECT_THAT(input, ElementsAre(5, 5, 5, 5, 5));
  533. EXPECT_EQ(input + 3, ranges::fill_n(input, 3, 3));
  534. EXPECT_THAT(input, ElementsAre(3, 3, 3, 5, 5));
  535. }
  536. TEST(RangesTest, Generate) {
  537. int input[] = {0, 0, 0, 0, 0};
  538. auto gen = [count = 0]() mutable { return ++count; };
  539. EXPECT_EQ(input + 3, ranges::generate(input, input + 3, gen));
  540. EXPECT_THAT(input, ElementsAre(1, 2, 3, 0, 0));
  541. EXPECT_EQ(input + 5, ranges::generate(input, gen));
  542. EXPECT_THAT(input, ElementsAre(1, 2, 3, 4, 5));
  543. }
  544. TEST(RangesTest, GenerateN) {
  545. int input[] = {0, 0, 0, 0, 0};
  546. auto gen = [count = 0]() mutable { return ++count; };
  547. EXPECT_EQ(input + 4, ranges::generate_n(input, 4, gen));
  548. EXPECT_THAT(input, ElementsAre(1, 2, 3, 4, 0));
  549. }
  550. TEST(RangesTest, Remove) {
  551. int input[] = {1, 0, 1, 1, 0};
  552. EXPECT_EQ(input + 3, ranges::remove(input + 1, input + 5, 1));
  553. EXPECT_EQ(input[0], 1);
  554. EXPECT_EQ(input[1], 0);
  555. EXPECT_EQ(input[2], 0);
  556. Int ints[] = {2, 2, 1, 1, 2, 2};
  557. EXPECT_EQ(ints + 2, ranges::remove(ints, 2, &Int::value));
  558. EXPECT_EQ(ints[0], 1);
  559. EXPECT_EQ(ints[1], 1);
  560. }
  561. TEST(RangesTest, RemoveIf) {
  562. int input[] = {0, 1, 2, 3, 4};
  563. EXPECT_EQ(input + 2, ranges::remove_if(input, input + 4, is_even));
  564. EXPECT_EQ(input[0], 1);
  565. EXPECT_EQ(input[1], 3);
  566. EXPECT_EQ(input[4], 4);
  567. Int ints[] = {2, 2, 1, 1, 2, 2};
  568. EXPECT_EQ(ints + 2, ranges::remove_if(ints, is_even, &Int::value));
  569. EXPECT_EQ(ints[0], 1);
  570. EXPECT_EQ(ints[1], 1);
  571. }
  572. TEST(RangesTest, RemoveCopy) {
  573. int input[] = {0, 1, 2, 3, 4};
  574. int output[] = {0, 0, 0, 0, 0};
  575. EXPECT_EQ(output + 1, ranges::remove_copy(input, input + 2, output, 0));
  576. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  577. EXPECT_THAT(output, ElementsAre(1, 0, 0, 0, 0));
  578. EXPECT_EQ(output + 4, ranges::remove_copy(input, output, 4));
  579. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  580. EXPECT_THAT(output, ElementsAre(0, 1, 2, 3, 0));
  581. }
  582. TEST(RangesTest, RemovCopyIf) {
  583. Int input[] = {0, 1, 2, 3, 4};
  584. Int output[] = {0, 0, 0, 0, 0};
  585. EXPECT_EQ(output + 2, ranges::remove_copy_if(input, input + 4, output,
  586. is_even, &Int::value));
  587. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  588. EXPECT_THAT(output, ElementsAre(1, 3, 0, 0, 0));
  589. EXPECT_EQ(output + 3,
  590. ranges::remove_copy_if(input, output, is_odd, &Int::value));
  591. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  592. EXPECT_THAT(output, ElementsAre(0, 2, 4, 0, 0));
  593. }
  594. TEST(RangesTest, Unique) {
  595. int input[] = {0, 0, 1, 1, 2};
  596. EXPECT_EQ(input + 2, ranges::unique(input, input + 3));
  597. EXPECT_EQ(input[0], 0);
  598. EXPECT_EQ(input[1], 1);
  599. EXPECT_EQ(input[3], 1);
  600. EXPECT_EQ(input[4], 2);
  601. Int ints[] = {2, 2, 1, 1, 2, 2};
  602. EXPECT_EQ(ints + 3, ranges::unique(ints, {}, &Int::value));
  603. EXPECT_EQ(ints[0], 2);
  604. EXPECT_EQ(ints[1], 1);
  605. EXPECT_EQ(ints[2], 2);
  606. }
  607. TEST(RangesTest, UniqueCopy) {
  608. Int input[] = {0, 0, 1, 2, 2};
  609. Int output[] = {0, 0, 0, 0, 0};
  610. EXPECT_EQ(output + 3,
  611. ranges::unique_copy(input, input + 4, output, {}, &Int::value));
  612. EXPECT_THAT(input, ElementsAre(0, 0, 1, 2, 2));
  613. EXPECT_THAT(output, ElementsAre(0, 1, 2, 0, 0));
  614. EXPECT_EQ(output + 3, ranges::unique_copy(input, output, {}, &Int::value));
  615. EXPECT_THAT(input, ElementsAre(0, 0, 1, 2, 2));
  616. EXPECT_THAT(output, ElementsAre(0, 1, 2, 0, 0));
  617. }
  618. TEST(RangesTest, Reverse) {
  619. int input[] = {0, 1, 2, 3, 4};
  620. EXPECT_EQ(input + 4, ranges::reverse(input + 2, input + 4));
  621. EXPECT_THAT(input, ElementsAre(0, 1, 3, 2, 4));
  622. EXPECT_EQ(input + 5, ranges::reverse(input));
  623. EXPECT_THAT(input, ElementsAre(4, 2, 3, 1, 0));
  624. }
  625. TEST(RangesTest, ReverseCopy) {
  626. int input[] = {0, 1, 2, 3, 4};
  627. int output[] = {0, 0, 0, 0, 0};
  628. EXPECT_EQ(output + 2, ranges::reverse_copy(input + 2, input + 4, output));
  629. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  630. EXPECT_THAT(output, ElementsAre(3, 2, 0, 0, 0));
  631. EXPECT_EQ(output + 5, ranges::reverse_copy(input, output));
  632. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  633. EXPECT_THAT(output, ElementsAre(4, 3, 2, 1, 0));
  634. }
  635. TEST(RangesTest, Rotate) {
  636. int input[] = {0, 1, 2, 3, 4};
  637. EXPECT_EQ(input + 3, ranges::rotate(input + 2, input + 3, input + 4));
  638. EXPECT_THAT(input, ElementsAre(0, 1, 3, 2, 4));
  639. EXPECT_EQ(input + 3, ranges::rotate(input, input + 2));
  640. EXPECT_THAT(input, ElementsAre(3, 2, 4, 0, 1));
  641. }
  642. TEST(RangesTest, RotateCopy) {
  643. int input[] = {0, 1, 2, 3, 4};
  644. int output[] = {0, 0, 0, 0, 0};
  645. EXPECT_EQ(output + 2,
  646. ranges::rotate_copy(input + 2, input + 3, input + 4, output));
  647. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  648. EXPECT_THAT(output, ElementsAre(3, 2, 0, 0, 0));
  649. EXPECT_EQ(output + 5, ranges::rotate_copy(input, input + 3, output));
  650. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  651. EXPECT_THAT(output, ElementsAre(3, 4, 0, 1, 2));
  652. }
  653. TEST(RangesTest, Shuffle) {
  654. int input[] = {0, 1, 2, 3, 4};
  655. // Shuffles input[2] and input[3], thus we can't be certain about their
  656. // positions.
  657. EXPECT_EQ(input + 4, ranges::shuffle(input + 2, input + 4,
  658. std::default_random_engine()));
  659. EXPECT_EQ(input[0], 0);
  660. EXPECT_EQ(input[1], 1);
  661. EXPECT_EQ(input[4], 4);
  662. EXPECT_THAT(input, ::testing::UnorderedElementsAre(0, 1, 2, 3, 4));
  663. EXPECT_EQ(input + 5, ranges::shuffle(input, std::default_random_engine()));
  664. EXPECT_THAT(input, ::testing::UnorderedElementsAre(0, 1, 2, 3, 4));
  665. }
  666. TEST(RangesTest, Sort) {
  667. int input[] = {3, 1, 2, 0, 4};
  668. EXPECT_EQ(input + 4, ranges::sort(input, input + 4));
  669. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
  670. EXPECT_EQ(input + 5, ranges::sort(input, input + 5, ranges::greater()));
  671. EXPECT_THAT(input, ElementsAre(4, 3, 2, 1, 0));
  672. Int ints[] = {6, 7, 9, 8, 5};
  673. EXPECT_EQ(ints + 5, ranges::sort(ints, {}, &Int::value));
  674. EXPECT_THAT(ints, ElementsAre(5, 6, 7, 8, 9));
  675. EXPECT_EQ(ints + 5, ranges::sort(ints, ranges::greater(), &Int::value));
  676. EXPECT_THAT(ints, ElementsAre(9, 8, 7, 6, 5));
  677. }
  678. TEST(RangesTest, StableSort) {
  679. // Integer divide each element by 2 to check stability of elements that
  680. // compare equal.
  681. auto idiv2 = [](int i) { return i / 2; };
  682. int input[] = {3, 1, 2, 0, 4};
  683. EXPECT_EQ(input + 4, ranges::stable_sort(input, input + 4, {}, idiv2));
  684. EXPECT_THAT(input, ElementsAre(1, 0, 3, 2, 4));
  685. EXPECT_EQ(input + 5,
  686. ranges::stable_sort(input, input + 5, ranges::greater()));
  687. EXPECT_THAT(input, ElementsAre(4, 3, 2, 1, 0));
  688. auto Idiv2 = [](Int i) { return i.value / 2; };
  689. Int ints[] = {6, 7, 9, 8, 5};
  690. EXPECT_EQ(ints + 5, ranges::stable_sort(ints, {}, Idiv2));
  691. EXPECT_THAT(ints, ElementsAre(5, 6, 7, 9, 8));
  692. EXPECT_EQ(ints + 5, ranges::stable_sort(ints, ranges::greater(), Idiv2));
  693. EXPECT_THAT(ints, ElementsAre(9, 8, 6, 7, 5));
  694. }
  695. TEST(RangesTest, PartialSort) {
  696. int input[] = {3, 1, 2, 0, 4};
  697. EXPECT_EQ(input + 4, ranges::partial_sort(input, input + 2, input + 4));
  698. EXPECT_EQ(input[0], 0);
  699. EXPECT_EQ(input[1], 1);
  700. EXPECT_EQ(input + 5, ranges::partial_sort(input, input + 3, input + 5,
  701. ranges::greater()));
  702. EXPECT_EQ(input[0], 4);
  703. EXPECT_EQ(input[1], 3);
  704. EXPECT_EQ(input[2], 2);
  705. Int ints[] = {6, 7, 9, 8, 5};
  706. EXPECT_EQ(ints + 5, ranges::partial_sort(ints, ints + 4, {}, &Int::value));
  707. EXPECT_EQ(ints[0], 5);
  708. EXPECT_EQ(ints[1], 6);
  709. EXPECT_EQ(ints[2], 7);
  710. EXPECT_EQ(ints[3], 8);
  711. EXPECT_EQ(ints + 5, ranges::partial_sort(ints, ints + 3, ranges::greater(),
  712. &Int::value));
  713. EXPECT_EQ(ints[0], 9);
  714. EXPECT_EQ(ints[1], 8);
  715. EXPECT_EQ(ints[2], 7);
  716. }
  717. TEST(RangesTest, PartialSortCopy) {
  718. int input[] = {3, 1, 2, 0, 4};
  719. int output[] = {0, 0, 0, 0, 0};
  720. EXPECT_EQ(output + 2,
  721. ranges::partial_sort_copy(input, input + 2, output, output + 4));
  722. EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
  723. EXPECT_THAT(output, ElementsAre(1, 3, 0, 0, 0));
  724. EXPECT_EQ(output + 5,
  725. ranges::partial_sort_copy(input, input + 3, output + 3, output + 5,
  726. ranges::greater()));
  727. EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
  728. EXPECT_THAT(output, ElementsAre(1, 3, 0, 3, 2));
  729. Int ints[] = {3, 1, 2, 0, 4};
  730. Int outs[] = {0, 0, 0};
  731. EXPECT_EQ(outs + 3, ranges::partial_sort_copy(ints, outs, {}, &Int::value,
  732. &Int::value));
  733. EXPECT_THAT(ints, ElementsAre(3, 1, 2, 0, 4));
  734. EXPECT_THAT(outs, ElementsAre(0, 1, 2));
  735. EXPECT_EQ(outs + 3, ranges::partial_sort_copy(ints, outs, ranges::greater(),
  736. &Int::value, &Int::value));
  737. EXPECT_THAT(ints, ElementsAre(3, 1, 2, 0, 4));
  738. EXPECT_THAT(outs, ElementsAre(4, 3, 2));
  739. EXPECT_EQ(outs + 3,
  740. ranges::partial_sort_copy(input, outs, {}, {}, &Int::value));
  741. }
  742. TEST(RangesTest, IsSorted) {
  743. constexpr int input[] = {3, 1, 2, 0, 4};
  744. static_assert(ranges::is_sorted(input + 1, input + 3), "");
  745. static_assert(!ranges::is_sorted(input + 1, input + 4), "");
  746. static_assert(ranges::is_sorted(input, input + 2, ranges::greater()), "");
  747. constexpr Int ints[] = {0, 1, 2, 3, 4};
  748. static_assert(ranges::is_sorted(ints, {}, &Int::value), "");
  749. static_assert(!ranges::is_sorted(ints, ranges::greater(), &Int::value), "");
  750. }
  751. TEST(RangesTest, IsSortedUntil) {
  752. constexpr int input[] = {3, 1, 2, 0, 4};
  753. static_assert(input + 3 == ranges::is_sorted_until(input + 1, input + 3), "");
  754. static_assert(input + 3 == ranges::is_sorted_until(input + 1, input + 4), "");
  755. static_assert(
  756. input + 2 == ranges::is_sorted_until(input, input + 2, ranges::greater()),
  757. "");
  758. constexpr Int ints[] = {0, 1, 2, 3, 4};
  759. static_assert(ints + 5 == ranges::is_sorted_until(ints, {}, &Int::value), "");
  760. static_assert(
  761. ints + 1 == ranges::is_sorted_until(ints, ranges::greater(), &Int::value),
  762. "");
  763. }
  764. TEST(RangesTest, NthElement) {
  765. int input[] = {3, 1, 2, 0, 4};
  766. EXPECT_EQ(input + 5, ranges::nth_element(input, input + 2, input + 5));
  767. EXPECT_THAT(input, ElementsAre(Lt(2), Lt(2), 2, Gt(2), Gt(2)));
  768. Int ints[] = {0, 1, 2, 3, 4};
  769. EXPECT_EQ(ints + 5, ranges::nth_element(ints, ints + 2, ranges::greater(),
  770. &Int::value));
  771. EXPECT_THAT(ints, ElementsAre(Gt(2), Gt(2), 2, Lt(2), Lt(2)));
  772. }
  773. TEST(RangesTest, LowerBound) {
  774. int array[] = {0, 0, 1, 1, 2, 2};
  775. EXPECT_EQ(array, ranges::lower_bound(array, array + 6, -1));
  776. EXPECT_EQ(array, ranges::lower_bound(array, array + 6, 0));
  777. EXPECT_EQ(array + 2, ranges::lower_bound(array, array + 6, 1));
  778. EXPECT_EQ(array + 4, ranges::lower_bound(array, array + 6, 2));
  779. EXPECT_EQ(array + 6, ranges::lower_bound(array, array + 6, 3));
  780. Int ints[] = {0, 0, 1, 1, 2, 2};
  781. EXPECT_EQ(ints, ranges::lower_bound(ints, -1, {}, &Int::value));
  782. EXPECT_EQ(ints, ranges::lower_bound(ints, 0, {}, &Int::value));
  783. EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, {}, &Int::value));
  784. EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 2, {}, &Int::value));
  785. EXPECT_EQ(ints + 6, ranges::lower_bound(ints, 3, {}, &Int::value));
  786. const auto proj = [](const Int& i) { return 2 - i.value; };
  787. EXPECT_EQ(ints, ranges::lower_bound(ints, 3, ranges::greater{}, proj));
  788. EXPECT_EQ(ints, ranges::lower_bound(ints, 2, ranges::greater{}, proj));
  789. EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, ranges::greater{}, proj));
  790. EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 0, ranges::greater{}, proj));
  791. EXPECT_EQ(ints + 6, ranges::lower_bound(ints, -1, ranges::greater{}, proj));
  792. }
  793. TEST(RangesTest, UpperBound) {
  794. int array[] = {0, 0, 1, 1, 2, 2};
  795. EXPECT_EQ(array, ranges::upper_bound(array, array + 6, -1));
  796. EXPECT_EQ(array + 2, ranges::upper_bound(array, array + 6, 0));
  797. EXPECT_EQ(array + 4, ranges::upper_bound(array, array + 6, 1));
  798. EXPECT_EQ(array + 6, ranges::upper_bound(array, array + 6, 2));
  799. EXPECT_EQ(array + 6, ranges::upper_bound(array, array + 6, 3));
  800. Int ints[] = {0, 0, 1, 1, 2, 2};
  801. EXPECT_EQ(ints, ranges::upper_bound(ints, -1, {}, &Int::value));
  802. EXPECT_EQ(ints + 2, ranges::upper_bound(ints, 0, {}, &Int::value));
  803. EXPECT_EQ(ints + 4, ranges::upper_bound(ints, 1, {}, &Int::value));
  804. EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 2, {}, &Int::value));
  805. EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 3, {}, &Int::value));
  806. const auto proj = [](const Int& i) { return 2 - i.value; };
  807. EXPECT_EQ(ints, ranges::upper_bound(ints, 3, ranges::greater{}, proj));
  808. EXPECT_EQ(ints + 2, ranges::upper_bound(ints, 2, ranges::greater{}, proj));
  809. EXPECT_EQ(ints + 4, ranges::upper_bound(ints, 1, ranges::greater{}, proj));
  810. EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 0, ranges::greater{}, proj));
  811. EXPECT_EQ(ints + 6, ranges::upper_bound(ints, -1, ranges::greater{}, proj));
  812. }
  813. TEST(RangesTest, EqualRange) {
  814. int array[] = {0, 0, 1, 1, 2, 2};
  815. EXPECT_THAT(ranges::equal_range(array, array + 6, -1), Pair(array, array));
  816. EXPECT_THAT(ranges::equal_range(array, array + 6, 0), Pair(array, array + 2));
  817. EXPECT_THAT(ranges::equal_range(array, array + 6, 1),
  818. Pair(array + 2, array + 4));
  819. EXPECT_THAT(ranges::equal_range(array, array + 6, 2),
  820. Pair(array + 4, array + 6));
  821. EXPECT_THAT(ranges::equal_range(array, array + 6, 3),
  822. Pair(array + 6, array + 6));
  823. Int ints[] = {0, 0, 1, 1, 2, 2};
  824. EXPECT_THAT(ranges::equal_range(ints, -1, {}, &Int::value), Pair(ints, ints));
  825. EXPECT_THAT(ranges::equal_range(ints, 0, {}, &Int::value),
  826. Pair(ints, ints + 2));
  827. EXPECT_THAT(ranges::equal_range(ints, 1, {}, &Int::value),
  828. Pair(ints + 2, ints + 4));
  829. EXPECT_THAT(ranges::equal_range(ints, 2, {}, &Int::value),
  830. Pair(ints + 4, ints + 6));
  831. EXPECT_THAT(ranges::equal_range(ints, 3, {}, &Int::value),
  832. Pair(ints + 6, ints + 6));
  833. const auto proj = [](const Int& i) { return 2 - i.value; };
  834. EXPECT_THAT(ranges::equal_range(ints, 3, ranges::greater{}, proj),
  835. Pair(ints, ints));
  836. EXPECT_THAT(ranges::equal_range(ints, 2, ranges::greater{}, proj),
  837. Pair(ints, ints + 2));
  838. EXPECT_THAT(ranges::equal_range(ints, 1, ranges::greater{}, proj),
  839. Pair(ints + 2, ints + 4));
  840. EXPECT_THAT(ranges::equal_range(ints, 0, ranges::greater{}, proj),
  841. Pair(ints + 4, ints + 6));
  842. EXPECT_THAT(ranges::equal_range(ints, -1, ranges::greater{}, proj),
  843. Pair(ints + 6, ints + 6));
  844. }
  845. TEST(RangesTest, BinarySearch) {
  846. int array[] = {0, 0, 1, 1, 2, 2};
  847. EXPECT_FALSE(ranges::binary_search(array, array + 6, -1));
  848. EXPECT_TRUE(ranges::binary_search(array, array + 6, 0));
  849. EXPECT_TRUE(ranges::binary_search(array, array + 6, 1));
  850. EXPECT_TRUE(ranges::binary_search(array, array + 6, 2));
  851. EXPECT_FALSE(ranges::binary_search(array, array + 6, 3));
  852. Int ints[] = {0, 0, 1, 1, 2, 2};
  853. EXPECT_FALSE(ranges::binary_search(ints, -1, {}, &Int::value));
  854. EXPECT_TRUE(ranges::binary_search(ints, 0, {}, &Int::value));
  855. EXPECT_TRUE(ranges::binary_search(ints, 1, {}, &Int::value));
  856. EXPECT_TRUE(ranges::binary_search(ints, 2, {}, &Int::value));
  857. EXPECT_FALSE(ranges::binary_search(ints, 3, {}, &Int::value));
  858. const auto proj = [](const Int& i) { return 2 - i.value; };
  859. EXPECT_FALSE(ranges::binary_search(ints, 3, ranges::greater{}, proj));
  860. EXPECT_TRUE(ranges::binary_search(ints, 2, ranges::greater{}, proj));
  861. EXPECT_TRUE(ranges::binary_search(ints, 1, ranges::greater{}, proj));
  862. EXPECT_TRUE(ranges::binary_search(ints, 0, ranges::greater{}, proj));
  863. EXPECT_FALSE(ranges::binary_search(ints, -1, ranges::greater{}, proj));
  864. }
  865. TEST(RangesTest, IsPartitioned) {
  866. int input[] = {1, 3, 5, 0, 4, 2};
  867. EXPECT_TRUE(ranges::is_partitioned(input, input, is_odd));
  868. EXPECT_TRUE(ranges::is_partitioned(input, input + 6, is_odd));
  869. EXPECT_TRUE(ranges::is_partitioned(input, input, is_even));
  870. EXPECT_FALSE(ranges::is_partitioned(input, input + 6, is_even));
  871. Int ints[] = {1, 0, 4, 3, 2};
  872. auto lt_2 = [](const Int& i) { return i.value < 2; };
  873. EXPECT_TRUE(ranges::is_partitioned(ints, lt_2, &Int::value));
  874. }
  875. TEST(RangesTest, Partition) {
  876. int input[] = {3, 1, 2, 0, 4};
  877. EXPECT_EQ(input + 3, ranges::partition(input, input + 5, is_even));
  878. EXPECT_TRUE(is_even(input[0]));
  879. EXPECT_TRUE(is_even(input[1]));
  880. EXPECT_TRUE(is_even(input[2]));
  881. EXPECT_TRUE(is_odd(input[3]));
  882. EXPECT_TRUE(is_odd(input[4]));
  883. Int ints[] = {6, 7, 9, 8, 5};
  884. EXPECT_EQ(ints + 3, ranges::partition(ints, is_odd, &Int::value));
  885. EXPECT_TRUE(is_odd(ints[0].value));
  886. EXPECT_TRUE(is_odd(ints[1].value));
  887. EXPECT_TRUE(is_odd(ints[2].value));
  888. EXPECT_TRUE(is_even(ints[3].value));
  889. EXPECT_TRUE(is_even(ints[4].value));
  890. }
  891. TEST(RangesTest, StablePartition) {
  892. int input[] = {3, 1, 2, 0, 4};
  893. EXPECT_EQ(input + 3, ranges::stable_partition(input, input + 5, is_even));
  894. EXPECT_THAT(input, ElementsAre(2, 0, 4, 3, 1));
  895. Int ints[] = {6, 7, 9, 8, 5};
  896. EXPECT_EQ(ints + 3, ranges::stable_partition(ints, is_odd, &Int::value));
  897. EXPECT_THAT(ints, ElementsAre(7, 9, 5, 6, 8));
  898. }
  899. TEST(RangesTest, PartitionCopy) {
  900. int input[] = {3, 1, 2, 0, 4};
  901. int evens[5] = {};
  902. int odds[5] = {};
  903. EXPECT_THAT(ranges::partition_copy(input, input + 5, evens, odds, is_even),
  904. Pair(evens + 3, odds + 2));
  905. EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
  906. EXPECT_THAT(evens, ElementsAre(2, 0, 4, 0, 0));
  907. EXPECT_THAT(odds, ElementsAre(3, 1, 0, 0, 0));
  908. Int ints[] = {6, 7, 9, 8, 5};
  909. Int odd_ints[5] = {};
  910. Int even_ints[5] = {};
  911. EXPECT_THAT(
  912. ranges::partition_copy(ints, odd_ints, even_ints, is_odd, &Int::value),
  913. Pair(odd_ints + 3, even_ints + 2));
  914. EXPECT_THAT(ints, ElementsAre(6, 7, 9, 8, 5));
  915. EXPECT_THAT(odd_ints, ElementsAre(7, 9, 5, 0, 0));
  916. EXPECT_THAT(even_ints, ElementsAre(6, 8, 0, 0, 0));
  917. }
  918. TEST(RangesTest, PartitionPoint) {
  919. int input[] = {1, 3, 5, 0, 4, 2};
  920. EXPECT_EQ(input, ranges::partition_point(input, input, is_odd));
  921. EXPECT_EQ(input + 3, ranges::partition_point(input, input + 6, is_odd));
  922. EXPECT_EQ(input, ranges::partition_point(input, input, is_even));
  923. Int ints[] = {1, 0, 4, 3, 2};
  924. auto lt_2 = [](const Int& i) { return i.value < 2; };
  925. EXPECT_EQ(ints + 2, ranges::partition_point(ints, lt_2, &Int::value));
  926. }
  927. TEST(RangesTest, Merge) {
  928. int input1[] = {0, 2, 4, 6, 8};
  929. int input2[] = {1, 3, 5, 7, 9};
  930. int output[10];
  931. EXPECT_EQ(output + 10,
  932. ranges::merge(input1, input1 + 5, input2, input2 + 5, output));
  933. EXPECT_THAT(output, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  934. Int ints1[] = {0, 2, 4, 6, 8};
  935. Int ints2[] = {1, 3, 5, 7, 9};
  936. Int outs[10];
  937. EXPECT_EQ(outs + 10,
  938. ranges::merge(ints1, ints2, outs, {}, &Int::value, &Int::value));
  939. EXPECT_THAT(outs, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  940. EXPECT_EQ(outs + 10, ranges::merge(input1, ints1, outs, {}, {}, &Int::value));
  941. EXPECT_THAT(outs, ElementsAre(0, 0, 2, 2, 4, 4, 6, 6, 8, 8));
  942. EXPECT_EQ(outs + 10, ranges::merge(ints2, input2, outs, {}, &Int::value, {}));
  943. EXPECT_THAT(outs, ElementsAre(1, 1, 3, 3, 5, 5, 7, 7, 9, 9));
  944. }
  945. TEST(RangesTest, InplaceMerge) {
  946. int input[] = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
  947. EXPECT_EQ(input + 10, ranges::inplace_merge(input, input + 5, input + 10));
  948. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  949. Int ints[] = {8, 6, 4, 2, 0, 9, 7, 5, 3, 1};
  950. EXPECT_EQ(ints + 10, ranges::inplace_merge(ints, ints + 5, ranges::greater(),
  951. &Int::value));
  952. EXPECT_THAT(ints, ElementsAre(9, 8, 7, 6, 5, 4, 3, 2, 1, 0));
  953. }
  954. TEST(RangesTest, Includes) {
  955. int evens[] = {0, 2, 4, 6, 8};
  956. int odds[] = {1, 3, 5, 7, 9};
  957. int fours[] = {0, 4, 8};
  958. EXPECT_TRUE(ranges::includes(evens, evens + 5, fours, fours + 3));
  959. EXPECT_FALSE(ranges::includes(fours, fours + 3, evens, evens + 5));
  960. EXPECT_FALSE(ranges::includes(evens, evens + 5, odds, odds + 5));
  961. EXPECT_FALSE(ranges::includes(odds, odds + 5, evens, evens + 5));
  962. Int even_ints[] = {0, 2, 4, 6, 8};
  963. Int odd_ints[] = {1, 3, 5, 7, 9};
  964. EXPECT_TRUE(ranges::includes(even_ints, fours, {}, &Int::value));
  965. EXPECT_FALSE(ranges::includes(fours, even_ints, {}, {}, &Int::value));
  966. EXPECT_FALSE(
  967. ranges::includes(even_ints, odd_ints, {}, &Int::value, &Int::value));
  968. EXPECT_FALSE(
  969. ranges::includes(odd_ints, even_ints, {}, &Int::value, &Int::value));
  970. }
  971. TEST(RangesTest, SetUnion) {
  972. int evens[] = {0, 2, 4, 6, 8};
  973. int odds[] = {1, 3, 5, 7, 9};
  974. int fours[] = {0, 4, 8};
  975. int result[10];
  976. EXPECT_EQ(result + 10,
  977. ranges::set_union(evens, evens + 5, odds, odds + 5, result));
  978. EXPECT_THAT(result, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  979. EXPECT_EQ(result + 5,
  980. ranges::set_union(evens, evens + 5, fours, fours + 3, result));
  981. EXPECT_THAT(make_vector(result, result + 5), ElementsAre(0, 2, 4, 6, 8));
  982. Int even_ints[] = {0, 2, 4, 6, 8};
  983. Int odd_ints[] = {1, 3, 5, 7, 9};
  984. Int result_ints[10];
  985. EXPECT_EQ(result_ints + 10,
  986. ranges::set_union(even_ints, odd_ints, result_ints, {}, &Int::value,
  987. &Int::value));
  988. EXPECT_THAT(result_ints, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  989. EXPECT_EQ(result_ints + 5,
  990. ranges::set_union(even_ints, fours, result_ints, {}, &Int::value));
  991. EXPECT_THAT(make_vector(result_ints, result_ints + 5),
  992. ElementsAre(0, 2, 4, 6, 8));
  993. EXPECT_EQ(result_ints + 8, ranges::set_union(fours, odd_ints, result_ints, {},
  994. {}, &Int::value));
  995. EXPECT_THAT(make_vector(result_ints, result_ints + 8),
  996. ElementsAre(0, 1, 3, 4, 5, 7, 8, 9));
  997. }
  998. TEST(RangesTest, SetIntersection) {
  999. int evens[] = {0, 2, 4, 6, 8};
  1000. int odds[] = {1, 3, 5, 7, 9};
  1001. int fours[] = {0, 4, 8};
  1002. int result[10];
  1003. EXPECT_EQ(result,
  1004. ranges::set_intersection(evens, evens + 5, odds, odds + 5, result));
  1005. EXPECT_EQ(result + 3, ranges::set_intersection(evens, evens + 5, fours,
  1006. fours + 3, result));
  1007. EXPECT_THAT(make_vector(result, result + 3), ElementsAre(0, 4, 8));
  1008. Int even_ints[] = {0, 2, 4, 6, 8};
  1009. Int odd_ints[] = {1, 3, 5, 7, 9};
  1010. Int result_ints[10];
  1011. EXPECT_EQ(result_ints,
  1012. ranges::set_intersection(even_ints, odd_ints, result_ints, {},
  1013. &Int::value, &Int::value));
  1014. EXPECT_EQ(
  1015. result_ints + 3,
  1016. ranges::set_intersection(even_ints, fours, result_ints, {}, &Int::value));
  1017. EXPECT_THAT(make_vector(result_ints, result_ints + 3), ElementsAre(0, 4, 8));
  1018. EXPECT_EQ(result_ints, ranges::set_intersection(fours, odd_ints, result_ints,
  1019. {}, {}, &Int::value));
  1020. }
  1021. TEST(RangesTest, SetDifference) {
  1022. int evens[] = {0, 2, 4, 6, 8};
  1023. int odds[] = {1, 3, 5, 7, 9};
  1024. int fours[] = {0, 4, 8};
  1025. int result[5];
  1026. EXPECT_EQ(result + 5,
  1027. ranges::set_difference(evens, evens + 5, odds, odds + 5, result));
  1028. EXPECT_THAT(result, ElementsAre(0, 2, 4, 6, 8));
  1029. EXPECT_EQ(result + 2,
  1030. ranges::set_difference(evens, evens + 5, fours, fours + 3, result));
  1031. EXPECT_THAT(make_vector(result, result + 2), ElementsAre(2, 6));
  1032. Int even_ints[] = {0, 2, 4, 6, 8};
  1033. Int odd_ints[] = {1, 3, 5, 7, 9};
  1034. Int result_ints[5];
  1035. EXPECT_EQ(result_ints + 5,
  1036. ranges::set_difference(even_ints, odd_ints, result_ints, {},
  1037. &Int::value, &Int::value));
  1038. EXPECT_THAT(result_ints, ElementsAre(0, 2, 4, 6, 8));
  1039. EXPECT_EQ(
  1040. result_ints + 2,
  1041. ranges::set_difference(even_ints, fours, result_ints, {}, &Int::value));
  1042. EXPECT_THAT(make_vector(result_ints, result_ints + 2), ElementsAre(2, 6));
  1043. EXPECT_EQ(result_ints + 3,
  1044. ranges::set_difference(fours, odd_ints, result_ints, {}, {},
  1045. &Int::value));
  1046. EXPECT_THAT(make_vector(result_ints, result_ints + 3), ElementsAre(0, 4, 8));
  1047. }
  1048. TEST(RangesTest, SetSymmetricDifference) {
  1049. int evens[] = {0, 2, 4, 6, 8};
  1050. int odds[] = {1, 3, 5, 7, 9};
  1051. int fours[] = {0, 4, 8};
  1052. int result[10];
  1053. EXPECT_EQ(result + 10, ranges::set_symmetric_difference(
  1054. evens, evens + 5, odds, odds + 5, result));
  1055. EXPECT_THAT(result, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  1056. EXPECT_EQ(result + 2, ranges::set_symmetric_difference(
  1057. evens, evens + 5, fours, fours + 3, result));
  1058. EXPECT_THAT(make_vector(result, result + 2), ElementsAre(2, 6));
  1059. Int even_ints[] = {0, 2, 4, 6, 8};
  1060. Int odd_ints[] = {1, 3, 5, 7, 9};
  1061. Int result_ints[10];
  1062. EXPECT_EQ(result_ints + 10,
  1063. ranges::set_symmetric_difference(even_ints, odd_ints, result_ints,
  1064. {}, &Int::value, &Int::value));
  1065. EXPECT_THAT(result_ints, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  1066. EXPECT_EQ(result_ints + 2,
  1067. ranges::set_symmetric_difference(even_ints, fours, result_ints, {},
  1068. &Int::value));
  1069. EXPECT_THAT(make_vector(result_ints, result_ints + 2), ElementsAre(2, 6));
  1070. EXPECT_EQ(result_ints + 8,
  1071. ranges::set_symmetric_difference(fours, odd_ints, result_ints, {},
  1072. {}, &Int::value));
  1073. EXPECT_THAT(make_vector(result_ints, result_ints + 8),
  1074. ElementsAre(0, 1, 3, 4, 5, 7, 8, 9));
  1075. }
  1076. TEST(RangesTest, PushHeap) {
  1077. int heap[] = {6, 4, 3, 2, 1, 0, 5};
  1078. EXPECT_EQ(heap + 7, ranges::push_heap(heap, heap + 7));
  1079. EXPECT_THAT(heap, ElementsAre(6, Ge(4), Ge(4), Le(3), Le(3), Le(3), Le(3)));
  1080. Int heap_int[] = {1, 2, 3, 4, 5, 6, 0};
  1081. EXPECT_EQ(heap_int + 7,
  1082. ranges::push_heap(heap_int, ranges::greater(), &Int::value));
  1083. EXPECT_THAT(heap_int, ElementsAre(0, 2, 1, 4, 5, 6, 3));
  1084. EXPECT_THAT(heap_int,
  1085. ElementsAre(0, Le(2), Le(2), Ge(3), Ge(3), Ge(3), Ge(3)));
  1086. }
  1087. TEST(RangesTest, PopHeap) {
  1088. int heap[] = {6, 5, 4, 3, 2, 1, 0};
  1089. EXPECT_EQ(heap + 7, ranges::pop_heap(heap, heap + 7));
  1090. EXPECT_THAT(heap, ElementsAre(5, Ge(3), Ge(3), Le(2), Le(2), Le(2), 6));
  1091. Int heap_int[] = {0, 1, 2, 3, 4, 5, 6};
  1092. EXPECT_EQ(heap_int + 7,
  1093. ranges::pop_heap(heap_int, ranges::greater(), &Int::value));
  1094. EXPECT_THAT(heap_int, ElementsAre(1, Le(3), Le(3), Ge(4), Ge(4), Ge(4), 0));
  1095. }
  1096. TEST(RangesTest, MakeHeap) {
  1097. int heap[] = {0, 1, 2, 3, 4, 5, 6};
  1098. EXPECT_EQ(heap + 7, ranges::make_heap(heap, heap + 7));
  1099. EXPECT_THAT(heap, ElementsAre(6, Ge(4), Ge(4), Le(3), Le(3), Le(3), Le(3)));
  1100. Int heap_int[] = {6, 5, 4, 3, 2, 1, 0};
  1101. EXPECT_EQ(heap_int + 7,
  1102. ranges::make_heap(heap_int, ranges::greater(), &Int::value));
  1103. EXPECT_THAT(heap_int,
  1104. ElementsAre(0, Le(2), Le(2), Ge(3), Ge(3), Ge(3), Ge(3)));
  1105. }
  1106. TEST(RangesTest, SortHeap) {
  1107. int heap[] = {6, 4, 5, 0, 1, 2, 3};
  1108. EXPECT_EQ(heap + 7, ranges::sort_heap(heap, heap + 7));
  1109. EXPECT_THAT(heap, ElementsAre(0, 1, 2, 3, 4, 5, 6));
  1110. Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
  1111. EXPECT_EQ(heap_int + 7,
  1112. ranges::sort_heap(heap_int, ranges::greater(), &Int::value));
  1113. EXPECT_THAT(heap_int, ElementsAre(6, 5, 4, 3, 2, 1, 0));
  1114. }
  1115. TEST(RangesTest, IsHeap) {
  1116. int heap[] = {6, 4, 5, 0, 1, 2, 3};
  1117. EXPECT_TRUE(ranges::is_heap(heap, heap + 7));
  1118. EXPECT_FALSE(ranges::is_heap(heap, heap + 7, ranges::greater()));
  1119. Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
  1120. EXPECT_TRUE(ranges::is_heap(heap_int, ranges::greater(), &Int::value));
  1121. EXPECT_FALSE(ranges::is_heap(heap_int, {}, &Int::value));
  1122. }
  1123. TEST(RangesTest, IsHeapUntil) {
  1124. int heap[] = {6, 4, 5, 0, 1, 2, 3};
  1125. EXPECT_EQ(heap + 7, ranges::is_heap_until(heap, heap + 7));
  1126. EXPECT_EQ(heap + 1, ranges::is_heap_until(heap, heap + 7, ranges::greater()));
  1127. Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
  1128. EXPECT_EQ(heap_int + 7,
  1129. ranges::is_heap_until(heap_int, ranges::greater(), &Int::value));
  1130. EXPECT_EQ(heap_int + 1, ranges::is_heap_until(heap_int, {}, &Int::value));
  1131. }
  1132. TEST(RangesTest, Min) {
  1133. constexpr int k1 = 1;
  1134. constexpr int k2 = 2;
  1135. static_assert(&ranges::min(k1, k1) == &k1, "");
  1136. static_assert(&ranges::min(k1, k2) == &k1, "");
  1137. static_assert(&ranges::min(k2, k1) == &k1, "");
  1138. static_assert(&ranges::min(k2, k2) == &k2, "");
  1139. constexpr Int k3 = 3;
  1140. constexpr Int k4 = 4;
  1141. static_assert(&ranges::min(k3, k3, ranges::greater(), &Int::value) == &k3,
  1142. "");
  1143. static_assert(&ranges::min(k3, k4, ranges::greater(), &Int::value) == &k4,
  1144. "");
  1145. static_assert(&ranges::min(k4, k3, ranges::greater(), &Int::value) == &k4,
  1146. "");
  1147. static_assert(&ranges::min(k4, k4, ranges::greater(), &Int::value) == &k4,
  1148. "");
  1149. constexpr Int array[] = {2, 6, 4, 3, 5, 1};
  1150. static_assert(ranges::min({5, 3, 4, 2, 1, 6}) == 1, "");
  1151. static_assert(ranges::min(array, ranges::greater(), &Int::value) == 6, "");
  1152. }
  1153. TEST(RangesTest, Max) {
  1154. constexpr int k1 = 1;
  1155. constexpr int k2 = 2;
  1156. static_assert(&ranges::max(k1, k2) == &k2, "");
  1157. static_assert(&ranges::max(k1, k2) == &k2, "");
  1158. static_assert(&ranges::max(k2, k1) == &k2, "");
  1159. static_assert(&ranges::max(k2, k1) == &k2, "");
  1160. constexpr Int k3 = 3;
  1161. constexpr Int k4 = 4;
  1162. static_assert(&ranges::max(k3, k3, ranges::greater(), &Int::value) == &k3,
  1163. "");
  1164. static_assert(&ranges::max(k3, k4, ranges::greater(), &Int::value) == &k3,
  1165. "");
  1166. static_assert(&ranges::max(k4, k3, ranges::greater(), &Int::value) == &k3,
  1167. "");
  1168. static_assert(&ranges::max(k4, k4, ranges::greater(), &Int::value) == &k4,
  1169. "");
  1170. constexpr Int array[] = {2, 6, 4, 3, 5, 1};
  1171. static_assert(ranges::max({5, 3, 4, 2, 1, 6}) == 6, "");
  1172. static_assert(ranges::max(array, ranges::greater(), &Int::value) == 1, "");
  1173. }
  1174. TEST(RangesTest, Minmax) {
  1175. constexpr int k1 = 1;
  1176. constexpr int k2 = 2;
  1177. static_assert(&ranges::minmax(k1, k1).first == &k1, "");
  1178. static_assert(&ranges::minmax(k1, k1).second == &k1, "");
  1179. static_assert(&ranges::minmax(k1, k2).first == &k1, "");
  1180. static_assert(&ranges::minmax(k1, k2).second == &k2, "");
  1181. static_assert(&ranges::minmax(k2, k1).first == &k1, "");
  1182. static_assert(&ranges::minmax(k2, k1).second == &k2, "");
  1183. static_assert(&ranges::minmax(k2, k2).first == &k2, "");
  1184. static_assert(&ranges::minmax(k2, k2).second == &k2, "");
  1185. static constexpr Int k3 = 3;
  1186. static constexpr Int k4 = 4;
  1187. {
  1188. constexpr auto kResult =
  1189. ranges::minmax(k3, k3, ranges::greater(), &Int::value);
  1190. static_assert(&kResult.first == &k3, "");
  1191. static_assert(&kResult.second == &k3, "");
  1192. }
  1193. {
  1194. constexpr auto kResult =
  1195. ranges::minmax(k3, k4, ranges::greater(), &Int::value);
  1196. static_assert(&kResult.first == &k4, "");
  1197. static_assert(&kResult.second == &k3, "");
  1198. }
  1199. {
  1200. constexpr auto kResult =
  1201. ranges::minmax(k4, k3, ranges::greater(), &Int::value);
  1202. static_assert(&kResult.first == &k4, "");
  1203. static_assert(&kResult.second == &k3, "");
  1204. }
  1205. {
  1206. constexpr auto kResult =
  1207. ranges::minmax(k4, k4, ranges::greater(), &Int::value);
  1208. static_assert(&kResult.first == &k4, "");
  1209. static_assert(&kResult.second == &k4, "");
  1210. }
  1211. static_assert(ranges::minmax({5, 3, 4, 2, 1, 6}).first == 1, "");
  1212. static_assert(ranges::minmax({5, 3, 4, 2, 1, 6}).second == 6, "");
  1213. constexpr Int array[] = {2, 6, 4, 3, 5, 1};
  1214. static_assert(
  1215. ranges::minmax(array, ranges::greater(), &Int::value).first == 6, "");
  1216. static_assert(
  1217. ranges::minmax(array, ranges::greater(), &Int::value).second == 1, "");
  1218. }
  1219. TEST(RangesTest, MinElement) {
  1220. constexpr int array[] = {2, 6, 4, 3, 5, 1};
  1221. constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
  1222. static_assert(*ranges::min_element(array, array + 6) == 1, "");
  1223. static_assert(*ranges::min_element(ints, ranges::greater(), &Int::value) == 6,
  1224. "");
  1225. }
  1226. TEST(RangesTest, MaxElement) {
  1227. constexpr int array[] = {2, 6, 4, 3, 5, 1};
  1228. constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
  1229. static_assert(*ranges::max_element(array, array + 6) == 6, "");
  1230. static_assert(*ranges::max_element(ints, ranges::greater(), &Int::value) == 1,
  1231. "");
  1232. }
  1233. TEST(RangesTest, MinmaxElement) {
  1234. constexpr int array[] = {2, 6, 4, 3, 5, 1};
  1235. static_assert(*ranges::minmax_element(array, array + 6).first == 1, "");
  1236. static_assert(*ranges::minmax_element(array, array + 6).second == 6, "");
  1237. constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
  1238. static_assert(
  1239. *ranges::minmax_element(ints, ranges::greater(), &Int::value).first == 6,
  1240. "");
  1241. static_assert(
  1242. *ranges::minmax_element(ints, ranges::greater(), &Int::value).second == 1,
  1243. "");
  1244. }
  1245. TEST(RangesTest, Clamp) {
  1246. constexpr int k1 = 1;
  1247. constexpr int k2 = 2;
  1248. constexpr int k3 = 3;
  1249. static_assert(&ranges::clamp(k1, k1, k1) == &k1, "");
  1250. static_assert(&ranges::clamp(k1, k1, k2) == &k1, "");
  1251. static_assert(&ranges::clamp(k1, k1, k3) == &k1, "");
  1252. static_assert(&ranges::clamp(k1, k2, k2) == &k2, "");
  1253. static_assert(&ranges::clamp(k1, k2, k3) == &k2, "");
  1254. static_assert(&ranges::clamp(k1, k3, k3) == &k3, "");
  1255. static_assert(&ranges::clamp(k2, k1, k1) == &k1, "");
  1256. static_assert(&ranges::clamp(k2, k1, k2) == &k2, "");
  1257. static_assert(&ranges::clamp(k2, k1, k3) == &k2, "");
  1258. static_assert(&ranges::clamp(k2, k2, k2) == &k2, "");
  1259. static_assert(&ranges::clamp(k2, k2, k3) == &k2, "");
  1260. static_assert(&ranges::clamp(k2, k3, k3) == &k3, "");
  1261. static_assert(&ranges::clamp(k3, k1, k1) == &k1, "");
  1262. static_assert(&ranges::clamp(k3, k1, k2) == &k2, "");
  1263. static_assert(&ranges::clamp(k3, k1, k3) == &k3, "");
  1264. static_assert(&ranges::clamp(k3, k2, k2) == &k2, "");
  1265. static_assert(&ranges::clamp(k3, k2, k3) == &k3, "");
  1266. static_assert(&ranges::clamp(k3, k3, k3) == &k3, "");
  1267. constexpr Int k4 = 4;
  1268. constexpr Int k5 = 5;
  1269. constexpr Int k6 = 6;
  1270. static_assert(
  1271. &ranges::clamp(k6, k6, k6, ranges::greater(), &Int::value) == &k6, "");
  1272. static_assert(
  1273. &ranges::clamp(k6, k6, k5, ranges::greater(), &Int::value) == &k6, "");
  1274. static_assert(
  1275. &ranges::clamp(k6, k6, k4, ranges::greater(), &Int::value) == &k6, "");
  1276. static_assert(
  1277. &ranges::clamp(k6, k5, k5, ranges::greater(), &Int::value) == &k5, "");
  1278. static_assert(
  1279. &ranges::clamp(k6, k5, k4, ranges::greater(), &Int::value) == &k5, "");
  1280. static_assert(
  1281. &ranges::clamp(k6, k4, k4, ranges::greater(), &Int::value) == &k4, "");
  1282. static_assert(
  1283. &ranges::clamp(k5, k6, k6, ranges::greater(), &Int::value) == &k6, "");
  1284. static_assert(
  1285. &ranges::clamp(k5, k6, k5, ranges::greater(), &Int::value) == &k5, "");
  1286. static_assert(
  1287. &ranges::clamp(k5, k6, k4, ranges::greater(), &Int::value) == &k5, "");
  1288. static_assert(
  1289. &ranges::clamp(k5, k5, k5, ranges::greater(), &Int::value) == &k5, "");
  1290. static_assert(
  1291. &ranges::clamp(k5, k5, k4, ranges::greater(), &Int::value) == &k5, "");
  1292. static_assert(
  1293. &ranges::clamp(k5, k4, k4, ranges::greater(), &Int::value) == &k4, "");
  1294. static_assert(
  1295. &ranges::clamp(k4, k6, k6, ranges::greater(), &Int::value) == &k6, "");
  1296. static_assert(
  1297. &ranges::clamp(k4, k6, k5, ranges::greater(), &Int::value) == &k5, "");
  1298. static_assert(
  1299. &ranges::clamp(k4, k6, k4, ranges::greater(), &Int::value) == &k4, "");
  1300. static_assert(
  1301. &ranges::clamp(k4, k5, k5, ranges::greater(), &Int::value) == &k5, "");
  1302. static_assert(
  1303. &ranges::clamp(k4, k5, k4, ranges::greater(), &Int::value) == &k4, "");
  1304. static_assert(
  1305. &ranges::clamp(k4, k4, k4, ranges::greater(), &Int::value) == &k4, "");
  1306. }
  1307. TEST(RangesTest, LexicographicalCompare) {
  1308. constexpr int inputs1[] = {0, 1, 2, 3, 4, 5};
  1309. constexpr int inputs2[] = {0, 1, 2, 3, 5, 4};
  1310. static_assert(!ranges::lexicographical_compare(inputs1, inputs1 + 6, inputs1,
  1311. inputs1 + 6),
  1312. "");
  1313. static_assert(ranges::lexicographical_compare(inputs1, inputs1 + 6, inputs2,
  1314. inputs2 + 6),
  1315. "");
  1316. static_assert(!ranges::lexicographical_compare(inputs2, inputs2 + 6, inputs1,
  1317. inputs1 + 6),
  1318. "");
  1319. static_assert(!ranges::lexicographical_compare(inputs2, inputs2 + 6, inputs2,
  1320. inputs2 + 6),
  1321. "");
  1322. constexpr Int ints1[] = {0, 1, 2, 3, 4, 5};
  1323. constexpr Int ints2[] = {5, 4, 3, 2, 1, 0};
  1324. static_assert(
  1325. !ranges::lexicographical_compare(inputs1, ints1, {}, {}, &Int::value),
  1326. "");
  1327. static_assert(
  1328. !ranges::lexicographical_compare(ints1, inputs1, {}, &Int::value), "");
  1329. static_assert(
  1330. !ranges::lexicographical_compare(inputs2, ints1, {}, {}, &Int::value),
  1331. "");
  1332. static_assert(
  1333. ranges::lexicographical_compare(ints1, inputs2, {}, &Int::value), "");
  1334. static_assert(ranges::lexicographical_compare(ints1, ints2, {}, &Int::value,
  1335. &Int::value),
  1336. "");
  1337. static_assert(!ranges::lexicographical_compare(ints2, ints1, {}, &Int::value,
  1338. &Int::value),
  1339. "");
  1340. static_assert(!ranges::lexicographical_compare(
  1341. ints1, ints2, ranges::greater(), &Int::value, &Int::value),
  1342. "");
  1343. static_assert(ranges::lexicographical_compare(ints2, ints1, ranges::greater(),
  1344. &Int::value, &Int::value),
  1345. "");
  1346. using List = std::initializer_list<int>;
  1347. static_assert(
  1348. ranges::lexicographical_compare(List{0, 1, 2}, List{0, 1, 2, 3}), "");
  1349. static_assert(
  1350. !ranges::lexicographical_compare(List{0, 1, 2, 3}, List{0, 1, 2}), "");
  1351. static_assert(
  1352. ranges::lexicographical_compare(List{0, 1, 2, 3}, List{0, 1, 2, 4}), "");
  1353. static_assert(
  1354. !ranges::lexicographical_compare(List{0, 1, 2, 4}, List{0, 1, 2, 3}), "");
  1355. }
  1356. TEST(RangesTest, NextPermutation) {
  1357. int input[] = {5, 4, 3, 2, 0, 1};
  1358. EXPECT_TRUE(ranges::next_permutation(input, input + 6));
  1359. EXPECT_THAT(input, ElementsAre(5, 4, 3, 2, 1, 0));
  1360. EXPECT_FALSE(ranges::next_permutation(input, input + 6));
  1361. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5));
  1362. Int ints[] = {0, 1, 2, 3, 5, 4};
  1363. EXPECT_TRUE(ranges::next_permutation(ints, ranges::greater(), &Int::value));
  1364. EXPECT_THAT(ints, ElementsAre(0, 1, 2, 3, 4, 5));
  1365. EXPECT_FALSE(ranges::next_permutation(ints, ranges::greater(), &Int::value));
  1366. EXPECT_THAT(ints, ElementsAre(5, 4, 3, 2, 1, 0));
  1367. int bits[] = {0, 0, 1, 0, 0};
  1368. EXPECT_TRUE(ranges::next_permutation(bits));
  1369. EXPECT_THAT(bits, ElementsAre(0, 1, 0, 0, 0));
  1370. }
  1371. TEST(RangesTest, PrevPermutation) {
  1372. int input[] = {0, 1, 2, 3, 5, 4};
  1373. EXPECT_TRUE(ranges::prev_permutation(input, input + 6));
  1374. EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5));
  1375. EXPECT_FALSE(ranges::prev_permutation(input, input + 6));
  1376. EXPECT_THAT(input, ElementsAre(5, 4, 3, 2, 1, 0));
  1377. Int ints[] = {5, 4, 3, 2, 0, 1};
  1378. EXPECT_TRUE(ranges::prev_permutation(ints, ranges::greater(), &Int::value));
  1379. EXPECT_THAT(ints, ElementsAre(5, 4, 3, 2, 1, 0));
  1380. EXPECT_FALSE(ranges::prev_permutation(ints, ranges::greater(), &Int::value));
  1381. EXPECT_THAT(ints, ElementsAre(0, 1, 2, 3, 4, 5));
  1382. int bits[] = {0, 0, 1, 0, 0};
  1383. EXPECT_TRUE(ranges::prev_permutation(bits));
  1384. EXPECT_THAT(bits, ElementsAre(0, 0, 0, 1, 0));
  1385. }
  1386. namespace internal {
  1387. const auto predicate = [](int value) { return value; };
  1388. struct TestPair {
  1389. int a;
  1390. int b;
  1391. };
  1392. } // namespace internal
  1393. // This is a compilation test that checks that using predicates and projections
  1394. // from the base::internal namespace in range algorithms doesn't result in
  1395. // ambiguous calls to base::invoke.
  1396. TEST(RangesTest, DontClashWithPredicateFromInternalInvoke) {
  1397. {
  1398. int input[] = {0, 1, 2};
  1399. ranges::any_of(input, internal::predicate);
  1400. }
  1401. {
  1402. internal::TestPair input[] = {{1, 2}, {3, 4}};
  1403. ranges::any_of(input, base::identity{}, &internal::TestPair::a);
  1404. }
  1405. }
  1406. } // namespace base