based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit 0555ffbfda572bdf91a725d63371a1f1f60fa599
parent b24481d5115e90a161f8e10d9becd165f5aeab25
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Thu, 10 Apr 2025 18:55:29 +0200

find_mismatch and find_mismatch_n, with tests

Diffstat:
M include/based/algorithm.hpp | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M test/CMakeLists.txt | ++
A test/source/find_mismatch_n_test.cpp | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A test/source/find_mismatch_test.cpp | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

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

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

@@ -376,6 +376,19 @@ auto reduce_nonzero(

return x;
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
requires SameAs<iter_value_t<I0>, iter_value_t<I1>>
auto find_mismatch(I0 f0, I0 d0, I1 f1, I1 d1, R r)
{
// Precondition: bounded_range(f0,d0)
// Precondition: bounded_range(f1,d1)
while (f0 != d0 && f1 != d1 && r(*f0, *f1)) {
f0 = successor(f0);
f1 = successor(f1);
}
return std::make_pair(f0, f1);
}

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

template<ReadableIterator I, IterUnaryProcedure<I> Proc>

@@ -546,6 +559,49 @@ auto count_if_not_n(I f, iter_dist_t<I> n, P p)

return count_if_not_n(f, n, p, iter_dist_t<I> {0});
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
requires SameAs<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)
{
// 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);
}
return std::make_tuple(f0, n0, f1);
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
requires SameAs<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)
{
// 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);
}
return std::make_tuple(f0, f1, n1);
}

template<ReadableIterator I0, ReadableIterator I1, IterRelation<I0> R>
requires SameAs<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)
{
// 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);
}
return std::make_tuple(f0, n0, f1, n1);
}

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

template<ReadableIterator I, IterUnaryPredicate<I> P>

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

@@ -39,6 +39,7 @@ add_test(find_if_test)

add_test(count_test)
add_test(count_if_test)
add_test(reduce_test)
add_test(find_mismatch_test)

## ----- Bounden Range -----

@@ -47,6 +48,7 @@ add_test(find_n_test)

add_test(find_if_n_test)
add_test(count_n_test)
add_test(count_if_n_test)
add_test(find_mismatch_n_test)

## ----- Unguarded Range -----

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

@@ -0,0 +1,374 @@

#include <array>

#include <catch2/catch_test_macros.hpp>

#include "based/algorithm.hpp"

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

TEST_CASE("find_mismatch_n(empty)", "[algorithm/find_mismatch_n]")
{
std::array<int, 0> arr0 = {};
std::array<int, 0> arr1 = {};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch_n(empty, nonempty)", "[algorithm/find_mismatch_n]")
{
std::array<int, 0> arr0 = {};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::begin(arr1));
}

TEST_CASE("find_mismatch_n(nonempty, empty)", "[algorithm/find_mismatch_n]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array<int, 0> arr1 = {};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::begin(arr0));
REQUIRE(n0 == std::size(arr0));

REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch_n(equal)", "[algorithm/find_mismatch_n]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch_n(equal, longer)", "[algorithm/find_mismatch_n]")
{
std::array arr0 = {0, 1, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::next(std::begin(arr1), std::size(arr0)));
}

TEST_CASE("find_mismatch_n(longer, equal)", "[algorithm/find_mismatch_n]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), std::size(arr1)));
REQUIRE(n0 == 2);

REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch_n(mismatch)", "[algorithm/find_mismatch_n]")
{
std::array arr0 = {0, 1, 4, 3, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1] = based::find_mismatch_n(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), 2));
REQUIRE(n0 == 3);

REQUIRE(itr1 == std::next(std::begin(arr1), 2));
}

TEST_CASE("find_mismatch_m(empty)", "[algorithm/find_mismatch_m]")
{
std::array<int, 0> arr0 = {};
std::array<int, 0> arr1 = {};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_m(empty, nonempty)", "[algorithm/find_mismatch_m]")
{
std::array<int, 0> arr0 = {};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));

REQUIRE(itr1 == std::begin(arr1));
REQUIRE(n1 == std::size(arr1));
}

