// Sigue quickselect con el primer elemento como pivote, vuelta por vuelta.
#include <cstddef>
#include <iostream>
#include <vector>

#include "select.h"

static void print(const std::vector<int>& v) {
    std::cout << "[";
    for (std::size_t i = 0; i < v.size(); i++) {
        std::cout << (i == 0 ? "" : " ") << v[i];
    }
    std::cout << "]";
}

int main() {
    std::vector<int> a = {6, 3, 9, 1, 7, 2, 8, 5, 4};
    std::size_t k = 4;
    long long comparisons = 0;
    while (true) {
        std::cout << "k = " << k << "  A = ";
        print(a);
        std::cout << "\n";
        if (a.size() == 1) {
            std::cout << "  un solo elemento: respuesta " << a[0] << "\n";
            break;
        }
        int pivot = a[0];
        Parts parts = partition3(a, pivot, comparisons);
        std::cout << "  pivote " << pivot << "  menores ";
        print(parts.less);
        std::cout << "  iguales ";
        print(parts.equal);
        std::cout << "  mayores ";
        print(parts.greater);
        std::cout << "\n";
        if (k < parts.less.size()) {
            a = parts.less;
        } else if (k < parts.less.size() + parts.equal.size()) {
            std::cout << "  k cae en los iguales: respuesta " << pivot << "\n";
            break;
        } else {
            k -= parts.less.size() + parts.equal.size();
            a = parts.greater;
        }
    }
    std::cout << comparisons << " comparaciones\n\n";

    std::cout << "arreglo ordenado, k = n - 1, primer elemento como pivote\n";
    std::cout << "        n   comparaciones   n(n+1)/2 - 1\n";
    for (long long n = 1000; n <= 8000; n *= 2) {
        std::vector<int> sorted(n);
        for (long long i = 0; i < n; i++) {
            sorted[i] = static_cast<int>(i);
        }
        long long count = 0;
        quickselect_first(sorted, n - 1, count);
        std::cout.width(9);
        std::cout << n;
        std::cout.width(16);
        std::cout << count;
        std::cout.width(15);
        std::cout << n * (n + 1) / 2 - 1 << "\n";
    }
}