linspace c++ and unit tests in catch BDD

Question

I have implemented matlab's linspace function

    /// linear_space -  linearly spaced vector
    /// linear_space(a,b,n) generates N points between a and b
    /// the goal of the function is to return an evenly distributed set of n points
    inline std::vector<double> linear_space(double a, double b, unsigned int n)
    {
        std::vector<double> array(n, a);
        //return an empty array if number of spaces is 0
        //return a if number of spaces is 1
        if (n <= 1 || std::fabs(a - b) < std::numeric_limits<double>::epsilon())
        {
            return array;
        }

        //we want to be sure we get exactly b in the end
        for (unsigned int i = 0; i < n - 1; ++i)
        {
            array[i] = a + ((b - a)*i) / (n - 1);
        }
        array[n - 1] = b;
        return array;
    }

here are the unit tests I did using Catch unit test framework, I used BDD style

#include "utilities.hpp"
#include "catch.hpp"
#include <memory>
#include <random>
#include <algorithm>
#include <vector>
double any_value()
{
    std::random_device random_device;
    std::mt19937 random_generator(random_device());

    auto lower = std::numeric_limits<int>::min();
    auto upper = std::numeric_limits<int>::max();

    std::uniform_real_distribution<double> distribution(lower, upper);

    return distribution(random_generator);
}

using namespace libcalc;
SCENARIO("Create linear_space for valid input")
{
    GIVEN("5 and 10 as points and number of cells is 5")
    {
        WHEN("trying to create linear_space")
        {
            std::vector<double> result = linear_space(5, 10, 5);
            THEN("the result should be 5 cells")
            {
                CHECK(result.size() == 5);
                CHECK(result[0] == 5.000);
                CHECK(result[1] == 6.2500);
                CHECK(result[2] == 7.5000);
                CHECK(result[3] == 8.7500);
                CHECK(result[4] == 10.000);
            }
        }
    }
    GIVEN("5 and 5 as points and number of cells is 5")
    {
        WHEN("trying to create linear_space =")
        {
            std::vector<double> result = linear_space(5, 5, 5);
            THEN("the result should be 5 cells")
            {
                CHECK(result.size() == 5);
                CHECK(result[0] == 5.000);
                CHECK(result[1] == 5.000);
                CHECK(result[2] == 5.000);
                CHECK(result[3] == 5.000);
                CHECK(result[4] == 5.000);
            }
        }
    }

    GIVEN("10 and 5 as points and number of cells is 5")
    {
        WHEN("trying to create linear_space")
        {
            std::vector<double> result = linear_space(10, 5, 5);
            THEN("the result should be 5 cells")
            {
                CHECK(result.size() == 5);
                CHECK(result[0] == 10.000);
                CHECK(result[1] == 8.7500);
                CHECK(result[2] == 7.5000);
                CHECK(result[3] == 6.2500);
                CHECK(result[4] == 5.000);
            }
        }
    }
}

SCENARIO("Linear space with zero, one or two points is well defined")
{
    auto number_of_repetitions = 10;

    THEN("any linear space with zero points will be empty")
    {
        while (number_of_repetitions-- > 0)
        {
            auto a = any_value();
            auto b = any_value();

            INFO("a: " << a);
            INFO("b: " << b);
            CHECK(true == linear_space(a, b, 0).empty());
        }
    }

    THEN("any linear space with one point will contain exactly the first input value")
    {
        while (number_of_repetitions-- > 0)
        {
            auto a = any_value();
            auto b = any_value();
            auto result = linear_space(a, b, 1);

            INFO("a: " << a);
            INFO("b: " << b);
            REQUIRE(1 == result.size());
            CHECK(a == result[0]);
        }
    }

    THEN("any linear space with two points will contain exactly the input values")
    {
        while (number_of_repetitions-- > 0)
        {
            auto a = any_value();
            auto b = any_value();
            auto result = linear_space(a, b, 2);

            INFO("a: " << a);
            INFO("b: " << b);
            REQUIRE(2 == result.size());
            CHECK(a == result[0]);
            CHECK(b == result[1]);
        }
    }
}

auto reverse = [](std::vector<double> const& x)
{
    std::vector<double> output(x.size());
    std::reverse_copy(x.begin(), x.end(), output.begin());
    return output;
};

SCENARIO("Any linear space (a, b) with two or more points will be same as"
    " the reversed linear space of (b, a)")
{
    GIVEN("a range of points to check starting from 2")
    {
        unsigned int starting_point = 2;
        unsigned int ending_point = 10;

        THEN("the linear space (a, b) is same as reversed linear space (b, a)")
        {
            for (unsigned int n = starting_point; n < ending_point; ++n)
            {
                auto a = any_value();
                auto b = any_value();

                auto fwd = linear_space(a, b, n);
                auto rev = reverse(linear_space(b, a, n));
                INFO("a: " << a);
                INFO("b: " << b);
                INFO("n: " << n);
                REQUIRE(fwd.size() == rev.size());
                for (unsigned int i = 0; i < n; i ++)
                {
                    REQUIRE(fwd[i] == Approx(rev[i]));
                }
            }
        }
    }
}

