// Búsqueda binaria y mergesort que copian de más, con un elemento que cuenta sus copias.
#pragma once

#include <cstddef>
#include <vector>

#include "merge_sort.h"

// Cada vez que se construye por copia, por ejemplo al copiar un std::vector, suma 1 al contador.
struct Counted {
    int value = 0;
    long long* copies = nullptr;

    Counted() = default;
    Counted(int v, long long* counter) : value(v), copies(counter) {}
    Counted(const Counted& other) : value(other.value), copies(other.copies) {
        if (copies != nullptr) {
            (*copies)++;
        }
    }
    Counted& operator=(const Counted& other) = default;

    bool operator<=(const Counted& other) const { return value <= other.value; }
};

inline std::vector<Counted> counted_range(int n, long long* counter) {
    std::vector<Counted> a;
    a.reserve(n);
    for (int i = 0; i < n; i++) {
        a.emplace_back(i, counter);
    }
    return a;
}

// Recibe el arreglo completo por valor: cada llamada copia n elementos, por chico que sea [lo, hi).
inline int search_whole_copy(std::vector<Counted> a, std::size_t lo, std::size_t hi, int target, int& calls) {
    calls++;
    if (lo == hi) {
        return -1;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    if (a[mid].value == target) {
        return static_cast<int>(mid);
    }
    if (target < a[mid].value) {
        return search_whole_copy(a, lo, mid, target, calls);
    }
    return search_whole_copy(a, mid + 1, hi, target, calls);
}

// Copia solo la mitad que sigue: cada llamada paga el tamaño de su propio subproblema.
inline bool search_half_copy(const std::vector<Counted>& a, int target, int& calls) {
    calls++;
    if (a.empty()) {
        return false;
    }
    std::size_t mid = a.size() / 2;
    if (a[mid].value == target) {
        return true;
    }
    if (target < a[mid].value) {
        std::vector<Counted> half(a.begin(), a.begin() + static_cast<std::ptrdiff_t>(mid));
        return search_half_copy(half, target, calls);
    }
    std::vector<Counted> half(a.begin() + static_cast<std::ptrdiff_t>(mid) + 1, a.end());
    return search_half_copy(half, target, calls);
}

// La misma búsqueda sin copiar nada: el costo por llamada es constante.
inline int search_by_reference(const std::vector<Counted>& a, std::size_t lo, std::size_t hi, int target, int& calls) {
    calls++;
    if (lo == hi) {
        return -1;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    if (a[mid].value == target) {
        return static_cast<int>(mid);
    }
    if (target < a[mid].value) {
        return search_by_reference(a, lo, mid, target, calls);
    }
    return search_by_reference(a, mid + 1, hi, target, calls);
}

// Mergesort con el error: el arreglo auxiliar se recibe por valor, y cada llamada lo copia entero.
template <typename T>
void sort_range_buffer_by_value(std::vector<T>& a, std::vector<T> buffer, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range_buffer_by_value(a, buffer, lo, mid);
    sort_range_buffer_by_value(a, buffer, mid, hi);
    merge_ranges(a, buffer, lo, mid, hi);
}