A very easily stated problem that has a surprising number of gotchas - return a value that's midway between the two supplied values.
Depending on the types given, we need to be aware of
- arithmetic overflow and underflow
- infinities
- NaNs
- rounding
For pointers and iterators, the mean only makes sense if the values point into the same object; the results are otherwise undefined. For forward-only iterators, the arguments need to be in the correct order; for other types, either order is accepted.
For aggregate types, we just need to compute the mean element-wise. I've provided code for arrays and complex numbers; third-party aggregates (e.g. "point" and "vector" geometric types) can be implemented by following the existing pattern.
I expect the template to work unaltered for other arithmetic classes (e.g. bignum and rational types).
#include <cmath>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
namespace std {
template<typename T> class complex;
template<typename T, std::size_t N> class array;
}
namespace _
{
template<typename T>
concept arithmetic = std::regular<T> && requires(T a, T b) {
a + (b - a); a < b;
};
template<arithmetic T>
T midpoint(T a, T b)
{
if (a == b) {
// this ensures infinities are correctly returned
return a;
}
if constexpr (std::is_floating_point_v<T>) {
if (std::isnan(a)) { return a; }
if (std::isnan(b)) { return b; }
}
if constexpr (std::is_arithmetic_v<T>) {
if ((a < 0) != (b < 0)) {
return (a + b) / 2;
}
}
if (a > b) {
using std::swap;
swap(a, b);
}
return a + (b - a) / 2;
}
// Non-random-access iterators
// a MUST be before b
template<std::forward_iterator T>
requires (!std::bidirectional_iterator<T>)
T midpoint(T a, T b)
{
bool skip = false;
T mid = a;
while (a != b) {
++a;
if (!skip) { ++mid; }
skip = !skip;
}
return mid;
}
// Aggregate types follow
// Pattern can be extended, e.g. for popular geometry types
template<arithmetic T>
std::complex<T> midpoint(std::complex<T> a, std::complex<T> b)
{
return {
midpoint(a.real(), b.real()),
midpoint(a.imag(), b.imag())
};
}
template<arithmetic T, std::size_t N>
std::array<T,N> midpoint(const std::array<T,N>& a, const std::array<T,N>& b)
{
std::array<T,N> result;
for (std::size_t i = 0; i < N; ++i) {
result[i] = midpoint(a[i], b[i]);
}
return result;
}
}
using _::midpoint;
// Tests
#include <gtest/gtest.h>
#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)
{
auto const s = "_abcdefghijklmnopqrstuvwxyz";
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 <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);
}
I've intentionally included some questionable choices:
_
as a namespace name is legal, but is it a good choice for the implementation-private namespace?- I believe I can forward-declare the template classes that belong to
std
, rather than drag in their entire headers. - The
arithmetic
concept has very similar name tostd::is_arithmetic
- could/should I change that? - The unit-tests still pass if I remove the early exit for NaN inputs, but should I retain them anyway? (The checks were once needed, but refactoring them has left them redundant).
- In the first test case, I assume that
-INT_MAX
is valid - could that legally overflow?
I didn't yet enclose the code in a namespace - I would do that when I add include guards and make it a header.
T
is anaffine_point
. \$\endgroup\$requires (!std::bidirectional_iterator<T>)
) bidi iterators so, for example,std::list::iterator
won’t work with any overload. Why ban bidi iterators? \$\endgroup\$std::swap
if no more specificswap()
function is found during argument-dependent lookup. \$\endgroup\$