Skip to content

Instantly share code, notes, and snippets.

@justinmeiners
Created August 21, 2021 19:39
Show Gist options
  • Save justinmeiners/cfe3dceaa5f0a4037a657622be2958ab to your computer and use it in GitHub Desktop.
Save justinmeiners/cfe3dceaa5f0a4037a657622be2958ab to your computer and use it in GitHub Desktop.
Implementing free group "free reduce" and a few other operations in a generic way. (C++20 concepts)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment