5
\$\begingroup\$

This is my generalisation of std::midpoint incorporating advice received for Find the mean of two values. As well as supporting arithmetic types and pointers, as std::midpoint does, it also supports iterators, complex numbers and user-defined types such as bignums, rationals and fixed-point numbers.

As well as advice from the first review, I've made a couple of other changes:

  • reject bool as argument type

  • pedantic handling of pointer difference where the result is too large for std::ptrdiff_t:

    If an array is so large (greater than PTRDIFF_MAX elements, but less than SIZE_MAX bytes), that the difference between two pointers may not be representable as std::ptrdiff_t, the result of subtracting two such pointers is undefined. — cppreference (CC-BY-SA 3.0)

#include <array>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>

namespace toby
{
namespace detail
{
    // A point on an affine line can be compared with another, and has
    // a difference type (which may be the same type).
    template<typename T>
    concept affine_point = std::regular<T> && requires(T a, T b) {
        a < b;
        a + (b - a);
    };

    // Subtraction helper, for pedantic handling of very large arrays
    template<typename T>
    auto distance(const T& a, const T& b) {
        return b - a;
    }
    template<typename T>
    requires ( sizeof (T) < SIZE_MAX / PTRDIFF_MAX )
    std::size_t distance(const T* a, const T* b) {
        if (b < a) {
            std::swap(a, b);
        }
        // If an array has more than PTRDIFF_MAX elements,
        // subtraction is undefined if the result is not
        // representable as std::ptrdiff_t.
        std::size_t gap = 1;
        while (a + gap < b - gap) {
            gap *= 2;
        }
        // (b - gap - a) promotes to size_t if necessary
        return b - gap - a + gap;
    }

    void midpoint(bool, bool) = delete;

    template<affine_point T>
    constexpr T midpoint(const T& a, const T& b)
    {
        if (a == b) {
            // This ensures infinities are correctly returned.
            return a;
        }

        if constexpr (std::is_signed_v<T>) {
            if ((a < 0) != (b < 0)) {
                // Values are opposite sign; avoid overflow when
                // magnitudes are large.
                return (a + b) / 2;
            }
        }

        if (a < b) {
            return a + distance(a, b) / 2;
        } else {
            return b + distance(b, a) / 2;
        }
    }

    // Iterators
    // If not random-access, then a MUST be before b
    template<std::input_or_output_iterator Iter, std::sentinel_for<Iter> S>
    constexpr Iter midpoint(Iter a, const S& b)
    {
        std::ranges::advance(a, std::ranges::distance(a, b) / 2);
        return a;
    }

    // Aggregate types follow
    // Pattern can be extended, e.g. for popular geometry types

    template<affine_point T>
    constexpr std::complex<T> midpoint(const std::complex<T>& a, const std::complex<T>& b)
    {
        return {
            midpoint(a.real(), b.real()),
            midpoint(a.imag(), b.imag())
        };
    }

    template<affine_point T, std::size_t N>
    constexpr std::array<T,N> midpoint(const std::array<T,N>& a, const std::array<T,N>& b)
    {
        std::array<T,N> result;
        auto f = [](auto&& x, auto&& y) { return midpoint(x,y); };
        std::transform(a.begin(), a.end(), b.begin(), result.begin(), f);
        return result;
    }
}

using detail::midpoint;
}

// Tests

#include <gtest/gtest.h>

using toby::midpoint;

#include <climits>
TEST(midpoint, int)
{
    EXPECT_EQ(midpoint(0, 0), 0);
    EXPECT_EQ(midpoint(0, 1), 0);
    EXPECT_EQ(midpoint(0, 2), 1);
    EXPECT_EQ(midpoint(1, 3), 2);
    EXPECT_EQ(midpoint(4, 1), 2);
    EXPECT_EQ(midpoint(INT_MIN, 0), INT_MIN/2);
    EXPECT_EQ(midpoint(INT_MAX, 0), INT_MAX/2);
    EXPECT_EQ(midpoint(INT_MAX, -INT_MAX), 0);
}

