// Paso 6, opcional: un filtro de Bloom.
#ifndef BLOOM_H
#define BLOOM_H

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

#include "not_implemented.h"

// El FNV-1a de 64 bits de la semana 7.
inline std::uint64_t fnv1a(const std::string& key) {
    std::uint64_t hash = 14695981039346656037ULL;
    for (char c : key) {
        hash ^= static_cast<unsigned char>(c);
        hash *= 1099511628211ULL;
    }
    return hash;
}

// De un solo hash salen k posiciones. La mitad baja es h1 y la mitad alta, forzada a impar, es h2:
// así, con bits par, h2 nunca es múltiplo de bits. La posición i es (h1 + i * h2) mod bits.
inline std::size_t bloom_position(const std::string& key, int i, std::size_t bits) {
    std::uint64_t hash = fnv1a(key);
    std::uint64_t h1 = hash & 0xFFFFFFFFULL;
    std::uint64_t h2 = (hash >> 32) | 1;
    return static_cast<std::size_t>((h1 + static_cast<std::uint64_t>(i) * h2) % bits);
}

// Invariante: bits_.size() es el tamaño pedido, y un bit encendido nunca se apaga.
class BloomFilter {
public:
    BloomFilter(std::size_t bits, int hash_count) : bits_(bits, false), hash_count_(hash_count) {
        assert(bits > 0 && hash_count > 0);
    }

    // Enciende las hash_count posiciones de key.
    void add(const std::string& key) {
        (void)key;
        not_implemented("BloomFilter::add");
    }

    // false: seguro que key no se agregó. true: quizás se agregó.
    bool possibly_contains(const std::string& key) const {
        (void)key;
        not_implemented("BloomFilter::possibly_contains");
    }

    // Cuántos bits están encendidos.
    std::size_t bits_on() const {
        not_implemented("BloomFilter::bits_on");
    }

    std::size_t bit_count() const { return bits_.size(); }
    int hash_count() const { return hash_count_; }

private:
    std::vector<bool> bits_;
    int hash_count_;
};

#endif