I recently posted an externally-evaluating median algorithm (i.e. not requiring move or copy of elements), and the feedback encouraged me to develop it further.
One simple suggestion was to handle NaN values, and test using infinities. It seems reasonable to return NaN if any are present in the input, as median becomes meaningless. If users wish to ignore NaNs, they can by using a filter view (see example in the test suite).
The other suggestion was to consider supporting projections of values. I also wanted to avoid inefficiency of storing pointers (worse: I had been storing iterators) in the cases where it's not necessary.
My original algorithm was already configurable with custom comparator and midpoint functions; adding a projection to this was heading for some combinatorial explosion of arguments, and making it hard to default some subset of them, so I moved to a Builder pattern. That allows simple use such as
// values is any sequence that satisfies Forward Range auto m = stats::median(values);
and more advanced use by calling factories, possibly chained:
auto m = stats::median.using_compare(<std::greater>) .using_arithmetic_midpoint() (values);
To minimise copying, I wanted to sort in-place when we're passed ownership:
auto m = stats::median(std::move(values));
If we want to permit mutating of all writable ranges, then we can specifically ask for the in-place policy:
auto calc_median = stats::median.using_inplace_strategy(); auto m = calc_median(values);
The other primitive policies are
copy_strategy, which always makes a copy of the (projected) values, andexternal_strategy, which makes pointers to the elements (without projection, since that need not be transparent).
Note that these three strategies have different requirements on the range - copy accepts an input range; external needs a forward range; inplace is most restrictive, needing a random-access range.
From these, we have two composite strategies:
- The default strategy sorts in-place if possible, otherwise by copying, falling back to the external strategy as a last resort.
- The minimum-space (
frugal) strategy also prefers to sort in-place if possible, but prefers the external strategy over copying when pointers to elements are smaller than projected values.
I've tried to use consistent template parameter names (i.e. Comp for
a comparator and Proj for projection). I looked to the standard for
guidance, but it's inconsistent in this respect - sometimes even within
one section (e.g. the description of nth_element() and its associated
concepts).
#include <algorithm>
#include <cmath>
#include <concepts>
#include <functional>
#include <iterator>
#include <memory>
#include <numeric>
#include <ranges>
#include <utility>
/*
A flexible but user-friendly way to evaluate the median of almost any collection.
Easy interface:
* stats::median(values) // values is unchanged
* stats::median(std::move(values)) // may re-order the container
* values | stats::median // works like a view
More advanced:
* auto small_median = stats::median.using_frugal_strategy();
small_median(values) // tries harder not to minimize memory use
* Other strategies are provided. The "inplace" strategy is useful to end users, as it treats all
inputs as rvalues (modifying through references) even without `std::move()`. The "copy" and
"external" strategies are mostly useful to the implementation of the default and frugal ones.
* We can use any comparator or projection function, and any any function to calculate the mean of
the mid elements (this function will be passed duplicate arguments if the input size is odd).
An "arithmetic" midpoint function is provided; this can be useful for getting fractional medians
from integer inputs. For example:
stats::median.using_arithmetic_midpoint()(std::array{ 0, 1, 2, 3}) ⟶ 1.5
*/
namespace stats
{
// Type traits
template<std::ranges::forward_range Range, typename Proj>
using projected_t =
std::projected<std::ranges::iterator_t<Range>, Proj>::value_type;
template<std::ranges::forward_range Range, typename Proj, typename Midpoint>
using median_result_t =
std::invoke_result_t<Midpoint, projected_t<Range, Proj>, projected_t<Range, Proj>>;
// Concepts
template<typename Range, typename Comp, typename Proj>
concept sortable_range =
std::sortable<std::ranges::iterator_t<Range>, Comp, Proj>;
template<typename C, typename Range, typename Proj>
concept projected_strict_weak_order =
std::indirect_strict_weak_order<C, std::projected<std::ranges::iterator_t<Range>, Proj>>;
template<typename M, typename Range, typename Proj>
concept midpoint_function =
std::invocable<M, projected_t<Range, Proj>, projected_t<Range, Proj>>;
template<typename S>
concept median_strategy =
std::is_same_v<std::invoke_result_t<S, std::vector<int>&&, std::less<>, std::identity, std::less<>>, bool>;
// Midpoint policies
struct default_midpoint
{
template<typename T>
constexpr auto operator()(T const& a, T const& b) const
{
using std::midpoint;
return midpoint(a, b);
}
};
template<typename T>
struct arithmetic_midpoint
{
constexpr auto operator()(T const& a, T const& b) const
{
return default_midpoint{}.operator()<T>(a, b);
}
};
// Median policies
struct inplace_strategy
{
template<std::ranges::random_access_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
requires sortable_range<Range, Comp, Proj>
{
auto const size = std::ranges::distance(values);
auto upper = std::ranges::begin(values) + size / 2;
std::ranges::nth_element(values, upper, compare, proj);
auto lower = size % 2 ? upper
: std::ranges::max_element(std::ranges::begin(values), upper, compare, proj);
return midpoint(std::invoke(proj, *lower), std::invoke(proj, *upper));
}
};
struct inplace_strategy_rvalues_only
{
// Exists mainly to implement the default and frugal strategies
// But could be useful if you need to disallow copy and external.
template<std::ranges::random_access_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
requires sortable_range<Range, Comp, Proj> && (!std::is_lvalue_reference_v<Range>)
{
return inplace_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
}
};
struct copy_strategy
{
template<std::ranges::input_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
requires std::copyable<std::remove_reference_t<projected_t<Range, Proj>>>
{
auto projected = values | std::views::transform(proj);
auto v = std::vector(std::ranges::begin(projected), std::ranges::end(projected));
return inplace_strategy{}(v, compare, std::identity{}, midpoint);
}
};
struct external_strategy
{
template<std::ranges::forward_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
{
using pointer_type = std::add_pointer_t<const std::ranges::range_value_t<Range>>;
using pointer_traits = std::pointer_traits<pointer_type>;
auto indirect_project = [proj](auto *a)->decltype(auto) { return std::invoke(proj, *a); };
auto pointers = values | std::views::transform(pointer_traits::pointer_to);
auto v = std::vector(std::ranges::begin(pointers), std::ranges::end(pointers));
return inplace_strategy{}(v, compare, indirect_project, midpoint);
}
};
struct default_strategy
{
template<std::ranges::forward_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
requires std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>
|| std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>
|| std::invocable<external_strategy, Range, Comp, Proj, Midpoint>
{
if constexpr (std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>) {
return inplace_strategy_rvalues_only{}(std::forward<Range>(values), compare, proj, midpoint);
}
if constexpr (std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>) {
try {
return copy_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
} catch (std::bad_alloc&) {
if constexpr (!std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
throw;
}
if constexpr (sizeof (projected_t<Range, Proj>*) >= sizeof (projected_t<Range, Proj>)) {
// external strategy won't help
throw;
}
// Else, we can try using external strategy more cheaply,
// so fallthrough to try that.
}
}
if constexpr (std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
return external_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
}
}
};
struct frugal_strategy
{
template<std::ranges::forward_range Range,
std::invocable<std::ranges::range_value_t<Range>> Proj,
projected_strict_weak_order<Range, Proj> Comp,
midpoint_function<Range, Proj> Midpoint>
auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
-> median_result_t<Range, Proj, Midpoint>
requires std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>
|| std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>
|| std::invocable<external_strategy, Range, Comp, Proj, Midpoint>
{
if constexpr (std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>) {
return inplace_strategy_rvalues_only{}(std::forward<Range>(values), compare, proj, midpoint);
}
if constexpr (std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
return external_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
}
if constexpr (std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>) {
return copy_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
}
}
};
// The median calculator type
template<typename Proj, typename Comp, typename Midpoint, typename Strategy>
class median_engine
{
const Strategy strategy;
const Comp compare;
const Proj projection;
const Midpoint midpoint;
public:
// For simple construction, start with stats::median and use
// the builder interface to customise it.
constexpr median_engine(Proj projection, Comp comparer,
Midpoint midpoint, Strategy strategy) noexcept
: strategy{std::move(strategy)},
compare{std::move(comparer)},
projection{std::move(projection)},
midpoint{std::move(midpoint)}
{}
// Builder interface
template<typename P>
constexpr auto using_projection(P projection) const {
return median_engine<P, Comp, Midpoint, Strategy>
(std::move(projection), compare, midpoint, strategy);
}
template<typename C>
constexpr auto using_compare(C compare) const {
return median_engine<Proj, C, Midpoint, Strategy>
(projection, std::move(compare), midpoint, strategy);
}
template<typename M>
constexpr auto using_midpoint(M midpoint) const {
return median_engine<Proj, Comp, M, Strategy>
(projection, compare, std::move(midpoint), strategy);
}
template<typename T = double>
constexpr auto using_arithmetic_midpoint() const {
return using_midpoint(arithmetic_midpoint<T>{});
}
template<median_strategy S>
constexpr auto using_strategy(S strategy) const
{
return median_engine<Proj, Comp, Midpoint, S>
(projection, compare, midpoint, std::move(strategy));
}
constexpr auto using_external_strategy() const { return using_strategy(external_strategy{}); }
constexpr auto using_inplace_strategy() const { return using_strategy(inplace_strategy{}); }
constexpr auto using_copy_strategy() const { return using_strategy(copy_strategy{}); }
constexpr auto using_frugal_strategy() const { return using_strategy(frugal_strategy{}); }
constexpr auto using_default_strategy() const { return using_strategy(default_strategy{}); }
// Main function interface:
// Compute the median of a range of values
template<std::ranges::forward_range Range>
auto operator()(Range&& values) const
requires std::invocable<Strategy, Range, Comp, Proj, Midpoint>
{
return calculate_median(std::forward<Range>(values));
}
// Overload for const filter views which are not standard ranges.
// Some standard views (chunk_by_view, drop_while_view, filter_view, split_view) are not
// const-iterable, due to time complexity requirements on begin() requiring it to remember
// its result. See https://stackoverflow.com/q/67667318
template<typename View>
auto operator()(View&& values) const
requires (!std::ranges::range<View>)
&& std::ranges::range<std::decay_t<View>>
{
// Make a copy - which is a range
auto values_copy = values;
// but pass it as an lvalue ref so we don't order in-place by default
return calculate_median(values_copy);
}
private:
template<std::ranges::forward_range Range>
auto calculate_median(Range&& values) const
requires std::invocable<Strategy, Range, Comp, Proj, Midpoint>
{
auto const begin = std::ranges::begin(values);
auto const size = std::ranges::distance(values);
switch (size) {
case 0:
throw std::invalid_argument("Attempting median of empty range");
case 1:
{
auto const& a = project(begin);
return midpoint(a, a);
}
case 2:
{
auto const& a = project(begin);
auto const& b = project(std::next(begin));
if (compare(a, b)) {
// Yes, the order matters!
// e.g. std::midpoint rounds towards its first argument.
return midpoint(a, b);
} else {
return midpoint(b, a);
}
}
}
// If the range contains NaN values, there is no meaningful median.
// We still need to launder through mipoint() for correct return type.
using value_type = std::ranges::range_value_t<Range>;
if constexpr (std::is_floating_point_v<std::remove_reference_t<value_type>>) {
auto isnan = [](value_type d){ return std::isnan(d); };
if (auto it = std::ranges::find_if(values, isnan, projection); it != std::ranges::end(values)) {
return midpoint(project(it), project(it));
}
}
// If already ordered, just access the middle elements
if (std::ranges::is_sorted(values, compare, projection)) {
auto const lower = std::next(std::ranges::begin(values), (size - 1) / 2);
auto const upper = size % 2 ? lower : std::next(lower);
return midpoint(project(lower), project(upper));
}
// else use selected strategy
return strategy(std::forward<Range>(values), compare, projection, midpoint);
}
auto project(std::indirectly_readable auto p) const -> decltype(auto)
{
return std::invoke(projection, *p);
}
};
// We can put a median engine at the end of an adaptor chain
// e.g. auto midval = view | filter | median;
template<typename InputRange, typename... MedianArgs>
auto operator|(InputRange&& range, median_engine<MedianArgs...> engine)
{
return std::forward<median_engine<MedianArgs...>>(engine)(std::forward<InputRange>(range));
}
// Default engine, from which we can obtain customised ones using the builder interface.
static constexpr auto median = median_engine
{
std::identity{},
std::less<>{},
default_midpoint{},
default_strategy{}
};
}
#include <gtest/gtest.h>
#include <array>
#include <forward_list>
#include <stdexcept>
#include <vector>
namespace test
{
struct moveonly_int
{
int value;
moveonly_int(int i) : value{i} {}
moveonly_int(const moveonly_int&) = delete;
moveonly_int(moveonly_int&&) = default;
void operator=(const moveonly_int&) = delete;
moveonly_int& operator=(moveonly_int&&) = default;
bool operator<(const moveonly_int& other) const
{ return value < other.value; }
};
// specific midpoint for this type, to be found by ADL
double midpoint(const moveonly_int& a, const moveonly_int& b)
{
return b.value - a.value; // the name is a lie
}
struct nocopy_int
{
int value;
nocopy_int(int i) : value{i} {}
nocopy_int(const nocopy_int&) = delete;
void operator=(const nocopy_int&) = delete;
bool operator<(const nocopy_int& other) const
{ return value < other.value; }
};
// specific midpoint for this type, to be found by ADL
double midpoint(const nocopy_int& a, const nocopy_int& b)
{
return a.value + b.value; // the name is a lie
}
template<typename T>
struct expect_midpoint {
const T expected_a;
const T expected_b;
void operator()(T const& actual_a, T const& actual_b) const
{
EXPECT_EQ(expected_a, actual_a);
EXPECT_EQ(expected_b, actual_b);
}
};
struct dummy_midpoint
{
auto operator()(auto&&, auto&&) const {}
};
struct invalid_strategy
{
template<std::ranges::forward_range Range,
typename Comp,
typename Proj,
typename Midpoint>
auto operator()(Range&&, Comp, Proj, Midpoint) const
-> stats::median_result_t<Range, Proj, Midpoint>
{
throw std::logic_error("should not be called");
}
};
}
// C++20 version of detection idiom
template<typename Func, typename... Args>
constexpr bool can_call(Func&&, Args&&...)
requires std::invocable<Func, Args...>
{ return true; }
template<typename... Args>
constexpr bool can_call(Args&&...)
{ return false; }
template<typename Strategy, typename Range>
concept strategy_accepts_type =
std::invocable<Strategy, Range, std::less<>, std::identity, test::dummy_midpoint>;
enum strategy_mask : unsigned {
sm_inplace = 0x01,
sm_inplace_rvalue = 0x02,
sm_copy = 0x04,
sm_external = 0x08,
sm_default = 0x10,
sm_frugal = 0x20,
sm_none = 0u,
sm_all = ~0u,
};
constexpr auto operator+(strategy_mask a, strategy_mask b)
{ return static_cast<strategy_mask>(static_cast<unsigned>(a) | static_cast<unsigned>(b)); }
constexpr auto operator-(strategy_mask a, strategy_mask b)
{ return static_cast<strategy_mask>(static_cast<unsigned>(a) & ~static_cast<unsigned>(b)); }
constexpr bool is_set(strategy_mask a, strategy_mask b)
{ return a & b; }
template<typename Range>
void expect_usable(strategy_mask m = 0)
{
if (!is_set(m, sm_inplace)) {
// if we can't inplace, then we certainly can't inplace-rvalue
m = m - sm_inplace_rvalue;
}
EXPECT_EQ(is_set(m, sm_inplace), (strategy_accepts_type<stats::inplace_strategy, Range>));
EXPECT_EQ(is_set(m, sm_inplace_rvalue), (strategy_accepts_type<stats::inplace_strategy_rvalues_only, Range>));
EXPECT_EQ(is_set(m, sm_copy), (strategy_accepts_type<stats::copy_strategy, Range>));
EXPECT_EQ(is_set(m, sm_external), (strategy_accepts_type<stats::external_strategy, Range>));
EXPECT_EQ(is_set(m, sm_default), (strategy_accepts_type<stats::default_strategy, Range>));
EXPECT_EQ(is_set(m, sm_frugal), (strategy_accepts_type<stats::frugal_strategy, Range>));
}
// Tests of callability
// (Could be static, but we get better diagnostics this way)
TEST(Strategies, Regular)
{
using Range = std::vector<int>;
{
SCOPED_TRACE("pass by value\n");
expect_usable<Range>(sm_all);
}
{
SCOPED_TRACE("pass by ref\n");
expect_usable<Range&>(sm_all - sm_inplace_rvalue);
}
{
SCOPED_TRACE("pass by const ref\n");
expect_usable<Range const&>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by rvalue\n");
expect_usable<Range&&>(sm_all);
}
}
TEST(Strategies, MoveOnly)
{
using Range = std::vector<test::moveonly_int>;
// can't be copied
{
SCOPED_TRACE("pass by value\n");
expect_usable<Range>(sm_all - sm_copy);
}
{
SCOPED_TRACE("pass by ref\n");
expect_usable<Range&>(sm_all - sm_copy - sm_inplace_rvalue);
}
{
SCOPED_TRACE("pass by const ref\n");
expect_usable<Range const&>(sm_external + sm_default + sm_frugal);
}
{
SCOPED_TRACE("pass by rvalue\n");
expect_usable<Range&&>(sm_all - sm_copy);
}
}
TEST(Strategies, NoCopy)
{
using Range = std::vector<test::nocopy_int>;
{
SCOPED_TRACE("pass by value\n");
expect_usable<Range>(sm_all - sm_inplace - sm_copy);
}
{
SCOPED_TRACE("pass by ref\n");
expect_usable<Range&>(sm_all - sm_inplace - sm_copy);
}
{
SCOPED_TRACE("pass by const ref\n");
expect_usable<Range const&>(sm_all - sm_inplace - sm_copy);
}
{
SCOPED_TRACE("pass by rvalue\n");
expect_usable<Range&&>(sm_all - sm_inplace - sm_copy);
}
}
TEST(Strategies, ForwardOnly)
{
using Range = std::forward_list<int>;
{
SCOPED_TRACE("pass by value\n");
expect_usable<Range>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by ref\n");
expect_usable<Range&>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by const ref\n");
expect_usable<Range const&>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by rvalue\n");
expect_usable<Range&&>(sm_all - sm_inplace);
}
}
TEST(Strategies, FilteredView)
{
using View = std::ranges::filter_view<std::ranges::ref_view<int[1]>, std::function<bool(int)>>;
{
SCOPED_TRACE("pass by value\n");
expect_usable<View>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by ref\n");
expect_usable<View&>(sm_all - sm_inplace);
}
{
SCOPED_TRACE("pass by const ref\n");
// const view isn't a range - needs median_engine to copy it
expect_usable<View const&>(sm_none);
}
{
SCOPED_TRACE("pass by rvalue\n");
expect_usable<View&&>(sm_all - sm_inplace);
}
}
// Don't even try compiling the rest unless earlier tests succeed!
#ifndef TYPE_TESTS_FAILED
// Use this one for tests where the engine should not call out to strategy.
// I.e. when input is ordered, or there's only 1 or 2 elements.
template<std::ranges::forward_range Container = std::vector<int>,
typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
typename Comp = std::less<>, typename Proj = std::identity>
static void test_values_trivial(Container&& values, Midpoint expected,
Comp compare = {}, Proj projection = {})
{
stats::median
.using_compare(compare)
.using_projection(projection)
.using_midpoint(expected)
.using_strategy(test::invalid_strategy{}) // will fail if called
(std::forward<Container>(values));
}
template<std::ranges::forward_range Container = std::vector<int>,
typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
typename Comp = std::less<>, typename Proj = std::identity>
static void test_values_const_input(const Container& values, Midpoint expected,
Comp compare = {}, Proj projection = {})
{
auto const m = stats::median
.using_compare(compare)
.using_projection(projection)
.using_midpoint(expected);
{
SCOPED_TRACE("default strategy");
m(values);
}
{
SCOPED_TRACE("copy strategy");
m.using_copy_strategy()(values);
}
{
SCOPED_TRACE("external strategy");
m.using_external_strategy()(values);
}
}
template<std::ranges::forward_range Container = std::vector<int>,
typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
typename Comp = std::less<>, typename Proj = std::identity>
static void test_values(Container&& values, Midpoint expected,
Comp compare = {}, Proj projection = {})
{
test_values_const_input(values, expected, compare, projection);
auto const m = stats::median
.using_compare(compare)
.using_projection(projection)
.using_midpoint(expected);
SCOPED_TRACE("inplace strategy");
m.using_inplace_strategy()(std::move(values));
}
TEST(Median, Empty)
{
EXPECT_THROW(stats::median(std::vector<int>{}), std::invalid_argument);
}
TEST(Median, OneElement)
{
SCOPED_TRACE("from here\n");
test_values_trivial({100}, {100, 100});
}
TEST(Median, TwoElements)
{
SCOPED_TRACE("from here\n");
test_values_trivial({100, 200}, {100, 200});
SCOPED_TRACE("from here\n");
test_values_trivial({200, 100}, {100, 200});
}
TEST(Median, ThreeSortedElements)
{
SCOPED_TRACE("from here\n");
test_values_trivial({1, 2, 3}, {2, 2});
}
TEST(Median, ThreeElements)
{
SCOPED_TRACE("from here\n");
test_values({1, 3, 2}, {2, 2});
}
TEST(Median, FourSortedElements)
{
SCOPED_TRACE("from here\n");
test_values_trivial({2, 4, 6, 8}, {4, 6});
SCOPED_TRACE("from here\n");
test_values_trivial({4, 4, 4, 6}, {4, 4});
}
TEST(Median, FourElements)
{
SCOPED_TRACE("from here\n");
test_values({8, 2, 6, 4}, {4, 6});
SCOPED_TRACE("from here\n");
test_values({4, 4, 6, 4}, {4, 4});
}
TEST(Median, FiveElements)
{
SCOPED_TRACE("from here\n");
test_values({8, 2, 6, 4, 0}, {4, 4});
}
TEST(Median, PlainArray)
{
int values[] = { 2, 1, 3};
test_values(values, {2, 2});
}
TEST(Median, ConstPlainArray)
{
const int values[] = { 2, 1, 3};
test_values_const_input(values, {2, 2});
// Also exercise the range-adaptor style
EXPECT_EQ(values | stats::median, 2);
}
TEST(Median, Strings)
{
SCOPED_TRACE("from here\n");
std::string_view values[] = { "one", "two", "three", "four", "five", "six" };
// Alphabetical: five four ONE SIX three two
test_values(values, test::expect_midpoint<std::string_view>{"one", "six"});
}
TEST(Median, NaNsFirst)
{
constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
double values[] = { nan, nan, 1, 1, 100, 100, 10 };
EXPECT_TRUE(std::isnan(stats::median(values)));
}
TEST(Median, NaNsLast)
{
constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
double values[] = { 1, 1, 100, 100, 10, nan, nan };
EXPECT_TRUE(std::isnan(stats::median(values)));
}
TEST(Median, Infinities)
{
constexpr auto inf = std::numeric_limits<double>::infinity();
std::vector<double> values;
values = { -inf, inf, -inf };
EXPECT_EQ(stats::median(values), -inf);
values = { inf, -inf, inf };
EXPECT_EQ(stats::median(values), inf);
values = { inf, -inf, inf, -inf };
EXPECT_TRUE(std::isnan(stats::median(values))); // midpoint of ±∞
}
TEST(Median, CustomOrder)
{
auto const values = std::array{20, 91, 92, 54, 63};
// order by last digit: 0, 1, 2, 4, 3
auto const compare = [](int a, int b){ return a % 10 < b % 10; };
EXPECT_EQ(stats::median.using_compare(compare)(values), 92);
}
TEST(Median, CustomProjection)
{
auto const values = std::array{20, 91, 92, 54, 63};
// project to last digit: 0, 1, 2, 4, 3
auto const projection = [](int a){ return a % 10; };
EXPECT_EQ(stats::median.using_projection(projection)(values), 2);
}
TEST(Median, Value)
{
auto const values = std::forward_list{0, 1, 2, 3};
EXPECT_EQ(stats::median(values), 1); // rounded down
EXPECT_EQ(stats::median.using_arithmetic_midpoint()(values), 1.5);
// And with reverse order (causing integer std::midpoint() to round upwards)
auto m = stats::median.using_compare(std::greater<int>{});
EXPECT_EQ(m(values), 2);
EXPECT_EQ(m.using_arithmetic_midpoint<long double>()(values), 1.5L);
}
TEST(Median, MoveOnly)
{
// finds test::midpoint (which returns the difference!)
std::array<test::moveonly_int, 4> values{0, 3, 5, 2};
EXPECT_FALSE(can_call(stats::median.using_copy_strategy(), values));
EXPECT_EQ(stats::median(values), 1); // 3 - 2
EXPECT_EQ(stats::median.using_inplace_strategy()(values), 1);
}
TEST(Median, NoCopy)
{
// finds test::midpoint (which returns the sum!)
std::array<test::nocopy_int, 4> values{0, 1, 4, 2};
EXPECT_FALSE(can_call(stats::median.using_inplace_strategy(), values));
EXPECT_FALSE(can_call(stats::median.using_copy_strategy(), values));
EXPECT_EQ(stats::median.using_external_strategy()(values), 3); // 1 + 2
EXPECT_EQ(stats::median(std::move(values)), 3);
}
TEST(Median, ProjectByValue)
{
auto twice = [](auto x) { return 2 * x; };
constexpr auto m = stats::median.using_projection(twice);
int values[] = {0, 1, 3, 4, 2};
EXPECT_EQ(m.using_copy_strategy()(values), 4);
EXPECT_EQ(m.using_external_strategy()(values), 4);
EXPECT_EQ(m.using_inplace_strategy()(values), 4);
}
TEST(Median, FilteredRange)
{
constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
double values[] = { nan, nan, 1, 100, 10 };
auto view = values | std::views::filter([](double d){ return !std::isnan(d); });
EXPECT_EQ(stats::median.using_copy_strategy()(view), 10);
EXPECT_EQ(stats::median.using_external_strategy()(view), 10);
EXPECT_EQ(stats::median(view), 10);
EXPECT_EQ(values[2], 1); // shouldn't have modified underlying range
}
TEST(Median, FilteredRangeConst)
{
constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
double values[] = { nan, nan, 1, 100, 10 };
auto const view = values | std::views::filter([](double d){ return !std::isnan(d); });
EXPECT_EQ(stats::median.using_copy_strategy()(view), 10);
EXPECT_EQ(stats::median.using_external_strategy()(view), 10);
EXPECT_EQ(stats::median(view), 10);
EXPECT_EQ(values[2], 1); // shouldn't have modified underlying range
}
#endif
The updated code is now on GitHub; this version corresponds to commit d6ac335.
