#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <cstring>
#include <random>
#include <ctime>
using namespace std;

/**
 * Ìø±íµÄÒ»ÖÖÊµÏÖ·½·¨¡£
 * Ìø±íÖÐ´æ´¢µÄÊÇÕýÕûÊý£¬²¢ÇÒ´æ´¢µÄÊÇ²»ÖØ¸´µÄ¡£
 *
 * Ìø±íµÄC++°æ±¾.
 * ·­ÒëJAVA°æ±¾ Ô­×÷Õß Author£ºZHENG
 * 
 * Author£ºpuhuaqiang
 * 
 *  Ìø±í½á¹¹:
 * 
 *  µÚK¼¶           1           9
 *  µÚK-1¼¶         1     5     9
 *  µÚK-2¼¶         1  3  5  7  9
 *  ...             ....
 *  µÚ0¼¶(Ô­Ê¼Á´±í)  1  2  3  4  5  6  7  8  9
 */

const int MAX_LEVEL = 16;

/**
 * @brief ½Úµã
*/
class CNode
{
public:
    CNode();
    ~CNode();

    std::string toString();
    /**
     * @brief »ñÈ¡Ë÷ÒýÁ´±í
    */
    CNode** GetIdxList();

    /**
     * @brief ÉèÖÃÊý¾Ý
    */
    void SetData(int v);
    /**
     * @brief »ñÈ¡Êý¾Ý
    */
    int GetData();
    /**
    * @brief ÉèÖÃ×î´óË÷Òý¼¶±ð
    */
    void SetLevel(int l);
private:
    /**µ±Ç°½ÚµãµÄÖµ*/
    int m_data;
    /** 
     * µ±Ç°½ÚµãµÄÃ¿¸öµÈ¼¶µÄÏÂÒ»¸ö½Úµã.
     * µÚ2¼¶ N1 N2
     * µÚ1¼¶ N1 N2
     * Èç¹ûN1ÊÇ±¾½Úµã,Ôò m_lpForwards[x] ±£´æµÄÊÇN2
     * 
     * [0] ¾ÍÊÇÔ­Ê¼Á´±í.
     */
    CNode* m_lpForwards[MAX_LEVEL];
    /**µ±Ç°½ÚµãµÄËùÔÚµÄ×î´óË÷Òý¼¶±ð*/
    int m_iMaxLevel;
};

/**
 * @brief Ìø±í
*/
class CSkipList
{
public:
    CSkipList();
    ~CSkipList();
    /**
     * @brief ²éÕÒÖ¸¶¨µÄÖµµÄ½Úµã
     * @param v ÕýÕûÊý
    */
    CNode* Find(int v);
    /**
     * @brief ²åÈëÖ¸¶¨µÄÖµ
     * @param v ÕýÕûÊý
    */
    void Insert(int v);
    /**
     * @brief É¾³ýÖ¸¶¨µÄÖµµÄ½Úµã
     * @param v ÕýÕûÊý
    */
    int Delete(int v);
    void PrintAll();
    /**
     * @brief ´òÓ¡Ìø±í½á¹¹
     * @param l µÈÓÚ-1Ê±´òÓ¡ËùÓÐ¼¶±ðµÄ½á¹¹ >=0Ê±´òÓ¡Ö¸¶¨¼¶±ðµÄ½á¹¹
    */
    void PrintAll(int l);
    /**
     * @brief ²åÈë½ÚµãÊ±,µÃµ½²åÈëK¼¶µÄËæ»úº¯Êý
     * @return K
    */
    int RandomLevel();

private:
    int levelCount;
    /**
     * Á´±í
     * ´øÍ·/ÉÚËù(½Úµã)
    */
    CNode* m_lpHead;
};

