justinmeiners · August 21, 2021 19:39 · Aug 21, 2021
diff --git a/generic_algebra.cpp b/generic_algebra.cpp
@@ -0,0 +1,119 @@
+#include <iostream>
+#include <iterator>
+
+// With C++20 concepts
+#include <concepts>
+
+template<typename F, typename T>
+concept unary_operation = std::invocable<F, T>
+    && std::same_as<T, std::invoke_result_t<F, T>>;
+
+template<
+    std::input_iterator I,
+    std::bidirectional_iterator D,
+    unary_operation<std::iter_value_t<I>> NegateOp
+    >
+
+    requires std::same_as<std::iter_value_t<I>, std::iter_value_t<D>>
+        && std::regular<std::iter_value_t<I>> 
+
+// Without C++20 concepts 
+/* 
+template<typename I, typename D, typename NegateOp>
+*/
+
+D free_reduce(I first, I last, D out, NegateOp negate)
+{
+  if (first == last) return out;
+
+  D out_start = out;
+  *out = *first;
+  ++out;
+  ++first;
+
+  while (first != last)
+  {
+    if (out != out_start && negate(*first) == *(out - 1))
+    {
+        --out;
+    }
+    else
+    {
+       *out = *first;
+       ++out;
+    }
+    ++first;
+  }
+
+  return out;
+}
+
+
+template<
+    std::input_iterator I,
+    std::bidirectional_iterator D,
+    unary_operation<std::iter_value_t<I>> NegateOp
+    >
+    requires std::same_as<std::iter_value_t<I>, std::iter_value_t<D>>
+
+D word_negate(I first, I last, D d_first, NegateOp negate)
+{
+  D d_last = std::transform(first, last, d_first, negate);
+  std::reverse(d_first, d_last);
+  return d_last;
+}
+
+
+template<
+    std::bidirectional_iterator I,
+    unary_operation<std::iter_value_t<I>> NegateOp
+    >
+
+void word_negate_inplace(I first, I last, NegateOp negate)
+{
+   word_negate(first, last, first, negate);
+}
+
+template<std::bidirectional_iterator I>
+void word_negate_inplace(I first, I last)
+{
+   word_negate(first, last, first, std::negate<std::iter_value_t<I>>());
+}
+
+
+template<typename I>
+void print_word(I start, I end)
+{
+    while (start != end)
+    {
+        std::cout << (*start) << " ";
+        ++start;
+    }
+    std::cout << std::endl;
+}
+
+int main(int argc, const char* argv[])
+{
+  int word[] = { 3, -2, 1, -1, 2, 7, -1, 1, 4 };
+  constexpr size_t n = sizeof(word) / sizeof(int);
+
+
+  {
+    int out[n];
+    int* end_out = free_reduce(word, word + n, out, std::negate());
+    print_word(out, end_out);
+  }
+
+  {
+    int out[n];
+    int* end_out = word_negate(word, word + n, out, std::negate());
+    print_word(out, end_out);
+  }
+
+  {
+     word_negate_inplace(word, word + n);
+     print_word(word, word + n);
+  }
+
+  return 0;
+}