#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

/**
 * Metodă: folosim un singur vector mare în care ne facem toate alocările,
 * pentru a evita alocări dinamice. Un element constă din valoarea propriu-
 * zisă și pointeri pentru fiecare nivel. Nivelul elementului nu este stocat
 * nicăieri, de aceea nici mărimea fiecărei înregistrări în vector nu poate fi
 * aflată explicit. Structura suportă ștergeri, dar memoria consumată nu mai
 * este eliberată.
 *
 * La începutul și la sfârșitul listei punem -INFINITY, de nivel MAX_LEVEL,
 * respectiv +INFINITY, fără pointeri.
 *
 * Exemplu: dacă inserăm elementele 17 (nivel 3) și 5 (nivel 2), presupunând
 * că MAX_LEVEL = 5, conținutul vectorului va fi (cu barele inserate pentru
 * claritate):
 *
 * -INF  11  11   7   6   6 | +INF |  17   6   6   6 |  5   7   7
 *    0   1   2   3   4   5 |    6 |   7   8   9  10 | 11  12  13
 */

#define MAX_LEVEL 20         // 2^MAX_LEVEL aproximativ egal cu TRIAL_SIZE
#define TRIAL_SIZE 1000000   // numărul de elemente căutate
#define MAX_BUF 3100000      // mărimea vectorului prealocat
#define INFINITY 2000000000
#define MAX_VALUE 2000000    // folosit la testare

int sl[MAX_BUF];             // zona de memorie prealocată
int level;                   // nivelul maxim al oricărui element
int bufPtr;                  // primul slot nealocat
int update[MAX_LEVEL];       // folosit în timpul inserării
char check[MAX_VALUE];       // folosit în timpul testării
long long t0;

void init() {
  // Capul listei are valoarea -INF și MAX_LEVEL pointeri către coada listei
  // Coada listei are valoarea +INF și zero pointeri
  sl[0] = -INFINITY;
  sl[MAX_LEVEL + 1] = INFINITY;
  for (int i = 0; i < MAX_LEVEL; i++) {
    sl[i + 1] = MAX_LEVEL + 1;
  }
  bufPtr = MAX_LEVEL + 2;
  level = 1;
}

int randomLevel() {
  unsigned r = rand() & ~(1 << (MAX_LEVEL - 1));
  int l = 1;
  while (r & 1) {
    l++;
    r >>= 1;
  }
  return l;
}

void insert(int x) {
  int pos = 0;
  for (int l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
    update[l] = pos;
  }
  pos = sl[pos + 1];

  if (sl[pos] != x) { // nu permitem duplicate
    int newLevel = randomLevel();
    if (newLevel > level) {
      for (int l = level; l < newLevel; l++) {
        update[l] = 0;
      }
      level = newLevel;
    }

    sl[bufPtr] = x;
    for (int l = 0; l < newLevel; l++) {
      sl[bufPtr + l + 1] = sl[update[l] + l + 1];
      sl[update[l] + l + 1] = bufPtr;
    }
    bufPtr += newLevel + 1;
    assert(bufPtr < MAX_BUF);
  }
}

int search (int x) {
  int pos = 0;
  for (int l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
  }
  pos = sl[pos + 1];
  return sl[pos] == x;
}

void erase(int x) {
  int pos = 0;
  for (int l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
    update[l] = pos;
  }
  pos = sl[pos + 1];

  if (sl[pos] == x) {
    // Refacem acei pointeri care pointează la pos (restul trec pe deasupra noastră).
    int l = 0;
    while ((l < MAX_LEVEL) && sl[update[l] + l + 1] == pos) {
      sl[update[l] + l + 1] = sl[pos + l + 1];
      l++;
    }
  }
}

void iterate() {
  int elem = sl[1];
  while (sl[elem] != INFINITY) {
    // printf("%d ", sl[elem]);
    elem = sl[elem + 1];
  }
  // printf("\n");
}

void debug() {
  for (int i = 0; i < bufPtr; i++) {
    printf("%d ", sl[i]);
  }
  printf("\n");
}

void test() {
  printf("Inserez %d numere între 0 și %d\n", TRIAL_SIZE, MAX_VALUE - 1);
  for (int i = 0; i < TRIAL_SIZE; i++) {
    int x = rand() % MAX_VALUE;
    insert(x);
    check[x] = 1;
  }
  printf("Testez numerele între 0 și %d\n", MAX_VALUE - 1);
  int sum = 0;
  for (int i = 0; i < MAX_VALUE; i++) {
    assert(check[i] == search(i));
    sum += check[i];
  }
  printf("%d valori marcate\n", sum);
}

void markTime() {
  timeval tv;

  gettimeofday (&tv, NULL);
  t0 = 1000LL * tv.tv_sec + tv.tv_usec / 1000;
}

void reportTime(const char* msg) {
  timeval tv;

  gettimeofday (&tv, NULL);
  long long t = 1000LL * tv.tv_sec + tv.tv_usec / 1000;
  printf("%s: %lld ms\n", msg, t - t0);
}

int main(void) {
  srand(time(NULL));
  init();

  // test();
  // return 0;

  markTime();
  for (int i = 0; i < TRIAL_SIZE; i++) {
    insert(rand() % MAX_VALUE);
  }
  reportTime("inserare");

  markTime();
  for (int i = 0; i < TRIAL_SIZE; i++) {
    search(rand() % MAX_VALUE);
  }
  reportTime("căutare");

  markTime();
  iterate();
  reportTime("iterare");

  markTime();
  for (int i = 0; i < TRIAL_SIZE; i++) {
    erase(rand() % MAX_VALUE);
  }
  reportTime("ștergere");
}