#include <iostream>
#include <vector>
#include <algorithm>

#include "partition_3area.hpp"

void quick_select(std::vector<PairTypeFloat>& arr,size_t low,size_t high, size_t target_index) {

    size_t nlow = low;
    size_t nhigh = high;
    size_t tmp_pivot_index = low + (nhigh - nlow) / 2; //なにかしらpivotを決める

    // pivotでパーティション
    PartitionFuncFloat cond(arr, tmp_pivot_index);
    std::array<int64_t, 3> ret= partition_3area(arr, nlow, nhigh, cond);

    nlow = ret[0]; // 左側開始位置
    size_t newpivot = ret[1]; // 処理後のpivotの位置
    nhigh = ret[2]; // 右側終了位置

    // [nlow～newpivot-1][newpivot][newpivot+1～nhigh] に分割される
    // このとき、
    if (newpivot == target_index) {
        // [nlow～newpivot-1][target_index][newpivot+1～nhigh] であれば、
        // target_indexの要素番号のデータはtarget_index番目の要素になっている
        return ;
    }
    else if (target_index < newpivot) {
        // [target_indexを含む][newpivot][newpivot+1～nhigh] であれば、
        // 左側を処理
        quick_select(arr, nlow, newpivot, target_index);
    }
    else {
        // [nlow～newpivot-1][newpivot][target_indexを含む] であれば、
        // 右側を処理
        quick_select(arr, newpivot+1, nhigh, target_index);
    }

}

int main()
{
    std::vector<PairTypeFloat> arr;

    arr.push_back(std::make_pair(3.7, "a"));
    arr.push_back(std::make_pair(2.3, "b"));
    arr.push_back(std::make_pair(7.5, "c"));
    arr.push_back(std::make_pair(1.2, "d"));
    arr.push_back(std::make_pair(6.8, "e"));
    arr.push_back(std::make_pair(5.6, "f"));
    arr.push_back(std::make_pair(2.4, "g"));
    arr.push_back(std::make_pair(0.9, "h"));
    arr.push_back(std::make_pair(6.1, "i"));
    arr.push_back(std::make_pair(5.8, "j"));// 
    arr.push_back(std::make_pair(4.5, "k"));
    arr.push_back(std::make_pair(8.2, "l"));
    arr.push_back(std::make_pair(9.1, "m"));
    arr.push_back(std::make_pair(1.7, "n"));
    arr.push_back(std::make_pair(5.3, "o"));
    arr.push_back(std::make_pair(7.7, "p"));
    arr.push_back(std::make_pair(3.8, "q"));
    arr.push_back(std::make_pair(4.2, "r"));

    std::cout << "処理前の配列: " << std::endl;
    for (size_t i = 0; i < arr.size(); i++) {
        std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl;
    }

    size_t target_index = arr.size() / 2;
    std::cout << target_index << "番目の要素: " << arr[target_index].first << " " << arr[target_index].second << std::endl;

    quick_select(arr, 0, arr.size(), target_index);// 中央値を求める

    std::cout << "--------------------------------------------" << std::endl;
    std::cout << "処理後の配列: " << std::endl;
    for (size_t i = 0; i < arr.size(); i++) {
        std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl;
    }

    std::cout << target_index << "番目の要素: " << arr[target_index].first << " " << arr[target_index].second << std::endl;

    std::cout << "--------------------------------------------" << std::endl;
    std::cout << "ソート結果: " << std::endl;

    arr.clear();
    arr.push_back(std::make_pair(3.7, "a"));
    arr.push_back(std::make_pair(2.3, "b"));
    arr.push_back(std::make_pair(7.5, "c"));
    arr.push_back(std::make_pair(1.2, "d"));
    arr.push_back(std::make_pair(6.8, "e"));
    arr.push_back(std::make_pair(5.6, "f"));
    arr.push_back(std::make_pair(2.4, "g"));
    arr.push_back(std::make_pair(0.9, "h"));
    arr.push_back(std::make_pair(6.1, "i"));
    arr.push_back(std::make_pair(5.8, "j")); //
    arr.push_back(std::make_pair(4.5, "k"));
    arr.push_back(std::make_pair(8.2, "l"));
    arr.push_back(std::make_pair(9.1, "m"));
    arr.push_back(std::make_pair(1.7, "n"));
    arr.push_back(std::make_pair(5.3, "o"));
    arr.push_back(std::make_pair(7.7, "p"));
    arr.push_back(std::make_pair(3.8, "q"));
    arr.push_back(std::make_pair(4.2, "r"));

    std::sort(arr.begin(), arr.end(), [](const PairTypeFloat& a, const PairTypeFloat& b) {return a.first < b.first; });
    for (size_t i = 0; i < arr.size(); i++) {
        std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl;
    }


}