// Tamaños de los rangos por nivel, con 16 elementos ya ordenados. Un punto es un rango de un elemento.
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

#include "quicksort.h"

namespace {

using Levels = std::map<int, std::vector<int>>;

void sizes(std::vector<int>& a, int lo, int hi, Pivot rule, std::mt19937& rng, int depth, Levels& levels) {
    if (hi - lo < 1) return;
    levels[depth].push_back(hi - lo);
    if (hi - lo < 2) return;
    choose_pivot(a, lo, hi, rule, rng);
    const int pivot = a[static_cast<std::size_t>(lo)];
    int p = lo;
    for (int i = lo + 1; i < hi; i++) {
        if (a[static_cast<std::size_t>(i)] < pivot) {
            p++;
            std::swap(a[static_cast<std::size_t>(i)], a[static_cast<std::size_t>(p)]);
        }
    }
    std::swap(a[static_cast<std::size_t>(lo)], a[static_cast<std::size_t>(p)]);
    sizes(a, lo, p, rule, rng, depth + 1, levels);
    sizes(a, p + 1, hi, rule, rng, depth + 1, levels);
}

void show(const char* title, Pivot rule) {
    std::vector<int> a(16);
    std::iota(a.begin(), a.end(), 0);
    std::mt19937 rng(7);
    Levels levels;
    sizes(a, 0, 16, rule, rng, 1, levels);
    std::cout << title << '\n';
    for (const auto& [depth, list] : levels) {
        std::cout << "  nivel " << depth << ":";
        for (int size : list) {
            if (size == 1) {
                std::cout << " .";
            } else {
                std::cout << ' ' << size;
            }
        }
        std::cout << '\n';
    }
}

}  // namespace

int main() {
    show("Primer elemento como pivote:", Pivot::First);
    show("Pivote al azar, semilla 7:", Pivot::Random);
}