// La misma consulta en std::map y en std::unordered_map: la menor clave >= x, y una por rango.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <random>
#include <unordered_map>
#include <vector>

#include "counted_key.h"

namespace {

struct CountedHash {
    std::size_t operator()(const CountedKey& key) const { return std::hash<int>{}(key.value); }
};

struct SameKey {
    bool operator()(const CountedKey& a, const CountedKey& b) const { return a.value == b.value; }
};

}  // namespace

int main() {
    const int n = 100000;
    std::mt19937 random(10);
    std::vector<int> values(n);
    for (int i = 0; i < n; i++) {
        values[i] = i * 3;
    }
    std::shuffle(values.begin(), values.end(), random);

    std::map<CountedKey, int> ordered;
    std::unordered_map<CountedKey, int, CountedHash, SameKey> hashed;
    for (int value : values) {
        ordered[CountedKey{value}] = value;
        hashed[CountedKey{value}] = value;
    }
    CountedKey target{100000};

    CountedKey::comparisons = 0;
    auto at_or_after = ordered.lower_bound(target);
    std::cout << "std::map, techo de 100000: " << at_or_after->first.value << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    // Sin orden no queda más que mirar todas las claves.
    long visited = 0;
    int best = -1;
    for (const auto& [key, value] : hashed) {
        visited++;
        if (key.value >= target.value && (best == -1 || key.value < best)) {
            best = key.value;
        }
    }
    std::cout << "std::unordered_map, techo de 100000: " << best << ", claves visitadas: " << visited << "\n";

    CountedKey::comparisons = 0;
    auto after = ordered.upper_bound(CountedKey{100000});
    std::cout << "std::map, piso de 100000: " << std::prev(after)->first.value << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    long in_range = 0;
    CountedKey::comparisons = 0;
    auto stop = ordered.lower_bound(CountedKey{100030});
    for (auto it = ordered.lower_bound(CountedKey{100000}); it != stop; ++it) {
        in_range++;
    }
    std::cout << "std::map, claves en [100000, 100030): " << in_range << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    std::cout << "std::map, primeras:";
    auto it_map = ordered.begin();
    for (int i = 0; i < 5; i++, ++it_map) {
        std::cout << " " << it_map->first.value;
    }
    std::cout << "\n";

    std::cout << "std::unordered_map, primeras:";
    auto it_hash = hashed.begin();
    for (int i = 0; i < 5; i++, ++it_hash) {
        std::cout << " " << it_hash->first.value;
    }
    std::cout << "\n";
    return 0;
}