#ifndef _NANXING_SORT_BASIC_H_
#define _NANXING_SORT_BASIC_H_
#include"nanxing_operator_check.h"
#include"../nanxing_type_trait.h"
#include<type_traits>
#include<iostream>
#include<climits>
namespace nanxing{

    template<typename T>
    class sort           //这里的T类型必须是一个指针类型否则会报错
    {
    public:
        
        static_assert(NANXING_BASIC_OPERATOR_(T,index),"It cannot be indexed");      //检查T类型能否下标访问
        static_assert(NANXING_BASIC_OPERATOR_(T,compare_ptr),"The data pointed cannot compared");  //检查指向的数据能否比较大小
        static_assert(NANXING_BASIC_OPERATOR_(T,equal_ptr),"The data pointed cannot assign value");   //检查指向的数据能否相互赋值

        void operator()(T data,size_t size)       //默认的sort用快速排序
        {
            fast_sort(data,0,size-1);
        }

        static void  fast_sort(T data,size_t left,size_t right)           //快速排序
        {
            if(right<=left)
            {
                return;
            }
            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type middle;
            //选取最后一个数字作为枢纽元(如果不是最后一个就将枢纽元和right元素交换)
            int i=left;
            int j=right-1;
            middle;             
            if((right-left)<=3)            //当划分的长度小于3的时候用直接插入排序
            { 
                for(int i=left+1;i<=right;i++)
                {
                    for(int j=i;j>left;j--)
                    {
                        if(data[j]<data[j-1])
                        {
                            middle=data[j];
                            data[j]=data[j-1];
                            data[j-1]=middle;
                        }
                    }
                }
                return;
            }
            for(;;)
            {
                while(data[i]<=data[right]&&i<right){i++;}
                while(data[j]>data[right]&&j>left){j--;}                 //注意书上的例程没有考虑一种非常特殊的情况即在ij同时等于枢纽元
                if(i<j)
                {                
                    middle=data[i];
                    data[i]=data[j];
                    data[j]=middle;
                }
                
                else
                {
                    break;
                }
            }
            middle=data[i];
            data[i]=data[right];
            data[right]=middle;
            fast_sort(data,left,i-1);
            fast_sort(data,i+1,right);
            
        }

        static void bubble_sort(T data,size_t size)          //冒泡排序
        {

            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type middle;
            
            for(int i=0;i<size;size--)
            {
                for(int j=i;j<size-1;j++)
                {
                    if(data[j]>data[j+1])
                    {
                       middle =data[j+1];
                       data[j+1]=data[j];
                       data[j]=middle;
                    }
                }
            }
        }

        static void  strait_insert_sort(T data, size_t size)     //直接插入排序
        {
            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type middle;
            for(size_t i=1;i<size;i++)
            {
                for(int j=i;j>0;j--)
                {
                    if(data[j]<data[j-1])
                    {
                        middle=data[j];
                        data[j]=data[j-1];
                        data[j-1]=middle;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }


        static void select_sort(T data,size_t size)        //选择排序
        {
            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type min;
            ptr_type middle;
            int n=0;        
            for(int i=0;i<size;i++)
            {
                min=data[i];
                n=i;
                for(int j=i;j<size;j++)
                {
                    if(data[j]<min)
                    {
                        n=j;
                        min=data[j];
                    }
                }
                data[n]=data[i];
                data[i]=min;   
            }
        }




        static void heap_sort(T data,size_t size)         //堆排序
        {
            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type middle;    
            size_t middle_size=size;
            for(int i=static_cast<int>(middle_size/2-1);i>=0;i--)          //构建堆
            {
                build_heap(data,i,size);
            }
            for(size_t i=size-1;i>0;i--)
            {
                middle=data[0];
                data[0]=data[i];
                data[i]=middle;
                build_heap(data,0,i);
            }
        }

        static void  Hill_sort(T data,size_t jump,size_t size)        //希尔排序
        {
            using ptr_type=nanxing::remove_pointer<T>::type;
            ptr_type middle;    
            if(jump*2>=size-1)                    //如果跳跃的间隔过大就直接用直接插入排序
            {
                strait_insert_sort(data,size);  
                return;
            }
            for(int i=0;i<jump;i++)                    //分组做直接插入排序
            {
                for(int j=i+jump;j<size;j+=jump)
                {
                    for(int k=j;k>=jump;k-=jump)
                    {
                        if(data[k]<data[k-jump])
                        {
                            middle=data[k-jump];
                            data[k-jump]=data[k];
                            data[k]=middle;
                        }
                        else{
                            break;
                        }
                    }         
                }
            }
            strait_insert_sort(data,size);
        }

        static void Print(T data,size_t size)
        {
            for(int i=0;i<size-1;i++)
            {
                std::cout<<data[i]<<" "<<","<<" ";
            }
            std::cout<<data[size-1]<<std::endl;
        }

    private:
        static void build_heap(T data ,size_t S,size_t size)    //除了S之外的所有点都满足大顶堆的定义
        {
            using ptr_type=typename nanxing::remove_pointer<T>::type;
            ptr_type middle=data[S];
            int middle_s=S;
            for(int j=2*middle_s+1;j<=(size-1);j=j*2+1)    //这个是左孩子
            {
                if(j<size-1&&data[j]<data[j+1])          //注意这里的范围j<size-1,size是其中点的数量，但是下标从0开始的
                {
                    j++;
                }
                if(middle>data[j])
                {
                    break;
                }
                else{
                    data[middle_s]=data[j];
                    middle_s=j;
                }
            }
            data[middle_s]=middle;
        }

    private:
        unsigned int amount;
    };
}
#endif