based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit927ba815575d69920bce3f172b922d917e95cc06
parent301e6b5c5e5860b347ebd8dd29b964bdf9016e3d
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateThu, 27 Mar 2025 12:40:34 +0100

Orbit functions

Diffstat:
M.clang-tidy|++
Mexample/CMakeLists.txt|+
Aexample/functional.cpp|+++++++++++++++++++++++++
Mexample/type_traits.cpp|++--
Ainclude/based/functional.hpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Minclude/based/type_traits.hpp|+++++++++---

6 files changed, 183 insertions(+), 5 deletions(-)

diff --git a/.clang-tidy b/.clang-tidy

@@ -147,6 +147,8 @@ CheckOptions:

value: 'CamelCase'
- key: 'readability-identifier-naming.TypeAliasCase'
value: 'lower_case'
- key: 'readability-identifier-naming.TypeAliasIgnoredRegexp'
value: 'N'
- key: 'readability-identifier-naming.TypedefCase'
value: 'lower_case'
- key: 'readability-identifier-naming.TypeTemplateParameterCase'

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

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

add_example(algorithm)
add_example(list)
add_example(type_traits)
add_example(functional)
add_folders(Example)

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

@@ -0,0 +1,25 @@

#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';
return 0;
}

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

@@ -57,7 +57,7 @@ int main()

using id = identity<double>;
using ii = identity<irregular>;
static_assert(std::same_as<based::domain_t<id>, std::tuple<double>>);
static_assert(std::same_as<based::domaind>, std::tuple<double>>);
static_assert(std::same_as<based::codomain_t<id>, double>);
static_assert(based::arity_v<id> == 1);

@@ -75,7 +75,7 @@ int main()

using aid = add<irregular, double>;
using adi = add<double, irregular>;
static_assert(std::same_as<based::domain_t<ad>,
static_assert(std::same_as<based::domaind>,
std::tuple<const double&, const double&>>);
static_assert(std::same_as<based::codomain_t<ad>, double>);
static_assert(based::arity_v<ad> == 2);

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

@@ -0,0 +1,144 @@

#pragma once
#include "based/type_traits.hpp"
namespace based
{
template<Transformation F>
distance_t<F> distance(codomain_t<F> x, codomain_t<F> 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<Transformation F>
codomain_t<F> convergant_point(codomain_t<F> x0, codomain_t<F> 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<Transformation F, UnaryPredicate P>
requires SameAs<domain_t<F>, domain_t<P>>
codomain_t<F> collision_point(const codomain_t<F>& 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<Transformation F, UnaryPredicate P>
requires SameAs<domain_t<F>, domain_t<P>>
bool terminating(const codomain_t<F>& x, F f, P p)
{
// Precondition: p(x) <=> F(x) is defined
return !p(collision_point(x, f, p));
}
template<Transformation F, UnaryPredicate P>
requires SameAs<domain_t<F>, domain_t<P>>
bool circular(const codomain_t<F>& 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<Transformation F, UnaryPredicate P>
requires SameAs<domain_t<F>, domain_t<P>>
bool connection_point(const codomain_t<F>& 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<Transformation F, UnaryPredicate P>
requires SameAs<domain_t<F>, domain_t<P>>
std::tuple<distance_t<F>, distance_t<F>, domain_t<F>> orbit_structure(
const codomain_t<F>& 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<Transformation F>
codomain_t<F> collision_point_nonterminating_orbit(const codomain_t<F>& 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<Transformation F>
bool circular_nonterminating_orbit(const codomain_t<F>& x, F f)
{
return x == f(collision_point_nonterminating_orbit(x, f));
}
template<Transformation F>
codomain_t<F> connection_point_nonterminating_orbit(const codomain_t<F>& x, F f)
{
return convergant_point(x, f(collision_point_nonterminating_orbit(x, f)), f);
}
template<Transformation F>
std::tuple<distance_t<F>, distance_t<F>, domain_t<F>>
orbit_structure_nonterminating_orbit(const domain_t<F>& x, F f)
{
const auto y = connection_point_nonterminating_orbit(x, f);
return {distance(x, y, f), distance(f(y), y, f), y};
}
template<Transformation F, Integer N>
codomain_t<F> power_unary(codomain_t<F> x, N n, F f)
{
while (n != N {0}) {
n = n - N {1};
x = f(x);
}
return x;
}
} // namespace based

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

@@ -13,11 +13,14 @@ concept Integer = std::integral<T>;

template<typename T>
concept Regular = std::regular<T>;
template<typename T, typename U>
concept SameAs = std::is_same_v<T, U> && std::is_same_v<U, T>;
template<typename T>
concept Input =
std::same_as<T,
std::remove_volatile_t<
std::remove_reference_t<std::remove_pointer_t<T>>>>
std::is_same_v<T,
std::remove_volatile_t<
std::remove_reference_t<std::remove_pointer_t<T>>>>
|| (std::is_lvalue_reference_v<T>
&& std::is_const_v<std::remove_reference_t<T>>);

@@ -196,6 +199,9 @@ template<typename P, std::size_t Idx>

using domain_elem_t = std::tuple_element_t<Idx, domain_t<P>>;
template<typename P>
using distance_t = std::uint64_t;
template<typename P>
concept Procedure = detail::FreeProcedure<P> || detail::MemberProcedure<P>
|| detail::FunctorProcedure<P>;