// Cuenta las copias de elementos en una búsqueda binaria y en mergesort, según cómo se pase el arreglo.
// La búsqueda es la del peor caso: un valor menor que todos, que siempre sigue por la izquierda.
#include <iostream>
#include <string>
#include <vector>

#include "copy_cost.h"

int main() {
    std::cout << "búsqueda binaria\n";
    std::cout << "n        llamadas  entero por valor  solo la mitad  por referencia\n";
    for (int n : {1024, 2048, 4096, 8192}) {
        long long whole = 0;
        int calls = 0;
        std::vector<Counted> a = counted_range(n, &whole);
        search_whole_copy(a, 0, a.size(), -1, calls);

        long long half = 0;
        int half_calls = 0;
        std::vector<Counted> b = counted_range(n, &half);
        search_half_copy(b, -1, half_calls);

        long long reference = 0;
        int reference_calls = 0;
        std::vector<Counted> c = counted_range(n, &reference);
        search_by_reference(c, 0, c.size(), -1, reference_calls);

        std::cout << n << "     " << calls << std::string(10 - std::to_string(calls).size(), ' ') << whole
                  << std::string(18 - std::to_string(whole).size(), ' ') << half
                  << std::string(15 - std::to_string(half).size(), ' ') << reference << '\n';
    }

    std::cout << "\nmergesort con el auxiliar por valor\n";
    std::cout << "n        llamadas  copias\n";
    for (int n : {1024, 2048, 4096}) {
        long long copies = 0;
        std::vector<Counted> a = counted_range(n, &copies);
        sort_range_buffer_by_value(a, a, 0, a.size());
        long long calls = 2LL * n - 1;
        std::cout << n << "     " << calls << std::string(10 - std::to_string(calls).size(), ' ') << copies << '\n';
    }
}