/* Wall-clock micro-benchmark: n random distinct keys, then n successful lookups in
 * random order, then n erases in random order. Prints ns/op for one run.
 * Build: gcc -O2 -Wall -Wextra -o bench bench.c
 * Run:   taskset -c 3 ./bench <structure> <n> <seed>
 *        structure = treap-rot | treap-sm | skip-1/2 | skip-1/4 */
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "treap.h"
#include "skiplist.h"

static double now_ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1e9 + ts.tv_nsec;
}

static void shuffle(int64_t *a, long n, rng_t *g)
{
    for (long i = n - 1; i > 0; i--) {
        long j = (long)rng_below(g, (uint64_t)i + 1);
        int64_t t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

int main(int argc, char **argv)
{
    if (argc != 4) { fprintf(stderr, "usage: %s structure n seed\n", argv[0]); return 2; }
    const char *what = argv[1];
    long n = atol(argv[2]);
    uint64_t seed = strtoull(argv[3], NULL, 10);
    int kind = !strcmp(what, "treap-rot") ? 0 : !strcmp(what, "treap-sm") ? 1
             : !strcmp(what, "skip-1/2") ? 2 : !strcmp(what, "skip-1/4") ? 3 : -1;
    if (kind < 0 || n <= 0) { fprintf(stderr, "bad arguments\n"); return 2; }

    rng_t g; rng_seed(&g, seed);
    int64_t *keys = malloc((size_t)n * sizeof *keys);
    uint64_t *prio = malloc((size_t)n * sizeof *prio);
    for (long i = 0; i < n; i++) keys[i] = i;
    shuffle(keys, n, &g);
    for (long i = 0; i < n; i++) prio[i] = rng_next(&g);

    tnode *root = NULL;
    skiplist sl;
    if (kind >= 2) sl_init(&sl, kind == 2 ? 0.5 : 0.25, 32, rng_next(&g));

    double t0 = now_ns();
    for (long i = 0; i < n; i++) {
        if (kind == 0) { long r = 0; int ins; root = treap_insert_rot(root, tnode_new(keys[i], prio[i]), &r, &ins); }
        else if (kind == 1) root = treap_insert_sm(root, tnode_new(keys[i], prio[i]));
        else sl_insert(&sl, keys[i]);
    }
    double t1 = now_ns();

    shuffle(keys, n, &g);
    long found = 0;
    double t2 = now_ns();
    if (kind <= 1) {
        long v = 0;
        for (long i = 0; i < n; i++) found += treap_find(root, keys[i], &v) != NULL;
    } else {
        slstats st = {0};
        for (long i = 0; i < n; i++) found += sl_find(&sl, keys[i], &st) != NULL;
    }
    double t3 = now_ns();

    shuffle(keys, n, &g);
    long erased = 0;
    double t4 = now_ns();
    for (long i = 0; i < n; i++) {
        int e = 0;
        if (kind == 0) { long r = 0; root = treap_erase_rot(root, keys[i], &r, &e); }
        else if (kind == 1) root = treap_erase_sm(root, keys[i], &e);
        else e = sl_erase(&sl, keys[i]);
        erased += e;
    }
    double t5 = now_ns();

    if (found != n || erased != n) { fprintf(stderr, "check failed\n"); return 1; }
    printf("%s n=%ld seed=%llu insert_ns=%.1f find_ns=%.1f erase_ns=%.1f\n", what, n,
           (unsigned long long)seed, (t1 - t0) / n, (t3 - t2) / n, (t5 - t4) / n);
    if (kind >= 2) sl_free(&sl);
    free(keys); free(prio);
    return 0;
}