/**
 *  @file sort_etc.h
 *  @brief  各種ソートルーチン. size個の配列を対象.
 */

#ifndef SORT_ETC_H
#define SORT_ETC_H

#include <cstddef>
#include <algorithm>

using std::swap;

/// バブル・ソート
template<typename T, class C>
void bubble_sort(T* data, size_t size, C cmp) {
    size_t  i, j;
    for (i = 0; i < size-1; ++i) {
        for (j = size; --j > i;) {
            if (cmp(data[j], data[j-1]))
                swap(data[j], data[j-1]);
        }
    }
}


/// 選択ソート
template<typename T, class C>
void selection_sort(T* data, size_t size, C cmp) {
    size_t  i, j;
    for (i = 0; i < size; ++i) {
        size_t  min = i;
        for (j = i+1; j < size; ++j) {
            if (cmp(data[j], data[min]))
                min = j;
        }
        swap(data[i], data[min]) ;
    }
}


/// 挿入ソート
template<typename T, class C>
void insertion_sort(T* data, size_t size, C cmp) {
    size_t  i, j;
    for (i = 1; i < size; ++i) {
        T   tmp = data[i];
        for (j = i; j > 0 && cmp(tmp, data[j-1]); --j)
            data[j] = data[j-1];
        data[j] = tmp;
    }
}



/// 挿入ソート (やなう版).  ※ 代入が1回減る可能性が高まる代わりに比較が1回増える.
template<typename T, class C>
void insertion_sort_y(T* data, size_t size, C cmp) {
    size_t i, j;
    for (i = 1; i < size; i++) {
        T tmp = data[i];
        if (cmp(tmp, data[i-1])) {
            j = i;
            do {
                data[j] = data[j-1];
                --j;
            } while ( j > 0 && cmp(tmp, data[j-1]));
            data[j] = tmp;
        }
    }
}


/// 挿入ソート (やなう版 改変) ※ 比較回数を増やさないように修正…がプログラムが複雑にorz.
template<typename T, class C>
void insertion_sort_y_mod(T* data, size_t size, C cmp) {
    size_t i = 0;
    for (;;) {
        size_t k = i;
        if (++i >= size)
            return;
        if (cmp(data[i], data[k])) {
            size_t j   = i;
            T   tmp = data[i];
            goto JJJ;
            do {
                --k;
                if (!(cmp(tmp, data[k])))
                    break;
          JJJ:
                data[j] = data[k];
                --j;
            } while (k);
            data[j] = tmp;
        }
    }
}


/// シェル・ソート
template<typename T, class C>
void shell_sort(T* data, size_t size, C cmp) {
    size_t  h, i, j;
    for (h = 1; h < size / 9; h = h * 3 + 1)
        ;
    for (; h > 0; h /= 3) {
        for (i = h; i < size; i++) {
            for (j = i; j >= h && cmp(data[j], data[j - h]); j -= h) {
                swap(data[j], data[j - h]);
            }
        }
    }
}


/// コム・ソート
template<typename T, class C>
void comb_sort(T* data, size_t size, C cmp) {
    size_t h    = size * 10 / 13;
    for (;;) {
        int     swapFlag = 0;
        size_t  i        = 0;
        for (i = 0; i + h < size; ++i) {
            if (cmp(data[i + h], data[i])) {
                swap(data[i + h], data[i]);
                swapFlag = 1;
            }
        }
        if (h <= 1) {
            if (!swapFlag)
                break;
        } else {
            h = h * 10 / 13;
        }
    }
}


/// コム・ソート11
template<typename T, class C>
void comb_sort11(T* data, size_t size, C cmp) {
    size_t      h       = size * 10 / 13;
    for (;;) {
        size_t  i;
        int     swapFlag = 0;
        for (i = 0; i + h < size; ++i) {
            if (cmp(data[i + h], data[i])) {
                swap(data[i + h], data[i]);
                swapFlag = 1;
            }
        }
        if (h <= 1) {
            if (!swapFlag)
                break;
        } else if ((h == 9) | (h == 10)) {
            h = 11;
        } else {
            h = h * 10 / 13;
        }
    }
}



/// 工夫なしのquickソート.
template<typename T, class C>
void simple_quick_sort(T* data, size_t size, C cmp) {
    T  m;
    T *l, *r, *e;
    if (size <= 1)
        return;
    m = data[size / 2];
    l = data;
    e = data + size;
    r = e - 1;
    for (;;) {
        while (cmp(*l, m))
            ++l;
        while (cmp(m, *r))
            --r;
        if (l >= r)
            break;
        swap(*l, *r);
        ++l;
    }
    simple_quick_sort(data, l - data, cmp);
    simple_quick_sort(l  , e - l    , cmp);
}



#ifdef USE_QSORT
#include <stdlib.h>

/// qsort用の比較関数. 比較は実体に対する < のみ.
template<typename T>
struct qsort_cmp {
    static int cmp(const void* a0, const void* b0) {
        const T* a = (const T* )a0;
        const T* b = (const T* )b0;
      #if 0 //defined QSORT_INT  // 正数の時くらい...
        return *a - *b;
      #else
        if (*a < *b)
            return -1;
        else if (*b < *a)
            return 1;
        return 0;
      #endif
    }
};

/// Cライブラリの qsort を使った場合. ※ 比較ファンクタは無視なので注意.
template<typename T, class C>
void c_qsort(T* data, size_t size, C) {
    qsort(data, size, sizeof(T), &qsort_cmp<T>::cmp);
}
#endif

#endif