// Una tabla de enteros con h(k) = k mod m y linear probing, que muestra cada paso.
// probe_trace <m> <órdenes>. Órdenes: i10 inserta, f31 busca, e17 borra vaciando la casilla
// (está mal, a propósito), t17 borra con tombstone.
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

namespace {

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

class TraceTable {
public:
    explicit TraceTable(std::size_t slots) : slots_(slots, kEmpty) {}

    void insert(int key) {
        std::size_t i = home(key);
        std::cout << "insertar " << key << " (inicio " << i << "):";
        // Basta para esta demostración: no revisa si la clave ya está.
        while (slots_[i] >= 0) {
            std::cout << " " << i;
            i = (i + 1) % slots_.size();
        }
        std::cout << " " << i << " <- aquí\n";
        slots_[i] = key;
    }

    // Devuelve la casilla donde está la clave, o -1.
    int find(int key, bool show = true) const {
        std::size_t i = home(key);
        std::size_t probes = 0;
        std::string path;
        int where = -1;
        while (probes < slots_.size()) {
            probes++;
            path += " " + std::to_string(i);
            if (slots_[i] == key) {
                where = static_cast<int>(i);
                break;
            }
            if (slots_[i] == kEmpty) {
                break;
            }
            i = (i + 1) % slots_.size();
        }
        if (show) {
            std::cout << "buscar " << key << " (inicio " << home(key) << "):" << path << " -> "
                      << (where >= 0 ? "está" : "no está") << ", " << probes << " casillas\n";
        }
        return where;
    }

    void erase_wrong(int key) {
        const int i = find(key, false);
        std::cout << "borrar " << key << " vaciando la casilla " << i << "\n";
        if (i >= 0) {
            slots_[static_cast<std::size_t>(i)] = kEmpty;
        }
    }

    void erase_tombstone(int key) {
        const int i = find(key, false);
        std::cout << "borrar " << key << " con tombstone en la casilla " << i << "\n";
        if (i >= 0) {
            slots_[static_cast<std::size_t>(i)] = kTombstone;
        }
    }

    void print() const {
        std::cout << "tabla:";
        for (std::size_t i = 0; i < slots_.size(); i++) {
            std::cout << " [" << i << ":";
            if (slots_[i] == kEmpty) {
                std::cout << "_";
            } else if (slots_[i] == kTombstone) {
                std::cout << "X";
            } else {
                std::cout << slots_[i];
            }
            std::cout << "]";
        }
        std::cout << "\n";
    }

private:
    std::size_t home(int key) const { return static_cast<std::size_t>(key) % slots_.size(); }

    std::vector<int> slots_;
};

}  // namespace

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "uso: probe_trace <m> <órdenes: i10 f31 e17 t17>\n";
        return 2;
    }
    TraceTable table(std::strtoul(argv[1], nullptr, 10));
    for (int a = 2; a < argc; a++) {
        const char order = argv[a][0];
        const int key = std::atoi(argv[a] + 1);
        if (order == 'i') {
            table.insert(key);
        } else if (order == 'f') {
            table.find(key);
        } else if (order == 'e') {
            table.erase_wrong(key);
        } else if (order == 't') {
            table.erase_tombstone(key);
        } else if (order == 'p') {
            table.print();
        }
    }
    table.print();
    return 0;
}