based

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

Tune clang-tidy checks for constistency

Stop using:
* magic-numbers
* readability-identifier-length
* modernize-use-nodiscard

Diffstat:
M .clang-tidy | +++++++++++ --------
M example/algorithm.cpp | +++++++++ ------
M example/instrumentation.cpp | ++++++++++ -------
M example/list.cpp | ++++ --
M example/template.cpp | ++++++++++++++++++++++ --------------------
M example/type_traits.cpp | +++++++++++++ -------------
M include/based/algorithm.hpp | ++++++++++++++++++++++++++++++++++++++++++ ----------------------------------------
M include/based/functional.hpp | ++++++++++++++++++++ --------------------
M include/based/instrumentation.hpp | +++++++++++ ----------
M include/based/iterator.hpp | ++++++++++++++++++ ------------------
M include/based/list.hpp | +++++++++++++++ ---------------
M include/based/string.hpp | +++++ -----
M include/based/template.hpp | +++++++ ----
M include/based/type_traits.hpp | +++++ -----
M test/source/find_if_test.cpp | ++++ ----
M test/source/find_mismatch_test.cpp | + -
M test/source/find_test.cpp | ++++ ----
M test/source/for_each_test.cpp | ++++++++ --------
M test/source/list_test.cpp | ++++ --
M test/source/partition_test.cpp | ++++++ ------
M test/source/reduce_test.cpp | ++ --
M test/source/string_literal_test.cpp | +++++ ----

22 files changed, 598 insertions(+), 558 deletions(-)

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

@@ -3,22 +3,21 @@

# misc-non-private-member-variables-in-classes: the options don't do anything
# modernize-use-nodiscard: too aggressive, attribute is situationally useful
Checks: "*,\
-google-readability-todo,\
-altera-*,\
-boost*,\
-cppcoreguidelines-avoid-do-while,\
-cppcoreguidelines-pro-bounds-constant-array-index,\
-fuchsia-*,\
fuchsia-multiple-inheritance,\
-google-readability-todo,\
-llvm-header-guard,\
-llvm-include-order,\
-llvmlibc-*,\
-cppcoreguidelines-avoid-do-while,\
-cppcoreguidelines-pro-bounds-constant-array-index,\
-misc-include-cleaner,\
-misc-non-private-member-variables-in-classes,\
-modernize-use-nodiscard,\
-misc-no-recursion,\
-modernize-use-trailing-return-type,\
-readability-identifier-length,\
-*-magic-numbers,\
-*-use-ranges,\
-readability-suspicious-call-argument,\
-*-ranges,\
"
WarningsAsErrors: ''
CheckOptions:

@@ -162,4 +161,8 @@ CheckOptions:

value: 'lower_case'
- key: 'readability-identifier-naming.VirtualMethodCase'
value: 'lower_case'
- key: 'readability-identifier-length.IgnoredVariableNames'
value: "^[abcdxyznm]$"
- key: 'readability-identifier-length.IgnoredParameterNames'
value: "^[abcdxyznm]$"
...

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

@@ -4,12 +4,15 @@


