#ifndef SKIPLIST_H
#define SKIPLIST_H

#include <ctime>
#include <initializer_list>
#include <iostream>
#include <random>

template <typename Key>
class Skiplist {
public:
 struct Node {
 Node(Key k) : key(k) {}
 Key key;
 Node* next[1]; // C語言中的柔性數(shù)組技巧
 };

private:
 int maxLevel;
 Node* head;

 enum { kMaxLevel = 12 };

public:
 Skiplist() : maxLevel(1)
 {
 head = newNode(0, kMaxLevel);
 }

 Skiplist(std::initializer_list<Key> init) : Skiplist()
 {
 for (const Key& k : init)
 {
  insert(k);
 }
 }

 ~Skiplist()
 {
 Node* pNode = head;
 Node* delNode;
 while (nullptr != pNode)
 {
  delNode = pNode;
  pNode = pNode->next[0];
  free(delNode); // 對應(yīng)malloc
 }
 }

 // 禁止拷貝構(gòu)造和賦值
 Skiplist(const Skiplist&) = delete;
 Skiplist& operator=(const Skiplist&) = delete;
 Skiplist& operator=(Skiplist&&) = delete;

private:
 Node* newNode(const Key& key, int level)
 {
 /*
 * 開辟sizeof(Node) + sizeof(Node*) * (level - 1)大小的空間
 * sizeof(Node*) * (level - 1)大小的空間是給Node.next[1]指針數(shù)組用的
 * 為什么是level-1而不是level，因為sizeof(Node)已包含一個Node*指針的空間
 */ 
 void* node_memory = malloc(sizeof(Node) + sizeof(Node*) * (level - 1));
 Node* node = new (node_memory) Node(key);
 for (int i = 0; i < level; ++i)
  node->next[i] = nullptr;

 return node;
 }
 /*
 * 隨機函數(shù)，范圍[1, kMaxLevel]，越小概率越大
 */ 
 static int randomLevel()
 {
 int level = 1;
 while (rand() % 2 && level < kMaxLevel)
  level++;

 return level;
 }

public:
 Node* find(const Key& key)
 {
 // 從最高層開始查找，每層查找最后一個小于key的前繼節(jié)點，不斷縮小范圍
 Node* pNode = head;
 for (int i = maxLevel - 1; i >= 0; --i)
 {
  while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
  {
  pNode = pNode->next[i];
  }
 }

 // 如果第一層的pNode[0]->key == key，則返回pNode->next[0]，即找到key
 if (nullptr != pNode->next[0] && pNode->next[0]->key == key)
  return pNode->next[0];

 return nullptr;
 }

 void insert(const Key& key)
 {
 int level = randomLevel();
 Node* new_node = newNode(key, level);
 Node* prev[kMaxLevel];
 Node* pNode = head;
 // 從最高層開始查找，每層查找最后一個小于key的前繼節(jié)點
 for (int i = level - 1; i >= 0; --i)
 {
  while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
  {
  pNode = pNode->next[i];
  }
  prev[i] = pNode;
 }
 // 然后每層將新節(jié)點插入到前繼節(jié)點后面
 for (int i = 0; i < level; ++i)
 {
  new_node->next[i] = prev[i]->next[i];
  prev[i]->next[i] = new_node;
 }

 if (maxLevel < level) // 層數(shù)大于最大層數(shù)，更新最大層數(shù)
  maxLevel = level;
 }

 void erase(const Key& key)
 {
 Node* prev[maxLevel];
 Node* pNode = head;
 // 從最高層開始查找，每層查找最后一個小于key的前繼節(jié)點
 for (int i = maxLevel - 1; i >= 0; --i)
 {
  while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
  pNode = pNode->next[i];
  prev[i] = pNode;
 }
 
 // 如果找到key，
 if (pNode->next[0] != nullptr && pNode->next[0]->key == key)
 {
  Node *delNode = pNode->next[0];
  // 從最高層開始，如果當(dāng)前層的next節(jié)點的值等于key，則刪除next節(jié)點
  for (int i = maxLevel - 1; i >= 0; --i)
  {
  if (prev[i]->next[i] != nullptr && key == prev[i]->next[i]->key)
   prev[i]->next[i] = prev[i]->next[i]->next[i];
  }
  free(delNode); // 最后銷毀pNode->next[0]節(jié)點
 }
 
 // 如果max_level>1且頭結(jié)點的next指針為空，則該層已無數(shù)據(jù)，max_level減一
 while (maxLevel > 1 && head->next[maxLevel] == nullptr)
 {
  maxLevel--;
 }
 }
};

#endif