zip

include/llvm/ADT/STLExtras.h

auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
     build_index_impl<
         std::tuple_size<typename std::decay<Tuple>::type>::value>())) {
   using Indices = build_index_impl<
       std::tuple_size<typename std::decay<Tuple>::type>::value>;
 
   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
                                   Indices());
 }
+
+namespace detail {
+template <typename... Iter> struct zipper {
+private:
+  template <std::size_t N>
+  static bool any_equal_pair(const std::tuple<Iter...> &LHS,
+                             const std::tuple<Iter...> &RHS) {
+    if (std::get<N>(LHS) == std::get<N>(RHS))
+      return true;
+    return any_equal_pair<N + 1>(LHS, RHS);
+  }
+  template <>
+  static bool any_equal_pair<sizeof...(Iter)>(const std::tuple<Iter...> &LHS,
+                                              const std::tuple<Iter...> &RHS) {
+    return false;
+  }
+
+  static auto deref_iter_tuple(Iter... Items) {
+    return std::tuple<decltype(*Items)...>(*std::forward<Iter>(Items)...);
+  }
+
+  static auto increment_iter_tuple(Iter... Items) {
+    return std::make_tuple(++std::forward<Iter>(Items)...);
+  }
+
+public:
+  explicit zipper(std::tuple<Iter...> &&Begins, std::tuple<Iter...> &&Ends)
+      : Begins(std::move(Begins)), Ends(std::move(Ends)) {}
+
+  struct iterator {
+    iterator(std::tuple<Iter...> Pos) : Pos(Pos) {}
+
+    auto operator*() { return apply_tuple(deref_iter_tuple, Pos); }
+
+    auto operator*() const { return apply_tuple(deref_iter_tuple, Pos); }
+
+    iterator &operator++() {
+      Pos = apply_tuple(increment_iter_tuple, Pos);
+      return *this;
+    }
+
+    bool operator==(const iterator &RHS) const {
+      // Return true if *any* of the items are equal.  This way consider a
+      // tuple of iterators where any one item refers to the end of the zipped
+      // members as referring to the end of the entire zipped sequence.
+      return zipper::any_equal_pair<0>(Pos, RHS.Pos);
+    }
+
+    bool operator!=(const iterator &RHS) const { return !(*this == RHS); }
+
+  private:
+    std::tuple<Iter...> Pos;
+  };
+
+  iterator begin() { return iterator(Begins); }
+  iterator end() { return iterator(Ends); }
+
+  iterator begin() const { return iterator(Begins); }
+  iterator end() const { return iterator(Ends); }
+
+private:
+  std::tuple<Iter...> Begins;
+  std::tuple<Iter...> Ends;
+};
+
+template <typename... Iter>
+auto make_zipper(std::tuple<Iter...> &&Begins, std::tuple<Iter...> &&Ends) {
+  return zipper<Iter...>(std::move(Begins), std::move(Ends));
+}
+}
+
+template <typename... Rs> auto zip(Rs &&... Ranges) {
+  return detail::make_zipper(
+      std::make_tuple(std::begin(std::forward<Rs>(Ranges))...),
+      std::make_tuple(std::end(std::forward<Rs>(Ranges))...));
+}
+
 } // End llvm namespace
 
 #endif

unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, ApplyTupleVariadic) {
   std::vector<char> B = {'A', 'B', 'C'};
   std::vector<std::string> C = {"A", "B", "C"};
 
   auto Iters = std::make_tuple(A.begin(), B.begin(), C.begin());
   auto Values = apply_tuple(deref_iterator_tuple(), Iters);
 
   static_assert(
       std::is_same<std::tuple<int, char, std::string>, decltype(Values)>::value,
-      "Incorrect tuple type!");
+      "Tuple elements are not value types!");
 
   EXPECT_EQ(1, std::get<0>(Values));
   EXPECT_EQ('A', std::get<1>(Values));
   EXPECT_EQ("A", std::get<2>(Values));
 
   Iters = apply_tuple(increment_iterator_tuple(), Iters);
   Values = apply_tuple(deref_iterator_tuple(), Iters);
 
   EXPECT_EQ(2, std::get<0>(Values));
   EXPECT_EQ('B', std::get<1>(Values));
   EXPECT_EQ("B", std::get<2>(Values));
 }
+
+TEST(STLExtrasTest, Zip) {
+  std::vector<int> A = {1, 2, 3};
+  std::vector<char> B = {'A', 'B', 'C'};
+  std::vector<std::string> C = {"A", "B", "C"};
+
+  std::vector<std::tuple<int, char, std::string>> Results;
+  for (auto entries : zip(A, B, C)) {
+    static_assert(std::is_same<std::tuple<int &, char &, std::string &>,
+                               decltype(entries)>::value,
+                  "tuple entries are not reference types!");
+    Results.push_back(entries);
+  }
+
+  ASSERT_EQ(3u, Results.size());
+  EXPECT_EQ(std::make_tuple(1, 'A', "A"), Results[0]);
+  EXPECT_EQ(std::make_tuple(2, 'B', "B"), Results[1]);
+  EXPECT_EQ(std::make_tuple(3, 'C', "C"), Results[2]);
+}
+
+TEST(STLExtrasTest, ZipUneven) {
+  std::vector<int> A = {1, 2, 3, 4, 5};
+  std::vector<char> B = {'A', 'B', 'C', 'D'};
+  std::vector<std::string> C = {"A", "B", "C", "D", "E", "F", "G"};
+
+  std::vector<std::tuple<int, char, std::string>> Results;
+  for (auto entries : zip(A, B, C)) {
+    Results.push_back(entries);
+  }
+
+  ASSERT_EQ(4u, Results.size());
+  EXPECT_EQ(std::make_tuple(1, 'A', "A"), Results[0]);
+  EXPECT_EQ(std::make_tuple(2, 'B', "B"), Results[1]);
+  EXPECT_EQ(std::make_tuple(3, 'C', "C"), Results[2]);
+  EXPECT_EQ(std::make_tuple(4, 'D', "D"), Results[3]);
+}
+
+TEST(STLExtrasTest, ZipEmpty) {
+  std::vector<int> A = {};
+  std::vector<char> B = {'A', 'B', 'C', 'D'};
+  std::vector<std::string> C = {"A", "B", "C", "D", "E", "F", "G"};
+
+  std::vector<std::tuple<int, char, std::string>> Results;
+  for (auto entries : zip(A, B, C)) {
+    Results.push_back(entries);
+  }
+
+  EXPECT_TRUE(Results.empty());
+}
+
+TEST(STLExtrasTest, ZipModifyNonConst) {
+  std::vector<int> A = {0, 1, 2};
+  std::vector<char> B = {'A', 'B', 'C'};
+  const std::vector<std::string> C = {"A", "B", "C"};
+
+  for (auto entries : zip(A, B, C)) {
+    static_assert(std::is_same<std::tuple<int &, char &, const std::string &>,
+                               decltype(entries)>::value,
+                  "tuple entries are not reference types!");
+    std::get<0>(entries) += 42;
+    std::get<1>(entries) -= 'A';
+  }
+
+  EXPECT_EQ(42, A[0]);
+  EXPECT_EQ(43, A[1]);
+  EXPECT_EQ(44, A[2]);
+
+  EXPECT_EQ(0, B[0]);
+  EXPECT_EQ(1, B[1]);
+  EXPECT_EQ(2, B[2]);
+}
 }