TEST_CASE("find_mismatch_m(nonempty, empty)", "[algorithm/find_mismatch_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array<int, 0> arr1 = {};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::begin(arr0));

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_m(equal)", "[algorithm/find_mismatch_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_m(equal, longer)", "[algorithm/find_mismatch_m]")
{
std::array arr0 = {0, 1, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));

REQUIRE(itr1 == std::next(std::begin(arr1), std::size(arr0)));
REQUIRE(n1 == 2);
}

TEST_CASE("find_mismatch_m(longer, equal)", "[algorithm/find_mismatch_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), std::size(arr1)));

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_m(mismatch)", "[algorithm/find_mismatch_m]")
{
std::array arr0 = {0, 1, 4, 3, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1, n1] = based::find_mismatch_m(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), 2));

REQUIRE(itr1 == std::next(std::begin(arr1), 2));
REQUIRE(n1 == 3);
}

TEST_CASE("find_mismatch_n_m(empty)", "[algorithm/find_mismatch_n_m]")
{
std::array<int, 0> arr0 = {};
std::array<int, 0> arr1 = {};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_n_m(empty, nonempty)", "[algorithm/find_mismatch_n_m]")
{
std::array<int, 0> arr0 = {};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::begin(arr1));
REQUIRE(n1 == std::size(arr1));
}

TEST_CASE("find_mismatch_n_m(nonempty, empty)", "[algorithm/find_mismatch_n_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array<int, 0> arr1 = {};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::begin(arr0));
REQUIRE(n0 == std::size(arr0));

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_n_m(equal)", "[algorithm/find_mismatch_n_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_n_m(equal, longer)", "[algorithm/find_mismatch_n_m]")
{
std::array arr0 = {0, 1, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(n0 == 0);

REQUIRE(itr1 == std::next(std::begin(arr1), std::size(arr0)));
REQUIRE(n1 == 2);
}

TEST_CASE("find_mismatch_n_m(longer, equal)", "[algorithm/find_mismatch_n_m]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), std::size(arr1)));
REQUIRE(n0 == 2);

REQUIRE(itr1 == std::end(arr1));
REQUIRE(n1 == 0);
}

TEST_CASE("find_mismatch_n_m(mismatch)", "[algorithm/find_mismatch_n_m]")
{
std::array arr0 = {0, 1, 4, 3, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, n0, itr1, n1] = based::find_mismatch_n_m(std::begin(arr0),
std::size(arr0),
std::begin(arr1),
std::size(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), 2));
REQUIRE(n0 == 3);

REQUIRE(itr1 == std::next(std::begin(arr1), 2));
REQUIRE(n1 == 3);
}

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

@@ -0,0 +1,115 @@

#include <array>

#include <catch2/catch_test_macros.hpp>

#include "based/algorithm.hpp"

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

TEST_CASE("find_mismatch(empty)", "[algorithm/find_mismatch]")
{
std::array<int, 0> arr0 = {};
std::array<int, 0> arr1 = {};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch(empty, nonempty)", "[algorithm/find_mismatch]")
{
std::array<int, 0> arr0 = {};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(itr1 == std::begin(arr1));
}

TEST_CASE("find_mismatch(nonempty, empty)", "[algorithm/find_mismatch]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array<int, 0> arr1 = {};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::begin(arr0));
REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch(equal)", "[algorithm/find_mismatch]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch(equal, longer)", "[algorithm/find_mismatch]")
{
std::array arr0 = {0, 1, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::end(arr0));
REQUIRE(itr1 == std::next(std::begin(arr1), std::size(arr0)));
}

TEST_CASE("find_mismatch(longer, equal)", "[algorithm/find_mismatch]")
{
std::array arr0 = {0, 1, 2, 3, 4};
std::array arr1 = {0, 1, 2};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), std::size(arr1)));
REQUIRE(itr1 == std::end(arr1));
}

TEST_CASE("find_mismatch(mismatch)", "[algorithm/find_mismatch]")
{
std::array arr0 = {0, 1, 4, 3, 2};
std::array arr1 = {0, 1, 2, 3, 4};

const auto [itr0, itr1] = based::find_mismatch(std::begin(arr0),
std::end(arr0),
std::begin(arr1),
std::end(arr1),
equal {});

REQUIRE(itr0 == std::next(std::begin(arr0), 2));
REQUIRE(itr1 == std::next(std::begin(arr1), 2));
}