[STLExtras] Add merge_unique

[Bigcheese]

Summary

This is for https://reviews.llvm.org/D36351

This adds the merge_unique algorithm. It's like std::unique except it allows modifying the uniqued values.

[grandinj]

include/llvm/ADT/STLExtras.h

936

modifiy -> modify

include/llvm/ADT/STLExtras.h

 ///
 /// This version works for any container with an erase method call accepting
 /// two iterators.
 template <typename Container, typename UnaryPredicate>
 void erase_if(Container &C, UnaryPredicate P) {
   C.erase(remove_if(C, P), C.end());
 }
 
+/// Like `std::unique`, but calls \p Merge on equal values. \p Merge is allowed
+/// to modifiy its first argument.
+///
+/// \param Merge a binary callable with a signature callable as
+///   `Merge(*declval<ForwardIt>(), *declval<ForwardIt>())`
+///
+/// Example:
+///
+///   int a[] = {1, 2, 2, 3, 4, 5, 5};
+///   auto end = merge_unique(std::begin(a), std::end(a),
+///     [](int a, int b) { return a == b; },
+///     [](int &a, int b) { a += b; });
+///
+///   for (auto i = a; i != end; ++i)
+///     std::cout << *i << " ";
+///
+///   -- 1 4 3 4 10
+template <class ForwardIt, class PredTy, class MergeTy>
+ForwardIt merge_unique(ForwardIt First, ForwardIt Last, PredTy Pred, MergeTy Merge) {
+  if (First == Last)
+    return Last;
+
+  ForwardIt I = First;
+  while (++I != Last) {
+    if (Pred(*First, *I))
+      Merge(*First, *I);
+    else if (++First != I)
+      *First = std::move(*I);
+  }
+  return ++First;
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 
 // Implement make_unique according to N3656.
 
 /// \brief Constructs a `new T()` with the given args and returns a
 ///        `unique_ptr<T>` which owns the object.

unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, ADLTest) {
   EXPECT_EQ(s.swap_val, "lhs");
   EXPECT_EQ(s2.swap_val, "rhs");
 
   int count = 0;
   llvm::for_each(s, [&count](int) { ++count; });
   EXPECT_EQ(5, count);
 }
 
+TEST(STLExtrasTest, merge_unique) {
+  int a[] = {1, 2, 2, 2, 2, 3, 4, 5, 5};
+  auto end = merge_unique(std::begin(a), std::end(a),
+                          [](int a, int b) { return a == b; },
+                          [](int &a, int b) { a += b; });
+  EXPECT_EQ(a + 6, end);
+  EXPECT_EQ(1, a[0]);
+  EXPECT_EQ(4, a[1]);
+  EXPECT_EQ(4, a[2]);
+  EXPECT_EQ(3, a[3]);
+  EXPECT_EQ(4, a[4]);
+  EXPECT_EQ(10, a[5]);
+}
 } // namespace