// ERROR A PROPÓSITO: la búsqueda termina en el primer tombstone, en vez de en la primera vacía.
// Compilar: g++ -Wall -Wextra -std=c++20 errors/stop_at_tombstone.cpp -o build/stop_at_tombstone
#include <array>
#include <cstddef>
#include <iostream>

namespace {

constexpr int kEmpty = -1;
constexpr int kTombstone = -2;

std::size_t home(int key) { return static_cast<std::size_t>(key) % 7; }

void insert(std::array<int, 7>& table, int key) {
    std::size_t i = home(key);
    while (table[i] >= 0) {
        i = (i + 1) % table.size();
    }
    table[i] = key;
}

bool contains(const std::array<int, 7>& table, int key) {
    std::size_t i = home(key);
    // Aquí está el error: un tombstone no dice nada sobre lo que viene después.
    while (table[i] != kEmpty && table[i] != kTombstone) {
        if (table[i] == key) {
            return true;
        }
        i = (i + 1) % table.size();
    }
    return false;
}

void erase(std::array<int, 7>& table, int key) {
    std::size_t i = home(key);
    while (table[i] != kEmpty) {
        if (table[i] == key) {
            table[i] = kTombstone;
            return;
        }
        i = (i + 1) % table.size();
    }
}

}  // namespace

int main() {
    std::array<int, 7> table;
    table.fill(kEmpty);
    insert(table, 8);
    insert(table, 15);
    insert(table, 22);
    erase(table, 15);
    std::cout << "contains(8) = " << contains(table, 8) << "\n";
    std::cout << "contains(22) = " << contains(table, 22) << "  <- la clave sigue en la tabla\n";
    return 0;
}