#include <string.h>
#include <time.h>
#include <iostream>
#include <map>
#include <stdexcept>
template <typename KeyType, typename ValueType>
struct skip_list_node {
    KeyType key;
    ValueType value;
    skip_list_node *forwards[1] = {nullptr};
};
template <typename KeyType, typename ValueType>
struct skip_list {
    int level = 0;
    skip_list_node<KeyType, ValueType>*header = nullptr;
};
using KeyType = int;
using ValueType = int;
using NodeType = struct skip_list_node<KeyType, ValueType>;
using ListType = struct skip_list<KeyType, ValueType>;
using Node = NodeType *;
using List = ListType *;
#define NEW_LEVEL_NODE(level) (Node)malloc(sizeof(NodeType) + (level) * sizeof(Node))
#define NEW_LIST (List)malloc(sizeof(ListType))
class CSkipList {
public:
    CSkipList() {
        srand(time(NULL));
        skip_list_ = NEW_LIST;
        if (nullptr == skip_list_) {
            throw std::bad_alloc();
        }
        skip_list_->header = NEW_LEVEL_NODE(MAX_LEVEL);
        if (nullptr == skip_list_->header) {
            throw std::bad_alloc();
        }
        for (int i = 0;i < MAX_LEVEL;i++) {
            skip_list_->header->forwards[i] = nullptr;
        }
    }
    CSkipList(const CSkipList &) = delete;
    CSkipList & operator = (const CSkipList &) = delete;
    ~CSkipList() {
        free_list();
    }
public:
    static inline int get_random_level() {
        int level = rand() % (MAX_LEVEL +1);
        return level;
    }
public:
    bool insert(const KeyType &key, const ValueType &value) {
        Node update[MAX_LEVEL] = {0};
        if (false == locate_insert_location(key, update)) {
            return false;
        }
        int level = expand_level(update);
        insert_node(key, value, level, update);
        return true;
    }
    bool search(const KeyType &key, ValueType &value) {
        Node node = skip_list_->header;
        Node index_node = nullptr;
        for (int i = skip_list_->level - 1;i >= 0;i--) {
            while ((index_node = node->forwards[i]) && (index_node->key <= key)) {
                if (key == index_node->key) {
                    value = index_node->value;
                    return true;
                }
                node = index_node;
            }
        }
        return false;
    }
private:
    bool locate_insert_location(const KeyType &key, Node *update) {
        Node node = skip_list_->header;
        Node index_node = nullptr;
        for (int i = skip_list_->level - 1;i >= 0;i--) {
            while ((index_node = node->forwards[i]) && (index_node->key < key)) {
                node = index_node;
            }
            update[i] = node;
        }
        node = node->forwards[0];
        if (node != nullptr && key == node->key) {
            std::cerr << key << " has already existed." << std::endl;
            return false;
        }
        return true;
    }
    int expand_level(Node *update) {
        int level = get_random_level();
        int &cur_level = skip_list_->level;
        if (level > cur_level) {
            for (int i = cur_level;i < level;i++) {
                update[i] = skip_list_->header;
            }
            cur_level = level;
        }
        return level;
    }
    void insert_node(const KeyType &key, const ValueType &value, int level, Node *update) {
        int &cur_level = skip_list_->level;
        Node new_node = NEW_LEVEL_NODE(level);
        if (nullptr == new_node) {
             throw std::bad_alloc();
        }
        new_node->key = key;
        new_node->value = value;
        for (int i = level - 1;i >= 0;i--) {
            new_node->forwards[i] = update[i]->forwards[i];
            update[i]->forwards[i] = new_node;    // cost time
        }
        ++size_;
    }
    void free_list() {
        if (nullptr == skip_list_) {
            return;
        }
        Node p = skip_list_->header;
        Node q = nullptr;
        while (p != nullptr) {
            q = p->forwards[0];
            free(p);
            p = q;
        }
        free(skip_list_);
        skip_list_ = nullptr;
        size_ = 0;
    }
private:
    static const int MAX_LEVEL = 10;
private:
    List skip_list_ = nullptr;
    int size_ = 0;
};
const int N = 100;
void test_map() {
    std::map<int, int>mm;
    for (int i = 0;i < N;i++) {
        mm[i] = i;
    }
    for (int i = 0;i < N;i++) {
        if (mm.find(i) != end(mm)) {
        }
    }
}
void test_skip_list() {
    CSkipList skipList;
    for (int i = 0;i < N;i++) {
        skipList.insert(i, i);
    }
    int value = 0;
    for (int i = 0;i < N;i++) {
        if (true == skipList.search(i, value)) {
            // std::cout << "value = " << value << std::endl;
        }
    }
}
int main() {
    // test_map();     // 9.559s
    test_skip_list();   // > 4m50.766s

    return 0;
}