#include "skiplist.h"

#define SKIPLIST_MAXLEVEL    32
#define SKIPLIST_P           0.25

struct skiplist_t {
    struct skiplist_node_t *head, *tail;    //分别指向跳表的头节点和尾节点
    unsigned int length;    //节点数，不包含头节点
    int level;    //当前跳表中具有最大层数的节点的层数
};

static struct skiplist_node_t *skiplist_create_node(int level)
{
    struct skiplist_node_t *node;

    node = malloc(sizeof(struct skiplist_node_t) + level * sizeof(struct skiplist_level_t));
    if(!node)
    {
        return NULL;
    }

    return node;
}

struct skiplist_t *skiplist_create(void)
{
    struct skiplist_t *skiplist;

    skiplist = malloc(sizeof(struct skiplist_t));
    if(!skiplist)
    {
        return NULL;
    }
    skiplist->length = 0;
    skiplist->level = 1;
    skiplist->tail = NULL;
    skiplist->head = skiplist_create_node(SKIPLIST_MAXLEVEL);
    if(!skiplist->head)
    {
        free(skiplist);
        return NULL;
    }
    skiplist->head->val = -1;
    skiplist->head->backward = NULL;
    for(int i = 0;i < SKIPLIST_MAXLEVEL;i++)
    {
        skiplist->head->level[i].forward = NULL;
    }

    return skiplist;
}

bool skiplist_search(struct skiplist_t *obj, int target)
{
    struct skiplist_node_t *node;
    int i;

    //按照从上到下从左到右的寻找原则
    node = obj->head;
    for(i = obj->level - 1;i >= 0;i--)
    {
        while(node->level[i].forward && (node->level[i].forward->val < target))
        {
            node = node->level[i].forward;
        }
        if(node->level[i].forward && (node->level[i].forward->val == target))
        {
            return true;
        }
    }

    return false;
}

static int skiplist_random_level(void)
{
    int level = 1;

    while((rand() & 0xFFFF) < (SKIPLIST_P * 0xFFFF))
    {
        level += 1;
    }

    return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
}

struct skiplist_node_t *skiplist_add(struct skiplist_t *obj, int target)
{
    struct skiplist_node_t *prev[SKIPLIST_MAXLEVEL];    //记录插入节点的前级节点
    struct skiplist_node_t *node;
    int i, lvl;

    //寻找并记录插入节点的前级节点
    node = obj->head;
    for(i = obj->level - 1;i >= 0;i--)
    {
        while(node->level[i].forward && node->level[i].forward->val < target)
        {
            node = node->level[i].forward;
        }
        prev[i] = node;
    }

    lvl = skiplist_random_level();
    //记录超过当前最大层时插入位置的前级节点
    if(obj->level < lvl)
    {
        for(i = obj->level;i < lvl;i++)
        {
            prev[i] = obj->head;
        }
        obj->level = lvl;
    }

    //创建新节点并添加
    node = skiplist_create_node(lvl);
    for(i = 0;i < lvl;i++)
    {
        node->level[i].forward = prev[i]->level[i].forward;
        prev[i]->level[i].forward = node;
    }
    node->val = target;
    //如果该节点为第二个节点，则将后退指针置为NULL，否则置为前级节点
    node->backward = (prev[0] == obj->head) ? NULL : prev[0];
    if(node->level[0].forward)
    {
        //更新前进指针指向节点的后退指针为当前节点
        node->level[0].forward->backward = node;
    }
    else
    {
        //更新尾节点为当前节点
        obj->tail = node;
    }

    ++obj->length;

    return node;
}

static void skiplist_delete_node(struct skiplist_t *obj, struct skiplist_node_t *node, struct skiplist_node_t *prev[])
{
    int i;

    for(i = obj->level - 1;i >= 0;i--)
    {
        //如果删除节点的前进指针指向的节点为本节点，则解除链接
        if(prev[i]->level[i].forward == node)
        {
            prev[i]->level[i].forward = node->level[i].forward;
        }
    }
    if(node->level[0].forward)
    {
        //更新后退指针
        node->level[0].forward->backward = node->backward;
    }
    else
    {
        //更新尾节点为当前节点
        obj->tail = node->backward;
    }

    //更新删除节点后当前跳表中具有最大层数的节点的层数
    while((obj->level > 1) && (obj->head->level[obj->level - 1].forward == NULL))
    {
        --obj->level;
    }
    --obj->length;
}

