#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <cassert>

using namespace std;

template<class T>
struct LinkNode
{
   LinkNode() = default;
   LinkNode(const T& t):m_data(t){}
   T m_data{0};
   LinkNode<T>* m_next{nullptr};
};

template<class T>
class LinkList
{
public:
    LinkList();
    ~LinkList();
    int length() const;
    void append(const T& t);
    void merge(const LinkList<T>& list);
    void show() const;
    void clear();
public:
    LinkNode<T> *m_head{nullptr};
};

template<class T>
LinkList<T>::LinkList()
{
    m_head = new LinkNode<T>();
}

template<class T>
LinkList<T>::~LinkList()
{
    LinkNode<T> *n{nullptr};
    while(m_head)
    {
        n = m_head;
        m_head = m_head->m_next;
        delete n;
    }
    m_head = nullptr;
}

template<class T>
void LinkList<T>::clear()
{
    LinkNode<T>* t = m_head->m_next,*t1{nullptr};
    while(t)
    {
       t1 = t;
       t = t->m_next; 
       delete t1;
    }
    m_head->m_next = nullptr;
}

template<class T>
void LinkList<T>::append(const T& v)
{
    LinkNode<T> *t = m_head;
    while(t && t->m_next)
    {
        t = t->m_next;
    }

    t->m_next = new LinkNode<T>(v);
}

template<class T>
int LinkList<T>::length() const
{
    LinkNode<T> *t = m_head->m_next;
    int n{0};
    while(t)
    {
        n++;
        t = t->m_next;
    }
    return n;
}

template<class T>
void LinkList<T>::show() const
{
   LinkNode<T> *t = m_head->m_next;
   while(t)
   {
       cout<<t->m_data<<","; 
       t = t->m_next;
   }
   cout<<endl;
}

template<class T>
void LinkList<T>::merge(const LinkList<T>& list)
{
    LinkNode<T> *t = list.m_head->m_next;
    while(t)
    {
        append(t->m_data);
        t = t->m_next;
    }
}

//===================================
class Bucket
{
public:
    int length() const { return m_list.length();}
    void setKey(int key){ m_key = key;}
    int key() const { return m_key;}
    void append(int n);
    void clear();
    void merge(const Bucket& b);
    void show() const;
    void copyToArray(int *array,int pos);
private:
    int m_key;
    LinkList<int> m_list;
};

void Bucket::copyToArray(int *array,int pos)
{
   LinkNode<int> *t = m_list.m_head->m_next;
   int k{0};
   while(t)
   {
        array[pos+k] = t->m_data;
        ++k;
        t = t->m_next;
   } 
}

void Bucket::append(int n)
{
    m_list.append(n);
    cout<<"["<<m_key<<"]"<<"桶里面现在有"<<m_list.length()<<" 个"<<endl;
}

void Bucket::clear()
{
    m_list.clear();
}

void Bucket::merge(const Bucket& b)
{
    m_list.merge(b.m_list);
}

void Bucket::show() const
{
    m_list.show();
}   

//================================================
void max_min(int *arr,int n,int &max,int &min)
{
    int minIndex{0},maxIndex{0};
    for(int i=1; i<n; ++i)
    {
        if(arr[minIndex] > arr[i])
            minIndex=i;
        if(arr[maxIndex] < arr[i])
            maxIndex=i;
    }

    max = arr[maxIndex];
    min = arr[minIndex];
}

/*!
桶排序的原则和排序扑克牌是一样的，
首先需要确定数据的范围，然后根据数据的范围
将所有的数据串起来,适合数据范围小的排序
1->9
10->J
11->Q
12->K
13->King
*/

void dumpPoker(int *arr,int & length)
{
    copy(arr,arr+length,ostream_iterator<int>(cout,","));
    cout<<endl;
}

void initPoker(int *&arr,int& length)
{
    length = 54;
    arr = new int[length];
    int k=0;
    for(int i=0; i<4; ++i)
        for(int j=0; j<13;j++)
            arr[k++] = j;
    arr[length-1]=arr[length-2] = 13;
    random_shuffle(arr,arr+length);
}

void checkPoker(int *arr,int length)
{
    for(int i=1; i<length; ++i)
    {
        if(arr[i-1] > arr[i])
        {
            cout<<"扑克牌无序"<<endl;
            assert(false);
            break;
        }
    }
}

void free(int *arr)
{
    delete []arr;
}

void bucket_sort(int *arr,int length)
{
    int min{0},max{0};
    max_min(arr,length,max,min);    
    int bucket_count{max-min+1};
    Bucket *brr = new Bucket[bucket_count];
    for(int i=min; i<=max;++i)
    {
        brr[i-min].setKey(i);
    }
    
    /*!
    将对应的数据放置到木桶中
    */
    for(int i=0; i<length; ++i)
    {
        brr[arr[i]-min].append(arr[i]);
    }

    Bucket r;
    for(int i=min; i<=max;++i)
    {
        r.merge(brr[i-min]);
    }

    r.show();
    
    /*!将木桶中的结果拷贝回去*/
    int pos{0},bucketcount{0};
    for(int i=0; i<bucket_count; ++i)
    {
        bucketcount = brr[i].length();
        if(bucketcount > 0)
        {
            brr[i].copyToArray(arr,pos);
            pos += bucketcount;
        }
    }
    
    cout<<"pos="<<pos<<" length="<<length<<endl;
    assert(pos == length);
    delete[] brr;
}


int main(int argc,char *argv[])
{
    int *poker{nullptr};
    int length{0};
    initPoker(poker,length);

    cout<<"原始数据"<<endl;
    dumpPoker(poker,length);
    bucket_sort(poker,length);
    cout<<"排序后"<<endl;
    dumpPoker(poker,length);
    checkPoker(poker,length);
    
    free(poker);
    return 0;
}