basedOpinionated utility library |
| git clone git://git.dimitrijedobrota.com/based.git |
| Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING |
| commit | 384b31564a11badfc731401661f1a3a7c6b1a76f |
| parent | 8b67b5bf5f39a7349c4b41486f91d83f76644a20 |
| author | Dimitrije Dobrota <mail@dimitrijedobrota.com> |
| date | Sun, 13 Apr 2025 15:22:56 +0200 |
Partition algorithms tests and bug fixing
Diffstat:| M | include/based/algorithm.hpp | | | ++++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | include/based/functional.hpp | | | +++++----- |
| M | test/CMakeLists.txt | | | +++-- |
| M | test/source/find_mismatch_test.cpp | | | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/source/partition_test.cpp | | | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 318 insertions(+), 85 deletions(-)
diff --git a/include/based/algorithm.hpp b/include/based/algorithm.hpp
@@ -409,24 +409,6 @@ I find_adjacent_mismatch(I f, I d, R r)
return f;
}
template<ReadableForwardIterator I, IterRelation<I> R>
I find_adjacent_mismatch_forward(I f, I d, R r)
{
// Precondition: readable_bounded_range(f, d)
if (f == d) {
return d;
}
I t;
do {
t = f;
f = successor(f);
} while (f != d && r(*t, *f));
return f;
}
template<ReadableIterator I, IterRelation<I> R>
bool relation_preserving(I f, I d, R r)
{
@@ -448,41 +430,7 @@ bool increasing_range(I f, I d, R r)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return relation_preserving(f, d, complement_of_converse(r));
}
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
bool partitioned(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d)
return find_if(f, d, p).second != d;
}
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
I partition_point(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d)
assert(partitioned(f, d, p));
return partition_point_n(f, d - f, p);
}
template<ReadableForwardIterator I, IterRelation<I> R>
I lower_bound(I f, I d, const iter_value_t<I>& a, R r)
{
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
return partition_point(f, d, lower_bound_predicate(a, r));
}
template<ReadableForwardIterator I, IterRelation<I> R>
I upper_bound(I f, I d, const iter_value_t<I>& a, R r)
{
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
return partition_point(f, d, upper_bound_predicate(a, r));
return relation_preserving(f, d, complement_of_converse<iter_value_t<I>>(r));
}
/* ----- Counted Range Algorithms ----- */
@@ -710,6 +658,7 @@ auto find_adjacent_mismatch_n(I f, iter_dist_t<I> n, R r)
auto x = *f;
f = successor(f);
n = predecessor(n);
while (!zero(n) && r(x, *f)) {
x = *f;
n = predecessor(n);
@@ -724,7 +673,7 @@ bool relation_preserving_n(I f, iter_dist_t<I> n, R r)
{
// Precondition: readable_bounded_range(f,n)
// Precondition: weak_ordering(r);
return find_adjacent_mismatch_n(f, n, r).second != 0;
return find_adjacent_mismatch_n(f, n, r).second == 0;
}
template<ReadableIterator I, IterRelation<I> R>
@@ -740,14 +689,56 @@ bool increasing_range_n(I f, iter_dist_t<I> n, R r)
{
// Precondition: readable_bounded_range(f,n)
// Precondition: weak_ordering(r);
return relation_preserving_n(f, n, complement_of_converse(r));
return relation_preserving_n(
f, n, complement_of_converse<iter_value_t<I>>(r));
}
/* ----- Sentinel Ranges ----- */
template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_unguarded(I f, P p)
{
// Precondition: readable_bounded_range(f, d) && some(f, d, p);
while (!p(*f)) {
f = successor(f);
}
return f;
}
template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_not_unguarded(I f, P p)
{
// Precondition: readable_bounded_range(f, d) && not_all(f, d, p);
while (p(*f)) {
f = successor(f);
}
return f;
}
template<ReadableForwardIterator I, IterRelation<I> R>
I find_adjacent_mismatch_forward(I f, I d, R r)
{
// Precondition: readable_bounded_range(f, d)
if (f == d) {
return d;
}
I t;
do {
t = f;
f = successor(f);
} while (f != d && r(*t, *f));
return f;
}
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
bool partitioned_n(I f, iter_dist_t<I> n, P p)
{
// Precondition: readable_bounded_range(f, n)
return find_if_n(f, n, p).second != 0;
std::tie(f, n) = find_if_n(f, n, p);
return find_if_not_n(f, n, p).second == 0;
}
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
@@ -756,13 +747,15 @@ I partition_point_n(I f, iter_dist_t<I> n, P p)
// Precondition: readable_bounded_range(f, n)
assert(partitioned_n(f, n, p));
auto h = half(n);
I m = f + h;
if (p(*f)) {
n = h;
} else {
n -= successor(h);
f = successor(n);
while (!zero(n)) {
const auto h = half(n);
I m = f + h;
if (p(*m)) {
n = h;
} else {
n -= successor(h);
f = successor(m);
}
}
return f;
}
@@ -785,26 +778,38 @@ I upper_bound_n(I f, iter_dist_t<I> n, const iter_value_t<I>& a, R r)
return partition_point_n(f, n, upper_bound_predicate(a, r));
}
/* ----- Sentinel Ranges ----- */
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
bool partitioned(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d)
return find_if_not(find_if(f, d, p), d, p) == d;
}
template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_unguarded(I f, P p)
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
I partition_point(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d) && some(f, d, p);
while (!p(*f)) {
f = successor(f);
}
return f;
// Precondition: readable_bounded_range(f, d)
assert(partitioned(f, d, p));
return partition_point_n(f, d - f, p);
}
template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_not_unguarded(I f, P p)
template<ReadableForwardIterator I, IterRelation<I> R>
I lower_bound(I f, I d, const iter_value_t<I>& a, R r)
{
// Precondition: readable_bounded_range(f, d) && not_all(f, d, p);
while (p(*f)) {
f = successor(f);
}
return f;
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
return based::lower_bound_n(f, d - f, a, r);
}
template<ReadableForwardIterator I, IterRelation<I> R>
I upper_bound(I f, I d, const iter_value_t<I>& a, R r)
{
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
return based::upper_bound_n(f, d - f, a, r);
}
} // namespace based
diff --git a/include/based/functional.hpp b/include/based/functional.hpp
@@ -217,31 +217,31 @@ I fibonacci(I n)
template<typename T, Relation<T> R>
auto complement(R r)
{
return [r](const T& a, const T& b) { return !r(a, b); };
return [=](const T& a, const T& b) { return !r(a, b); };
}
template<typename T, Relation<T> R>
auto converse(R r)
{
return [r](const T& a, const T& b) { return r(b, a); };
return [=](const T& a, const T& b) { return r(b, a); };
}
template<typename T, Relation<T> R>
auto complement_of_converse(R r)
{
return [r](const T& a, const T& b) { return !r(b, a); };
return [=](const T& a, const T& b) { return !r(b, a); };
}
template<typename T, Relation<T> R>
auto lower_bound_predicate(const T& a, R r)
{
return [a, r](const T& x) { return !r(x, a); };
return [=](const T& x) { return !r(x, a); };
}
template<typename T, Relation<T> R>
auto upper_bound_predicate(const T& a, R r)
{
return [a, r](const T& x) { return r(a, x); };
return [=](const T& x) { return r(a, x); };
}
} // namespace based
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
@@ -27,7 +27,7 @@ endfunction()
add_test(min_test)
add_test(max_test)
## ----- Bounden Range -----
## ----- Bounded Range -----
add_test(min_element_test)
add_test(max_element_test)
@@ -40,8 +40,9 @@ add_test(count_test)
add_test(count_if_test)
add_test(reduce_test)
add_test(find_mismatch_test)
add_test(partition_test)
## ----- Bounden Range -----
## ----- Counted Range -----
add_test(for_each_n_test)
add_test(find_n_test)
diff --git a/test/source/find_mismatch_test.cpp b/test/source/find_mismatch_test.cpp
@@ -176,3 +176,69 @@ TEST_CASE("find_adjacent_mismatch(nonequal)",
REQUIRE(itr == std::next(std::begin(arr), 4));
}
TEST_CASE("find_adjacent_mismatch_forward(empty)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array<int, 0> arr = {};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("find_adjacent_mismatch_forward(one)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array arr = {0};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("find_adjacent_mismatch_forward(two equal)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array arr = {0, 0};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("find_adjacent_mismatch_forward(two nonequal)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array arr = {0, 1};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::next(std::begin(arr), 1));
}
TEST_CASE("find_adjacent_mismatch_forward(equal)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array arr = {0, 0, 0, 0, 0, 0};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("find_adjacent_mismatch_forward(nonequal)",
"[algorithm/find_adjacent_mismatch_forward]")
{
std::array arr = {0, 0, 0, 0, 1, 1, 1, 1};
const auto* itr = based::find_adjacent_mismatch_forward(
std::begin(arr), std::end(arr), equal {});
REQUIRE(itr == std::next(std::begin(arr), 4));
}
diff --git a/test/source/partition_test.cpp b/test/source/partition_test.cpp
@@ -0,0 +1,161 @@
#include <array>
#include <catch2/catch_test_macros.hpp>
#include "based/algorithm.hpp"
struct equal
{
auto operator()(int a) const { return a == goal; }
int goal;
};
TEST_CASE("partitioned(empty)", "[algorithm/partitioned]")
{
std::array<int, 0> arr = {};
REQUIRE(based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partitioned(one equal)", "[algorithm/partitioned]")
{
std::array arr = {4};
REQUIRE(based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partitioned(one nonequal)", "[algorithm/partitioned]")
{
std::array arr = {1};
REQUIRE(based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partitioned(partitioned)", "[algorithm/partitioned]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 4, 4};
REQUIRE(based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partitioned(nonpartitioned equal)", "[algorithm/partitioned]")
{
std::array arr = {4, 0, 1, 2, 3, 4, 4, 4};
REQUIRE(!based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partitioned(nonpartitioned nonequal)", "[algorithm/partitioned]")
{
std::array arr = {4, 0, 1, 2, 3, 4, 4, 4, 0};
REQUIRE(!based::partitioned(std::begin(arr), std::end(arr), equal {4}));
}
TEST_CASE("partition_point(empty)", "[algorithm/partition_point]")
{
std::array<int, 0> arr = {};
const auto* itr =
based::partition_point(std::begin(arr), std::end(arr), equal {4});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("partition_point(one equal)", "[algorithm/partition_point]")
{
std::array arr = {4};
const auto* itr =
based::partition_point(std::begin(arr), std::end(arr), equal {4});
REQUIRE(itr == std::begin(arr));
}
TEST_CASE("partition_point(one nonequal)", "[algorithm/partition_point]")
{
std::array arr = {1};
const auto* itr =
based::partition_point(std::begin(arr), std::end(arr), equal {4});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("partition_point(sequence)", "[algorithm/partition_point]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 4, 4};
const auto* itr =
based::partition_point(std::begin(arr), std::end(arr), equal {4});
REQUIRE(itr == std::next(std::begin(arr), 4));
}
TEST_CASE("lower_bound(empty)", "[algorithm/lower_bound]")
{
std::array<int, 0> arr = {};
const auto* itr =
based::lower_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("lower_bound(one equal)", "[algorithm/lower_bound]")
{
std::array arr = {4};
const auto* itr =
based::lower_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::begin(arr));
}
TEST_CASE("lower_bound(one nonequal)", "[algorithm/lower_bound]")
{
std::array arr = {1};
const auto* itr =
based::lower_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("lower_bound(sequence)", "[algorithm/lower_bound]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 5, 5};
const auto* itr =
based::lower_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 4));
}
TEST_CASE("upper_bound(empty)", "[algorithm/lower_bound]")
{
std::array<int, 0> arr = {};
const auto* itr =
based::upper_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("upper_bound(one equal)", "[algorithm/lower_bound]")
{
std::array arr = {4};
const auto* itr =
based::upper_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("upper_bound(one nonequal)", "[algorithm/lower_bound]")
{
std::array arr = {1};
const auto* itr =
based::upper_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::end(arr));
}
TEST_CASE("upper_bound(sequence)", "[algorithm/lower_bound]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 5, 5};
const auto* itr =
based::upper_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 6));
}