Program Listing for File sorted.hpp

↰ Return to documentation for file (include/sorted.hpp)

#pragma once

#include "partition.hpp"
#include "predicates.hpp"
#include "htlist.hpp"


namespace ctql {

    enum class Order { Asc, Desc };

    template <Order Ord, typename List>
    struct sort_list;

    template <Order Ord>
    struct sort_list<Ord, detail::HTList<>> {
        using type = detail::HTList<>;
    };

    template <Order Ord, HasStaticSize T0, HasStaticSize... TRest>
    struct sort_list<Ord, detail::HTList<T0, TRest...>> {
    private:
        // Choose relational operators based on order:
        //   Asc:  Left = "<",  Right = ">="
        //   Desc: Left = ">",  Right = "<="
        using LeftRel  = std::conditional_t<Ord == Order::Asc,  op_type<"<"_ct>,  op_type<">"_ct>>;
        using RightRel = std::conditional_t<Ord == Order::Asc,  op_type<">="_ct>, op_type<"<="_ct>>;

        // Partition the tail TRest... with respect to pivot T0.
        // P::pass  => elements on the Left side (strict compare vs pivot)
        // Not-pass => elements on the Right side (>= or <= vs pivot)
        using P = partition_by<T0, LeftRel::template pred, TRest...>;
        using LeftSorted = typename sort_list<Ord, typename P::pass>::type;

        using RightUnsorted = filter_by<T0, RightRel::template pred, TRest...>;
        using RightSorted   = typename sort_list<Ord, RightUnsorted>::type;

    public:
        // Concatenate: LeftSorted ++ [T0] ++ RightSorted
        using type = typename detail::append<
            typename detail::append<LeftSorted, detail::HTList<T0>>::type,
            RightSorted
        >::type;
    };

    template <Order Ord = Order::Asc, template <typename> class KeyOf = Size, typename... Ts>
    using TypeSort = typename sort_list<Ord, detail::HTList<KeyOf<Ts>...>>::type;

} // namespace ctql