based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit 6402785e18820dd2c78155a1b9ec43a9da5a7728
parent af6f09456de19449cd0697120574a50ab4d4e0b8
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Mon, 28 Apr 2025 15:33:47 +0200

Remove math stuff for now...

Diffstat:
M example/CMakeLists.txt | -
D example/functional.cpp | ------------------------------------------
M include/based/functional.hpp | ---------------------------------------------------------------------------------
M include/based/type_traits.hpp | ---------------------------------------------------------------------------------

4 files changed, 0 insertions(+), 346 deletions(-)

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

@@ -24,7 +24,6 @@ add_example(instrumentation)

add_example(algorithm)
add_example(list)
add_example(type_traits)
add_example(functional)
add_example(template)

add_folders(Example)

diff --git a/ example/functional.cpp b/ example/functional.cpp

@@ -1,42 +0,0 @@

#include <iostream>

#include "based/functional.hpp"

int main()
{
static const auto func = [](int x)
{
return x != 32 ? 2 * x : 1;
};
static const auto pred = [](int /* x */)
{
return true;
};

std::cout << based::distance(1, 16, func) << '\n';
std::cout << based::power_unary(1, 2, func) << '\n';

std::cout << '\n';
std::cout << based::collision_point(1, func, pred) << '\n';
std::cout << based::terminating(1, func, pred) << '\n';
std::cout << based::circular(1, func, pred) << '\n';
std::cout << based::connection_point(1, func, pred) << '\n';

std::cout << '\n';
std::cout << based::collision_point_nonterminating_orbit(1, func) << '\n';
std::cout << based::circular_nonterminating_orbit(1, func) << '\n';
std::cout << based::connection_point_nonterminating_orbit(1, func) << '\n';

std::cout << '\n';
std::cout << based::power(3, 0, std::multiplies<int> {}, 1) << '\n';
for (std::size_t i = 1; i < 8; i++) {
std::cout << based::power(3, i, std::multiplies<int> {}) << '\n';
}

std::cout << '\n';
for (std::size_t i = 0; i < 8; i++) {
std::cout << based::fibonacci(i) << '\n';
}

return 0;
}

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

@@ -7,216 +7,6 @@

