sort.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: BSD-2-Clause
 
#ifndef pRC_ALGORITHMS_SORT_H
#define pRC_ALGORITHMS_SORT_H
 
#include <prc/core/basic/concepts.hpp>
#include <prc/core/functors/less.hpp>
#include <prc/core/functors/subscript.hpp>
 
namespace pRC
{
    template<class C, IsSubscriptable T,
        class S = ResultOf<Subscript, T &, Index>>
        requires IsInvocable<C, S, S> && IsAssignable<S>
    static inline constexpr void sort(C const &compare, T &a,
        Size const k = T::size(), Size const d = 0)
    {
        auto const insertionSort =
            [](auto &a, auto const &compare, auto const k, auto const d)
        {
            for(Index i = d + 1; i < k; ++i)
            {
                auto const x = move(a[i]);
                auto j = i;
                for(; j > d; --j)
                {
                    if(!compare(x, a[j - 1]))
                    {
                        break;
                    }
                    a[j] = move(a[j - 1]);
                }
                a[j] = move(x);
            }
 
            return;
        };
 
        insertionSort(a, compare, k, d);
 
        for(Index i = k; i < T::size(); ++i)
        {
            if(compare(a[i], a[k - 1]))
            {
                swap(a[i], a[k - 1]);
 
                insertionSort(a, compare, k, d);
            }
        }
    }
 
    template<class C = Less, IsSubscriptable T,
        class S = ResultOf<Subscript, T &, Index>>
        requires IsInvocable<C, S, S> && IsAssignable<S>
    static inline constexpr void sort(T &a, Size const k = T::size(),
        Size const d = 0)
    {
        return sort(C(), a, k, d);
    }
}
#endif // pRC_ALGORITHMS_SORT_H