/**
 *  @file   backet_sort.h
 *  @brief  バケット(ビン)ソート
 *  @note
 *  -   範囲は一応0x10000としているが、スタックにバケットを置くので注意.
 *  -   実体の並べ直しのためにソート対象の個数分のバッファをnew[]している.
 */
#ifndef BACKET_SORT_H
#define BACKET_SORT_H

#include <cstddef>
#include <functional>
#include <algorithm>


/** バケット(ビン)ソート. srcからsizeの範囲をソート. Tは整数型で値は[minVal,maxVal]の範囲であること.
 */
template <typename T>
void backet_sort_copy(const T* src, std::size_t size, const T& minVal, const T& maxVal, T* dst)
{
    using std::swap;
    assert(maxVal+1 - minVal <= 0x10000);
    assert(dst != NULL);

    if (size < 2) {
        if (size == 1)
            dst[0] = src[0];
        return;
    }

    const unsigned  backet_size = unsigned(maxVal+1 - minVal);
    std::size_t*    ofs         = (std::size_t*) alloca( backet_size * sizeof(std::size_t) );

    for (unsigned i = 0; i < backet_size; ++i) {
        ofs[i]  = 0;
    }
    const T*    src_end = src + size;
    const T*    s       = src;
    do {
        ++ofs[ *s - minVal ];
    } while (++s != src_end);   // it != last

    for (unsigned i = 1; i < backet_size; ++i) {
        ofs[i] += ofs[i - 1];
    }

    s = src_end;
    do {
        --s;
        std::size_t j = --ofs[ *s - minVal ];
        dst[j]        = *s;
    } while (s != src);
}



namespace backet_sort_detail {  // backet_sort 内部で使う. 他は使っちゃ駄目.
    template <typename VALUE_TYPE >
    struct backet_sort_value_buffer {   // メモリー開放用にクラス化.
        backet_sort_value_buffer() : ptr_(0) {}
        ~backet_sort_value_buffer() { delete[] ptr_; }
        VALUE_TYPE*     ptr_;
    };
};



/** バケット(ビン)ソート. dataからsizeの範囲をソート. Tは整数型で値は[minVal,maxVal]の範囲であること.
 *  並べ替え用のバッファをnew[]で確保する.
 */
template <typename T> inline
void backet_sort(T* data, std::size_t size, const T& minVal, const T& maxVal)
{
    backet_sort_detail::backet_sort_value_buffer<T> work;
    work.ptr_ = new T[ size ];
    std::copy(data, data+size, work.ptr_);
    backet_sort_copy(work.ptr_, size, minVal, maxVal, data);
}


#endif  // BACKET_SORT_H