#include <limits>
TEST(midpoint, double)
{
    static constexpr auto inf = std::numeric_limits<double>::infinity();
    static constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    EXPECT_EQ(midpoint(0.0, 0.0), 0.0);
    EXPECT_EQ(midpoint(1.0, 2.0), 1.5);
    EXPECT_EQ(midpoint(1.0, inf), inf);
    EXPECT_EQ(midpoint(1.0, -inf), -inf);
    EXPECT_EQ(midpoint(inf, inf), inf);
    EXPECT_EQ(midpoint(-inf, -inf), -inf);
    EXPECT_TRUE(std::isnan(midpoint(inf, -inf)));
    EXPECT_TRUE(std::isnan(midpoint(nan, 0.0)));
    EXPECT_TRUE(std::isnan(midpoint(0.0, nan)));
    EXPECT_TRUE(std::isnan(midpoint(nan, nan)));
}

#include <complex>
TEST(midpoint, complex)
{
    auto const a = std::complex{2,10};
    auto const b = std::complex{0,20};
    auto const c = std::complex{1,15};
    EXPECT_EQ(midpoint(a, b), c);
}

TEST(midpoint, pointer)
{
    char const s[50] = {};
    EXPECT_EQ(midpoint(s+1, s+25), s+13);
    EXPECT_EQ(midpoint(s+25, s+1), s+13);
}

#include <string_view>
TEST(midpoint, iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    EXPECT_EQ(*midpoint(s.begin(), s.end()), 'n');
    EXPECT_EQ(*midpoint(s.end(), s.begin()), 'n');
}

#include <list>
TEST(midpoint, bidi_iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    auto const l = std::list(s.begin(), s.end());
    EXPECT_EQ(*midpoint(l.begin(), l.end()), 'n');
}

#include <forward_list>
TEST(midpoint, forward_iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    auto const l = std::forward_list(s.begin(), s.end());
    EXPECT_EQ(*midpoint(l.begin(), l.end()), 'n');
}

