/**
 *  @file   radix_sort.h
 *  @brief  基数ソート
 *  @note
 *  -   結局、こちらのページ
 *          http://www.moon.sannet.ne.jp/okahisa/sort/node26.html
 *      のソースを変形したもの.
 *  -   基数は 256(8bit) を想定.
 *      スタックに 256〜2KBytesのバッファを取ることになる.
 *  -   実体の並べ直しのためにソート対象の個数分のバッファをnew[]している.
 */
#ifndef RADIX_SORT_H
#define RADIX_SORT_H

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

// ----------------------------------------------------------------------------
/// VALクラスの先頭から ofs バイト目からを UINT_TYPE型として値を取得.
template<typename UINT_TYPE, class VAL, unsigned ofs = 0>
struct radix_sort_ofsaddr_getkey : public std::unary_function<VAL, UINT_TYPE> {
    UINT_TYPE   operator()(const VAL& v) const {
        return *(const UINT_TYPE*)((const char*)&v + ofs);
    }
};


/// cls_typeクラスのメンバー名memb のアドレスから強制的に uint_type 型の値として値を取得.
#define RADIX_SORT_MEMBER_GETKEY(uint_type,cls_type,memb)   radix_sort_ofsaddr_getkey< uint_type,cls_type,offsetof(cls_type, memb) >()



// ----------------------------------------------------------------------------

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



// ----------------------------------------------------------------------------

/** 基数ソート. dataからsizeの範囲をgetkeyで符号無整数化した値を元にソートする.
 *  buf は、並べ替えのためにfirst, last の範囲を収められる配列であること.
 */
template <unsigned RADIX_BITS, typename T, class GETKEY>
void radix_sort_with_buf(T* data, std::size_t size, GETKEY getkey, T* buf, std::size_t buf_size)
{
    using std::swap;
    assert(buf_size >= size);
    if (size < 2) {
        return;
    }

    typedef typename GETKEY::result_type    key_type;

    // UINT_TYPEが符号無整数型であるかをチェック. static_assert の代わり...
    typedef char    static_check_cond[ key_type(~0) > 0 ? 1 : -1 ];
    enum { STATIC_ASSERT_CHECK = sizeof( static_check_cond ) };

    enum { KEY_BITS         = sizeof(key_type) * 8 };
    enum { RADIX_SIZE       = 1 << RADIX_BITS };
    enum { RADIX_MASK       = RADIX_SIZE - 1    };

    assert(buf != NULL);
    std::size_t ofs[ RADIX_SIZE ];

    T*  src     = data;
    T*  dst     = buf;
    T*  src_end = src + size;
    for (unsigned  sh = 0; sh < KEY_BITS; sh += RADIX_BITS) {
        for (unsigned i = 0; i < RADIX_SIZE; ++i) {
            ofs[i] = 0;
        }
        bool    done = 1;
        T*      s    = src;
        do {
            key_type k    = getkey(*s) >> sh;
            if (k > 0)          // done &= (k <= 0);
                done = 0;
            ++ofs[k & RADIX_MASK];
        } while (++s != src_end);   // it != last

        if (done) {
            break;
        }

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

        s = src_end;
        do {
            --s;
            std::size_t j = --ofs[(getkey(*s) >> sh) & RADIX_MASK];
            dst[j]        = *s;
        } while (s != src);
        swap(src, dst);
        src_end = src + size;
    }

    // data 側がsrcになっていないなら、ソート済みデータはbuf側にあるのでコピー.
    if (data == dst) {
        std::copy(src, src_end, dst);
    }
}



/** 基数ソート. dataからsizeの範囲をgetkeyで符号無整数化した値を元にソートする.
 *  並べ替え用のバッファをnew[]で確保する.
 */
template <unsigned RADIX_BITS, typename T, class GETKEY>
void radix_sort(T* data, std::size_t size, GETKEY getkey)
{
    radix_sort_detail::radix_sort_value_buffer<T>   work;
    work.ptr_ = new T[ size ];
    radix_sort_with_buf<RADIX_BITS>(data, size, getkey, work.ptr_, size);
}



#endif  // RADIX_SORT_H