based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit8b67b5bf5f39a7349c4b41486f91d83f76644a20
parent054e424411720be888fea8a68711cfaa22d3d044
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSat, 12 Apr 2025 16:30:23 +0200

Bunch on partition algorithms

Diffstat:
Minclude/based/algorithm.hpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Minclude/based/functional.hpp|++++++++++++
Minclude/based/type_traits.hpp|++++++++++++

3 files changed, 187 insertions(+), 0 deletions(-)

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

@@ -3,6 +3,7 @@

#include <functional>
#include <utility>
#include "based/functional.hpp"
#include "based/iterator.hpp"
#include "based/type_traits.hpp"

@@ -408,6 +409,82 @@ 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)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return find_adjacent_mismatch(f, d, r) == d;
}
template<ReadableIterator I, IterRelation<I> R>
bool strictly_increasing_range(I f, I d, R r)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return relation_preserving(f, d, r);
}
template<ReadableIterator I, IterRelation<I> R>
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));
}
/* ----- Counted Range Algorithms ----- */
template<ReadableIterator I, IterUnaryProcedure<I> Proc>

@@ -622,6 +699,92 @@ auto find_mismatch_n_m(

return std::make_tuple(f0, n0, f1, n1);
}
template<ReadableIterator I, IterRelation<I> R>
auto find_adjacent_mismatch_n(I f, iter_dist_t<I> n, R r)
{
// Precondition: readable_bounded_range(f,d)
if (zero(n)) {
return std::make_pair(f, n);
}
auto x = *f;
f = successor(f);
while (!zero(n) && r(x, *f)) {
x = *f;
n = predecessor(n);
f = successor(f);
}
return std::make_pair(f, n);
}
template<ReadableIterator I, IterRelation<I> R>
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;
}
template<ReadableIterator I, IterRelation<I> R>
bool strictly_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, r);
}
template<ReadableIterator I, IterRelation<I> R>
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));
}
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;
}
template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
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);
}
return f;
}
template<ReadableForwardIterator I, IterRelation<I> R>
I lower_bound_n(I f, iter_dist_t<I> n, const iter_value_t<I>& a, R r)
{
// Precondition: weak_ordering(r)
assert(increasing_range_n(f, n, r));
return partition_point_n(f, n, lower_bound_predicate(a, r));
}
template<ReadableForwardIterator I, IterRelation<I> R>
I upper_bound_n(I f, iter_dist_t<I> n, const iter_value_t<I>& a, R r)
{
// Precondition: weak_ordering(r)
assert(increasing_range_n(f, n, r));
return partition_point_n(f, n, upper_bound_predicate(a, r));
}
/* ----- Sentinel Ranges ----- */
template<ReadableIterator I, IterUnaryPredicate<I> P>

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

@@ -232,4 +232,16 @@ auto complement_of_converse(R r)

return [r](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); };
}
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); };
}
} // namespace based

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

@@ -99,11 +99,23 @@ concept Iterator = requires(T t) {

};
template<typename T>
concept ForwardIterator = requires(T t) {
requires(Iterator<T>);
// successor is regular
};
template<typename T>
concept ReadableIterator = requires {
requires(Iterator<T>);
requires(Readable<T>);
};
template<typename T>
concept ReadableForwardIterator = requires {
requires(ForwardIterator<T>);
requires(Readable<T>);
};
// clang-format on
template<typename T>