std::size_t count_unique_differences(std::vector<double> const &  vec)
{
    auto n_1 = vec.size() - 1;
    std::vector<double> distributed_vector(n_1);
    for (unsigned int i = 0; i < n_1; i++)
    {
        distributed_vector[i] = vec[i + 1] - vec[i];
    }

    //we need this threshold and not using std::numeric_limits<double>::epsilon())
    //since it is too small for std::unique
    double threshold = 0.00001;
    auto last = std::unique(distributed_vector.begin(), distributed_vector.end(), [threshold](double left, double right) {return std::abs(left - right) < threshold; });
    return std::distance(distributed_vector.begin(), last);
}

SCENARIO("For any n greater than two the linear space will contain the"
    " given number of equally distributed points")
{
    GIVEN("a range of points to check starting from 2")
    {
        unsigned int starting_point = 2;
        unsigned int ending_point = 10;

        THEN("all the points should have the same space between them i.e equally distributed")
        {
            for (auto n = starting_point; n < ending_point; ++n)
            {
                auto a = any_value();
                auto b = any_value();

                auto x = linear_space(a, b, n);
                auto y = reverse(linear_space(b, a, n));

                auto count_forward = count_unique_differences(x);
                auto count_reverse = count_unique_differences(y);;
                INFO("a: " << a);
                INFO("b: " << b);
                INFO("n: " << n);
                CHECK(count_forward == 1);
                CHECK(count_reverse == 1);
            }
        }
    }
}

Can you please review the BDD unit tests. What do you about the usage of BDD, did I implement the tests according to it? do I need to add more tests? do you think this covers the functionally of linspace from end to end?
I would appreciate any comment.
Thanks

Toby Speight · Accepted Answer · 2024-08-24 15:24:15Z

I don't think that random input makes for good tests, because they become unreproducible. If a random test fails, how do I reproduce the failure to work on it, and how do I demonstrate that I have fixed it?

The deterministic tests generally look good - I do like the thought that has gone into ensuring that the intermediate values are exactly representable in both binary and decimal floating-point, so that it's portable. The downside to this is that we're missing any tests that the mid value is exactly as expected when the division is inexact.

I'd prefer to see the trivial tests first, so I would start with the zero-element case and work up from there.

We don't have any tests that include infinities and NaNs in the inputs. Also, no tests that span the maximum range from the most-negative to most positive double (likely to make the b - a arithmetic overflow). Similarly, I'd like to see some tests of very small numbers and/or subnormals (perhaps 0.0 and std::nextafter(0.0, 1) as I suspect they will fail due to the unwarranted use of epsilon() - remember, that's only meaningful for numbers near 1.0.

Recommendations

Remove the nondeterministic tests.
Re-order so that the tests of invalid arguments come first, followed by the most trivial tests.
Add tests of extremely large and extremely small limits.
Add tests of elements that should be exact when division is inexact (e.g. specify n=7 with consecutive integers as a and b, and test that element 3 is exactly std::midpoint(a, b)).
Add a test that std::adjacent_difference() finds that the largest and smallest differences between adjacent elements are the same or are adjacent double values - i.e. std::nextafter(min_delta, max_delta) == max_delta.

I know you didn't ask for a review of the linear_space() function itself, but I have a few suggestions here anyway (in addition to making the new tests all pass):

Consider templating it so that we can have float or long double versions.
Instead of requiring it to be materialised as a vector, make it a standard view class like std::views::iota. It might be easiest to make it a std::views::transform of iota, rather than implementing the iota functionality yourself.
Leave out the inline keyword - this seldom adds value.

Definitely second the suggestion not to use randomness in unit tests. Randomness is for fuzz testing, not unit testing. — indi
– indi, Commented Aug 25, 2024 at 15:43

G. Sliepen · Accepted Answer · 2024-08-25 10:31:57Z

Make it more generic

This is definitely nice to have, but the problem is that you hardcoded the value type to double, and the container type to std::vector. What if I want a std::deque<float>? A straightforward way to solve this would be to make this a templated function:

template<typename T = std::vector<double>>
T linear_space(typename T::value_type a, typename T::value_type b, typename T::size_type n)
{
    T array(n, a);
    …
    return array;
}

It gets a bit more complicated if you also want to handle containers that are not random access, like std::list, but it is possible. However, you could also consider not creating a container at all, and just generate the desired values, and leave it up to something else to create a container for them. Basically, you want to create a range that when iterated over, gives you the desired values. You can make something that, even with just C++11, would allow you to write:

for (auto value: linspace(5, 10, 5)) {
    std::cout << value << '\n';
}

C++23 makes this very easy with std::generator:

template<typename T>
std::generator<T> linear_space(T a, T b, std::size_t n) {
    for (std::size_t i = 0; i < n - 1; ++i) {
        co_yield a + i * (b - a) / (n - 1);
    }
    co_yield b;
}

To turn this into a container, you can use std::ranges::to():

auto result = linear_space(5, 10, 5) | std::ranges::to<std::vector>();

Note that there is already something similar in the standard library, and it's std::ranges::iota_view, although this doesn't have an easy way to set the endpoint and step size. The ranges-v3 library does have ranges::views::linear_distribute though, which does exactly what you want.

Stack Exchange Network

linspace c++ and unit tests in catch BDD

2 Answers 2

Recommendations

Make it more generic

You must log in to answer this question.

Hot Network Questions

linspace c++ and unit tests in catch BDD

2 Answers 2

Recommendations

Make it more generic

You must log in to answer this question.

Related

Hot Network Questions