based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit7878c84a84832916d834b32a13cf5ff504896ef1
parent5339e33b06119b799b79910226098157f26174db
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 8 Apr 2025 13:24:43 +0200

Reduce functions and test

Diffstat:
M.clang-tidy|+
Minclude/based/algorithm.hpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------
Mtest/CMakeLists.txt|+
Atest/source/reduce_test.cpp|++++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 125 insertions(+), 13 deletions(-)

diff --git a/.clang-tidy b/.clang-tidy

@@ -10,6 +10,7 @@ Checks: "*,\

-llvm-header-guard,\
-llvm-include-order,\
-llvmlibc-*,\
-cppcoreguidelines-avoid-do-while,\
-cppcoreguidelines-pro-bounds-constant-array-index,\
-misc-include-cleaner,\
-misc-non-private-member-variables-in-classes,\

diff --git a/include/based/algorithm.hpp b/include/based/algorithm.hpp

@@ -166,7 +166,7 @@ Proc for_each(I f, I d, Proc proc)

// Precondition: readable_bounded_range(f, d);
while (f != d) {
proc(*f);
f = next(f);
f++;
}
return proc;
}

@@ -176,7 +176,7 @@ I find(I f, I d, const iter_value_t<I>& x)

{
// Precondition: readable_bounded_range(f, d);
while (f != d && *f != x) {
f = next(f);
f++;
}
return f;
}

@@ -186,7 +186,7 @@ I find_not(I f, I d, const iter_value_t<I>& x)

{
// Precondition: readable_bounded_range(f, d);
while (f != d && *f == x) {
f = next(f);
f++;
}
return f;
}

@@ -196,7 +196,7 @@ I find_if(I f, I d, P p)

{
// Precondition: readable_bounded_range(f, d);
while (f != d && !p(*f)) {
f = next(f);
f++;
}
return f;
}

@@ -206,7 +206,7 @@ I find_if_not(I f, I d, P p)

{
// Precondition: readable_bounded_range(f, d);
while (f != d && p(*f)) {
f = next(f);
f++;
}
return f;
}

@@ -245,9 +245,9 @@ J count(I f, I d, const iter_value_t<I>& x, J j)

// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (*f == x) {
j = next(j);
j++;
}
f = next(f);
f++;
}
return j;
}

@@ -258,15 +258,16 @@ iter_dist_t<I> count(I f, I d, const iter_value_t<I>& x)

// Precondition: readable_bounded_range(f, d);
return count(f, d, x, iter_dist_t<I> {0});
}
template<ReadableIterator I, Iterator J>
J count_not(I f, I d, const iter_value_t<I>& x, J j)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (*f != x) {
j = next(j);
j++;
}
f = next(f);
f++;
}
return j;
}

@@ -284,9 +285,9 @@ J count_if(I f, I d, P p, J j)

// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (p(*f)) {
j = next(j);
j++;
}
f = next(f);
f++;
}
return j;
}

@@ -304,9 +305,9 @@ J count_if_not(I f, I d, P p, J j)

// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (!p(*f)) {
j = next(j);
j++;
}
f = next(f);
f++;
}
return j;
}

@@ -318,4 +319,57 @@ iter_dist_t<I> count_if_not(I f, I d, P p)

return count_if_not(f, d, p, iter_dist_t<I> {0});
}
template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce_nonempty(I f, I d, Op op, F fun)
{
assert(f != d);
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
auto r = fun(f);
f++;
while (f != d) {
r = op(r, fun(f));
f++;
}
return r;
}
template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce(
I f, I d, Op op, F fun, const decltype(reduce_nonempty(f, d, op, fun))& z)
{
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
if (f == d) {
return z;
}
return reduce_nonempty(f, d, op, fun);
}
template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce_nonzero(
I f, I d, Op op, F fun, const decltype(reduce_nonempty(f, d, op, fun))& z)
{
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
codomain_t<F, I> x;
do {
if (f == d) {
return z;
}
x = fun(f);
f++;
} while (x == z);
while (f != d) {
auto y = fun(f);
if (y != z) {
x = op(x, y);
}
f++;
}
return x;
}
} // namespace based

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt

@@ -32,6 +32,7 @@ add_test(find_test)

add_test(find_if_test)
add_test(count_test)
add_test(count_if_test)
add_test(reduce_test)
# ---- List ----
add_test(list_test)

diff --git a/test/source/reduce_test.cpp b/test/source/reduce_test.cpp

@@ -0,0 +1,56 @@

#include <array>
#include <vector>
#include <catch2/catch_test_macros.hpp>
#include "based/algorithm.hpp"
struct op
{
auto operator()(const auto& a, const auto& b) { return a + b; }
};
struct fun
{
auto operator()(based::Iterator auto it) { return *it; }
};
TEST_CASE("reduce(empty)", "[algorithm/reduce]")
{
const std::array<int, 0> arr = {};
const auto count =
based::reduce(std::cbegin(arr), std::cend(arr), op {}, fun {}, 0);
REQUIRE(count == 0);
}
TEST_CASE("reduce(sequence)", "[algorithm/reduce]")
{
const std::array arr = {0, 1, 2, 3, 4, 5};
const auto count =
based::reduce(std::cbegin(arr), std::cend(arr), op {}, fun {}, 0);
REQUIRE(count == 15);
}
TEST_CASE("reduce_nonzero(empty)", "[algorithm/reduce_nonzero]")
{
const std::array<int, 0> arr = {};
const auto count =
based::reduce_nonzero(std::cbegin(arr), std::cend(arr), op {}, fun {}, 0);
REQUIRE(count == 0);
}
TEST_CASE("reduce_nonzero(sequence)", "[algorithm/reduce_nonzero]")
{
const std::array arr = {0, 1, 2, 3, 4, 5};
const auto count =
based::reduce_nonzero(std::cbegin(arr), std::cend(arr), op {}, fun {}, 0);
REQUIRE(count == 15);
}