template heap sort

cpp_template_heap_sort.cpp

#include <cstddef>
#include <iostream>
#include <array>

// 断言 debug用的
template<bool>
struct m_assert;

template<>
struct m_assert<true> {
    typedef int result_type;
};

template<>
struct m_assert<false> {};

template<bool flag, typename ...T>
struct m_assert_print{
    typedef typename m_assert<flag>::result_type result_type;
};

// 判断，输出一个类型
template<bool, typename T, typename S>
struct m_if;

template<typename T, typename S>
struct m_if<true, T, S> {
    typedef T result_type;
    typedef S not_result_type;
};

template<typename T, typename S>
struct m_if<false, T, S> {
    typedef S result_type;
    typedef T not_result_type;
};

// 逻辑运算 and
template<bool ...value>
struct m_and;

template<bool first,bool ...value>
struct m_and<first, value...> {
    typedef m_and<value...> __next_type;
    constexpr static bool result = first && __next_type::result;
};

template<>
struct m_and<> {
    constexpr static bool result = true;
};

// 逻辑运算 or
template<bool ...value>
struct m_or;

template<bool first,bool ...value>
struct m_or<first, value...> {
    typedef m_or<value...> __next_type;
    constexpr static bool result = first || __next_type::result;
};

template<>
struct m_or<> {
    constexpr static bool result = false;
};

// 逻辑运算 not
template<bool value>
struct m_not {
    constexpr static bool result = !value;
};


// 数据结构定义
template<int ...>
struct mvector;

template<int ...data, int _head>
struct mvector<_head, data...> {
    constexpr static int head = _head; 
    typedef mvector<_head> head_type;
    typedef mvector<data...> tail_type;
    constexpr static std::array<int, 1 + sizeof...(data)> value = {_head, data...};
    constexpr static size_t size = sizeof...(data) + 1;
};

template<int _head>
struct mvector<_head> {
    constexpr static int head = _head; 
    typedef mvector<_head> head_type;
    typedef mvector<> tail_type;
    constexpr static std::array<int, 1> value = {_head};
    constexpr static size_t size = 1;
};

template<>
struct mvector<> {
    constexpr static int head = -1;
    typedef mvector<> head_type;
    typedef mvector<> tail_type;
    constexpr static std::array<int, 0> value = {};
    constexpr static size_t size = 0;
};


// 对比两个元素
template<typename T, typename S>
struct mvector_cmp{
    constexpr static bool result = T::head >= S::head; // 使用等于，防止两个子节点相等时出现问题
};

// 在数组前增加一个元素
template<int data, typename list>
struct mvector_push_front;

template<int data, int ...data_list>
struct mvector_push_front<data, mvector<data_list...>> {
    typedef mvector<data, data_list...> result_type;
};

// 合并多个个数组
template<typename ...T>
struct mvector_merge;

template<typename T1, typename ...T>
struct mvector_merge<T1, T...> {
    typedef mvector_merge<T...> __next_type;
    typedef typename mvector_merge<T1, typename __next_type::result_type>::result_type result_type;
};

template<int ...dataa, int ...datab>
struct mvector_merge<mvector<dataa...>, mvector<datab...>> {
    typedef mvector<dataa..., datab...> result_type;
};

template<typename T>
struct mvector_merge<T> {
    typedef T result_type;
};

template<>
struct mvector_merge<> {
    typedef mvector<> result_type;
};

// 将数组分成两块
template<typename T, int a>
struct mvector_split{
    typedef mvector_split<typename T::tail_type, a - 1> __next_type;
    typedef typename __next_type::tail_type tail_type;
    typedef typename __next_type::value_type value_type;
    typedef typename mvector_merge<typename T::head_type, typename __next_type::front_type>::result_type front_type;
};

template<typename T>
struct mvector_split<T, 0> {
    typedef typename T::tail_type tail_type;
    typedef typename T::head_type value_type;
    typedef mvector<> front_type;
};

template<int a>
struct mvector_split<mvector<>, a> {
    typedef mvector<> tail_type;
    typedef mvector<> value_type;
    typedef mvector<> front_type;
};

template<>
struct mvector_split<mvector<>, 0> {
    typedef mvector<> tail_type;
    typedef mvector<> value_type;
    typedef mvector<> front_type;
};