namespace based
{

template<typename T, Transformation<T> F>
distance_t<F> distance(T x, T y, F f)
{
// Precondition: y is reachable from x under f
using N = distance_t<F>;

N n {0};
while (x != y) {
x = f(x);
n = n + N {1};
}
return n;
}

template<typename T, Transformation<T> F>
T convergant_point(T x0, T x1, F f)
{
// Precondition: (exists n from distance_t<F>) n>= 0 ^ f^n(x0) = f^n(x1)
while (x0 != x1) {
x0 = f(x0);
x1 = f(x1);
}
return x0;
}

template<typename T, Transformation<T> F, UnaryPredicate<T> P>
T collision_point(const T& x, F f, P p)
{
// Precondition p(x) <=> f(x) is defined
if (!p(x)) {
return x;
}

auto slow = x;
auto fast = f(x);
while (fast != slow) {
slow = f(slow);
if (!p(fast)) {
return fast;
}
fast = f(fast);
if (!p(fast)) {
return fast;
}
fast = f(fast);
}
return fast;
// Postcondition: return value is terminal point or collision point
}

template<typename T, Transformation<T> F, UnaryPredicate<T> P>
bool terminating(const T& x, F f, P p)
{
// Precondition: p(x) <=> F(x) is defined
return !p(collision_point(x, f, p));
}

template<typename T, Transformation<T> F, UnaryPredicate<T> P>
bool circular(const T& x, F f, P p)
{
// Precondition: p(x) <=> F(x) is defined
const auto y = collision_point(x, f, p);
return p(y) && x == f(y);
}

template<typename T, Transformation<T> F, UnaryPredicate<T> P>
bool connection_point(const T& x, F f, P p)
{
// Precondition: p(x) <=> F(x) is defined
const auto y = collision_point(x, f, p);
if (!p(y)) {
return y;
}
return convergant_point(x, f(y), f);
}

template<typename T, Transformation<T> F, UnaryPredicate<T> P>
std::tuple<distance_t<F>, distance_t<F>, T> orbit_structure(
const T& x, F f, P p
)
{
// Precondition: p(x) <=> F(x) is defined
const auto y = connection_point(x, f, p);
const auto m = distance(x, y, f);
const auto n = p(y) ? distance(f(y), y, f) : 0;
return {m, n, y};
}

template<typename T, Transformation<T> F>
T collision_point_nonterminating_orbit(const T& x, F f)
{
auto slow = x;
auto fast = f(x);
while (fast != slow) {
slow = f(slow);
fast = f(fast);
fast = f(fast);
}
return fast;
// Postcondition: return value is terminal point or collision point
}

template<typename T, Transformation<T> F>
bool circular_nonterminating_orbit(const T& x, F f)
{
return x == f(collision_point_nonterminating_orbit(x, f));
}

template<typename T, Transformation<T> F>
T connection_point_nonterminating_orbit(const T& x, F f)
{
return convergant_point(x, f(collision_point_nonterminating_orbit(x, f)), f);
}

template<typename T, Transformation<T> F>
std::tuple<distance_t<F>, distance_t<F>, T>
orbit_structure_nonterminating_orbit(const T& x, F f)
{
const auto y = connection_point_nonterminating_orbit(x, f);
return {distance(x, y, f), distance(f(y), y, f), y};
}

template<typename T, Transformation<T> F, Integer N>
T power_unary(T x, N n, F f)
{
while (!zero(n)) {
n = predecessor(n);
x = f(x);
}
return x;
}

template<typename T, Integer I, BinaryOperation<T> Op>
T power_left_associated(T a, I n, Op op)
{
assert(n > 0);
return one(n) ? a : op(power_left_associated(a, predecessor(n), op), a);
}

template<typename T, Integer I, BinaryOperation<T> Op>
T power_right_associated(T a, I n, Op op)
{
assert(n > 0);
return one(n) ? a : op(a, power_right_associated(a, predecessor(n), op));
}

template<typename T, Integer I, AssociativeBinaryOperation<T> Op>
T power_accumulate_positive(T r, T a, I n, Op op)
{
assert(n > 0);
while (true) {
if (odd(n)) {
r = op(r, a);
if (one(n)) {
return r;
}
}
a = op(a, a);
n = half(n);
}
}

template<typename T, Integer I, AssociativeBinaryOperation<T> Op>
T power_accumulate(T r, T a, I n, Op op)
{
assert(n >= 0);
return zero(n) ? r : power_accumulate_positive(r, a, n, op);
}

template<typename T, Integer I, AssociativeBinaryOperation<T> Op>
T power(T a, I n, Op op)
{
assert(n > 0);
while (even(n)) {
a = op(a, a);
n = half(n);
}

n = half(n);
return zero(n) ? a : power_accumulate_positive(a, op(a, a), n, op);
}

template<typename T, Integer I, AssociativeBinaryOperation<T> Op>
T power(T a, I n, Op op, T id)
{
assert(n >= 0);
return !zero(n) ? power(a, n, op) : id;
}

template<Integer I>
std::pair<I, I> fibonacci_matrix_multiply(
const std::pair<I, I>& x, const std::pair<I, I>& y
)
{
return {
(x.first * (y.first + y.second)) + (x.second * y.first),
(x.first * y.first) + (x.second * y.second)
};
}

template<Integer I>
I fibonacci(I n)
{
assert(n >= 0);
return !zero(n)
? power<std::pair<I, I>>({I {1}, I {0}}, n, fibonacci_matrix_multiply<I>)
.first
: I {0};
}

template<typename T, Relation<T> R>
auto complement(R r)
{

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

@@ -294,97 +294,4 @@ concept IterRelation = requires {

requires(Relation<P, iter_value_t<I>>);
};

/* ----- Abstract Algebra ----- */

// clang-format off
template<typename T>
concept AdditiveSemigroup = requires(T a, T b) {
requires(Regular<T>);
{ a + b } -> std::same_as<T>;
// associative(+)
// commutative(+)
};

template<typename T>
concept MultiplicativeSemigroup = requires(T a, T b) {
requires(Regular<T>);
{ a * b } -> std::same_as<T>;
// associative(*)
};

template<typename T>
concept AdditiveMonoid = requires {
requires(AdditiveSemigroup<T>);
requires(T{0});
// identity_element(0, +);
};

template<typename T>
concept MultiplicativeMonoid = requires {
requires(MultiplicativeSemigroup<T>);
requires(T{1});
// identity_element(1, *);
};

template<typename T>
concept AdditiveGroup = requires(T a, T b) {
requires(AdditiveMonoid<T>);
{ -a } -> std::same_as<T>;
// inverse_operation(unary -, 0, +);
{ a - b } -> std::same_as<T>;
};

template<typename T>
concept MultiplicativeGroup = requires(T a, T b) {
requires(MultiplicativeMonoid<T>);
// multiplicative_inverse: T -> T;
// inverse_operation(multiplicative_inverse, 1, *)
{ a / b } -> std::same_as<T>;
};

template<typename T>
concept Semiring = requires {
requires(AdditiveMonoid<T>);
requires(MultiplicativeMonoid<T>);
requires(T{0} != T{1});
// annihilation property of 0
// distributivity of multiplication over addition
};

template<typename T>
concept CommutativeSemiring = requires {
requires(Semiring<T>);
// commutative(*)
};

template<typename T>
concept Ring = requires {
requires(AdditiveGroup<T>);
requires(Semiring<T>);
};

template<typename T>
concept CommutativeRing = requires {
requires(AdditiveGroup<T>);
requires(CommutativeSemiring<T>);
};

template<typename T, typename S>
// T -> vectors; S -> scalars
concept Semimodule = requires (S s, T t) {
requires(AdditiveGroup<T>);
requires(CommutativeSemiring<S>);
{ s * t } -> std::same_as<T>;
};

template<typename T, typename S>
// T -> vectors; S -> scalars
concept Module = requires {
requires(Semimodule<T, S>);
requires(AdditiveGroup<T>);
requires(Ring<S>);
};

// clang-format on

} // namespace based