int main()
{
    CSkipList skipList;
    /// ²åÈëÔ­Ê¼Öµ
    for(int i=1; i< 50; i++){
        if((i%3) == 0){
            skipList.Insert(i);
        }
    }
    for(int i=1; i< 50; i++){
        if((i%3) == 1){
            skipList.Insert(i);
        }
    }
    skipList.PrintAll();
    std::cout<<std::endl;
    /// ´òÓ¡ËùÓÐµÈ¼¶½á¹¹
    skipList.PrintAll(-1);
    /// ²éÕÒ
    std::cout<<std::endl;
    CNode* lpNode = skipList.Find(27);
    if(NULL != lpNode){
        std::cout<<"²éÕÒÖµÎª27µÄ½Úµã,ÕÒµ½¸Ã½Úµã,½ÚµãÖµ:"<<lpNode->GetData()<<std::endl;
    }else{
        std::cout<<"²éÕÒÖµÎª27µÄ½Úµã,Î´ÕÒµ½¸Ã½Úµã"<<std::endl;
    }
    /// É¾³ý
    std::cout<<std::endl;
    int ret = skipList.Delete(46);
    if(0 == ret){
        std::cout<<"²éÕÒÖµÎª46µÄ½Úµã,ÕÒµ½¸Ã½Úµã,²¢É¾³ý³É¹¦"<<std::endl;
    }else{
        std::cout<<"²éÕÒÖµÎª46µÄ½Úµã,ÕÒµ½¸Ã½Úµã,É¾³ýÊ§°Ü"<<std::endl;
    }
    std::cout<<std::endl;
    //´òÓ¡ËùÓÐµÈ¼¶½á¹¹
    skipList.PrintAll(-1);
    std::cin.ignore();
    return 0;
}

CNode::CNode()
{
    m_data = -1;
    m_iMaxLevel = 0;
    for(int i=0; i<MAX_LEVEL; i++){
        m_lpForwards[i] = NULL;
    }
}
CNode::~CNode()
{

}
CNode** CNode::GetIdxList()
{
    return m_lpForwards;
}

void CNode::SetData(int v)
{
    m_data = v;
}
int CNode::GetData()
{
    return m_data;
}
void CNode::SetLevel(int l)
{
    m_iMaxLevel = l;
}
std::string CNode::toString()
{
    char tmp[32];
    std::string ret;

    ret.append("{ data: ");
    sprintf(tmp, "%d", m_data);
    ret.append(tmp);
    ret.append("; levels: ");
    sprintf(tmp, "%d", m_iMaxLevel);
    ret.append(tmp);
    ret.append(" }");
    return ret;
}

