basedOpinionated utility library |
| git clone git://git.dimitrijedobrota.com/based.git |
| Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING |
| commit | d1259323ef4d4cf80573dc14c76064af133a49bd |
| parent | 5d77a74c63b3ff6af2945c707ab6b30a104bee77 |
| author | Dimitrije Dobrota <mail@dimitrijedobrota.com> |
| date | Fri, 4 Apr 2025 17:18:02 +0200 |
Rework iterator and many algorithms
Diffstat:| M | include/based/algorithm.hpp | | | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- |
| A | include/based/iterator.hpp | | | +++++++++++++++++++++++++++++++++++++++++++ |
| M | include/based/type_traits.hpp | | | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------- |
3 files changed, 283 insertions(+), 20 deletions(-)
diff --git a/include/based/algorithm.hpp b/include/based/algorithm.hpp
@@ -3,6 +3,7 @@
#include <functional>
#include <utility>
#include "based/iterator.hpp"
#include "based/type_traits.hpp"
namespace based
@@ -26,7 +27,7 @@ decltype(auto) min(T&& lhs, U&& rhs)
}
// return first min element
template<RegularIterator I, Relation R>
template<Iterator I, Relation R>
requires SameAs<iter_value_t<I>, domain_t<R>>
I min_element(I first, I last, R r)
{
@@ -44,7 +45,7 @@ I min_element(I first, I last, R r)
return mini;
}
template<RegularIterator I>
template<Iterator I>
I min_element(I first, I last)
{
return based::min_element(first, last, std::less<iter_value_t<I>>());
@@ -68,7 +69,7 @@ decltype(auto) max(T&& lhs, U&& rhs)
}
// return last max element
template<RegularIterator I, Relation R>
template<Iterator I, Relation R>
requires std::same_as<iter_value_t<I>, domain_t<R>>
I max_element(I first, I last, R r)
{
@@ -86,14 +87,14 @@ I max_element(I first, I last, R r)
return maxi;
}
template<RegularIterator I>
template<Iterator I>
I max_element(I first, I last)
{
return based::max_element(first, last, std::less<iter_value_t<I>>());
}
// return first min and last max element
template<RegularIterator I, Relation R>
template<Iterator I, Relation R>
requires std::same_as<iter_value_t<I>, domain_t<R>>
std::pair<I, I> minmax_element(I first, I last, R r)
{
@@ -111,7 +112,7 @@ std::pair<I, I> minmax_element(I first, I last, R r)
std::swap(mini, maxi);
}
I next = std::next(first);
I next = based::next(first);
while (first != last && next != last) {
I pmini = first;
I pmaxi = next;
@@ -144,10 +145,180 @@ std::pair<I, I> minmax_element(I first, I last, R r)
return {mini, maxi};
}
template<RegularIterator I>
template<Iterator I>
std::pair<I, I> minmax_element(I first, I last)
{
return based::minmax_element(first, last, std::less<iter_value_t<I>>());
}
template<ReadableIterator I, UnaryProcedure Proc>
requires SameAs<iter_value_t<I>, domain_t<Proc>>
Proc for_each(I f, I d, Proc proc)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
proc(*f);
f = next(f);
}
return proc;
}
template<ReadableIterator I>
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);
}
return f;
}
template<ReadableIterator I>
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);
}
return f;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
I find_if(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && !p(*f)) {
f == next(f);
}
return f;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
I find_if_not(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && p(*f)) {
f == next(f);
}
return f;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
bool all(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return find_if_not(f, d, p) == d;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
bool none(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return find_if(f, d, p) == d;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
bool not_all(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return find_if_not(f, d, p) != d;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
bool some(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return find_if(f, d, p) != d;
}
template<ReadableIterator I, UnaryPredicate P, Iterator J>
requires SameAs<iter_value_t<I>, domain_t<P>>
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);
}
f = next(f);
}
return j;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
iter_dist_t<I> count_if(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return count_if(f, d, p, iter_dist_t<I> {0});
}
template<ReadableIterator I, Iterator J>
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);
}
f = next(f);
}
return j;
}
template<ReadableIterator I>
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, UnaryPredicate P, Iterator J>
requires SameAs<iter_value_t<I>, domain_t<P>>
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);
}
f = next(f);
}
return j;
}
template<ReadableIterator I, UnaryPredicate P>
requires SameAs<iter_value_t<I>, domain_t<P>>
iter_dist_t<I> count_if_not(I f, I d, P p)
{
// Precondition: readable_bounded_range(f, d);
return count_if_not(f, d, p, 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);
}
f = next(f);
}
return j;
}
template<ReadableIterator I>
iter_dist_t<I> count_not(I f, I d, const iter_value_t<I>& x)
{
// Precondition: readable_bounded_range(f, d);
return count_not(f, d, x, iter_dist_t<I> {0});
}
} // namespace based
diff --git a/include/based/iterator.hpp b/include/based/iterator.hpp
@@ -0,0 +1,43 @@
#include "based/integer.hpp"
#include "based/type_traits.hpp"
namespace based
{
template<Iterator I>
I next(I i)
{
return ++i;
}
template<Iterator I>
void increment(I& x)
{
// Precondition: next(x) is defined
x = next(x);
}
template<Iterator I>
I operator+(I f, distance_t<I> n)
{
// Precondition: n >= 0 & weak_range(f, n)
while (!zero(n)) {
n = predecessor(n);
f = based::next(f);
}
return f;
}
template<Iterator I>
distance_t<I> operator-(I d, I f)
{
// Precondition: bounded_range(f, d)
distance_t<I> n {0};
while (f != d) {
n = successor(n);
f = next(f);
}
return n;
}
} // namespace based
diff --git a/include/based/type_traits.hpp b/include/based/type_traits.hpp
@@ -10,6 +10,8 @@
namespace based
{
/* ----- Integer ----- */
template<typename T>
concept Integer = requires(T n) {
successor(n);
@@ -24,35 +26,75 @@ concept Integer = requires(T n) {
odd(n);
};
/* ----- Regular ----- */
template<typename T>
using bare_t = std::remove_cvref_t<T>;
template<typename T>
using iter_value_t = std::iterator_traits<T>::value_type;
concept Regular = std::regular<T>;
template<typename T>
concept BareRegular = std::regular<bare_t<T>>;
template<typename T, typename U>
concept SameAs = std::is_same_v<T, U> && std::is_same_v<U, T>;
template<typename T, typename U>
concept BareSameAs = SameAs<bare_t<T>, bare_t<U>>;
/* ----- Iterator ----- */
// clang-format off
namespace detail {
template<typename I>
struct iterator_traits {
using value_type = std::iterator_traits<I>::value_type;
using distance_type = std::iterator_traits<I>::difference_type;
using pointer_type = std::iterator_traits<I>::pointer;
using reference_type = std::iterator_traits<I>::reference;
};
} // namespace detail
template<typename T>
using iter_diff_t = std::iterator_traits<T>::difference_type;
using iter_value_t = detail::iterator_traits<T>::value_type;
template<typename T>
using iter_ptr_t = std::iterator_traits<T>::pointer;
using iter_dist_t = detail::iterator_traits<T>::distance_type;
template<typename T>
using iter_ref_t = std::iterator_traits<T>::reference;
using iter_ptr_t = detail::iterator_traits<T>::pointer;
template<typename T>
concept Regular = std::regular<T>;
using iter_ref_t = detail::iterator_traits<T>::reference;
template<typename T>
concept BareRegular = std::regular<bare_t<T>>;
concept Readable = requires(T t) {
requires(Regular<T>);
typename T::value_type;
{ *t } -> std::same_as<typename T::value_type>;
};
template<typename T>
concept RegularIterator = std::regular<iter_value_t<T>>;
concept Iterator = requires(T t) {
requires(Regular<T>);
typename iter_dist_t<T>;
// requires(Integer<iter_dist_t<T>>);
{ ++t } -> BareSameAs<T>;
// successor is not necessarily regular
template<typename T, typename U>
concept SameAs = std::is_same_v<T, U> && std::is_same_v<U, T>;
};
template<typename T, typename U>
concept BareSameAs = SameAs<bare_t<T>, bare_t<U>>;
template<typename T>
concept ReadableIterator = requires {
requires(Iterator<T>);
requires(Readable<T>);
};
// clang-format on
template<typename T>
concept Input =
@@ -228,6 +270,7 @@ template<class T>
concept HomogenousDomain = is_input_tuple_v<domain_t<T>>;
} // namespace detail
template<typename P>
inline constexpr auto arity_v = std::tuple_size<detail::domain_t<P>>::value;
@@ -245,7 +288,7 @@ using domain_t =
template<typename P>
using codomain_t = detail::codomain_t<P>;
template<typename P>
template<typename T>
using distance_t = std::uint64_t;
template<typename P>
@@ -253,6 +296,12 @@ concept Procedure = detail::FreeProcedure<P> || detail::MemberProcedure<P>
|| detail::FunctorProcedure<P>;
template<typename P>
concept UnaryProcedure = requires {
requires(Procedure<P>);
requires(arity_v<P> == 1);
};
template<typename P>
concept RegularProcedure = requires {
requires(Procedure<P>);
requires(detail::RegularDomain<P>);
@@ -268,7 +317,7 @@ concept FunctionalProcedure = requires {
template<typename P>
concept UnaryFunction = requires {
requires(FunctionalProcedure<P>);
requires(arity_v<P> == 1);
requires(UnaryProcedure<P>);
};
template<typename P>