text: #include <library/cpp/iterator/functools.h>
  
  #include <library/cpp/testing/gtest/gtest.h>
  
  #include <util/generic/vector.h>
  #include <util/generic/xrange.h>
  #include <util/generic/adaptor.h>
  
  #include <set>
  
  // default-win-x86_64-release compiler can't decompose tuple to structure binding (02.03.2019)
  #ifndef _WINDOWS
  #   define FOR_DISPATCH_2(i, j, r) \
          for (auto [i, j] : r)
  #   define FOR_DISPATCH_3(i, j, k, r) \
          for (auto [i, j, k] : r)
  #else
  #   define FOR_DISPATCH_2(i, j, r) \
          for (auto __t_##i##_##j : r) \
              if (auto& i = std::get<0>(__t_##i##_##j); true) \
                  if (auto& j = std::get<1>(__t_##i##_##j); true)
  #   define FOR_DISPATCH_3(i, j, k, r) \
          for (auto __t_##i##_##j##_##k : r) \
              if (auto& i = std::get<0>(__t_##i##_##j##_##k); true) \
                  if (auto& j = std::get<1>(__t_##i##_##j##_##k); true) \
                      if (auto& k = std::get<2>(__t_##i##_##j##_##k); true)
  #endif
  
  using namespace NFuncTools;
  
  
      template <typename TContainer>
      auto ToVector(TContainer&& container) {
          return std::vector{container.begin(), container.end()};
      }
  
      template <typename TContainerObjOrRef>
      void TestViewCompileability(TContainerObjOrRef&& container) {
          using TContainer = std::decay_t<TContainerObjOrRef>;
          using TIterator = typename TContainer::iterator;
  
          static_assert(std::is_same_v<decltype(container.begin()), TIterator>);
  
          // iterator_traits must work!
          using difference_type = typename std::iterator_traits<TIterator>::difference_type;
          using value_type = typename std::iterator_traits<TIterator>::value_type;
          using reference = typename std::iterator_traits<TIterator>::reference;
          using pointer = typename std::iterator_traits<TIterator>::pointer;
  
          {
              // operator assignment
              auto it = container.begin();
              it = container.end();
              it = std::move(container.begin());
              // operator copying
              auto it2 = it;
              Y_UNUSED(it2);
              auto it3 = std::move(it);
              Y_UNUSED(it3);
              Y_UNUSED(*it3);
              EXPECT_TRUE(it3 == it3);
              EXPECT_FALSE(it3 != it3);
              // const TIterator
              const auto it4 = it3;
              Y_UNUSED(*it4);
              EXPECT_TRUE(it4 == it4);
              EXPECT_FALSE(it4 != it4);
              EXPECT_TRUE(it3 == it4);
              EXPECT_TRUE(it4 == it3);
              EXPECT_FALSE(it3 != it4);
              EXPECT_FALSE(it4 != it3);
          }
  
          auto it = container.begin();
  
          // sanity check for types
          using TConstReference = const std::remove_reference_t<reference>&;
          TConstReference ref = *it;
          Y_UNUSED(ref);
          (void) static_cast<value_type>(*it);
          (void) static_cast<difference_type>(1);
          if constexpr (std::is_reference_v<decltype(*it)>) {
              pointer ptr = &*it;
              Y_UNUSED(ptr);
          }
  
          // std compatibility
          ToVector(container);
  
          // const iterators
          [](const auto& cont) {
              auto constBeginIterator = cont.begin();
              auto constEndIterator = cont.end();
              static_assert(std::is_same_v<decltype(constBeginIterator), typename TContainer::const_iterator>);
              Y_UNUSED(constBeginIterator);
              Y_UNUSED(constEndIterator);
          }(container);
      }
  
      struct TTestSentinel {};
      struct TTestIterator {
          int operator*() {
              return X;
          }
          void operator++() {
              ++X;
          }
          bool operator!=(const TTestSentinel&) const {
              return X < 3;
          }
  
          int X;
      };
  
      // container with minimal interface
      auto MakeMinimalisticContainer() {
          return MakeIteratorRange(TTestIterator{}, TTestSentinel{});
      }
  
  
      TEST(FuncTools, CompileRange) {
          TestViewCompileability(Range(19));
          TestViewCompileability(Range(10, 19));
          TestViewCompileability(Range(10, 19, 2));
      }
  
  
      TEST(FuncTools, Enumerate) {
          TVector<size_t> a = {1, 2, 4};
          TVector<size_t> b;
          TVector<size_t> c = {1};
          for (auto& v : {a, b, c}) {
              size_t j = 0;
              FOR_DISPATCH_2(i, x, Enumerate(v)) {
                  EXPECT_EQ(v[i], x);
                  EXPECT_EQ(i, j++);
                  EXPECT_LT(i, v.size());
              }
              EXPECT_EQ(j, v.size());
          }
  
          TVector<size_t> d = {0, 0, 0};
          FOR_DISPATCH_2(i, x, Enumerate(d)) {
              x = i;
          }
          EXPECT_THAT(
              d,
              testing::ElementsAre(0u, 1u, 2u)
          );
      }
  
      TEST(FuncTools, EnumerateTemporary) {
          TVector<size_t> a = {1, 2, 4};
          TVector<size_t> b;
          TVector<size_t> c = {1};
          for (auto& v : {a, b, c}) {
              size_t j = 0;
              FOR_DISPATCH_2(i, x, Enumerate(TVector(v))) {
                  EXPECT_EQ(v[i], x);
                  EXPECT_EQ(i, j++);
                  EXPECT_LT(i, v.size());
              }
              EXPECT_EQ(j, v.size());
          }
  
          FOR_DISPATCH_2(i, x, Enumerate(TVector<size_t>{1, 2, 3})) {
              EXPECT_EQ(i + 1, x);
          }
      }
  
      TEST(FuncTools, CompileEnumerate) {
          auto container = std::vector{1, 2, 3};
          TestViewCompileability(Enumerate(container));
          const auto constContainer = std::vector{1, 2, 3};
          TestViewCompileability(Enumerate(constContainer));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(Enumerate(arrayContainer));
  
          std::vector<std::pair<int, int>> res;
          FOR_DISPATCH_2(i, x, Enumerate(MakeMinimalisticContainer())) {
              res.push_back({i, x});
          }
          EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
              {0, 0}, {1, 1}, {2, 2},
          }));
      }
  
      TEST(FuncTools, Zip) {
          TVector<std::pair<TVector<size_t>, TVector<size_t>>> ts = {
              {{1, 2, 3}, {4, 5, 6}},
              {{1, 2, 3}, {4, 5, 6, 7}},
              {{1, 2, 3, 4}, {4, 5, 6}},
              {{1, 2, 3, 4}, {}},
          };
  
          FOR_DISPATCH_2(a, b, ts) {
              size_t k = 0;
              FOR_DISPATCH_2(i, j, Zip(a, b)) {
                  EXPECT_EQ(++k, i);
                  EXPECT_EQ(i + 3, j);
              }
              EXPECT_EQ(k, Min(a.size(), b.size()));
          }
      }
  
      TEST(FuncTools, ZipReference) {
          TVector a = {0, 1, 2};
          TVector b = {2, 1, 0, -1};
          FOR_DISPATCH_2(ai, bi, Zip(a, b)) {
              ai = bi;
          }
          EXPECT_THAT(
              a,
              testing::ElementsAre(2u, 1u, 0u)
          );
      }
  
      TEST(FuncTools, Zip3) {
          TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
              {{1, 2, 3}, {4, 5, 6}, {11, 3}},
              {{1, 2, 3}, {4, 5, 6, 7}, {9, 0}},
              {{1, 2, 3, 4}, {9}, {4, 5, 6}},
              {{1, 2, 3, 4}, {1}, {}},
              {{}, {1}, {1, 2, 3, 4}},
          };
  
          FOR_DISPATCH_3(a, b, c, ts) {
              TVector<std::tuple<i32, i32, i32>> e;
              for (size_t j = 0; j < a.size() && j < b.size() && j < c.size(); ++j) {
                  e.push_back({a[j], b[j], c[j]});
              }
  
              TVector<std::tuple<i32, i32, i32>> f;
              FOR_DISPATCH_3(ai, bi, ci, Zip(a, b, c)) {
                  f.push_back({ai, bi, ci});
              }
  
              EXPECT_EQ(e, f);
          }
      }
  
      TEST(FuncTools, CompileZip) {
          auto container = std::vector{1, 2, 3};
          TestViewCompileability(Zip(container));
          TestViewCompileability(Zip(container, container, container));
          const auto constContainer = std::vector{1, 2, 3};
          TestViewCompileability(Zip(constContainer, constContainer));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(Zip(arrayContainer, arrayContainer));
  
          std::vector<std::pair<int, int>> res;
          FOR_DISPATCH_2(a, b, Zip(MakeMinimalisticContainer(), container)) {
              res.push_back({a, b});
          }
          EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
              {0, 1}, {1, 2}, {2, 3},
          }));
      }
  
      TEST(FuncTools, Filter) {
          TVector<TVector<i32>> ts = {
              {},
              {1},
              {2},
              {1, 2},
              {2, 1},
              {1, 2, 3, 4, 5, 6, 7},
          };
  
          auto pred = [](i32 x) -> bool { return x & 1; };
  
          for (auto& a : ts) {
              TVector<i32> b;
              for (i32 x : a) {
                  if (pred(x)) {
                      b.push_back(x);
                  }
              }
  
              TVector<i32> c;
              for (i32 x : Filter(pred, a)) {
                  c.push_back(x);
              }
  
              EXPECT_EQ(b, c);
          }
      }
  
      TEST(FuncTools, CompileFilter) {
          auto container = std::vector{1, 2, 3};
          auto isOdd = [](int x) { return bool(x & 1); };
          TestViewCompileability(Filter(isOdd, container));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(Filter(isOdd, arrayContainer));
      }
  
      TEST(FuncTools, Map) {
          TVector<TVector<i32>> ts = {
              {},
              {1},
              {1, 2},
              {1, 2, 3, 4, 5, 6, 7},
          };
  
          auto f = [](i32 x) { return x * x; };
  
          for (auto& a : ts) {
              TVector<i32> b;
              for (i32 x : a) {
                  b.push_back(f(x));
              }
  
              TVector<i32> c;
              for (i32 x : Map(f, a)) {
                  c.push_back(x);
              }
  
              EXPECT_EQ(b, c);
          }
  
          TVector floats = {1.4, 4.1, 13.9};
          TVector ints = {1, 4, 13};
          TVector<float> roundedFloats = {1, 4, 13};
          TVector<int> res;
          TVector<float> resFloat;
          for (auto i : Map<int>(floats)) {
              res.push_back(i);
          }
          for (auto i : Map<float>(Map<int>(floats))) {
              resFloat.push_back(i);
          }
          EXPECT_EQ(ints, res);
          EXPECT_EQ(roundedFloats, resFloat);
      }
  
      TEST(FuncTools, CompileMap) {
          auto container = std::vector{1, 2, 3};
          auto sqr = [](int x) { return x * x; };
          TestViewCompileability(Map(sqr, container));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(Map(sqr, arrayContainer));
      }
  
      TEST(FuncTools, MapRandomAccess) {
          auto sqr = [](int x) { return x * x; };
          {
              auto container = std::vector{1, 2, 3};
              auto mapped = Map(sqr, container);
              static_assert(
                  std::is_same_v<decltype(mapped)::iterator::iterator_category, std::random_access_iterator_tag>
              );
          }
          {
              auto container = std::set<int>{1, 2, 3};
              auto mapped = Map(sqr, container);
              static_assert(
                  std::is_same_v<decltype(mapped)::iterator::iterator_category, std::input_iterator_tag>
              );
          }
      }
  
      TEST(FuncTools, CartesianProduct) {
          TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
              {{1, 2, 3}, {4, 5, 6}},
              {{1, 2, 3}, {4, 5, 6, 7}},
              {{1, 2, 3, 4}, {4, 5, 6}},
              {{1, 2, 3, 4}, {}},
              {{}, {1, 2, 3, 4}},
          };
  
          for (auto [a, b] : ts) {
              TVector<std::pair<i32, i32>> c;
              for (auto ai : a) {
                  for (auto bi : b) {
                      c.push_back({ai, bi});
                  }
              }
  
              TVector<std::pair<i32, i32>> d;
              FOR_DISPATCH_2(ai, bi, CartesianProduct(a, b)) {
                  d.push_back({ai, bi});
              }
  
              EXPECT_EQ(c, d);
          }
  
          {
              TVector<TVector<int>> g = {{}, {}};
              TVector h = {10, 11, 12};
              FOR_DISPATCH_2(gi, i, CartesianProduct(g, h)) {
                  gi.push_back(i);
              }
              EXPECT_EQ(g[0], h);
              EXPECT_EQ(g[1], h);
          }
      }
  
      TEST(FuncTools, CartesianProduct3) {
          TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
              {{1, 2, 3}, {4, 5, 6}, {11, 3}},
              {{1, 2, 3}, {4, 5, 6, 7}, {9}},
              {{1, 2, 3, 4}, {9}, {4, 5, 6}},
              {{1, 2, 3, 4}, {1}, {}},
              {{}, {1}, {1, 2, 3, 4}},
          };
  
          FOR_DISPATCH_3(a, b, c, ts) {
              TVector<std::tuple<i32, i32, i32>> e;
              for (auto ai : a) {
                  for (auto bi : b) {
                      for (auto ci : c) {
                          e.push_back({ai, bi, ci});
                      }
                  }
              }
  
              TVector<std::tuple<i32, i32, i32>> f;
              FOR_DISPATCH_3(ai, bi, ci, CartesianProduct(a, b, c)) {
                  f.push_back({ai, bi, ci});
              }
  
              EXPECT_EQ(e, f);
          }
      }
  
      TEST(FuncTools, CompileCartesianProduct) {
          auto container = std::vector{1, 2, 3};
          TestViewCompileability(CartesianProduct(container, container));
          const auto constContainer = std::vector{1, 2, 3};
          TestViewCompileability(CartesianProduct(constContainer, constContainer));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(CartesianProduct(arrayContainer, arrayContainer));
  
          std::vector<std::pair<int, int>> res;
          FOR_DISPATCH_2(a, b, CartesianProduct(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
              res.push_back({a, b});
          }
          EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
              {0, 0}, {0, 1}, {0, 2},
              {1, 0}, {1, 1}, {1, 2},
              {2, 0}, {2, 1}, {2, 2},
          }));
      }
  
      TEST(FuncTools, Concatenate2) {
          TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
              {{1, 2, 3}, {4, 5, 6}},
              {{1, 2, 3}, {4, 5, 6, 7}},
              {{1, 2, 3, 4}, {4, 5, 6}},
              {{1, 2, 3, 4}, {}},
              {{}, {1, 2, 3, 4}},
          };
  
          for (auto [a, b] : ts) {
              TVector<i32> c;
              for (auto ai : a) {
                  c.push_back(ai);
              }
              for (auto bi : b) {
                  c.push_back(bi);
              }
  
              TVector<i32> d;
              for (auto x : Concatenate(a, b)) {
                  d.push_back(x);
              }
  
              EXPECT_EQ(c, d);
          }
  
          {
              TVector<i32> a = {1, 2, 3, 4};
              TVector<i32> c;
              for (auto x : Concatenate(a, TVector<i32>{5, 6})) {
                  c.push_back(x);
              }
              EXPECT_EQ(c, (TVector<i32>{1, 2, 3, 4, 5, 6}));
          }
      }
  
      TEST(FuncTools, CompileConcatenate) {
          auto container = std::vector{1, 2, 3};
          TestViewCompileability(Concatenate(container, container));
          const auto constContainer = std::vector{1, 2, 3};
          TestViewCompileability(Concatenate(constContainer, constContainer));
          const int arrayContainer[] = {1, 2, 3};
          TestViewCompileability(Concatenate(arrayContainer, arrayContainer));
  
          std::vector<int> res;
          for (auto a : Concatenate(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
              res.push_back(a);
          }
          EXPECT_EQ(res, (std::vector{0, 1, 2, 0, 1, 2}));
      }
  
      TEST(FuncTools, Combo) {
          FOR_DISPATCH_2(i, j, Enumerate(xrange(10u))) {
              EXPECT_EQ(i, j);
          }
  
          FOR_DISPATCH_2(i, jk, Enumerate(Enumerate(xrange(10u)))) {
              EXPECT_EQ(i, std::get<0>(jk));
              EXPECT_EQ(std::get<0>(jk), std::get<1>(jk));
          }
  
          TVector<size_t> a = {0, 1, 2};
          FOR_DISPATCH_2(i, j, Enumerate(Reversed(a))) {
              EXPECT_EQ(i, 2 - j);
          }
  
          FOR_DISPATCH_2(i, j, Enumerate(Map<float>(a))) {
              EXPECT_EQ(i, (size_t)j);
          }
  
          FOR_DISPATCH_2(i, j, Zip(a, Map<float>(a))) {
              EXPECT_EQ(i, (size_t)j);
          }
  
          auto mapper = [](auto&& x) {
              return std::get<0>(x) + std::get<1>(x);
          };
          FOR_DISPATCH_2(i, j, Zip(a, Map(mapper, Zip(a, a)))) {
              EXPECT_EQ(j, 2 * i);
          }
      }
  
  
      TEST(FuncTools, CopyIterator) {
          TVector a = {1, 2, 3, 4};
          TVector b = {4, 5, 6, 7};
  
          // calls f on 2nd, 3d and 4th positions (numeration from 1st)
          auto testIterator = [](auto it, auto f) {
              ++it;
              auto it2 = it;
              ++it2;
              ++it2;
              auto it3 = it;
              ++it3;
              f(*it, *it3, *it2);
          };
  
          {
              auto iterable = Enumerate(a);
              testIterator(std::begin(iterable),
                  [](auto p2, auto p3, auto p4) {
                      EXPECT_EQ(std::get<0>(p2), 1u);
                      EXPECT_EQ(std::get<1>(p2), 2);
                      EXPECT_EQ(std::get<0>(p3), 2u);
                      EXPECT_EQ(std::get<1>(p3), 3);
                      EXPECT_EQ(std::get<0>(p4), 3u);
                      EXPECT_EQ(std::get<1>(p4), 4);
                  });
          }
  
          {
              auto iterable = Map([](i32 x) { return x*x; }, a);
              testIterator(std::begin(iterable),
                  [](auto p2, auto p3, auto p4) {
                      EXPECT_EQ(p2, 4);
                      EXPECT_EQ(p3, 9);
                      EXPECT_EQ(p4, 16);
                  });
          }
  
          {
              auto iterable = Zip(a, b);
              testIterator(std::begin(iterable),
                  [](auto p2, auto p3, auto p4) {
                      EXPECT_EQ(std::get<0>(p2), 2);
                      EXPECT_EQ(std::get<1>(p2), 5);
                      EXPECT_EQ(std::get<0>(p3), 3);
                      EXPECT_EQ(std::get<1>(p3), 6);
                      EXPECT_EQ(std::get<0>(p4), 4);
                      EXPECT_EQ(std::get<1>(p4), 7);
                  });
          }
  
          {
              auto c = {1, 2, 3, 4, 5, 6, 7, 8};
              auto iterable = Filter([](i32 x) { return !(x & 1); }, c);
              testIterator(std::begin(iterable),
                  [](auto p2, auto p3, auto p4) {
                      EXPECT_EQ(p2, 4);
                      EXPECT_EQ(p3, 6);
                      EXPECT_EQ(p4, 8);
                  });
          }
  
          {
              auto iterable = CartesianProduct(TVector{0, 1}, TVector{2, 3});
              // (0, 2), (0, 3), (1, 2), (1, 3)
              testIterator(std::begin(iterable),
                  [](auto p2, auto p3, auto p4) {
                      EXPECT_EQ(std::get<0>(p2), 0);
                      EXPECT_EQ(std::get<1>(p2), 3);
                      EXPECT_EQ(std::get<0>(p3), 1);
                      EXPECT_EQ(std::get<1>(p3), 2);
                      EXPECT_EQ(std::get<0>(p4), 1);
                      EXPECT_EQ(std::get<1>(p4), 3);
                  });
          }
      }
  