#include <iostream>
#include <vector>

#include "insertion_sort.h"

int main()
{
    int data[]={5,7,4,2,8,6,1,9,0,3};
    //auto p= upper_bound(data,data+(sizeof(data)/ sizeof(int)),6);
    //std::cout<<*p<<" : "<<*(p+1)<<"\n";
    for (auto &value : data)
        std::cout<<value<<" ";
    std::cout<<"\n";
    Csz_stl::insertion_sort(std::begin(data),std::end(data));
    for (auto &value : data)
        std::cout<<value<<" ";
    std::cout<<"\n";
    return 0;
}

//复杂度 N^2

namespace Csz_stl
{
    //有序,寻找比value大的值
    //二分查找
    template<class ForwardIt,typename Value>
    ForwardIt upper_bound(ForwardIt T_first,ForwardIt T_last,const Value &T_value)
    {
        //count共有多少个element，step每次前进的距离
        typename std::iterator_traits<ForwardIt>::difference_type count,step;
        count= std::distance(T_first,T_last);
        if (count<= 0)
            return T_last;
        while (count> 0)
        {
            auto mid= T_first;
            step= count/ 2;
            std::advance(mid,step);
            if (!(*mid> T_value))
            {
                T_first= std::move(++mid);
                count-= step+ 1;
            }
            else
            {
                count= step;
            }
        }
        return T_first;
    }
    //旋转
    template<class ForwardIt>
    ForwardIt rotate(ForwardIt T_first,ForwardIt n_first,ForwardIt T_last)
    {
        if (T_first== n_first)
            return T_last;
        if (T_last== n_first)
            return T_first;
        auto temp= n_first;
        do
        {
            std::iter_swap(T_first,temp);
            ++T_first;
            ++temp;
            //前短后长，重新定位旋转点
            if (T_first== n_first)
                n_first= temp;
        }while (temp!= T_last);
        //旋转完全后，后半段的第一个element
        auto ret= T_first;
        for (temp= n_first; temp!= T_last;)
        {
            std::iter_swap(T_first,temp);
            ++temp;
            ++T_first;
            //前短后长，重新定位旋转点
            if (T_first== n_first)
                n_first= temp;
            //当旋转点到达T_last时，T_first也同时到达T_last- 1
            //T_first+ 1== n_first== temp== T_last
            else if (temp== T_last)
                temp= n_first;
        }
        return ret;
    }
    //插入排序
    template<class ForwardIt>
    void insertion_sort(ForwardIt T_first,ForwardIt T_last)
    {
        if (T_first== T_last)
            return ;
        auto next= T_first;
        ++next;
        while (next!= T_last)
        {
            //寻找[T_first,next)中比*next更大的element
            rotate(upper_bound(T_first,next,*next),next,next+1);
            ++next;
        }
    }
}

#include <iostream>

#include "quick_sort.h"

int main()
{
    int data[]={1,30,-4,3,5,-4,1,6,-8,2,-5,64,1,92};
    for (auto &value : data)
        std::cout<<value<<" ";
    std::cout<<"\n";
    Csz_stl::quick_sort(std::begin(data),std::end(data));
    for (auto &value : data)
        std::cout<<value<<" ";
    std::cout<<"\n";
    return 0;
}

//复杂度 平均复杂度NlogN 最坏情况N^2

namespace Csz_stl
{
    //复杂度distance(T_first,T_last)线性，寻找第一个不符合条件的变量，
    //若没有则返回T_last
    template<class ForwardIt,class UnaryPredicate>
    ForwardIt find_if_not(ForwardIt T_first,ForwardIt T_last,UnaryPredicate T_unary_pred)
    {
        if (T_first== T_last)
            return T_last;
        while (T_first!= T_last)
        {
            if (!T_unary_pred(*T_first))
                return T_first;
            ++T_first;
        }
        return T_last;
    }
    //复杂度distance(T_first,T_last)线性,将符合条件的element在左边，
    //不符合条件的element在右边，切记判断find_if_not返回值，若没判断
    //可能会越界(++next)
    template<class ForwardIt,class UnaryPredicate>
    ForwardIt partition(ForwardIt T_first,ForwardIt T_last,UnaryPredicate T_unary_pred)
    {
        T_first= find_if_not(T_first,T_last,T_unary_pred);
        if (T_first== T_last)
            return T_last;
        auto next= T_first;
        ++next;
        while (next!= T_last)
        {
            if (T_unary_pred(*next))
            {
                std::iter_swap(T_first,next);
                ++T_first;
            }
            ++next;
        }
        return T_first;
    }
    template<class ForwardIt>
    void quick_sort(ForwardIt T_first,ForwardIt T_last)
    {
        if (T_first== T_last)
            return ;
        //取中间值
        auto value= http://www.mamicode.com/*(std::next(T_first,std::distance(T_first,T_last)/ 2));
        //分割
        auto middle1= partition(T_first,T_last,[value](const typename std::iterator_traits<ForwardIt>::value_type &T_val){return T_val< value;});
        //将等值element已到左边，这时候中间出现了一部分已经排序完成的element
        auto middle2= partition(middle1,T_last,[value](const typename std::iterator_traits<ForwardIt>::value_type &T_val){return !(T_val> value);});
        //[middle1,middle2)已排序完成
        quick_sort(T_first,middle1);
        quick_sort(middle2,T_last);
    }
}