#include <iostream>
#include <type_traits>

// =====================================================================
// 1. Boost.MPL Core Components
// =====================================================================

// An MPL vector is just a type holding a list of other types.
template <typename... Ts>
struct vector {};

// An MPL int_ represents an integer as a TYPE.
template <int N>
struct int_ : std::integral_constant<int, N> {};

// A generic less-than predicate for types.
template <typename T1, typename T2>
struct less : std::integral_constant<bool, (T1::value < T2::value)> {};

// =====================================================================
// 2. Type-Level Concatenation (Joining lists)
// =====================================================================
template <typename L1, typename L2, typename L3>
struct concat;

// Specialization to extract the types from three vectors and merge them
template <typename... T1, typename... T2, typename... T3>
struct concat<vector<T1...>, vector<T2...>, vector<T3...>> {
    using type = vector<T1..., T2..., T3...>;
};

// =====================================================================
// 3. Type-Level Partitioning (Splitting list around a pivot)
// =====================================================================
template <bool Cond, typename T, typename Less, typename GreaterEq>
struct push_impl;

// If true: push to Less vector
template <typename T, typename... L, typename... G>
struct push_impl<true, T, vector<L...>, vector<G...>> {
    using less = vector<L..., T>;
    using greater_eq = vector<G...>;
};

// If false: push to GreaterEq vector
template <typename T, typename... L, typename... G>
struct push_impl<false, T, vector<L...>, vector<G...>> {
    using less = vector<L...>;
    using greater_eq = vector<G..., T>;
};

template <typename Pivot, typename List, template<typename, typename> class Pred, typename LessList = vector<>, typename GreaterEqList = vector<>>
struct partition;

// Base Case: Empty List
template <typename Pivot, template<typename, typename> class Pred, typename LessList, typename GreaterEqList>
struct partition<Pivot, vector<>, Pred, LessList, GreaterEqList> {
    using less = LessList;
    using greater_eq = GreaterEqList;
};

// Recursive Case: Evaluate Head against Pivot, push to correct list, recurse on Tail
template <typename Pivot, typename Head, typename... Tail, template<typename, typename> class Pred, typename LessList, typename GreaterEqList>
struct partition<Pivot, vector<Head, Tail...>, Pred, LessList, GreaterEqList> {
    // 1. Check if Head < Pivot
    static constexpr bool is_less = Pred<Head, Pivot>::value;
    
    // 2. Route the Head into the temporary less/greater lists
    using step = push_impl<is_less, Head, LessList, GreaterEqList>;
    
    // 3. Recurse down the Tail
    using recurse = partition<Pivot, vector<Tail...>, Pred, typename step::less, typename step::greater_eq>;
    
    using less = typename recurse::less;
    using greater_eq = typename recurse::greater_eq;
};

// =====================================================================
// 4. THE SORT ALGORITHM (Type-Level Quicksort)
// =====================================================================
template <typename List, template<typename, typename> class Pred = less>
struct sort;

// Base Case: Empty list is already sorted
template <template<typename, typename> class Pred>
struct sort<vector<>, Pred> {
    using type = vector<>;
};

// Recursive Quicksort
template <typename Pivot, typename... Tail, template<typename, typename> class Pred>
struct sort<vector<Pivot, Tail...>, Pred> {
    // 1. Partition the Tail around the Pivot
    using parts = partition<Pivot, vector<Tail...>, Pred>;
    
    // 2. Sort the Less list
    using sorted_less = typename sort<typename parts::less, Pred>::type;
    
    // 3. Sort the Greater list
    using sorted_greater = typename sort<typename parts::greater_eq, Pred>::type;
    
    // 4. Concat: [Sorted Less] + [Pivot] + [Sorted Greater]
    using type = typename concat<sorted_less, vector<Pivot>, sorted_greater>::type;
};

// =====================================================================
// PROOF IT WORKS (Strictly Compile-Time Verification)
// =====================================================================

using UnsortedData = vector<int_<8>, int_<3>, int_<9>, int_<1>, int_<4>>;

// 💥 THE COMPILER SORTS THE TYPES HERE 💥
using SortedData = sort<UnsortedData>::type;

// We use std::is_same to prove to the compiler that SortedData is exactly 
// equivalent to a manually sorted vector. If this fails, compilation stops.
static_assert(std::is_same<
    SortedData, 
    vector<int_<1>, int_<3>, int_<4>, int_<8>, int_<9>>
>::value, "Boost.MPL Sort Failed!");

int main() {
    std::cout << "Type-Level Metaprogramming Sort successful!\n";
    std::cout << "The sorting didn't happen in 0ms... it never 'happened' at all.\n";
    std::cout << "The types themselves dictate the sorted order.\n";
    return 0;
}