CSkipList::CSkipList()
{
    levelCount = 1;
    m_lpHead = new CNode();
}
CSkipList::~CSkipList()
{

}
CNode* CSkipList::Find(int v)
{
    CNode* lpNode = m_lpHead;
    /**
     * ´Ó ×î´ó¼¶Ë÷ÒýÁ´±í¿ªÊ¼²éÕÒ.
     * K -> k-1 -> k-2 ...->0
    */
    for(int i=levelCount-1; i>=0; --i){
        /**
         * ²éÕÒÐ¡ÓÚvµÄ½Úµã(lpNode).
        */
        while((NULL != lpNode->GetIdxList()[i]) && (lpNode->GetIdxList()[i]->GetData() < v)){
            lpNode = lpNode->GetIdxList()[i];
        }
    }
    /**
     * lpNode ÊÇÐ¡ÓÚvµÄ½Úµã, lpNodeµÄÏÂÒ»¸ö½Úµã¾ÍµÈÓÚ»ò´óÓÚvµÄ½Úµã
    */
    if((NULL != lpNode->GetIdxList()[0]) && (lpNode->GetIdxList()[0]->GetData() == v)){
        return lpNode->GetIdxList()[0];
    }
    return NULL;
}
void CSkipList::Insert(int v)
{
    /// ÐÂ½Úµã
    CNode* lpNewNode = new CNode();
    if(NULL == lpNewNode){
        return;
    }

    /**
     * ÐÂ½Úµã×î´ó·Ö²¼ÔÚµÄË÷ÒýÁ´±íµÄÉÏÏÞ
     * Èç¹û·µ»Ø 3,Ôò ÐÂµÄ½Úµã»áÔÚË÷Òý1¡¢2¡¢3ÉÏµÄÁ´±í¶¼´æÔÚ
    */
    int level = RandomLevel();
    lpNewNode->SetData(v);
    lpNewNode->SetLevel(level);

    /**
     * ÁÙÊ±Ë÷ÒýÁ´±í
     * Ö÷ÒªÊÇµÃµ½ÐÂµÄ½ÚµãÔÚÃ¿¸öË÷ÒýÁ´±íÉÏµÄÎ»ÖÃ
    */
    CNode *lpUpdateNode[level];
    for(int i=0; i<level; i++){
        /// Ã¿¸öË÷ÒýÁ´±íµÄÍ·½Úµã
        lpUpdateNode[i] =m_lpHead;
    }
    CNode* lpFind = m_lpHead;
    for(int i= level-1; i >= 0; --i){
        /**
         * ²éÕÒÎ»ÖÃ
         *   eg.  µÚ1¼¶  1  7  10
         *   Èç¹û²åÈëµÄÊÇ 6
         *   lpFind->GetIdxList()[i]->GetData() : ±íÊ¾½ÚµãlpFindÔÚµÚ1¼¶Ë÷ÒýµÄÏÂÒ»¸ö½ÚµãµÄÊý¾Ý
         *   µ± "lpFind->GetIdxList()[i]->GetData() < v"²»³ÉÁ¢µÄÊ±ºò,
         *   ÐÂ½Úµã¾ÍÒª²åÈëµ½ lpFind½ÚµãµÄºóÃæ, lpFind->GetIdxList()[i] ½ÚµãµÄÇ°Ãæ
         *   ¼´ÔÚÕâÀï lpFind¾ÍÊÇ1  lpFind->GetIdxList()[i] ¾ÍÊÇ7
        */
        while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
            lpFind = lpFind->GetIdxList()[i];
        }
        /// lpFind ÊÇÐÂ½ÚµãÔÚ µÚi¼¶Ë÷ÒýÁ´±íµÄºóÒ»¸ö½Úµã
        lpUpdateNode[i] = lpFind;
    }

    for(int i=0; i<level; ++i){
        /**
         * ÖØÐÂÉèÖÃÁ´±íÖ¸ÕëÎ»ÖÃ
         *   eg  µÚ1¼¶Ë÷Òý 1  7  10
         *      ²åÈë6.
         *      lpUpdateNode[i] ½ÚµãÊÇ1; lpUpdateNode[i]->GetIdxList()[i]½ÚµãÊÇ7
         *  
         *  Õâ2¾ä´úÂë¾ÍÊÇ °Ñ6·ÅÔÚ 1ºÍ7Ö®¼ä
        */
        lpNewNode->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i];
        lpUpdateNode[i]->GetIdxList()[i] = lpNewNode;
    }
    if(levelCount < level){
        levelCount = level;
    }
}
int CSkipList::Delete(int v)
{
    int ret = -1;
    CNode *lpUpdateNode[levelCount];
    CNode *lpFind = m_lpHead;
    for(int i=levelCount-1; i>= 0; --i){
        /**
         * ²éÕÒÐ¡ÓÚvµÄ½Úµã(lpFind).
        */
        while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
            lpFind = lpFind->GetIdxList()[i];
        }
        lpUpdateNode[i] = lpFind;
    }
    /**
     * lpFind ÊÇÐ¡ÓÚvµÄ½Úµã, lpFindµÄÏÂÒ»¸ö½Úµã¾ÍµÈÓÚ»ò´óÓÚvµÄ½Úµã
    */
    if((NULL != lpFind->GetIdxList()[0]) && (lpFind->GetIdxList()[0]->GetData() == v)){
        for(int i=levelCount-1; i>=0; --i){
            if((NULL != lpUpdateNode[i]->GetIdxList()[i]) && (v == lpUpdateNode[i]->GetIdxList()[i]->GetData())){
                lpUpdateNode[i]->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i]->GetIdxList()[i];
                ret = 0;
            }
        }
    }
    return ret;
}
void CSkipList::PrintAll()
{
    CNode* lpNode = m_lpHead;
    while(NULL != lpNode->GetIdxList()[0]){
        std::cout<<lpNode->GetIdxList()[0]->toString().data()<<std::endl;
        lpNode = lpNode->GetIdxList()[0];
    }
}
void CSkipList::PrintAll(int l)
{
    for(int i=MAX_LEVEL-1; i>=0;--i){
        CNode* lpNode = m_lpHead;
        std::cout<<"µÚ"<<i<<"¼¶:"<<std::endl;
        if((l < 0) || ((l >= 0) && (l == i))){
            while(NULL != lpNode->GetIdxList()[i]){
                std::cout<<lpNode->GetIdxList()[i]->GetData()<<" ";
                lpNode = lpNode->GetIdxList()[i];
            }
            std::cout<<std::endl;
            if(l >= 0){
                break;
            }
        }
    }
}
int GetRandom()
{
    static int _count = 1;
	std::default_random_engine generator(time(0) + _count);
	std::uniform_int_distribution<int> distribution(1,99999/*0x7FFFFFFF*/);
	int dice_roll = distribution(generator);
    _count += 100;
	return dice_roll;
}
int CSkipList::RandomLevel()
{
    int level = 1;
    for(int i=1; i<MAX_LEVEL; ++i){
        if(1 == (GetRandom()%3)){
            level++;
        }
    }
    return level;
}