// 交换元素 实际
template<bool, typename T, int a, int b>
struct __mvector_swap;

// 如果不满足要求，则直接返回原数组
template<typename T, int a, int b>
struct __mvector_swap<false, T, a, b> {
    typedef T result_type;
};

template<typename T, int a, int b>
struct __mvector_swap<true, T, a, b> {
    typedef mvector_split<T, a> __first_split;
    typedef mvector_split<typename __first_split::tail_type, b - a - 1> __second_split;
    typedef typename mvector_merge<
        typename __first_split::front_type, 
        typename __second_split::value_type, 
        typename __second_split::front_type,
        typename __first_split::value_type,
        typename __second_split::tail_type
    >::result_type result_type;
};

// 交换元素
template<typename T, int a, int b>
struct mvector_swap {
    constexpr static bool valid = m_and<(a > b), (a >= 0), (b < T::size)>::result;
    typedef __mvector_swap<valid, T, a, b> __next_type;
    typedef typename __next_type::result_type result_type;
};

// 维护堆
template<bool valid, typename T, int begin>
struct __max_heapify;

template<typename T, int begin>
struct __max_heapify<false, T, begin> {
    typedef T result_type;
};

template<typename T, int begin>
struct __max_heapify<true, T, begin> {
    constexpr static int right = begin * 2 + 1;
    constexpr static int left = begin * 2 + 2;
    
    typedef typename mvector_split<T, right>::value_type right_type;
    typedef typename mvector_split<T, left>::value_type left_type;
    typedef typename mvector_split<T, begin>::value_type parent_type;
    
    constexpr static bool right_valid = m_and<(right < T::size), mvector_cmp<right_type, parent_type>::result, mvector_cmp<right_type, left_type>::result>::result;
    constexpr static bool left_valid = m_and<(left < T::size), mvector_cmp<left_type, parent_type>::result, mvector_cmp<left_type, right_type>::result>::result;
    typedef typename __mvector_swap<right_valid, T, begin, right>::result_type right_swaped_type;
    typedef typename __mvector_swap<left_valid, T, begin, left>::result_type left_swaped_type;
    
    typedef typename __max_heapify<right_valid, right_swaped_type, right>::result_type __right_next_type;
    typedef typename __max_heapify<left_valid, left_swaped_type, left>::result_type __left_next_type;
    typedef typename m_if<right_valid, __right_next_type, __left_next_type>::result_type result_type;
    //typename m_assert_print<m_or<begin != 0, T::size != 3>::result, result_type>::result_type non_data;
};

template<typename T>
struct max_heapify {
    typedef __max_heapify<(T::size > 0), T, 0> __work_type;
    typedef typename __work_type::result_type result_type;
};

// 对原始数组进行建堆
template<typename T>
struct setup_heap {
    typedef setup_heap<typename T::tail_type> __next_type;
    typedef typename max_heapify<typename mvector_merge<typename T::head_type, typename __next_type::result_type>::result_type>::result_type result_type;
};

template<>
struct setup_heap<mvector<>> {
    typedef mvector<> result_type;
};

// 对建好堆的数组进行排序
template<typename T>
struct seted_heap_sort {
    typedef mvector_split<T, T::size - 1> last_node_type;
    typedef typename mvector_merge<typename last_node_type::value_type, typename last_node_type::front_type::tail_type>::result_type swaped_tail_type;

    typedef seted_heap_sort<typename max_heapify<swaped_tail_type>::result_type> __next_type;
    typedef typename mvector_merge<typename T::head_type, typename __next_type::result_type>::result_type result_type;
};

template<int data>
struct seted_heap_sort<mvector<data>> {
    typedef mvector<data> result_type;
};

template<>
struct seted_heap_sort<mvector<>> {
    typedef mvector<> result_type;
};

// 排序
template<typename in_vector>
struct heap_sort {
    typedef typename setup_heap<in_vector>::result_type heap_type;
    typedef typename seted_heap_sort<heap_type>::result_type result_type;
};

constexpr static std::array<int, 8> result =  heap_sort<mvector<1, 123, 4, 31, 12, 4, 56, 8>>::result_type::value;

int main() {
    for (int loop_i = 0; loop_i < result.size(); ++loop_i) {
        std::cout << result[loop_i] << ",";
    }
    std::cout << std::endl;
    return 0;
}