#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define SKIPLIST_MAX_LEVEL 6

typedef struct snode
{
	int key;
	int value;
	struct snode **forward;			// 每个节点都含有一个二级指针，指向着不同层的next节点
}snode;

typedef struct skiplist
{
	int level;
	int size;
	struct snode *header;		// 一个链表表头
}skiplist;

static int rand_level() {		// 对于rand_level，要具体实现在于如何设置概率，网上一般要求为 2层的概率为0.5,3层0.25， 0.125...
    int level;
    for(level = 1; level < SKIPLIST_MAX_LEVEL && rand() % 2 == 0; level++);

  	// while (rand() < RAND_MAX / 2 && level < SKIPLIST_MAX_LEVEL)
    //    level++;
    printf("return level: %d\n", level);
    return level;
}
snode *skiplist_search(skiplist *list, int key)
{
	snode *x = list->header;
	int i;

	for(i = list->level; i >= 1; i--){
		while(x->forward[i]->key < key)
			x = x->forward[i];
	}
	x = x->forward[1];

	if(x->key == key)
		return x;
	else
		return NULL;
}

static void skiplist_node_free(snode *x)
{
    if (x) {
        free(x->forward);
        free(x);
    }
}

// 把insert看懂，这个就会了
int skiplist_delete(skiplist *list, int key)
{
	snode *update[SKIPLIST_MAX_LEVEL + 1];
	snode *x = list->header;
	int i;

	for(i = list->level; i >= 1; i--){
		while(x->forward[i]->key < key)
			x = x->forward[i];
		update[i] = x;
	}

	x = x->forward[1];
	if(x->key == key){
		for(i = 1; i <= list->level; i++){
			if(update[i]->forward[i] != x)
				break;
			update[i]->forward[i] = x->forward[i];
		}
		skiplist_node_free(x);
		// 对于那些删除该key节点后，只剩一个header的，level就会减一（没必要保持）
		while(list->level > 1 && list->header->forward[list->level] == list->header)
			list->level--;
		return 0;
	}
	return 1;
}
int skiplist_insert(skiplist *list, int key, int value)
{
  	/* update在于保存每一层中当前节点的下一个节点的key值大于key的，
    * 通过保存update，我们能在最后的时候一并更新
    */
	snode *update[SKIPLIST_MAX_LEVEL + 1];
	snode *x = list->header;
	int i;

	for(i = list->level; i >= 1; i--){
		while(x->forward[i]->key < key)
			x = x->forward[i];
		update[i] = x;
	}

  	// 查看是否存在key相等的可能
	x = x->forward[1];

	if(x->key == key){
		x->value = value;
		return 0;
	}else{
      	// 节点获取的level跟自己的属性和整体的属性没有关系，都是通过一定概率的函数（！！但是概率中又存在着概率，因为rand（）是个伪随机）
		int lvl = rand_level();
		if(lvl > list->level){
			for(int i = list->level + 1; i <= lvl; i++){
              	// 如果当前的level小于节点的level，则把上层的level的header作为更新点(因为默认每层为空时只存在一个header）
				update[i] = list->header;
			}
			list->level = lvl;
		}

		x = (snode *)malloc(sizeof(struct snode));
		x->key = key;
		x->value = value;
		x->forward = (snode **)malloc(sizeof(snode*) * (lvl+1));
		for(int i = 1; i <= lvl; i++){
			x->forward[i] = update[i] -> forward[i];
			update[i] -> forward[i] =x;
		}
	}

	return 0;
}

skiplist *skiplist_init(skiplist *list)
{
	snode *header = (snode *)malloc(sizeof(struct snode));
	list->header = header;
	header->key = INT_MAX;
	header->forward = (snode **)malloc(sizeof(snode*)
				* (SKIPLIST_MAX_LEVEL + 1));
	for(int i = 0; i<= SKIPLIST_MAX_LEVEL; i++){
		header->forward[i] = list->header;
	}

	list->level = 1;
	list->size = 0;
}

static void skiplist_dump(skiplist *list)
{
	snode *x = list->header;
	while(x && x->forward[1] != list->header){
		printf("%d[%d] ->", x->forward[1]->key, x->forward[1]->value);
		x = x->forward[1];
	}

	printf("NIL\n");
}

int main(){

	int arr[] = {3, 6, 9, 2, 11, 1, 4, 8}, i;
	skiplist list;
	skiplist_init(&list);
	printf("Insert:--------------------\n");
	for(i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){
		skiplist_insert(&list, arr[i], arr[i]);
	}

	printf("Search:--------------------\n");
    int keys[] = {3, 4, 7, 10, 111};

    for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++) {
    	snode *x = skiplist_search(&list, keys[i]);
    	if(x)
    		printf("key = %d, value = %d\n", keys[i], x->value);
    	else
    		printf("key = %d, not found\n", keys[i]);
    }
    printf("Search:--------------------\n");
    skiplist_delete(&list, 3);
    skiplist_delete(&list, 9);
	skiplist_dump(&list);
}