int main()
{
static constexpr std::size_t size = 16;
static constexpr std::size_t mega = 1024;

{
const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
size,
size * mega * mega,
[](const auto& a, const auto& b)
{
based::min_element(a, b);

@@ -22,8 +25,8 @@ int main()

const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
size,
size * mega * mega,
[](const auto& a, const auto& b)
{
based::max_element(a, b);

@@ -36,8 +39,8 @@ int main()

const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
size,
size * mega * mega,
[](const auto& a, const auto& b)
{
based::minmax_element(a, b);

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

@@ -6,22 +6,25 @@

class reg : public based::registry<reg>
{
public:
explicit reg(int i)
: m_i(i)
explicit reg(int val)
: m_val(val)
{
}

int m_i;
int m_val;
};

int main()
{
static constexpr std::size_t size = 16;
static constexpr std::size_t mega = 1024;

{
const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
size,
size * mega * mega,
[](const auto& a, const auto& b)
{
std::sort(a, b);

@@ -34,8 +37,8 @@ int main()

const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
size,
size * mega * mega,
[](const auto& a, const auto& b)
{
std::stable_sort(a, b);

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

@@ -10,10 +10,12 @@ int main()

using list_pool = based::list_pool<instrumented, std::uint8_t>;
using iter = list_pool::iterator;

static constexpr std::size_t iter_count = 0xFF;

auto pool = list_pool();
auto head = pool.node_empty();

for (std::size_t i = 0; i < 0xFF; i++) {
for (std::size_t i = 0; i < iter_count; i++) {
head = pool.allocate(static_cast<double>(i), head);
}

@@ -25,7 +27,7 @@ int main()

based::free_list(pool, head);

auto queue = pool.queue_empty();
for (std::size_t i = 0; i < 0xFF; i++) {
for (std::size_t i = 0; i < iter_count; i++) {
if (i % 2 == 0) {
queue = pool.push_front(queue, static_cast<double>(i));
} else {

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

@@ -5,37 +5,39 @@


int main()
{
const auto l = based::overload {
[](const int* i)
{
std::cout << "i=" << *i << '\n';
},
[](const double* d)
{
std::cout << "d=" << *d << '\n';
}
};
{
const auto func = based::overload {
[](const int* integer)
{
std::cout << "i=" << *integer << '\n';
},
[](const double* dbl)
{
std::cout << "d=" << *dbl << '\n';
}
};

const int i = 5;
l(&i);
const int integer = 5;
func(&integer);

const double d = 7.3;
l(&d);
const double dbl = 7.3;
func(&dbl);
}

{
const based::Function f = [](int a)
const based::Function func = [](int val)
{
return a + 1;
return val + 1;
};
std::cout << f(3) << '\n';
std::cout << func(3) << '\n';
}

{
const std::function f = [](int a)
const std::function func = [](int val)
{
return a + 1;
return val + 1;
};
std::cout << f(3) << '\n';
std::cout << func(3) << '\n';
}

return 0;

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

@@ -103,29 +103,29 @@ int main()

double,
double>);

static const auto l1 = [](double a)
static const auto func1 = [](double /* a */)
{
return a;
return 1;
};
static_assert(based::Procedure<decltype(l1), double>);
static_assert(based::RegularProcedure<decltype(l1), double>);
static_assert(based::FunctionalProcedure<decltype(l1), double>);
static_assert(based::Procedure<decltype(func1), double>);
static_assert(based::RegularProcedure<decltype(func1), double>);
static_assert(based::FunctionalProcedure<decltype(func1), double>);

static const auto l2 = [](irregular /* a */)
static const auto func2 = [](irregular /* a */)
{
return 1;
};
static_assert(!based::Procedure<decltype(l2), irregular>);
static_assert(!based::RegularProcedure<decltype(l2), irregular>);
static_assert(!based::FunctionalProcedure<decltype(l2), irregular>);
static_assert(!based::Procedure<decltype(func2), irregular>);
static_assert(!based::RegularProcedure<decltype(func2), irregular>);
static_assert(!based::FunctionalProcedure<decltype(func2), irregular>);

static const auto l3 = [](const irregular& /* a */)
static const auto func3 = [](const irregular& /* a */)
{
return 1;
};
static_assert(based::Procedure<decltype(l3), irregular>);
static_assert(!based::RegularProcedure<decltype(l3), irregular>);
static_assert(!based::FunctionalProcedure<decltype(l3), irregular>);
static_assert(based::Procedure<decltype(func3), irregular>);
static_assert(!based::RegularProcedure<decltype(func3), irregular>);
static_assert(!based::FunctionalProcedure<decltype(func3), irregular>);

return 0;
}

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

@@ -25,11 +25,11 @@ concept NoninputRelation = requires {

} // namespace detail

// returns min element, first if equal
template<BareRegular T, BareRegular U, detail::NoninputRelation<T> R>
template<BareRegular T, BareRegular U, detail::NoninputRelation<T> Rel>
requires BareSameAs<T, U>
decltype(auto) min(T&& lhs, U&& rhs, R r)
decltype(auto) min(T&& lhs, U&& rhs, Rel rel)
{
return r(rhs, lhs) ? std::forward<U>(rhs) : std::forward<T>(lhs);
return rel(rhs, lhs) ? std::forward<U>(rhs) : std::forward<T>(lhs);
}

// returns min element, first if equal

@@ -43,11 +43,11 @@ decltype(auto) min(T&& lhs, U&& rhs)

}

// returns max element, second if equal
template<BareRegular T, BareRegular U, detail::NoninputRelation<T> R>
template<BareRegular T, BareRegular U, detail::NoninputRelation<T> Rel>
requires BareSameAs<T, U>
decltype(auto) max(T&& lhs, U&& rhs, R r)
decltype(auto) max(T&& lhs, U&& rhs, Rel rel)
{
return r(rhs, lhs) ? std::forward<T>(lhs) : std::forward<U>(rhs);
return rel(rhs, lhs) ? std::forward<T>(lhs) : std::forward<U>(rhs);
}

// returns max element, second if equal

@@ -63,8 +63,8 @@ decltype(auto) max(T&& lhs, U&& rhs)

/* ----- Bounded Range Algorithms ----- */

// return first min element
template<Iterator I, IterRelation<I> R>
I min_element(I first, I last, R r)
template<Iterator I, IterRelation<I> Rel>
I min_element(I first, I last, Rel rel)
{
if (first == last) {
return last;

@@ -72,7 +72,7 @@ I min_element(I first, I last, R r)


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

@@ -87,8 +87,8 @@ I min_element(I first, I last)

}

// return last max element
template<Iterator I, IterRelation<I> R>
I max_element(I first, I last, R r)
template<Iterator I, IterRelation<I> Rel>
I max_element(I first, I last, Rel rel)
{
if (first == last) {
return last;

@@ -96,7 +96,7 @@ I max_element(I first, I last, R r)


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

@@ -111,8 +111,8 @@ I max_element(I first, I last)

}

// return first min and last max element
template<Iterator I, IterRelation<I> R>
std::pair<I, I> minmax_element(I first, I last, R r)
template<Iterator I, IterRelation<I> Rel>
std::pair<I, I> minmax_element(I first, I last, Rel rel)
{
if (first == last) {
return {last, last};

@@ -124,7 +124,7 @@ std::pair<I, I> minmax_element(I first, I last, R r)

}

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

@@ -133,15 +133,15 @@ std::pair<I, I> minmax_element(I first, I last, R r)

I pmini = first;
I pmaxi = next;

if (r(*pmaxi, *pmini)) {
if (rel(*pmaxi, *pmini)) {
std::swap(pmini, pmaxi);
}

if (r(*pmini, *mini)) {
if (rel(*pmini, *mini)) {
mini = pmini;
}

if (!r(*pmaxi, *maxi)) {
if (!rel(*pmaxi, *maxi)) {
maxi = pmaxi;
}

@@ -151,9 +151,9 @@ std::pair<I, I> minmax_element(I first, I last, R r)

}

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

@@ -168,654 +168,674 @@ std::pair<I, I> minmax_element(I first, I last)

}

template<ReadableIterator I, IterUnaryProcedure<I> Proc>
Proc for_each(I f, I d, Proc proc)
Proc for_each(I first, I last, Proc proc)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
proc(*f);
f = successor(f);
// Precondition: readable_bounded_range(first, last);
while (first != last) {
proc(*first);
first = successor(first);
}
return proc;
}

template<ReadableIterator I>
I find(I f, I d, const iter_value_t<I>& x)
I find(I first, I lst, const iter_value_t<I>& val)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && *f != x) {
f = successor(f);
// Precondition: readable_bounded_range(first, last);
while (first != lst && *first != val) {
first = successor(first);
}
return f;
return first;
}

template<ReadableIterator I>
I find_not(I f, I d, const iter_value_t<I>& x)
I find_not(I first, I last, const iter_value_t<I>& val)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && *f == x) {
f = successor(f);
// Precondition: readable_bounded_range(first, last);
while (first != last && *first == val) {
first = successor(first);
}
return f;
return first;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
I find_if(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && !p(*f)) {
f = successor(f);
// Precondition: readable_bounded_range(first, last);
while (first != last && !pred(*first)) {
first = successor(first);
}
return f;
return first;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_not(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
I find_if_not(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
while (f != d && p(*f)) {
f = successor(f);
// Precondition: readable_bounded_range(first, last);
while (first != last && pred(*first)) {
first = successor(first);
}
return f;
return first;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool all(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool all(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return find_if_not(f, d, p) == d;
// Precondition: readable_bounded_range(first, last);
return find_if_not(first, last, pred) == last;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool none(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool none(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return find_if(f, d, p) == d;
// Precondition: readable_bounded_range(first, last);
return find_if(first, last, pred) == last;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool not_all(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool not_all(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return f == d || find_if_not(f, d, p) != d;
// Precondition: readable_bounded_range(first, last);
return first == last || find_if_not(first, last, pred) != last;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool some(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool some(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return find_if(f, d, p) != d;
// Precondition: readable_bounded_range(first, last);
return find_if(first, last, pred) != last;
}

template<ReadableIterator I, Iterator J>
J count(I f, I d, const iter_value_t<I>& x, J j)
J count(I first, I last, const iter_value_t<I>& val, J cnt)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (*f == x) {
j++;
// Precondition: readable_bounded_range(first, last);
while (first != last) {
if (*first == val) {
cnt++;
}
f = successor(f);
first = successor(first);
}
return j;
return cnt;
}

template<ReadableIterator I>
iter_dist_t<I> count(I f, I d, const iter_value_t<I>& x)
iter_dist_t<I> count(I first, I last, const iter_value_t<I>& val)
{
// Precondition: readable_bounded_range(f, d);
return count(f, d, x, iter_dist_t<I> {0});
// Precondition: readable_bounded_range(first, last);
return count(first, last, val, 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)
J count_not(I first, I last, const iter_value_t<I>& val, J cnt)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (*f != x) {
j++;
// Precondition: readable_bounded_range(first, last);
while (first != last) {
if (*first != val) {
cnt++;
}
f = successor(f);
first = successor(first);
}
return j;
return cnt;
}

template<ReadableIterator I>
iter_dist_t<I> count_not(I f, I d, const iter_value_t<I>& x)
iter_dist_t<I> count_not(I first, I last, const iter_value_t<I>& val)
{
// Precondition: readable_bounded_range(f, d);
return count_not(f, d, x, iter_dist_t<I> {0});
// Precondition: readable_bounded_range(first, last);
return count_not(first, last, val, iter_dist_t<I> {0});
}

template<ReadableIterator I, IterUnaryPredicate<I> P, Iterator J>
J count_if(I f, I d, P p, J j)
template<ReadableIterator I, IterUnaryPredicate<I> Pred, Iterator J>
J count_if(I first, I last, Pred pred, J cnt)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (p(*f)) {
j++;
// Precondition: readable_bounded_range(first, last);
while (first != last) {
if (pred(*first)) {
cnt++;
}
f = successor(f);
first = successor(first);
}
return j;
return cnt;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
iter_dist_t<I> count_if(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
iter_dist_t<I> count_if(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return count_if(f, d, p, iter_dist_t<I> {0});
// Precondition: readable_bounded_range(first, last);
return count_if(first, last, pred, iter_dist_t<I> {0});
}

template<ReadableIterator I, IterUnaryPredicate<I> P, Iterator J>
J count_if_not(I f, I d, P p, J j)
template<ReadableIterator I, IterUnaryPredicate<I> Pred, Iterator J>
J count_if_not(I first, I last, Pred pred, J cnt)
{
// Precondition: readable_bounded_range(f, d);
while (f != d) {
if (!p(*f)) {
j++;
// Precondition: readable_bounded_range(first, last);
while (first != last) {
if (!pred(*first)) {
cnt++;
}
f = successor(f);
first = successor(first);
}
return j;
return cnt;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
iter_dist_t<I> count_if_not(I f, I d, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
iter_dist_t<I> count_if_not(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d);
return count_if_not(f, d, p, iter_dist_t<I> {0});
// Precondition: readable_bounded_range(first, last);
return count_if_not(first, last, pred, iter_dist_t<I> {0});
}

template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce_nonempty(I f, I d, Op op, F fun)
auto reduce_nonempty(I first, I last, Op opr, F fun)
{
assert(f != d);
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
assert(first != last);
// Precondition: bounded_range(first, last)
// Precondition: partially_associative(opr)

auto r = fun(f);
f = successor(f);
while (f != d) {
r = op(r, fun(f));
f = successor(f);
auto res = fun(first);
first = successor(first);
while (first != last) {
res = opr(res, fun(first));
first = successor(first);
}
return r;
return res;
}

template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce(
I f, I d, Op op, F fun, const decltype(reduce_nonempty(f, d, op, fun))& z
I first,
I last,
Op opr,
F fun,
const decltype(reduce_nonempty(first, last, opr, fun))& zero
)
{
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
if (f == d) {
return z;
// Precondition: bounded_range(first, last)
// Precondition: partially_associative(opr)
if (first == last) {
return zero;
}
return reduce_nonempty(f, d, op, fun);
return reduce_nonempty(first, last, opr, fun);
}

template<Iterator I, UnaryFunction<I> F, BinaryOperation<codomain_t<F, I>> Op>
auto reduce_nonzero(
I f, I d, Op op, F fun, const decltype(reduce_nonempty(f, d, op, fun))& z
I first,
I last,
Op opr,
F fun,
const decltype(reduce_nonempty(first, last, opr, fun))& zero
)
{
// Precondition: bounded_range(f,d)
// Precondition: partially_associative(op)
codomain_t<F, I> x;
// Precondition: bounded_range(first, last)
// Precondition: partially_associative(opr)
codomain_t<F, I> res;
do {
if (f == d) {
return z;
if (first == last) {
return zero;
}
x = fun(f);
f = successor(f);
} while (x == z);

while (f != d) {
auto y = fun(f);
if (y != z) {
x = op(x, y);
res = fun(first);
first = successor(first);
} while (res == zero);

while (first != last) {
auto crnt = fun(first);
if (crnt != zero) {
res = opr(res, crnt);
}
f = successor(f);
first = successor(first);
}
return x;
return res;
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> Rel>
requires BareSameAs<iter_value_t<I0>, iter_value_t<I1>>
auto find_mismatch(I0 f0, I0 d0, I1 f1, I1 d1, R r)
auto find_mismatch(I0 first0, I0 last0, I1 first1, I1 last1, Rel rel)
{
// Precondition: readable_bounded_range(f0,d0)
// Precondition: readable_bounded_range(f1,d1)
while (f0 != d0 && f1 != d1 && r(*f0, *f1)) {
f0 = successor(f0);
f1 = successor(f1);
// Precondition: readable_bounded_range(first0, last0)
// Precondition: readable_bounded_range(first1, last1)
while (first0 != last0 && first1 != last1 && rel(*first0, *first1)) {
first0 = successor(first0);
first1 = successor(first1);
}
return std::make_pair(f0, f1);
return std::make_pair(first0, first1);
}

template<ReadableIterator I, IterRelation<I> R>
I find_adjacent_mismatch(I f, I d, R r)
template<ReadableIterator I, IterRelation<I> Rel>
I find_adjacent_mismatch(I first, I last, Rel rel)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: readable_bounded_range(first, last)

if (f == d) {
return d;
if (first == last) {
return last;
}

auto x = *f;
f = successor(f);
while (f != d && r(x, *f)) {
x = *f;
f = successor(f);
auto crnt = *first;
first = successor(first);
while (first != last && rel(crnt, *first)) {
crnt = *first;
first = successor(first);
}

return f;
return first;
}

template<ReadableIterator I, IterRelation<I> R>
bool relation_preserving(I f, I d, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool relation_preserving(I first, I last, Rel rel)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return find_adjacent_mismatch(f, d, r) == d;
// Precondition: readable_bounded_range(first, last)
// Precondition: weak_ordering(rel);
return find_adjacent_mismatch(first, last, rel) == last;
}

template<ReadableIterator I, IterRelation<I> R>
bool strictly_increasing_range(I f, I d, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool strictly_increasing_range(I first, I last, Rel rel)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return relation_preserving(f, d, r);
// Precondition: readable_bounded_range(first, last)
// Precondition: weak_ordering(rel);
return relation_preserving(first, last, rel);
}

template<ReadableIterator I, IterRelation<I> R>
bool increasing_range(I f, I d, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool increasing_range(I first, I last, Rel rel)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: weak_ordering(r);
return relation_preserving(f, d, complement_of_converse<iter_value_t<I>>(r));
// Precondition: readable_bounded_range(first, last)
// Precondition: weak_ordering(rel);
return relation_preserving(
first, last, complement_of_converse<iter_value_t<I>>(rel)
);
}

/* ----- Counted Range Algorithms ----- */

template<ReadableIterator I, IterUnaryProcedure<I> Proc>
auto for_each_n(I f, iter_dist_t<I> n, Proc proc)
auto for_each_n(I first, iter_dist_t<I> size, Proc proc)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n)) {
n = predecessor(n);
proc(*f);
f = successor(f);
// Precondition: readable_weak_range(first, size);
while (!zero(size)) {
size = predecessor(size);
proc(*first);
first = successor(first);
}
return std::make_pair(proc, f);
return std::make_pair(proc, first);
}

template<ReadableIterator I>
auto find_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x)
auto find_n(I first, iter_dist_t<I> size, const iter_value_t<I>& val)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n) && *f != x) {
n = predecessor(n);
f = successor(f);
// Precondition: readable_weak_range(first, size);
while (!zero(size) && *first != val) {
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, n);
return std::make_pair(first, size);
}

template<ReadableIterator I>
auto find_not_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x)
auto find_not_n(I first, iter_dist_t<I> size, const iter_value_t<I>& val)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n) && *f == x) {
n = predecessor(n);
f = successor(f);
// Precondition: readable_weak_range(first, size);
while (!zero(size) && *first == val) {
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, n);
return std::make_pair(first, size);
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
auto find_if_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
auto find_if_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n) && !p(*f)) {
n = predecessor(n);
f = successor(f);
// Precondition: readable_weak_range(first, size);
while (!zero(size) && !pred(*first)) {
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, n);
return std::make_pair(first, size);
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
auto find_if_not_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
auto find_if_not_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n) && p(*f)) {
n = predecessor(n);
f = successor(f);
// Precondition: readable_weak_range(first, size);
while (!zero(size) && pred(*first)) {
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, n);
return std::make_pair(first, size);
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool all_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool all_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, d);
return find_if_not_n(f, n, p).second == 0;
// Precondition: readable_weak_range(first, last);
return find_if_not_n(first, size, pred).second == 0;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool none_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool none_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
return find_if_n(f, n, p).second == 0;
// Precondition: readable_weak_range(first, size);
return find_if_n(first, size, pred).second == 0;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool not_all_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool not_all_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
return n == 0 || find_if_not_n(f, n, p).second != 0;
// Precondition: readable_weak_range(first, size);
return size == 0 || find_if_not_n(first, size, pred).second != 0;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
bool some_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
bool some_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
return find_if_n(f, n, p).second != 0;
// Precondition: readable_weak_range(first, size);
return find_if_n(first, size, pred).second != 0;
}

template<ReadableIterator I, Iterator J>
auto count_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x, J j)
auto count_n(I first, iter_dist_t<I> size, const iter_value_t<I>& val, J cnt)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n)) {
if (*f == x) {
j++;
// Precondition: readable_weak_range(first, size);
while (!zero(size)) {
if (*first == val) {
cnt++;
}
n = predecessor(n);
f = successor(f);
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, j);
return std::make_pair(first, cnt);
}

template<ReadableIterator I>
auto count_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x)
auto count_n(I first, iter_dist_t<I> size, const iter_value_t<I>& val)
{
// Precondition: readable_weak_range(f, n);
return count_n(f, n, x, iter_dist_t<I> {0});
// Precondition: readable_weak_range(first, size);
return count_n(first, size, val, iter_dist_t<I> {0});
}

template<ReadableIterator I, Iterator J>
auto count_not_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x, J j)
auto count_not_n(
I first, iter_dist_t<I> size, const iter_value_t<I>& val, J cnt
)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n)) {
if (*f != x) {
j++;
// Precondition: readable_weak_range(first, size);
while (!zero(size)) {
if (*first != val) {
cnt++;
}
n = predecessor(n);
f = successor(f);
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, j);
return std::make_pair(first, cnt);
}

template<ReadableIterator I>
auto count_not_n(I f, iter_dist_t<I> n, const iter_value_t<I>& x)
auto count_not_n(I first, iter_dist_t<I> size, const iter_value_t<I>& val)
{
// Precondition: readable_weak_range(f, n);
return count_not_n(f, n, x, iter_dist_t<I> {0});
// Precondition: readable_weak_range(first, size);
return count_not_n(first, size, val, iter_dist_t<I> {0});
}

template<ReadableIterator I, IterUnaryPredicate<I> P, Iterator J>
auto count_if_n(I f, iter_dist_t<I> n, P p, J j)
template<ReadableIterator I, IterUnaryPredicate<I> Pred, Iterator J>
auto count_if_n(I first, iter_dist_t<I> size, Pred pred, J cnt)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n)) {
if (p(*f)) {
j++;
// Precondition: readable_weak_range(first, size);
while (!zero(size)) {
if (pred(*first)) {
cnt++;
}
n = predecessor(n);
f = successor(f);
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, j);
return std::make_pair(first, cnt);
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
auto count_if_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
auto count_if_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
return count_if_n(f, n, p, iter_dist_t<I> {0});
// Precondition: readable_weak_range(first, size);
return count_if_n(first, size, pred, iter_dist_t<I> {0});
}

template<ReadableIterator I, IterUnaryPredicate<I> P, Iterator J>
auto count_if_not_n(I f, iter_dist_t<I> n, P p, J j)
template<ReadableIterator I, IterUnaryPredicate<I> Pred, Iterator J>
auto count_if_not_n(I first, iter_dist_t<I> size, Pred pred, J cnt)
{
// Precondition: readable_weak_range(f, n);
while (!zero(n)) {
if (!p(*f)) {
j++;
// Precondition: readable_weak_range(first, size);
while (!zero(size)) {
if (!pred(*first)) {
cnt++;
}
n = predecessor(n);
f = successor(f);
size = predecessor(size);
first = successor(first);
}
return std::make_pair(f, j);
return std::make_pair(first, cnt);
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
auto count_if_not_n(I f, iter_dist_t<I> n, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
auto count_if_not_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_weak_range(f, n);
return count_if_not_n(f, n, p, iter_dist_t<I> {0});
// Precondition: readable_weak_range(first, size);
return count_if_not_n(first, size, pred, iter_dist_t<I> {0});
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> Rel>
requires BareSameAs<iter_value_t<I0>, iter_value_t<I1>>
auto find_mismatch_n(I0 f0, iter_dist_t<I0> n0, I1 f1, I1 d1, R r)
auto find_mismatch_n(
I0 first0, iter_dist_t<I0> size0, I1 first1, I1 last1, Rel rel
)
{
// Precondition: readable_weak_range(f0,n0)
// Precondition: readable_bounded_range(f1,d1)
while (!zero(n0) && f1 != d1 && r(*f0, *f1)) {
n0 = predecessor(n0);
f0 = successor(f0);
f1 = successor(f1);
// Precondition: readable_weak_range(first0, size0)
// Precondition: readable_bounded_range(first1,last1)
while (!zero(size0) && first1 != last1 && rel(*first0, *first1)) {
size0 = predecessor(size0);
first0 = successor(first0);
first1 = successor(first1);
}
return std::make_tuple(f0, n0, f1);
return std::make_tuple(first0, size0, first1);
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> Rel>
requires BareSameAs<iter_value_t<I0>, iter_value_t<I1>>
auto find_mismatch_m(I0 f0, I0 d0, I1 f1, iter_dist_t<I1> n1, R r)
auto find_mismatch_m(
I0 first0, I0 last0, I1 first1, iter_dist_t<I1> size1, Rel rel
)
{
// Precondition: readable_bounded_range(f0,d0)
// Precondition: readable_weak_range(f1,n1)
while (f0 != d0 && !zero(n1) && r(*f0, *f1)) {
n1 = predecessor(n1);
f0 = successor(f0);
f1 = successor(f1);
// Precondition: readable_bounded_range(first0,last0)
// Precondition: readable_weak_range(first1, size1)
while (first0 != last0 && !zero(size1) && rel(*first0, *first1)) {
size1 = predecessor(size1);
first0 = successor(first0);
first1 = successor(first1);
}
return std::make_tuple(f0, f1, n1);
return std::make_tuple(first0, first1, size1);
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> Rel>
requires BareSameAs<iter_value_t<I0>, iter_value_t<I1>>
auto find_mismatch_n_m(
I0 f0, iter_dist_t<I0> n0, I1 f1, iter_dist_t<I1> n1, R r
I0 first0, iter_dist_t<I0> size0, I1 first1, iter_dist_t<I1> size1, Rel rel
)
{
// Precondition: readable_weak_range(f0,n0)
// Precondition: readable_weak_range(f1,n1)
while (!zero(n0) && !zero(n1) && r(*f0, *f1)) {
n0 = predecessor(n0);
n1 = predecessor(n1);
f0 = successor(f0);
f1 = successor(f1);
// Precondition: readable_weak_range(first0, size0)
// Precondition: readable_weak_range(first1, size1)
while (!zero(size0) && !zero(size1) && rel(*first0, *first1)) {
size0 = predecessor(size0);
size1 = predecessor(size1);
first0 = successor(first0);
first1 = successor(first1);
}
return std::make_tuple(f0, n0, f1, n1);
return std::make_tuple(first0, size0, first1, size1);
}

template<ReadableIterator I, IterRelation<I> R>
auto find_adjacent_mismatch_n(I f, iter_dist_t<I> n, R r)
template<ReadableIterator I, IterRelation<I> Rel>
auto find_adjacent_mismatch_n(I first, iter_dist_t<I> size, Rel rel)
{
// Precondition: readable_bounded_range(f,d)
// Precondition: readable_bounded_range(first, last)

if (zero(n)) {
return std::make_pair(f, n);
if (zero(size)) {
return std::make_pair(first, size);
}

auto x = *f;
f = successor(f);
n = predecessor(n);
while (!zero(n) && r(x, *f)) {
x = *f;
n = predecessor(n);
f = successor(f);
auto crnt = *first;
first = successor(first);
size = predecessor(size);
while (!zero(size) && rel(crnt, *first)) {
crnt = *first;
size = predecessor(size);
first = successor(first);
}

return std::make_pair(f, n);
return std::make_pair(first, size);
}

template<ReadableIterator I, IterRelation<I> R>
bool relation_preserving_n(I f, iter_dist_t<I> n, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool relation_preserving_n(I first, iter_dist_t<I> size, Rel rel)
{
// Precondition: readable_bounded_range(f,n)
// Precondition: weak_ordering(r);
return find_adjacent_mismatch_n(f, n, r).second == 0;
// Precondition: readable_bounded_range(first, size)
// Precondition: weak_ordering(rel);
return find_adjacent_mismatch_n(first, size, rel).second == 0;
}

template<ReadableIterator I, IterRelation<I> R>
bool strictly_increasing_range_n(I f, iter_dist_t<I> n, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool strictly_increasing_range_n(I first, iter_dist_t<I> size, Rel rel)
{
// Precondition: readable_bounded_range(f,n)
// Precondition: weak_ordering(r);
return relation_preserving_n(f, n, r);
// Precondition: readable_bounded_range(first, size)
// Precondition: weak_ordering(rel);
return relation_preserving_n(first, size, rel);
}

template<ReadableIterator I, IterRelation<I> R>
bool increasing_range_n(I f, iter_dist_t<I> n, R r)
template<ReadableIterator I, IterRelation<I> Rel>
bool increasing_range_n(I first, iter_dist_t<I> size, Rel rel)
{
// Precondition: readable_bounded_range(f,n)
// Precondition: weak_ordering(r);
// Precondition: readable_bounded_range(first, size)
// Precondition: weak_ordering(rel);
return relation_preserving_n(
f, n, complement_of_converse<iter_value_t<I>>(r)
first, size, complement_of_converse<iter_value_t<I>>(rel)
);
}

/* ----- Sentinel Ranges ----- */

template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_unguarded(I f, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
I find_if_unguarded(I first, Pred pred)
{
// Precondition: readable_bounded_range(f, d) && some(f, d, p);
while (!p(*f)) {
f = successor(f);
// Precondition: readable_bounded_range(first, last) && some(f, d, p);
while (!pred(*first)) {
first = successor(first);
}
return f;
return first;
}

template<ReadableIterator I, IterUnaryPredicate<I> P>
I find_if_not_unguarded(I f, P p)
template<ReadableIterator I, IterUnaryPredicate<I> Pred>
I find_if_not_unguarded(I first, Pred pred)
{
// Precondition: readable_bounded_range(f, d) && not_all(f, d, p);
while (p(*f)) {
f = successor(f);
// Precondition: readable_bounded_range(first, last) && not_all(f, d, p);
while (pred(*first)) {
first = successor(first);
}
return f;
return first;
}

template<ReadableForwardIterator I, IterRelation<I> R>
I find_adjacent_mismatch_forward(I f, I d, R r)
template<ReadableForwardIterator I, IterRelation<I> Rel>
I find_adjacent_mismatch_forward(I first, I last, Rel rel)
{
// Precondition: readable_bounded_range(f, d)
// Precondition: readable_bounded_range(first, last)

if (f == d) {
return d;
if (first == last) {
return last;
}

I t;
I tmp;
do {
t = f;
f = successor(f);
} while (f != d && r(*t, *f));
tmp = first;
first = successor(first);
} while (first != last && rel(*tmp, *first));

return f;
return first;
}

template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
bool partitioned_n(I f, iter_dist_t<I> n, P p)
template<ReadableForwardIterator I, IterUnaryPredicate<I> Pred>
bool partitioned_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_bounded_range(f, n)
std::tie(f, n) = find_if_n(f, n, p);
return find_if_not_n(f, n, p).second == 0;
// Precondition: readable_bounded_range(first, size)
std::tie(first, size) = find_if_n(first, size, pred);
return find_if_not_n(first, size, pred).second == 0;
}

template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
I partition_point_n(I f, iter_dist_t<I> n, P p)
template<ReadableForwardIterator I, IterUnaryPredicate<I> Pred>
I partition_point_n(I first, iter_dist_t<I> size, Pred pred)
{
// Precondition: readable_bounded_range(f, n)
assert(partitioned_n(f, n, p));
// Precondition: readable_bounded_range(first, size)
assert(partitioned_n(first, size, pred));

while (!zero(n)) {
const auto h = half(n);
I m = f + h;
if (p(*m)) {
n = h;
while (!zero(size)) {
const auto hlf = half(size);
I mid = first + hlf;
if (pred(*mid)) {
size = hlf;
} else {
n -= successor(h);
f = successor(m);
size -= successor(hlf);
first = successor(mid);
}
}
return f;
return first;
}

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)
template<ReadableForwardIterator I, IterRelation<I> Rel>
I lower_bound_n(
I first, iter_dist_t<I> size, const iter_value_t<I>& val, Rel rel
)
{
// Precondition: weak_ordering(r)
assert(increasing_range_n(f, n, r));
// Precondition: weak_ordering(rel)
assert(increasing_range_n(first, size, rel));

return partition_point_n(f, n, lower_bound_predicate(a, r));
return partition_point_n(first, size, lower_bound_predicate(val, rel));
}

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)
template<ReadableForwardIterator I, IterRelation<I> Rel>
I upper_bound_n(
I first, iter_dist_t<I> size, const iter_value_t<I>& val, Rel rel
)
{
// Precondition: weak_ordering(r)
assert(increasing_range_n(f, n, r));
// Precondition: weak_ordering(rel)
assert(increasing_range_n(first, size, rel));

return partition_point_n(f, n, upper_bound_predicate(a, r));
return partition_point_n(first, size, upper_bound_predicate(val, rel));
}

template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
bool partitioned(I f, I d, P p)
template<ReadableForwardIterator I, IterUnaryPredicate<I> Pred>
bool partitioned(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d)
return find_if_not(find_if(f, d, p), d, p) == d;
// Precondition: readable_bounded_range(first, last)
return find_if_not(find_if(first, last, pred), last, pred) == last;
}

template<ReadableForwardIterator I, IterUnaryPredicate<I> P>
I partition_point(I f, I d, P p)
template<ReadableForwardIterator I, IterUnaryPredicate<I> Pred>
I partition_point(I first, I last, Pred pred)
{
// Precondition: readable_bounded_range(f, d)
assert(partitioned(f, d, p));
// Precondition: readable_bounded_range(first, last)
assert(partitioned(first, last, pred));

return partition_point_n(f, d - f, p);
return partition_point_n(first, last - first, pred);
}

template<ReadableForwardIterator I, IterRelation<I> R>
I lower_bound(I f, I d, const iter_value_t<I>& a, R r)
template<ReadableForwardIterator I, IterRelation<I> Rel>
I lower_bound(I first, I last, const iter_value_t<I>& val, Rel rel)
{
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
// Precondition: weak_ordering(rel)
assert(increasing_range(first, last, rel));

return based::lower_bound_n(f, d - f, a, r);
return based::lower_bound_n(first, last - first, val, rel);
}

template<ReadableForwardIterator I, IterRelation<I> R>
I upper_bound(I f, I d, const iter_value_t<I>& a, R r)
template<ReadableForwardIterator I, IterRelation<I> Rel>
I upper_bound(I first, I last, const iter_value_t<I>& val, Rel rel)
{
// Precondition: weak_ordering(r)
assert(increasing_range(f, d, r));
// Precondition: weak_ordering(rel)
assert(increasing_range(first, last, rel));

return based::upper_bound_n(f, d - f, a, r);
return based::upper_bound_n(first, last - first, val, rel);
}

} // namespace based

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

@@ -7,48 +7,48 @@

namespace based
{

template<typename T, Relation<T> R>
auto complement(R r)
template<typename T, Relation<T> Rel>
auto complement(Rel rel)
{
return [=](const T& a, const T& b)
return [=](const T& lhs, const T& rhs)
{
return !r(a, b);
return !rel(lhs, rhs);
};
}

template<typename T, Relation<T> R>
auto converse(R r)
template<typename T, Relation<T> Rel>
auto converse(Rel rel)
{
return [=](const T& a, const T& b)
return [=](const T& lhs, const T& rhs)
{
return r(b, a);
return rel(rhs, lhs);
};
}

template<typename T, Relation<T> R>
auto complement_of_converse(R r)
template<typename T, Relation<T> Rel>
auto complement_of_converse(Rel rel)
{
return [=](const T& a, const T& b)
return [=](const T& lhs, const T& rhs)
{
return !r(b, a);
return !rel(rhs, lhs);
};
}

template<typename T, Relation<T> R>
auto lower_bound_predicate(const T& a, R r)
template<typename T, Relation<T> Rel>
auto lower_bound_predicate(const T& goal, Rel rel)
{
return [=](const T& x)
return [=](const T& val)
{
return !r(x, a);
return !rel(val, goal);
};
}

template<typename T, Relation<T> R>
auto upper_bound_predicate(const T& a, R r)
template<typename T, Relation<T> Rel>
auto upper_bound_predicate(const T& goal, Rel rel)
{
return [=](const T& x)
return [=](const T& val)
{
return r(a, x);
return rel(goal, val);
};
}

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

@@ -260,8 +260,8 @@ D* registry<D>::head(nullptr);


template<typename Function>
void count_operations(
size_t i,
size_t j,
size_t first,
size_t last,
Function fun,
double (*norm)(double, double) = dont_normalize
)

@@ -273,21 +273,22 @@ void count_operations(


std::array<double, cols> values = {0};

table tbl(12);
static constexpr int width = 12;
table tbl(width);
tbl.print_header(
std::begin(instrumented::names), std::end(instrumented::names)
);

std::mt19937 rng(0); // NOLINT cert-msc32-c cert-msc51-cpp
while (i <= j) {
std::vector<instrumented> vec(i);
while (first <= last) {
std::vector<instrumented> vec(first);
std::iota(std::begin(vec), std::end(vec), 0.0);
std::shuffle(std::begin(vec), std::end(vec), rng);

instrumented::initialize(i);
instrumented::initialize(first);
fun(std::begin(vec), std::end(vec));

const auto dbl = static_cast<double>(i);
const auto dbl = static_cast<double>(first);

values[0] = dbl;
for (size_t k = 1; k < cols; ++k) {

@@ -296,7 +297,7 @@ void count_operations(


tbl.print_row(std::begin(values), std::end(values), decimals);

i <<= 1U;
first <<= 1U;
}
}

@@ -337,9 +338,9 @@ public:

const auto end = count(endp);

const auto duration = end - start;
const auto ms = static_cast<double>(duration) * 0.001;
const auto msec = static_cast<double>(duration) * 0.001;

std::cout << std::format("{}us ({}ms)\n", duration, ms);
std::cout << std::format("{}us ({}ms)\n", duration, msec);
}

private:

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

@@ -5,39 +5,39 @@ namespace based

{

template<Iterator I>
I successor(I i)
I successor(I itr)
{
return ++i;
return ++itr;
}

template<Iterator I>
void increment(I& x)
void increment(I& itr)
{
// Precondition: next(x) is defined
x = next(x);
// Precondition: next(itr) is defined
itr = next(itr);
}

template<Iterator I>
I operator+(I f, distance_t<I> n)
I operator+(I first, distance_t<I> size)
{
// Precondition: n >= 0 & weak_range(f, n)
while (!zero(n)) {
n = predecessor(n);
f = successor(f);
// Precondition: size >= 0 & weak_range(first, size)
while (!zero(size)) {
size = predecessor(size);
first = successor(first);
}
return f;
return first;
}

template<Iterator I>
distance_t<I> operator-(I d, I f)
distance_t<I> operator-(I last, I first)
{
// Precondition: bounded_range(f, d)
distance_t<I> n {0};
while (f != d) {
n = successor(n);
f = successor(f);
// Precondition: bounded_range(first, last)
distance_t<I> cnt {0};
while (first != last) {
cnt = successor(cnt);
first = successor(first);
}
return n;
return cnt;
}

} // namespace based

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

@@ -27,19 +27,19 @@ private:

std::vector<node_t> m_pool;
list_type m_free_list;

const node_t& node(list_type x) const
[[nodiscard]] const node_t& node(list_type x) const
{
assert(x != 0);
return m_pool[x - 1];
}

node_t& node(list_type x)
[[nodiscard]] node_t& node(list_type x)
{
assert(x != 0);
return m_pool[x - 1];
}

list_type new_node()
[[nodiscard]] list_type new_node()
{
m_pool.push_back(node_t());
return list_type(m_pool.size());

@@ -104,14 +104,14 @@ public:

list_pool::list_type m_node;
};

bool is_empty(list_type x) const { return x == node_empty(); }
list_type node_empty() const { return list_type(0); }
[[nodiscard]] bool is_empty(list_type x) const { return x == node_empty(); }
[[nodiscard]] list_type node_empty() const { return list_type(0); }

const value_type& value(list_type x) const { return node(x).value; }
value_type& value(list_type x) { return node(x).value; }
[[nodiscard]] const value_type& value(list_type x) const { return node(x).value; }
[[nodiscard]] value_type& value(list_type x) { return node(x).value; }

const list_type& next(list_type x) const { return node(x).next; }
list_type& next(list_type x) { return node(x).next; }
[[nodiscard]] const list_type& next(list_type x) const { return node(x).next; }
[[nodiscard]] list_type& next(list_type x) { return node(x).next; }

list_type free(list_type x)
{

@@ -136,7 +136,7 @@ public:

return ret;
}

list_type allocate(const value_type& val, list_type tail)
[[nodiscard]] list_type allocate(const value_type& val, list_type tail)
{
list_type new_list = m_free_list;

@@ -153,10 +153,10 @@ public:


using queue_t = std::pair<list_type, list_type>;

bool is_empty(const queue_t& queue) const { return is_empty(queue.first); }
queue_t queue_empty() { return {node_empty(), node_empty()}; }
[[nodiscard]] bool is_empty(const queue_t& queue) const { return is_empty(queue.first); }
[[nodiscard]] queue_t queue_empty() { return {node_empty(), node_empty()}; }

queue_t push_front(const queue_t& queue, const value_type& val)
[[nodiscard]] queue_t push_front(const queue_t& queue, const value_type& val)
{
auto new_node = allocate(val, queue.first);
if (is_empty(queue)) {

@@ -165,7 +165,7 @@ public:

return {new_node, queue.second};
}

queue_t push_back(const queue_t& queue, const value_type& val)
[[nodiscard]] queue_t push_back(const queue_t& queue, const value_type& val)
{
auto new_node = allocate(val, node_empty());
if (is_empty(queue)) {

@@ -175,7 +175,7 @@ public:

return {queue.first, new_node};
}

queue_t pop_front(const queue_t& queue)
[[nodiscard]] queue_t pop_front(const queue_t& queue)
{
if (is_empty(queue)) {
return queue;

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

@@ -6,19 +6,19 @@

namespace based
{

template<std::size_t N>
template<std::size_t n>
struct string_literal
{
// NOLINTNEXTLINE *-explicit-constructor *-avoid-c-arrays
constexpr string_literal(const char (&str)[N])
constexpr string_literal(const char (&str)[n])
: m_value(std::to_array(str))
{
}

constexpr std::size_t size() const { return N; }
constexpr const char* data() const { return m_value.data(); }
[[nodiscard]] constexpr std::size_t size() const { return n; }
[[nodiscard]] constexpr const char* data() const { return m_value.data(); }

std::array<char, N> m_value;
std::array<char, n> m_value;
};

} // namespace based

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

@@ -258,14 +258,14 @@ struct buffer


template<typename T>
requires(valid_type<T>())
T* as() noexcept
[[nodiscard]] T* as() noexcept
{
return reinterpret_cast<T*>(&m_space); // NOLINT reinterpret_cast
}

template<typename T>
requires(valid_type<T>())
const T* as() const noexcept
[[nodiscard]] const T* as() const noexcept
{
return const_cast<buffer*>(this)->as<T>(); // NOLINT const_cast
}

@@ -282,7 +282,7 @@ struct buffer

/* ----- Overload Lambdas ----- */

template<typename... F>
struct overload : public F... // NOLINT multiple-inheritance
struct overload : public F...
{
using F::operator()...;
};

@@ -292,7 +292,10 @@ overload(F&&...) -> overload<F...>;


/* ----- Function Wrapper with type erasure ----- */

template<typename Signature, std::size_t size = 16, std::size_t alignment = 8>
template<
typename Signature,
std::size_t size = sizeof(void*),
std::size_t alignment = alignof(void*)>
class Function;

template<

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

@@ -82,24 +82,24 @@ template<typename T>

using iter_ref_t = detail::iterator_traits<T>::reference;

template<typename T>
concept Readable = requires(T t) {
concept Readable = requires(T val) {
requires(Regular<T>);
typename iter_value_t<T>;
{ *t } -> BareSameAs<iter_value_t<T>>;
{ *val } -> BareSameAs<iter_value_t<T>>;
};

template<typename T>
concept Iterator = requires(T t) {
concept Iterator = requires(T val) {
requires(Regular<T>);
typename iter_dist_t<T>;
// requires(Integer<iter_dist_t<T>>);
{ ++t } -> BareSameAs<T>;
{ ++val } -> BareSameAs<T>;
// successor is not necessarily regular

};

template<typename T>
concept ForwardIterator = requires(T t) {
concept ForwardIterator = requires {
requires(Iterator<T>);
// successor is regular
};

diff --git a/ test/source/find_if_test.cpp b/ test/source/find_if_test.cpp

@@ -19,10 +19,10 @@ struct predicate

TEST_CASE("find_if(empty)", "[algorithm/find_if]")
{
const std::array<int, 0> arr = {};
const auto* it =
const auto* itr =
based::find_if(std::begin(arr), std::end(arr), predicate {0});

REQUIRE(it == std::end(arr));
REQUIRE(itr == std::end(arr));
}

TEST_CASE("find_if(one)", "[algorithm/find_if]")

@@ -99,10 +99,10 @@ TEST_CASE("find_if(multiple)", "[algorithm/find_if]")

TEST_CASE("find_if_not(empty)", "[algorithm/find_if_not]")
{
const std::array<int, 0> arr = {};
const auto* it =
const auto* itr =
based::find_if_not(std::begin(arr), std::end(arr), predicate {0});

REQUIRE(it == std::end(arr));
REQUIRE(itr == std::end(arr));
}

TEST_CASE("find_if_not(one)", "[algorithm/find_if_not]")

diff --git a/ test/source/find_mismatch_test.cpp b/ test/source/find_mismatch_test.cpp

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


struct equal
{
auto operator()(int a, int b) const { return a == b; }
auto operator()(int lhs, int rhs) const { return lhs == rhs; }
};

TEST_CASE("find_mismatch(empty)", "[algorithm/find_mismatch]")

diff --git a/ test/source/find_test.cpp b/ test/source/find_test.cpp

@@ -7,9 +7,9 @@

TEST_CASE("find(empty)", "[algorithm/find]")
{
const std::array<int, 0> arr = {};
const auto* it = based::find(std::begin(arr), std::end(arr), 0);
const auto* itr = based::find(std::begin(arr), std::end(arr), 0);

REQUIRE(it == std::end(arr));
REQUIRE(itr == std::end(arr));
}

TEST_CASE("find(one) = found", "[algorithm/find]")

@@ -79,9 +79,9 @@ TEST_CASE("find(multiple) = found", "[algorithm/find]")

TEST_CASE("find_not(empty)", "[algorithm/find_not]")
{
const std::array<int, 0> arr = {};
const auto* it = based::find_not(std::begin(arr), std::end(arr), 0);
const auto* itr = based::find_not(std::begin(arr), std::end(arr), 0);

REQUIRE(it == std::end(arr));
REQUIRE(itr == std::end(arr));
}

TEST_CASE("find_not(one) = found", "[algorithm/find_not]")

diff --git a/ test/source/for_each_test.cpp b/ test/source/for_each_test.cpp

@@ -14,31 +14,31 @@ struct functor

TEST_CASE("for_each(empty)", "[algorithm/for_each]")
{
const std::array<int, 0> arr = {};
const auto f = based::for_each(std::begin(arr), std::end(arr), functor {});
const auto func = based::for_each(std::begin(arr), std::end(arr), functor {});

REQUIRE(f.sum == 0);
REQUIRE(func.sum == 0);
}

TEST_CASE("for_each(one)", "[algorithm/for_each]")
{
const std::array arr = {1};
const auto f = based::for_each(std::begin(arr), std::end(arr), functor {});
const auto func = based::for_each(std::begin(arr), std::end(arr), functor {});

REQUIRE(f.sum == 1);
REQUIRE(func.sum == 1);
}

TEST_CASE("for_each(two)", "[algorithm/for_each]")
{
const std::array arr = {1, 2};
const auto f = based::for_each(std::begin(arr), std::end(arr), functor {});
const auto func = based::for_each(std::begin(arr), std::end(arr), functor {});

REQUIRE(f.sum == 3);
REQUIRE(func.sum == 3);
}

TEST_CASE("for_each(three)", "[algorithm/for_each]")
{
const std::array arr = {1, 2, 3};
const auto f = based::for_each(std::begin(arr), std::end(arr), functor {});
const auto func = based::for_each(std::begin(arr), std::end(arr), functor {});

REQUIRE(f.sum == 6);
REQUIRE(func.sum == 6);
}

diff --git a/ test/source/list_test.cpp b/ test/source/list_test.cpp

@@ -66,7 +66,8 @@ TEST_CASE("list_pool iterator", "[list/list_pool/iterator]")

auto pool = list_pool();
auto head = pool.node_empty();

for (std::uint8_t i = 0; i < 0xFF; i++) {
static constexpr std::size_t iter_count = 0xFF;
for (std::uint8_t i = 0; i < iter_count; i++) {
head = pool.allocate(i, head);
}

@@ -116,7 +117,8 @@ TEST_CASE("list_pool queue", "[list/list_pool/queue]")

REQUIRE(pool.pop_front(queue) == queue);
}

for (std::uint8_t i = 0; i < 0xFF; i++) {
static constexpr std::size_t iter_count = 0xFF;
for (std::uint8_t i = 0; i < iter_count; i++) {
if (i % 2 == 0) {
queue = pool.push_front(queue, i);
} else {

diff --git a/ test/source/partition_test.cpp b/ test/source/partition_test.cpp

@@ -117,11 +117,11 @@ TEST_CASE("lower_bound(one nonequal)", "[algorithm/lower_bound]")


TEST_CASE("lower_bound(sequence)", "[algorithm/lower_bound]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 5, 5};
std::array arr = {0, 1, 2, 3, 3, 4};

const auto* itr =
based::lower_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 4));
based::lower_bound(std::begin(arr), std::end(arr), 3, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 3));
}

TEST_CASE("upper_bound(empty)", "[algorithm/lower_bound]")

@@ -153,9 +153,9 @@ TEST_CASE("upper_bound(one nonequal)", "[algorithm/lower_bound]")


TEST_CASE("upper_bound(sequence)", "[algorithm/lower_bound]")
{
std::array arr = {0, 1, 2, 3, 4, 4, 5, 5};
std::array arr = {0, 1, 2, 3, 3, 4};

const auto* itr =
based::upper_bound(std::begin(arr), std::end(arr), 4, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 6));
based::upper_bound(std::begin(arr), std::end(arr), 3, std::less<int> {});
REQUIRE(itr == std::next(std::begin(arr), 5));
}

diff --git a/ test/source/reduce_test.cpp b/ test/source/reduce_test.cpp

@@ -7,12 +7,12 @@


struct op
{
auto operator()(const auto& a, const auto& b) { return a + b; }
auto operator()(const auto& lhs, const auto& rhs) { return lhs + rhs; }
};

struct fun
{
auto operator()(based::Iterator auto it) { return *it; }
auto operator()(based::Iterator auto itr) { return *itr; }
};

TEST_CASE("reduce(empty)", "[algorithm/reduce]")

diff --git a/ test/source/string_literal_test.cpp b/ test/source/string_literal_test.cpp

@@ -20,13 +20,14 @@ TEST_CASE("nonempty", "[string/string_literal]")


TEST_CASE("template", "[string/string_literal]")
{
const auto data = []<based::string_literal L>()
const auto data = []<based::string_literal l>()
{
return L.data();
return l.data();
};
const auto size = []<based::string_literal L>()

const auto size = []<based::string_literal l>()
{
return L.size();
return l.size();
};

REQUIRE(size.operator()<"">() == 1);