#include "stdlib.h"
#include "stdio.h"
#include "limits.h"

typedef struct _Node{
    int key;
    int val;

    int topLevel;
    struct _Node **next;
} Node;

typedef struct _SkipList{
    int maxLevel;
    Node *head, *tail;

    Node **preds, **succs;
} SkipList;

Node *create_node(int topLevel, int key, int val){
    Node *node;
    node = calloc(1, sizeof(Node));
    node->next = (Node **) calloc(topLevel+1, sizeof(Node *));
    node->key = key;
    node->val = val;
    node->topLevel = topLevel;
    return node;
}

void free_node(Node *node){
    free(node->next);
    free(node);
    return;
}

int search(SkipList *sl, int key){
    int res, level;
    Node *pre, *crr;
    pre = sl -> head;
    res = -1;
    for(level = sl->maxLevel - 1; level >= 0; --level){
        crr = pre->next[level];
        while(key > crr->key){
            pre = crr;
            crr = pre->next[level];
        }
        if(res == -1 && key == crr->key) res = level;
        sl->preds[level] = pre;
        sl->succs[level] = crr;
    }
    return res;
}

int delete(SkipList *sl, int key){
    int level;
    int res;
    Node *node;
    if(search(sl, key) == -1) return -1;
    node = sl->preds[0]->next[0];
    for(level = node->topLevel; level>=0; --level)
        sl->preds[level]->next[level] = node->next[level];
    res = node->val;
    free_node(node);
    return res;
}

SkipList *init_list(int maxLevel){
    SkipList *sl;
    Node *head, *tail;
    int i;
    sl = (SkipList *) calloc(1, sizeof(SkipList));
    sl->preds = (Node**) calloc(maxLevel+1, sizeof(Node*));
    sl->succs = (Node**) calloc(maxLevel+1, sizeof(Node*));
    sl -> maxLevel = maxLevel;

    head = create_node(maxLevel, INT_MIN, 0);
    tail = create_node(maxLevel, INT_MAX, 0);
    for(i=0; i<maxLevel; ++i){
        head -> next[i] = tail;
        tail -> next[i] = NULL;
    }
    sl -> head = head;
    sl -> tail = tail;
    return sl;
}

void free_list(SkipList *sl){
    Node *node;
    while(sl->head->next[0] != sl->tail) delete(sl, sl->head->next[0]->key);
    free_node(sl->head);
    free_node(sl->tail);
    free(sl->preds);
    free(sl->succs);
    free(sl);
}


int add(SkipList *sl, int key, int val){
    int level, topLevel, fLevel;
    Node *node;
    int r = rand();
    if((fLevel = search(sl, key)) != -1) return -1;
    topLevel = (r % sl->maxLevel);
    node = create_node(topLevel, key, val);
    for(level = 0; level <= topLevel; ++level){
        node->next[level] = sl->succs[level];
        sl->preds[level]->next[level] = node;
    }
    return 0;
}

int find(SkipList *sl, int key){
    int res;
    if(search(sl, key) != -1) return -1;
    return sl->preds[0]->next[0]->val;
}

void print_list(SkipList *sl){
    int i;
    Node *node;
    for(i=sl->maxLevel-1; i>=0; --i){
        printf("\tlevel %2d: ", i);
        for(node = sl->head->next[0]; node != sl->tail; node = node->next[0]){
            if(i <= node->topLevel)
                printf(" [%5d]", node->key);
            else
                printf("        ");
        }
        printf("\n");
    }
    return;
}



int main(void) {
    int i;
    SkipList *sl;

    int *nums;
    int t = 10;

    nums = calloc(t, sizeof(int));
    sl = init_list(4);

    for (i = 0; i < t; i++) {
        add(sl, (nums[i] = i), i);
        printf("add %d\n", nums[i]);
        print_list(sl);
    }

    for (i = t - 1; 1 <= i; i--) {
        printf("delete %d\n", delete(sl, nums[i]));
        print_list(sl);
    }

    free(nums);
    free_list(sl);
    exit(0);
    return 0;
}