6
\$\begingroup\$

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

  1. copy_strategy, which always makes a copy of the (projected) values, and
  2. external_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:

  1. The default strategy sorts in-place if possible, otherwise by copying, falling back to the external strategy as a last resort.
  2. 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.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

This looks very watertight. Just a few minor remarks:

Perhaps too much constraints?

You constrain the template parameters inside the template parameter list, but also using a requires-clause. A concept like std::sortable, or your own helper sortable_range, will already check that Range is a random access range and that Projected values can be compared using Comp. So it's a bit redundant, and you could remove some to make the code slightly more readable.

It might also the impact on the quality of the error messages. It might be nice to see "this set of arguments must form something that I can sort with" instead of "this comparator function does not give me a strict weak order over this range". But you'd have to check the output from different compilers to check what the actual effect is.

Make indirect_project() take a const pointer

A small nitpick, but the projection operation should not modify the range, so it would be better to make indirect_project take a const pointer argument.

The frugal_strategy might not be right for small value types

Consider that I might want the median value of a vector of std::int8_ts, then copy_strategy is preferrably over external_strategy, yet frugal_strategy always prefers the latter. Maybe have it check the size first and prefer copy when the size of a projected value type is equal to or smaller than a pointer.

Moving vs. copying the parameters of median_engine

The constructor of median_engine std::move()s all parameters. But the builder interface std::move()s only the single parameter of each builder function, but copies the corresponding 3 other member variables. You could make the member values of median_engine non-const, so all of them can be moved in the builder interface. On the other hand, you could just always copy, assuming it's unlikely that it is expensive.

Overhead of std::is_sorted()

While checking if the input is already sorted might speed up things greatly if the range is indeed sorted, it adds overhead in case it isn't. Also consider that for the in-place strategies, not checking it might be as fast as checking it, depending on the implementation of std::ranges::nth_element(). For the copy and external strategies, perhaps checking for sortedness during the copy is cheap enough to always do.

\$\endgroup\$
3
  • \$\begingroup\$ I think I'd need const and non-const overloads of the builder functions to move the members to the new object; in any case, I expect those to be const-evaluated in most usage, so probably not worth changing. \$\endgroup\$ Feb 20, 2022 at 9:44
  • \$\begingroup\$ I wanted the is_sorted() check before any allocation was attempted. It clearly doesn't make sense for the in-place strategies, but I was thinking it might be cheap enough to pay itself back by avoiding making and populating the auxiliary data structure. That likely depends on how frequently an already-sorted range will be passed. Sounds like another configuration option is coming... \$\endgroup\$ Feb 20, 2022 at 9:49
  • 1
    \$\begingroup\$ I agree with the rest of your review. I think I added the extra constraints to get more useful messages while I was writing the code - I ought to write some incorrect code to investigate what's most useful for actual users rather than the implementer! \$\endgroup\$ Feb 20, 2022 at 9:50
2
\$\begingroup\$

Even though I left the code overnight before posting (that always works; I wake up with improvements in my head) I still spotted a couple of improvements.

Avoid misunderstanding of the builder interface

Although the using_*() members are marked const, users might forget that and assume that they modify an instance rather than returning a new one (which wouldn't actually be possible, because the new object has a different type, in general).

That leads to them writing code like this:

auto m = stats::median;
m.using_inplace_strategy();  // WRONG
m(values);

We can make that an error by using a [[nodiscard]] attribute on those functions.

Simplify use of SCOPED_TRACE()

Instead of having to create small blocks like this:

{
    SCOPED_TRACE("default strategy");
    m(values);
}
{
    SCOPED_TRACE("copy strategy");
    m.using_copy_strategy()(values);
}
{
    SCOPED_TRACE("external strategy");
    m.using_external_strategy()(values);
}

A small helper function can reduce the repetition:

static void test_strategy(auto const& m, auto&& range, auto&& name = "")
{
    SCOPED_TRACE(name);
    m(std::forward<decltype(range)>(range));
}

And we use in in five places thus:

test_strategy(m, values, "default strategy");
test_strategy(m.using_copy_strategy(), values, "copy strategy");
test_strategy(m.using_external_strategy(), values, "external strategy");

Test custom compare and projection using all strategies

We only tested these using the default strategy. Instead, we should use test_values to test all strategies:

TEST(Median, CustomOrder)
{
    auto values = std::array{3, 4, 5, 100, 101, 102};
    // order by last digit:  100, 101, 102, 3, 4, 5
    auto const compare = [](int a, int b){ return a % 10 < b % 10; };
    SCOPED_TRACE("from here\n");
    test_values(values, {102, 3}, compare);
}

TEST(Median, CustomProjection)
{
    auto values = std::array{3, 4, 5, 100, 101, 102};
    // project to last digit:  0, 1, 2, 3, 4, 5
    auto const projection = [](int a){ return a % 10; };
    SCOPED_TRACE("from here\n");
    test_values(values, {2, 3}, {}, projection);
}

Ensure strategy is not used when NaN values are present

Just add a call to test_values_trivial:

TEST(Median, NaNsFirst)
{
    constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    double values[] = { nan, nan, 1, 1, 100, 100, 10 };
    test_values_trivial(values, test::dummy_midpoint{});
    EXPECT_TRUE(std::isnan(stats::median(values)));
}

Duplicate test

TEST(Median, ProjectByValue) tests exactly the same functionality as TEST(Median, CustomProjection) so can be dropped. Transparent projection is the default, so that's also thoroughly tested.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Good point about [[nodiscard]] for the builder interface. Another possibility would be to make the builder member functions &&-qualified, but that would not allow you to declare stats::median like you do now. \$\endgroup\$
    – G. Sliepen
    Feb 20, 2022 at 14:12

Your Answer

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

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