bool skiplist_delete(struct skiplist_t *obj, int target, struct skiplist_node_t **unlink_node)
{
    struct skiplist_node_t *prev[SKIPLIST_MAXLEVEL];    //记录删除节点的前级节点
    struct skiplist_node_t *node;
    int i;

    //寻找并记录删除节点的前级节点
    node = obj->head;
    for(i = obj->level - 1;i >= 0;i--)
    {
        while(node->level[i].forward && node->level[i].forward->val < target)
        {
            node = node->level[i].forward;
        }
        prev[i] = node;
    }

    node = node->level[0].forward;
    if(node && (node->val == target))
    {
        //分离该节点
        skiplist_delete_node(obj, node, prev);
        if(!unlink_node)
        {
            //释放该节点
            free(node);
        }
        else
        {
            //获得分离后的节点
            *unlink_node = node;
        }

        return true;
    }
    return false;
}

struct skiplist_node_t *skiplist_update(struct skiplist_t *obj, int target, int new_target)
{
    struct skiplist_node_t *prev[SKIPLIST_MAXLEVEL];    //记录删除节点的前级节点
    struct skiplist_node_t *node;
    int i;

    //寻找并记录删除节点的前级节点
    node = obj->head;
    for(i = obj->level - 1;i >= 0;i--)
    {
        while(node->level[i].forward && node->level[i].forward->val < target)
        {
            node = node->level[i].forward;
        }
        prev[i] = node;
    }

    //未找到该节点，直接返回
    node = node->level[0].forward;
    if(!node || (node->val != target))
    {
        return NULL;
    }
    //如果更新后排名不变，则直接更新即可
    if((node->backward == NULL || node->backward->val < new_target) &&
        (node->level[0].forward == NULL || node->level[0].forward->val > new_target))
    {
        node->val = new_target;
        return node;
    }
    //更新后排名发生变化，则先删除节点然后重新插入
    skiplist_delete_node(obj, node, prev);
    //释放掉之前的节点
    free(node);
    //重新插入节点
    node = skiplist_add(obj, new_target);

    return node;
}

void skiplist_destroy(struct skiplist_t *obj)
{
    struct skiplist_node_t *de;
    struct skiplist_node_t *node;

    node = obj->head->level[0].forward;
    while(node)
    {
        de = node;
        node = node->level[0].forward;
        free(de);
    }

    free(obj->head);
    obj->head = NULL;

    free(obj);
}

void skiplist_for_each(struct skiplist_t* obj)
{
    struct skiplist_node_t *node;
    int i;

    for(i = obj->level - 1;i >= 0;i--)
    {
        node = obj->head->level[i].forward;
        while(node)
        {
            printf("%d-->", node->val);

            node = node->level[i].forward;
        }
        printf("null\r\n");
    }

    printf("null");
    node = obj->tail;
    while(node)
    {
        printf("<--%d", node->val);

        node = node->backward;
    }
    printf("\r\n");
}

//leetCode测试接口
#include <time.h>

typedef struct skiplist_t Skiplist;

Skiplist* skiplistCreate() {
    return skiplist_create();
}

bool skiplistSearch(Skiplist* obj, int target) {
    return skiplist_search(obj, target);
}

void skiplistAdd(Skiplist* obj, int num) {
    skiplist_add(obj, num);
}

bool skiplistErase(Skiplist* obj, int num) {
    return skiplist_delete(obj, num, NULL);
}

void skiplistFree(Skiplist* obj) {
    skiplist_destroy(obj);
}

int main(int argc, char *argv[])
{
    Skiplist *skiplist;

    srand(time(NULL));

    skiplist = skiplistCreate();
    printf("skiplist:%p\r\n", skiplist);
    for(int i = 0;i < SKIPLIST_MAXLEVEL;i++)
    {
        printf("%p\r\n", &skiplist->head[i]);
    }

    skiplistAdd(skiplist, 1);
    skiplistAdd(skiplist, 3);
    skiplistAdd(skiplist, 5);
    skiplistAdd(skiplist, 5);
    skiplistAdd(skiplist, 7);
    skiplistAdd(skiplist, 9);
    skiplistAdd(skiplist, 11);

    skiplist_for_each(skiplist);

    printf("length:%d, level:%d, tail:%d\r\n", skiplist->length, skiplist->level, skiplist->tail->val);
    printf("%s\r\n", skiplistSearch(skiplist, 1) ? "true" : "false");
    printf("%s\r\n", skiplistSearch(skiplist, 2) ? "true" : "false");

    skiplistErase(skiplist, 5);
    skiplist_for_each(skiplist);
    printf("%s\r\n", skiplistSearch(skiplist, 5) ? "true" : "false");
    printf("length:%d, level:%d, tail:%d\r\n", skiplist->length, skiplist->level, skiplist->tail->val);

    skiplist_update(skiplist, 5, 0);
    skiplist_for_each(skiplist);
    printf("%s\r\n", skiplistSearch(skiplist, 0) ? "true" : "false");
    printf("length:%d, level:%d, tail:%d\r\n", skiplist->length, skiplist->level, skiplist->tail->val);

    skiplistFree(skiplist);

    return 0;
}