#include <array>
TEST(midpoint, std_array)
{
    auto const a = std::array{ 0, 10, 20};
    auto const b = std::array{10, 10, 10};
    auto const c = std::array{ 5, 10, 15};
    EXPECT_EQ(midpoint(a, b), c);
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I don’t have anything to add, but here’s a good video from CppCon on implementing std::midpoint \$\endgroup\$
    – Rish
    Jun 10, 2021 at 11:25

3 Answers 3

2
\$\begingroup\$

I think you've done a good job of coming up to speed with language features and library organization. 😀

Your distance for pointers is interesting, but takes a while to understand.

Note that if someone calls midpoint(true,true) it will be a compile-time error, but calling midpoint<bool>(x1,x2) will still call the template specialization, and ignore the plain function overload.

Your iterator code won't like single-pass iterators; does input_or_output_iterator exclude those or is that an orthogonal classification?

As for Ayxan's complaint about not knowing what "affine" meant, you could include a very brief comment in the concept body, pointing out that your concern is that subtraction can produce a result of a different type. If you minimally word it along the lines of "this is what I need and this is what it's properly called" you will make it readable without bothering people who do know that term already or bloating up the code with documentation that's not really about the code.

\$\endgroup\$
6
  • \$\begingroup\$ I was thinking of creating some "discovery" tests, to prove we can't call the bool overload. I'll look into that, and add some for the single-pass iterators too. \$\endgroup\$ Jun 11, 2021 at 7:40
  • \$\begingroup\$ see codeproject.com/Tips/1247697/… \$\endgroup\$
    – JDługosz
    Jun 11, 2021 at 13:39
  • 1
    \$\begingroup\$ Yes, that is exactly what I had been reading. I just need to find time to actually put it into practice... \$\endgroup\$ Jun 11, 2021 at 14:51
  • \$\begingroup\$ Yea, I remember discussing it a few days ago, but I thought it was on someone else's post. \$\endgroup\$
    – JDługosz
    Jun 11, 2021 at 15:40
  • \$\begingroup\$ Probably was - I either found it by Web search or followed a link from a comment I read on SE. \$\endgroup\$ Jun 11, 2021 at 16:13
3
\$\begingroup\$
  1. std::transform is defined in <algorithm>. You should include that.

  2. Have it work for ranges with minimal work:

template <std::ranges::range range>
constexpr auto midpoint(range &&r)
{
    return midpoint(std::ranges::begin(r), std::ranges::end(r));
}
  1. I had look up what "affine" means. Perhaps not a big deal, but hinders the readability a little bit.
\$\endgroup\$
0
\$\begingroup\$

Final version, incorporating suggestions from the other answers.

Changes made:

  • Use detection idiom to ensure constraints are applied (includes a simple implementation of is_detected_v, since my platform doesn't have the standard one yet).
  • Use std::midpoint() to handle pointer types.
  • Constrain bool out rather than overloading, so explicit specialization is affected.
  • Use std::forward_iterator concept, to prohibit single-pass iterators.
  • Accept a range as alternative to iterators.

Code

#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <numeric>
#include <ranges>
#include <type_traits>
#include <utility>

namespace toby
{
namespace detail
{
    // A point on an affine line can be compared with another, and has
    // a difference type (which may be the same type).
    template<typename T>
    concept affine_point
    =   std::regular<T>
        && !std::is_same_v<std::decay_t<T>, bool>
        && requires(T a, T b) { a < b; a + (b - a); };

    template<typename T>
    constexpr auto midpoint(const T* a, const T* b) {
        return std::midpoint(a, b);
    }
    template<affine_point T>
    constexpr T midpoint(const T& a, const T& b)
    {
        if (a == b) {
            // This ensures infinities are correctly returned.
            return a;
        }

        if constexpr (std::is_signed_v<T>) {
            if ((a < 0) != (b < 0)) {
                // Values are opposite sign; avoid overflow when
                // magnitudes are large.
                return (a + b) / 2;
            }
        }

        if (a < b) {
            return a + (b - a) / 2;
        } else {
            return b + (a - b) / 2;
        }
    }


    // Iterators and ranges
    // If not random-access, then a MUST precede b
    template<std::forward_iterator Iter, std::sentinel_for<Iter> S>
    constexpr Iter midpoint(Iter a, const S& b)
    {
        std::ranges::advance(a, std::ranges::distance(a, b) / 2);
        return a;
    }
    template <std::ranges::range Range>
    constexpr auto midpoint(const Range& r)
    {
        return midpoint(std::ranges::begin(r), std::ranges::end(r));
    }

    // Aggregate types follow
    // Pattern can be extended, e.g. for popular geometry types

    template<affine_point T>
    constexpr std::complex<T> midpoint(const std::complex<T>& a, const std::complex<T>& b)
    {
        return {
            midpoint(a.real(), b.real()),
            midpoint(a.imag(), b.imag())
        };
    }

    template<affine_point T, std::size_t N>
    constexpr std::array<T,N> midpoint(const std::array<T,N>& a, const std::array<T,N>& b)
    {
        std::array<T,N> result;
        auto f = [](auto&& x, auto&& y) { return midpoint(x,y); };
        std::transform(a.begin(), a.end(), b.begin(), result.begin(), f);
        return result;
    }
}

using detail::midpoint;
}

// Tests

#include <gtest/gtest.h>

using toby::midpoint;

#include <climits>
TEST(midpoint, int)
{
    EXPECT_EQ(midpoint(0, 0), 0);
    EXPECT_EQ(midpoint(0, 1), 0);
    EXPECT_EQ(midpoint(0, 2), 1);
    EXPECT_EQ(midpoint(1, 3), 2);
    EXPECT_EQ(midpoint(4, 1), 2);
    EXPECT_EQ(midpoint(INT_MIN, 0), INT_MIN/2);
    EXPECT_EQ(midpoint(INT_MAX, 0), INT_MAX/2);
    EXPECT_EQ(midpoint(INT_MAX, -INT_MAX), 0);
}

#include <limits>
TEST(midpoint, double)
{
    static constexpr auto inf = std::numeric_limits<double>::infinity();
    static constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    EXPECT_EQ(midpoint(0.0, 0.0), 0.0);
    EXPECT_EQ(midpoint(1.0, 2.0), 1.5);
    EXPECT_EQ(midpoint(1.0, inf), inf);
    EXPECT_EQ(midpoint(1.0, -inf), -inf);
    EXPECT_EQ(midpoint(inf, inf), inf);
    EXPECT_EQ(midpoint(-inf, -inf), -inf);
    EXPECT_TRUE(std::isnan(midpoint(inf, -inf)));
    EXPECT_TRUE(std::isnan(midpoint(nan, 0.0)));
    EXPECT_TRUE(std::isnan(midpoint(0.0, nan)));
    EXPECT_TRUE(std::isnan(midpoint(nan, nan)));
}

#include <complex>
TEST(midpoint, complex)
{
    auto const a = std::complex{2,10};
    auto const b = std::complex{0,20};
    auto const c = std::complex{1,15};
    EXPECT_EQ(midpoint(a, b), c);
}

TEST(midpoint, pointer)
{
    char const s[50] = {};
    EXPECT_EQ(midpoint(s+1, s+25), s+13);
    EXPECT_EQ(midpoint(s+25, s+1), s+13);
}

#include <string_view>
TEST(midpoint, iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    EXPECT_EQ(*midpoint(s.begin(), s.end()), 'n');
    EXPECT_EQ(*midpoint(s.end(), s.begin()), 'n');
    EXPECT_EQ(*midpoint(s), 'n');
}

#include <list>
TEST(midpoint, bidi_iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    auto const l = std::list(s.begin(), s.end());
    EXPECT_EQ(*midpoint(l.begin(), l.end()), 'n');
    EXPECT_EQ(*midpoint(l), 'n');
}

#include <forward_list>
TEST(midpoint, forward_iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    auto const l = std::forward_list(s.begin(), s.end());
    EXPECT_EQ(*midpoint(l.begin(), l.end()), 'n');
    EXPECT_EQ(*midpoint(l), 'n');
}

#include <array>
TEST(midpoint, std_array)
{
    auto const a = std::array{ 0, 10, 20};
    auto const b = std::array{10, 10, 10};
    auto const c = std::array{ 5, 10, 15};
    EXPECT_EQ(midpoint(a, b), c);
}

#if 1
// use detection idiom to ensure invalid overloads don't exist
// Inspired from library fundamentals TS v3
namespace {
    template <class AlwaysVoid, template<class...> class Op, class... Args>
    struct detector : std::false_type {};

    template <template<class...> class Op, class... Args>
    struct detector<std::void_t<Op<Args...>>, Op, Args...> : std::true_type {};

    template <template<class...> class Op, class... Args>
    constexpr bool is_detected_v = detector<void, Op, Args...>::value;
}
#else

#include <experimental/type_traits>
    using std::is_detected_v;

#endif

template<typename T, typename U = T>
using midpoint_exists = decltype(midpoint(std::declval<T>(), std::declval<U>()));


//static constexpr bool a = is_detected<midpoint_exists, int, int>;
static_assert(is_detected_v<midpoint_exists, int>);
static_assert(!is_detected_v<midpoint_exists, bool>);
static_assert(!is_detected_v<midpoint_exists, bool&>);

static_assert(!is_detected_v<midpoint_exists, std::istream_iterator<char>>);
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Strictly speaking affine space does not require points to be ordered. For example, complex numbers form an affine space. So maybe affine_ordered_point is a better name? \$\endgroup\$
    – G. Sliepen
    Jun 13, 2021 at 20:40
  • 1
    \$\begingroup\$ If you want to use std::midpoint for pointers, be aware that it rounds towards the first argument, not necessarily the smaller one. \$\endgroup\$ Jun 25, 2021 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.