functools_ut.cpp 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603
  1. #include <library/cpp/iterator/functools.h>
  2. #include <library/cpp/testing/gtest/gtest.h>
  3. #include <util/generic/vector.h>
  4. #include <util/generic/xrange.h>
  5. #include <util/generic/adaptor.h>
  6. #include <set>
  7. // default-win-x86_64-release compiler can't decompose tuple to structure binding (02.03.2019)
  8. #ifndef _WINDOWS
  9. # define FOR_DISPATCH_2(i, j, r) \
  10. for (auto [i, j] : r)
  11. # define FOR_DISPATCH_3(i, j, k, r) \
  12. for (auto [i, j, k] : r)
  13. #else
  14. # define FOR_DISPATCH_2(i, j, r) \
  15. for (auto __t_##i##_##j : r) \
  16. if (auto& i = std::get<0>(__t_##i##_##j); true) \
  17. if (auto& j = std::get<1>(__t_##i##_##j); true)
  18. # define FOR_DISPATCH_3(i, j, k, r) \
  19. for (auto __t_##i##_##j##_##k : r) \
  20. if (auto& i = std::get<0>(__t_##i##_##j##_##k); true) \
  21. if (auto& j = std::get<1>(__t_##i##_##j##_##k); true) \
  22. if (auto& k = std::get<2>(__t_##i##_##j##_##k); true)
  23. #endif
  24. using namespace NFuncTools;
  25. template <typename TContainer>
  26. auto ToVector(TContainer&& container) {
  27. return std::vector{container.begin(), container.end()};
  28. }
  29. template <typename TContainerObjOrRef>
  30. void TestViewCompileability(TContainerObjOrRef&& container) {
  31. using TContainer = std::decay_t<TContainerObjOrRef>;
  32. using TIterator = typename TContainer::iterator;
  33. static_assert(std::is_same_v<decltype(container.begin()), TIterator>);
  34. // iterator_traits must work!
  35. using difference_type = typename std::iterator_traits<TIterator>::difference_type;
  36. using value_type = typename std::iterator_traits<TIterator>::value_type;
  37. using reference = typename std::iterator_traits<TIterator>::reference;
  38. using pointer = typename std::iterator_traits<TIterator>::pointer;
  39. {
  40. // operator assignment
  41. auto it = container.begin();
  42. it = container.end();
  43. it = std::move(container.begin());
  44. // operator copying
  45. auto it2 = it;
  46. Y_UNUSED(it2);
  47. auto it3 = std::move(it);
  48. Y_UNUSED(it3);
  49. Y_UNUSED(*it3);
  50. EXPECT_TRUE(it3 == it3);
  51. EXPECT_FALSE(it3 != it3);
  52. // const TIterator
  53. const auto it4 = it3;
  54. Y_UNUSED(*it4);
  55. EXPECT_TRUE(it4 == it4);
  56. EXPECT_FALSE(it4 != it4);
  57. EXPECT_TRUE(it3 == it4);
  58. EXPECT_TRUE(it4 == it3);
  59. EXPECT_FALSE(it3 != it4);
  60. EXPECT_FALSE(it4 != it3);
  61. }
  62. auto it = container.begin();
  63. // sanity check for types
  64. using TConstReference = const std::remove_reference_t<reference>&;
  65. TConstReference ref = *it;
  66. Y_UNUSED(ref);
  67. (void) static_cast<value_type>(*it);
  68. (void) static_cast<difference_type>(1);
  69. if constexpr (std::is_reference_v<decltype(*it)>) {
  70. pointer ptr = &*it;
  71. Y_UNUSED(ptr);
  72. }
  73. // std compatibility
  74. ToVector(container);
  75. // const iterators
  76. [](const auto& cont) {
  77. auto constBeginIterator = cont.begin();
  78. auto constEndIterator = cont.end();
  79. static_assert(std::is_same_v<decltype(constBeginIterator), typename TContainer::const_iterator>);
  80. Y_UNUSED(constBeginIterator);
  81. Y_UNUSED(constEndIterator);
  82. }(container);
  83. }
  84. struct TTestSentinel {};
  85. struct TTestIterator {
  86. int operator*() {
  87. return X;
  88. }
  89. void operator++() {
  90. ++X;
  91. }
  92. bool operator!=(const TTestSentinel&) const {
  93. return X < 3;
  94. }
  95. int X;
  96. };
  97. // container with minimal interface
  98. auto MakeMinimalisticContainer() {
  99. return MakeIteratorRange(TTestIterator{}, TTestSentinel{});
  100. }
  101. TEST(FuncTools, CompileRange) {
  102. TestViewCompileability(Range(19));
  103. TestViewCompileability(Range(10, 19));
  104. TestViewCompileability(Range(10, 19, 2));
  105. }
  106. TEST(FuncTools, Enumerate) {
  107. TVector<size_t> a = {1, 2, 4};
  108. TVector<size_t> b;
  109. TVector<size_t> c = {1};
  110. for (auto& v : {a, b, c}) {
  111. size_t j = 0;
  112. FOR_DISPATCH_2(i, x, Enumerate(v)) {
  113. EXPECT_EQ(v[i], x);
  114. EXPECT_EQ(i, j++);
  115. EXPECT_LT(i, v.size());
  116. }
  117. EXPECT_EQ(j, v.size());
  118. }
  119. TVector<size_t> d = {0, 0, 0};
  120. FOR_DISPATCH_2(i, x, Enumerate(d)) {
  121. x = i;
  122. }
  123. EXPECT_THAT(
  124. d,
  125. testing::ElementsAre(0u, 1u, 2u)
  126. );
  127. }
  128. TEST(FuncTools, EnumerateTemporary) {
  129. TVector<size_t> a = {1, 2, 4};
  130. TVector<size_t> b;
  131. TVector<size_t> c = {1};
  132. for (auto& v : {a, b, c}) {
  133. size_t j = 0;
  134. FOR_DISPATCH_2(i, x, Enumerate(TVector(v))) {
  135. EXPECT_EQ(v[i], x);
  136. EXPECT_EQ(i, j++);
  137. EXPECT_LT(i, v.size());
  138. }
  139. EXPECT_EQ(j, v.size());
  140. }
  141. FOR_DISPATCH_2(i, x, Enumerate(TVector<size_t>{1, 2, 3})) {
  142. EXPECT_EQ(i + 1, x);
  143. }
  144. }
  145. TEST(FuncTools, CompileEnumerate) {
  146. auto container = std::vector{1, 2, 3};
  147. TestViewCompileability(Enumerate(container));
  148. const auto constContainer = std::vector{1, 2, 3};
  149. TestViewCompileability(Enumerate(constContainer));
  150. const int arrayContainer[] = {1, 2, 3};
  151. TestViewCompileability(Enumerate(arrayContainer));
  152. std::vector<std::pair<int, int>> res;
  153. FOR_DISPATCH_2(i, x, Enumerate(MakeMinimalisticContainer())) {
  154. res.push_back({i, x});
  155. }
  156. EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
  157. {0, 0}, {1, 1}, {2, 2},
  158. }));
  159. }
  160. TEST(FuncTools, Zip) {
  161. TVector<std::pair<TVector<size_t>, TVector<size_t>>> ts = {
  162. {{1, 2, 3}, {4, 5, 6}},
  163. {{1, 2, 3}, {4, 5, 6, 7}},
  164. {{1, 2, 3, 4}, {4, 5, 6}},
  165. {{1, 2, 3, 4}, {}},
  166. };
  167. FOR_DISPATCH_2(a, b, ts) {
  168. size_t k = 0;
  169. FOR_DISPATCH_2(i, j, Zip(a, b)) {
  170. EXPECT_EQ(++k, i);
  171. EXPECT_EQ(i + 3, j);
  172. }
  173. EXPECT_EQ(k, Min(a.size(), b.size()));
  174. }
  175. }
  176. TEST(FuncTools, ZipReference) {
  177. TVector a = {0, 1, 2};
  178. TVector b = {2, 1, 0, -1};
  179. FOR_DISPATCH_2(ai, bi, Zip(a, b)) {
  180. ai = bi;
  181. }
  182. EXPECT_THAT(
  183. a,
  184. testing::ElementsAre(2u, 1u, 0u)
  185. );
  186. }
  187. TEST(FuncTools, Zip3) {
  188. TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
  189. {{1, 2, 3}, {4, 5, 6}, {11, 3}},
  190. {{1, 2, 3}, {4, 5, 6, 7}, {9, 0}},
  191. {{1, 2, 3, 4}, {9}, {4, 5, 6}},
  192. {{1, 2, 3, 4}, {1}, {}},
  193. {{}, {1}, {1, 2, 3, 4}},
  194. };
  195. FOR_DISPATCH_3(a, b, c, ts) {
  196. TVector<std::tuple<i32, i32, i32>> e;
  197. for (size_t j = 0; j < a.size() && j < b.size() && j < c.size(); ++j) {
  198. e.push_back({a[j], b[j], c[j]});
  199. }
  200. TVector<std::tuple<i32, i32, i32>> f;
  201. FOR_DISPATCH_3(ai, bi, ci, Zip(a, b, c)) {
  202. f.push_back({ai, bi, ci});
  203. }
  204. EXPECT_EQ(e, f);
  205. }
  206. }
  207. TEST(FuncTools, CompileZip) {
  208. auto container = std::vector{1, 2, 3};
  209. TestViewCompileability(Zip(container));
  210. TestViewCompileability(Zip(container, container, container));
  211. const auto constContainer = std::vector{1, 2, 3};
  212. TestViewCompileability(Zip(constContainer, constContainer));
  213. const int arrayContainer[] = {1, 2, 3};
  214. TestViewCompileability(Zip(arrayContainer, arrayContainer));
  215. std::vector<std::pair<int, int>> res;
  216. FOR_DISPATCH_2(a, b, Zip(MakeMinimalisticContainer(), container)) {
  217. res.push_back({a, b});
  218. }
  219. EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
  220. {0, 1}, {1, 2}, {2, 3},
  221. }));
  222. }
  223. TEST(FuncTools, Filter) {
  224. TVector<TVector<i32>> ts = {
  225. {},
  226. {1},
  227. {2},
  228. {1, 2},
  229. {2, 1},
  230. {1, 2, 3, 4, 5, 6, 7},
  231. };
  232. auto pred = [](i32 x) -> bool { return x & 1; };
  233. for (auto& a : ts) {
  234. TVector<i32> b;
  235. for (i32 x : a) {
  236. if (pred(x)) {
  237. b.push_back(x);
  238. }
  239. }
  240. TVector<i32> c;
  241. for (i32 x : Filter(pred, a)) {
  242. c.push_back(x);
  243. }
  244. EXPECT_EQ(b, c);
  245. }
  246. }
  247. TEST(FuncTools, CompileFilter) {
  248. auto container = std::vector{1, 2, 3};
  249. auto isOdd = [](int x) { return bool(x & 1); };
  250. TestViewCompileability(Filter(isOdd, container));
  251. const int arrayContainer[] = {1, 2, 3};
  252. TestViewCompileability(Filter(isOdd, arrayContainer));
  253. }
  254. TEST(FuncTools, Map) {
  255. TVector<TVector<i32>> ts = {
  256. {},
  257. {1},
  258. {1, 2},
  259. {1, 2, 3, 4, 5, 6, 7},
  260. };
  261. auto f = [](i32 x) { return x * x; };
  262. for (auto& a : ts) {
  263. TVector<i32> b;
  264. for (i32 x : a) {
  265. b.push_back(f(x));
  266. }
  267. TVector<i32> c;
  268. for (i32 x : Map(f, a)) {
  269. c.push_back(x);
  270. }
  271. EXPECT_EQ(b, c);
  272. }
  273. TVector floats = {1.4, 4.1, 13.9};
  274. TVector ints = {1, 4, 13};
  275. TVector<float> roundedFloats = {1, 4, 13};
  276. TVector<int> res;
  277. TVector<float> resFloat;
  278. for (auto i : Map<int>(floats)) {
  279. res.push_back(i);
  280. }
  281. for (auto i : Map<float>(Map<int>(floats))) {
  282. resFloat.push_back(i);
  283. }
  284. EXPECT_EQ(ints, res);
  285. EXPECT_EQ(roundedFloats, resFloat);
  286. }
  287. TEST(FuncTools, CompileMap) {
  288. auto container = std::vector{1, 2, 3};
  289. auto sqr = [](int x) { return x * x; };
  290. TestViewCompileability(Map(sqr, container));
  291. const int arrayContainer[] = {1, 2, 3};
  292. TestViewCompileability(Map(sqr, arrayContainer));
  293. }
  294. TEST(FuncTools, MapRandomAccess) {
  295. auto sqr = [](int x) { return x * x; };
  296. {
  297. auto container = std::vector{1, 2, 3};
  298. auto mapped = Map(sqr, container);
  299. static_assert(
  300. std::is_same_v<decltype(mapped)::iterator::iterator_category, std::random_access_iterator_tag>
  301. );
  302. }
  303. {
  304. auto container = std::set<int>{1, 2, 3};
  305. auto mapped = Map(sqr, container);
  306. static_assert(
  307. std::is_same_v<decltype(mapped)::iterator::iterator_category, std::input_iterator_tag>
  308. );
  309. }
  310. }
  311. TEST(FuncTools, CartesianProduct) {
  312. TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
  313. {{1, 2, 3}, {4, 5, 6}},
  314. {{1, 2, 3}, {4, 5, 6, 7}},
  315. {{1, 2, 3, 4}, {4, 5, 6}},
  316. {{1, 2, 3, 4}, {}},
  317. {{}, {1, 2, 3, 4}},
  318. };
  319. for (auto [a, b] : ts) {
  320. TVector<std::pair<i32, i32>> c;
  321. for (auto ai : a) {
  322. for (auto bi : b) {
  323. c.push_back({ai, bi});
  324. }
  325. }
  326. TVector<std::pair<i32, i32>> d;
  327. FOR_DISPATCH_2(ai, bi, CartesianProduct(a, b)) {
  328. d.push_back({ai, bi});
  329. }
  330. EXPECT_EQ(c, d);
  331. }
  332. {
  333. TVector<TVector<int>> g = {{}, {}};
  334. TVector h = {10, 11, 12};
  335. FOR_DISPATCH_2(gi, i, CartesianProduct(g, h)) {
  336. gi.push_back(i);
  337. }
  338. EXPECT_EQ(g[0], h);
  339. EXPECT_EQ(g[1], h);
  340. }
  341. }
  342. TEST(FuncTools, CartesianProduct3) {
  343. TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
  344. {{1, 2, 3}, {4, 5, 6}, {11, 3}},
  345. {{1, 2, 3}, {4, 5, 6, 7}, {9}},
  346. {{1, 2, 3, 4}, {9}, {4, 5, 6}},
  347. {{1, 2, 3, 4}, {1}, {}},
  348. {{}, {1}, {1, 2, 3, 4}},
  349. };
  350. FOR_DISPATCH_3(a, b, c, ts) {
  351. TVector<std::tuple<i32, i32, i32>> e;
  352. for (auto ai : a) {
  353. for (auto bi : b) {
  354. for (auto ci : c) {
  355. e.push_back({ai, bi, ci});
  356. }
  357. }
  358. }
  359. TVector<std::tuple<i32, i32, i32>> f;
  360. FOR_DISPATCH_3(ai, bi, ci, CartesianProduct(a, b, c)) {
  361. f.push_back({ai, bi, ci});
  362. }
  363. EXPECT_EQ(e, f);
  364. }
  365. }
  366. TEST(FuncTools, CompileCartesianProduct) {
  367. auto container = std::vector{1, 2, 3};
  368. TestViewCompileability(CartesianProduct(container, container));
  369. const auto constContainer = std::vector{1, 2, 3};
  370. TestViewCompileability(CartesianProduct(constContainer, constContainer));
  371. const int arrayContainer[] = {1, 2, 3};
  372. TestViewCompileability(CartesianProduct(arrayContainer, arrayContainer));
  373. std::vector<std::pair<int, int>> res;
  374. FOR_DISPATCH_2(a, b, CartesianProduct(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
  375. res.push_back({a, b});
  376. }
  377. EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
  378. {0, 0}, {0, 1}, {0, 2},
  379. {1, 0}, {1, 1}, {1, 2},
  380. {2, 0}, {2, 1}, {2, 2},
  381. }));
  382. }
  383. TEST(FuncTools, Concatenate2) {
  384. TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
  385. {{1, 2, 3}, {4, 5, 6}},
  386. {{1, 2, 3}, {4, 5, 6, 7}},
  387. {{1, 2, 3, 4}, {4, 5, 6}},
  388. {{1, 2, 3, 4}, {}},
  389. {{}, {1, 2, 3, 4}},
  390. };
  391. for (auto [a, b] : ts) {
  392. TVector<i32> c;
  393. for (auto ai : a) {
  394. c.push_back(ai);
  395. }
  396. for (auto bi : b) {
  397. c.push_back(bi);
  398. }
  399. TVector<i32> d;
  400. for (auto x : Concatenate(a, b)) {
  401. d.push_back(x);
  402. }
  403. EXPECT_EQ(c, d);
  404. }
  405. {
  406. TVector<i32> a = {1, 2, 3, 4};
  407. TVector<i32> c;
  408. for (auto x : Concatenate(a, TVector<i32>{5, 6})) {
  409. c.push_back(x);
  410. }
  411. EXPECT_EQ(c, (TVector<i32>{1, 2, 3, 4, 5, 6}));
  412. }
  413. }
  414. TEST(FuncTools, CompileConcatenate) {
  415. auto container = std::vector{1, 2, 3};
  416. TestViewCompileability(Concatenate(container, container));
  417. const auto constContainer = std::vector{1, 2, 3};
  418. TestViewCompileability(Concatenate(constContainer, constContainer));
  419. const int arrayContainer[] = {1, 2, 3};
  420. TestViewCompileability(Concatenate(arrayContainer, arrayContainer));
  421. std::vector<int> res;
  422. for (auto a : Concatenate(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
  423. res.push_back(a);
  424. }
  425. EXPECT_EQ(res, (std::vector{0, 1, 2, 0, 1, 2}));
  426. }
  427. TEST(FuncTools, Combo) {
  428. FOR_DISPATCH_2(i, j, Enumerate(xrange(10u))) {
  429. EXPECT_EQ(i, j);
  430. }
  431. FOR_DISPATCH_2(i, jk, Enumerate(Enumerate(xrange(10u)))) {
  432. EXPECT_EQ(i, std::get<0>(jk));
  433. EXPECT_EQ(std::get<0>(jk), std::get<1>(jk));
  434. }
  435. TVector<size_t> a = {0, 1, 2};
  436. FOR_DISPATCH_2(i, j, Enumerate(Reversed(a))) {
  437. EXPECT_EQ(i, 2 - j);
  438. }
  439. FOR_DISPATCH_2(i, j, Enumerate(Map<float>(a))) {
  440. EXPECT_EQ(i, (size_t)j);
  441. }
  442. FOR_DISPATCH_2(i, j, Zip(a, Map<float>(a))) {
  443. EXPECT_EQ(i, (size_t)j);
  444. }
  445. auto mapper = [](auto&& x) {
  446. return std::get<0>(x) + std::get<1>(x);
  447. };
  448. FOR_DISPATCH_2(i, j, Zip(a, Map(mapper, Zip(a, a)))) {
  449. EXPECT_EQ(j, 2 * i);
  450. }
  451. }
  452. TEST(FuncTools, CopyIterator) {
  453. TVector a = {1, 2, 3, 4};
  454. TVector b = {4, 5, 6, 7};
  455. // calls f on 2nd, 3d and 4th positions (numeration from 1st)
  456. auto testIterator = [](auto it, auto f) {
  457. ++it;
  458. auto it2 = it;
  459. ++it2;
  460. ++it2;
  461. auto it3 = it;
  462. ++it3;
  463. f(*it, *it3, *it2);
  464. };
  465. {
  466. auto iterable = Enumerate(a);
  467. testIterator(std::begin(iterable),
  468. [](auto p2, auto p3, auto p4) {
  469. EXPECT_EQ(std::get<0>(p2), 1u);
  470. EXPECT_EQ(std::get<1>(p2), 2);
  471. EXPECT_EQ(std::get<0>(p3), 2u);
  472. EXPECT_EQ(std::get<1>(p3), 3);
  473. EXPECT_EQ(std::get<0>(p4), 3u);
  474. EXPECT_EQ(std::get<1>(p4), 4);
  475. });
  476. }
  477. {
  478. auto iterable = Map([](i32 x) { return x*x; }, a);
  479. testIterator(std::begin(iterable),
  480. [](auto p2, auto p3, auto p4) {
  481. EXPECT_EQ(p2, 4);
  482. EXPECT_EQ(p3, 9);
  483. EXPECT_EQ(p4, 16);
  484. });
  485. }
  486. {
  487. auto iterable = Zip(a, b);
  488. testIterator(std::begin(iterable),
  489. [](auto p2, auto p3, auto p4) {
  490. EXPECT_EQ(std::get<0>(p2), 2);
  491. EXPECT_EQ(std::get<1>(p2), 5);
  492. EXPECT_EQ(std::get<0>(p3), 3);
  493. EXPECT_EQ(std::get<1>(p3), 6);
  494. EXPECT_EQ(std::get<0>(p4), 4);
  495. EXPECT_EQ(std::get<1>(p4), 7);
  496. });
  497. }
  498. {
  499. auto c = {1, 2, 3, 4, 5, 6, 7, 8};
  500. auto iterable = Filter([](i32 x) { return !(x & 1); }, c);
  501. testIterator(std::begin(iterable),
  502. [](auto p2, auto p3, auto p4) {
  503. EXPECT_EQ(p2, 4);
  504. EXPECT_EQ(p3, 6);
  505. EXPECT_EQ(p4, 8);
  506. });
  507. }
  508. {
  509. auto iterable = CartesianProduct(TVector{0, 1}, TVector{2, 3});
  510. // (0, 2), (0, 3), (1, 2), (1, 3)
  511. testIterator(std::begin(iterable),
  512. [](auto p2, auto p3, auto p4) {
  513. EXPECT_EQ(std::get<0>(p2), 0);
  514. EXPECT_EQ(std::get<1>(p2), 3);
  515. EXPECT_EQ(std::get<0>(p3), 1);
  516. EXPECT_EQ(std::get<1>(p3), 2);
  517. EXPECT_EQ(std::get<0>(p4), 1);
  518. EXPECT_EQ(std::get<1>(p4), 3);
  519. });
  520. }
  521. }