// Consultas ordenadas sobre un árbol perfecto de 1023 claves, contando comparaciones.
#include <iostream>
#include <vector>

#include "bst_set.h"
#include "counted_key.h"

namespace {

// La raíz primero: así el árbol sale perfecto.
void add_balanced(BstSet<CountedKey>& tree, int low, int high) {
    if (low > high) {
        return;
    }
    int middle = low + (high - low) / 2;
    tree.insert(CountedKey{middle * 10});
    add_balanced(tree, low, middle - 1);
    add_balanced(tree, middle + 1, high);
}

}  // namespace

int main() {
    BstSet<CountedKey> tree;
    add_balanced(tree, 0, 1022);
    std::cout << "claves: " << tree.size() << ", altura: " << tree.height() << "\n";

    CountedKey::comparisons = 0;
    std::cout << "contains(5000): " << tree.contains(CountedKey{5000});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    CountedKey::comparisons = 0;
    std::cout << "contains(5001): " << tree.contains(CountedKey{5001});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    CountedKey::comparisons = 0;
    std::cout << "floor(5001): " << *tree.floor(CountedKey{5001});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    for (int count : {1, 10, 100, 1000}) {
        CountedKey::comparisons = 0;
        std::vector<CountedKey> keys = tree.range(CountedKey{100}, CountedKey{100 + count * 10});
        std::cout << "range con " << keys.size() << " claves, comparaciones: " << CountedKey::comparisons << "\n";
    }
    return 0;
}