// Sigue una vuelta de la mediana de medianas con 23 elementos: grupos, medianas, pivote y conteos.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

#include "select.h"

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

// Sigue select_linear: una línea por llamada, sin entrar en la búsqueda de cada pivote.
static int trace_select(std::vector<int> a, std::size_t k) {
    long long ignored = 0;
    std::cout << "|A| = " << a.size() << ", k = " << k;
    if (a.size() <= 5) {
        std::sort(a.begin(), a.end());
        std::cout << ": se ordena [";
        print(a);
        std::cout << "] y la respuesta es " << a[k] << "\n";
        return a[k];
    }
    int pivot = median_of_medians(a, ignored);
    Parts parts = partition3(a, pivot, ignored);
    std::cout << ": pivote " << pivot << ", |L| = " << parts.less.size() << ", |E| = " << parts.equal.size()
              << ", |G| = " << parts.greater.size() << "\n";
    if (k < parts.less.size()) {
        return trace_select(parts.less, k);
    }
    if (k < parts.less.size() + parts.equal.size()) {
        std::cout << "k cae en E: la respuesta es " << pivot << "\n";
        return pivot;
    }
    return trace_select(parts.greater, k - parts.less.size() - parts.equal.size());
}

int main() {
    std::vector<int> a = {12, 3, 25, 8, 17, 40, 6, 31, 22, 9, 15, 37, 1, 28, 19, 44, 11, 33, 5, 26, 14, 30, 2};
    long long comparisons = 0;
    std::cout << "n = " << a.size() << "\n";
    for (std::size_t start = 0; start < a.size(); start += 5) {
        std::size_t stop = std::min(start + 5, a.size());
        std::vector<int> group(a.begin() + start, a.begin() + stop);
        std::cout << "grupo: ";
        print(group);
        sort_group(group, comparisons);
        std::cout << "  ordenado: ";
        print(group);
        std::cout << "  mediana: " << group[(group.size() - 1) / 2] << "\n";
    }
    comparisons = 0;
    std::vector<int> medians = group_medians(a, comparisons);
    std::cout << "medianas: ";
    print(medians);
    std::cout << "\n";
    int pivot = median_of_medians(a, comparisons);
    std::cout << "pivote (mediana inferior de las medianas): " << pivot << "\n";
    auto at_most = std::count_if(a.begin(), a.end(), [&](int x) { return x <= pivot; });
    auto at_least = std::count_if(a.begin(), a.end(), [&](int x) { return x >= pivot; });
    std::cout << "elementos <= pivote: " << at_most << "\n";
    std::cout << "elementos >= pivote: " << at_least << "\n";
    std::cout << "cota 3n/10 - 3: " << 3.0 * static_cast<double>(a.size()) / 10 - 3 << "\n";
    long long ignored = 0;
    Parts parts = partition3(a, pivot, ignored);
    std::cout << "menores: " << parts.less.size() << "  iguales: " << parts.equal.size()
              << "  mayores: " << parts.greater.size() << "\n";
    std::cout << "cota 7n/10 + 3: " << 7.0 * static_cast<double>(a.size()) / 10 + 3 << "\n";

    std::cout << "\nla mediana, k = 11\n";
    int answer = trace_select(a, 11);
    std::vector<int> sorted = a;
    std::sort(sorted.begin(), sorted.end());
    std::cout << "ordenando, la posicion 11 es " << sorted[11] << "; la funcion dio " << answer << "\n";
}