// Los ordenamientos de la clase, solo para enteros. Cuentan comparaciones para poder
// comparar algoritmos con un número que no depende de la máquina.
#ifndef INT_SORTS_H
#define INT_SORTS_H

#include <cstddef>
#include <random>
#include <utility>
#include <vector>

// Mezcla items[lo, mid) con items[mid, hi), que ya están ordenados.
inline void merge_runs(std::vector<int>& items, std::vector<int>& buffer, std::size_t lo,
                       std::size_t mid, std::size_t hi, long long& comparisons) {
    std::size_t left = lo;
    std::size_t right = mid;
    std::size_t out = lo;
    while (left < mid && right < hi) {
        comparisons++;
        if (items[right] < items[left]) {
            buffer[out++] = items[right++];
        } else {
            buffer[out++] = items[left++];
        }
    }
    while (left < mid) {
        buffer[out++] = items[left++];
    }
    while (right < hi) {
        buffer[out++] = items[right++];
    }
    for (std::size_t i = lo; i < hi; i++) {
        items[i] = buffer[i];
    }
}

inline void merge_sort_range(std::vector<int>& items, std::vector<int>& buffer, std::size_t lo,
                             std::size_t hi, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    merge_sort_range(items, buffer, lo, mid, comparisons);
    merge_sort_range(items, buffer, mid, hi, comparisons);
    merge_runs(items, buffer, lo, mid, hi, comparisons);
}

inline void merge_sort_ints(std::vector<int>& items, long long& comparisons) {
    std::vector<int> buffer(items.size());
    merge_sort_range(items, buffer, 0, items.size(), comparisons);
}

// Partición con el primer elemento como pivote. Al terminar, el pivote queda en su lugar
// final, y se devuelve esa posición.
inline std::size_t partition_first(std::vector<int>& items, std::size_t lo, std::size_t hi,
                                   long long& comparisons) {
    int pivot = items[lo];
    std::size_t boundary = lo;
    // Invariante: items(lo, boundary] < pivot, e items(boundary, scan) >= pivot.
    for (std::size_t scan = lo + 1; scan < hi; scan++) {
        comparisons++;
        if (items[scan] < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
    }
    std::swap(items[lo], items[boundary]);
    return boundary;
}

inline void quick_first_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                              long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::size_t p = partition_first(items, lo, hi, comparisons);
    quick_first_range(items, lo, p, comparisons);
    quick_first_range(items, p + 1, hi, comparisons);
}

inline void quick_sort_first_ints(std::vector<int>& items, long long& comparisons) {
    quick_first_range(items, 0, items.size(), comparisons);
}

// Lo mismo, pero antes de partir se cambia el primer elemento por uno al azar.
inline void quick_random_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                               std::mt19937& rng, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::uniform_int_distribution<std::size_t> pick(lo, hi - 1);
    std::swap(items[lo], items[pick(rng)]);
    std::size_t p = partition_first(items, lo, hi, comparisons);
    quick_random_range(items, lo, p, rng, comparisons);
    quick_random_range(items, p + 1, hi, rng, comparisons);
}

inline void quick_sort_random_ints(std::vector<int>& items, unsigned seed, long long& comparisons) {
    std::mt19937 rng(seed);
    quick_random_range(items, 0, items.size(), rng, comparisons);
}

// Partición en tres, con pivote al azar. Invariante: items[lo, less_end) < pivot,
// items[less_end, scan) == pivot, items[scan, greater_start) sin revisar, items[greater_start, hi) > pivot.
inline void quick_three_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                              std::mt19937& rng, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::uniform_int_distribution<std::size_t> pick(lo, hi - 1);
    int pivot = items[pick(rng)];
    std::size_t less_end = lo;
    std::size_t scan = lo;
    std::size_t greater_start = hi;
    while (scan < greater_start) {
        comparisons++;
        if (items[scan] < pivot) {
            std::swap(items[less_end], items[scan]);
            less_end++;
            scan++;
            continue;
        }
        comparisons++;
        if (pivot < items[scan]) {
            greater_start--;
            std::swap(items[scan], items[greater_start]);
        } else {
            scan++;
        }
    }
    quick_three_range(items, lo, less_end, rng, comparisons);
    quick_three_range(items, greater_start, hi, rng, comparisons);
}

inline void quick_sort_three_ints(std::vector<int>& items, unsigned seed, long long& comparisons) {
    std::mt19937 rng(seed);
    quick_three_range(items, 0, items.size(), rng, comparisons);
}

// Búsqueda binaria. Devuelve la posición del primer elemento >= x, o size() si no hay.
inline std::size_t lower_bound_index(const std::vector<int>& items, int x, long long& probes) {
    std::size_t lo = 0;
    std::size_t hi = items.size();
    // Invariante: todo en [0, lo) es < x, y todo en [hi, n) es >= x.
    while (lo < hi) {
        std::size_t mid = lo + (hi - lo) / 2;
        probes++;
        if (items[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

#endif