based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commitaa6555033365b5b0da0384f2a5e6329eeb2a062c
parent2562c3261807b3e74ffbae8ea7228e5a5d98359d
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSat, 29 Mar 2025 15:18:59 +0100

Relation, tighten algorithm's constraints

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

3 files changed, 63 insertions(+), 30 deletions(-)

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

@@ -3,27 +3,30 @@

#include <functional>
#include <utility>
#include "based/type_traits.hpp"
namespace based
{
// need to deal with returned reference to temporary object...
// returns min element, first if equal
template<typename T, typename Cmp>
const T& min(const T& lhs, const T& rhs, Cmp cmp)
template<Relation R>
const domain_t<R>& min(const domain_t<R>& lhs, const domain_t<R>& rhs, R r)
{
return cmp(rhs, lhs) ? rhs : lhs;
return r(rhs, lhs) ? rhs : lhs;
}
template<typename T>
template<Regular T>
const T& min(const T& lhs, const T& rhs)
{
return based::min(lhs, rhs, std::less());
return based::min(lhs, rhs, std::less<T>());
}
// return first min element
template<typename I, typename Cmp>
I min_element(I first, I last, Cmp cmp)
template<RegularIterator I, Relation R>
requires std::same_as<typename I::value_type, domain_t<R>>
I min_element(I first, I last, R r)
{
if (first == last) {
return last;

@@ -31,7 +34,7 @@ I min_element(I first, I last, Cmp cmp)

I mini = first++;
while (first != last) {
if (cmp(*first, *mini)) {
if (r(*first, *mini)) {
mini = first;
}
first++;

@@ -39,28 +42,29 @@ I min_element(I first, I last, Cmp cmp)

return mini;
}
template<typename I>
template<RegularIterator I>
I min_element(I first, I last)
{
return based::min_element(first, last, std::less());
return based::min_element(first, last, std::less<typename I::value_type>());
}
// returns max element, second if equal
template<typename T, typename Cmp>
const T& max(const T& lhs, const T& rhs, Cmp cmp)
template<Relation R>
const domain_t<R>& max(const domain_t<R>& lhs, const domain_t<R>& rhs, R r)
{
return cmp(rhs, lhs) ? lhs : rhs;
return r(rhs, lhs) ? lhs : rhs;
}
template<typename T>
template<Regular T>
const T& max(const T& lhs, const T& rhs)
{
return based::max(lhs, rhs, std::less());
return based::max(lhs, rhs, std::less<T>());
}
// return last max element
template<typename I, typename Cmp>
I max_element(I first, I last, Cmp cmp)
template<RegularIterator I, Relation R>
requires std::same_as<typename I::value_type, domain_t<R>>
I max_element(I first, I last, R r)
{
if (first == last) {
return last;

@@ -68,7 +72,7 @@ I max_element(I first, I last, Cmp cmp)

I maxi = first++;
while (first != last) {
if (!cmp(*first, *maxi)) {
if (!r(*first, *maxi)) {
maxi = first;
}
first++;

@@ -76,15 +80,16 @@ I max_element(I first, I last, Cmp cmp)

return maxi;
}
template<typename I>
template<RegularIterator I>
I max_element(I first, I last)
{
return based::max_element(first, last, std::less());
return based::max_element(first, last, std::less<typename I::value_type>());
}
// return first min and last max element
template<typename I, typename Cmp>
std::pair<I, I> minmax_element(I first, I last, Cmp cmp)
template<RegularIterator I, Relation R>
requires std::same_as<typename I::value_type, domain_t<R>>
std::pair<I, I> minmax_element(I first, I last, R r)
{
if (first == last) {
return {last, last};

@@ -96,7 +101,7 @@ std::pair<I, I> minmax_element(I first, I last, Cmp cmp)

}
I maxi = first++;
if (cmp(*maxi, *mini)) {
if (r(*maxi, *mini)) {
std::swap(mini, maxi);
}

@@ -105,15 +110,15 @@ std::pair<I, I> minmax_element(I first, I last, Cmp cmp)

I pmini = first;
I pmaxi = next;
if (cmp(*pmaxi, *pmini)) {
if (r(*pmaxi, *pmini)) {
std::swap(pmini, pmaxi);
}
if (cmp(*pmini, *mini)) {
if (r(*pmini, *mini)) {
mini = pmini;
}
if (!cmp(*pmaxi, *maxi)) {
if (!r(*pmaxi, *maxi)) {
maxi = pmaxi;
}

@@ -123,9 +128,9 @@ std::pair<I, I> minmax_element(I first, I last, Cmp cmp)

}
if (first != last) {
if (cmp(*first, *mini)) {
if (r(*first, *mini)) {
mini = first;
} else if (!cmp(*first, *maxi)) {
} else if (!r(*first, *maxi)) {
maxi = first;
}
}

@@ -133,10 +138,11 @@ std::pair<I, I> minmax_element(I first, I last, Cmp cmp)

return {mini, maxi};
}
template<typename I>
template<RegularIterator I>
std::pair<I, I> minmax_element(I first, I last)
{
return based::minmax_element(first, last, std::less());
return based::minmax_element(
first, last, std::less<typename I::value_type>());
}
} // namespace based

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

@@ -219,4 +219,22 @@ I fibonacci(I n)

: I {0};
}
template<Relation R>
auto complement(R r)
{
return [r](const domain_t<R>& a, const domain_t<R>& b) { return !r(a, b); };
}
template<Relation R>
auto converse(R r)
{
return [r](const domain_t<R>& a, const domain_t<R>& b) { return r(b, a); };
}
template<Relation R>
auto complement_of_converse(R r)
{
return [r](const domain_t<R>& a, const domain_t<R>& b) { return !r(b, a); };
}
} // namespace based

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

@@ -26,6 +26,9 @@ concept Integer = requires(T n) {

template<typename T>
concept Regular = std::regular<T>;
template<typename T>
concept RegularIterator = std::regular<typename T::value_type>;
template<typename T, typename U>
concept SameAs = std::is_same_v<T, U> && std::is_same_v<U, T>;

@@ -296,4 +299,10 @@ concept AssociativeBinaryOperation = requires {

// requires(P is associative)
};
template<typename P>
concept Relation = requires {
requires(HomogenousPredicate<P>);
requires(arity_v<P> == 2);
};
} // namespace based