#include<iostream>
#include<cstdlib>
#include<ctime>
#include<limits>

using namespace std;

template<class T>
class SkipList{
    private:
        class SkipNode{
            public:
                T* key;
                SkipNode** forward;
                int level;
                SkipNode(T* key, int maxlvl, int lvl){
                    forward = new SkipNode*[maxlvl];
                    this->key=key;
                    level=lvl;
                }
                ~SkipNode(){}
        };

        SkipNode *header,*NIL;
        float probability;
        int level;
        int MaxLevel;

        int randomLevel(){
            int lvl = 0;
            while( (float(rand())/RAND_MAX < probability) && (lvl < MaxLevel-1) )
                lvl++;
            return lvl;
        }

    public:
        SkipList(float probability, int maxlvl){
            this->probability = probability;
            MaxLevel = maxlvl;
            srand(time(0));
            header=new SkipNode(NULL,MaxLevel,0);
            T* maxValue = new T;
            *maxValue = numeric_limits<T>::max();
            NIL = new SkipNode(maxValue,MaxLevel,MaxLevel);
            level=0;
            for(int i=0; i<MaxLevel; i++){
                header->forward[i]=NIL;
            }
        }

        ~SkipList(){
            delete header;
            delete NIL;
        }

        SkipNode* search(T* key){
            SkipNode* cursor = header;
            for(int i=level; i>=0; i--)
                while(*(cursor->forward[i]->key) < (*key))
                    cursor=cursor->forward[0];
            cursor=cursor->forward[0];
            if(*(cursor->key) == *key)
                return cursor;
            return NULL;
        }

        SkipList* insert(T* key){
            SkipNode* cursor = header;
            SkipNode* update[MaxLevel];
            for(int i=level; i>=0; i--){
                while(*(cursor->forward[i]->key) < *(key))
                    cursor=cursor->forward[i];
                update[i]=cursor;
            }
            cursor=cursor->forward[0];
            if(*(cursor->key) == *(key)) //Node already inserted
                return this;
            int lvl = randomLevel();
            if(lvl > level){
                for(int i=level; i<=lvl; i++)
                    update[i]=header;
                level=lvl;
            }
            SkipNode* x = new SkipNode(key,MaxLevel,lvl);
            for(int i=0; i<=lvl; i++){
                x->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = x;
            }
            return this;
        }

        SkipList* erase(T* key){
            SkipNode* cursor = header;
            SkipNode* update[MaxLevel];
            for(int i=level; i>=0; i--){
                while(*(cursor->forward[i]->key) < *(key))
                    cursor=cursor->forward[i];
                update[i]=cursor;
            }
            cursor=cursor->forward[0];
            if(*(cursor->key) == *(key)){
                for(int i=0; i<=level && update[i]->forward[i] == cursor; i++){
                    update[i]->forward[i] = cursor->forward[i];
                }
                delete cursor;
                while(level>0 && header->forward[level]==NIL){
                    level=level-1;
                }
            }
            return this;
        }

        SkipList* print(){
            SkipNode* cursor = header->forward[0];
            int i=1;
            while (cursor != NIL) {
            cout << "(" << *cursor->key << "," << cursor->level << ") ";
            cursor = cursor->forward[0];
            if(i%15==0) cout << endl; i++;
            }
            cout << endl;
            return this;
        }
};

main(){
    SkipList<int>* list = new SkipList<int>(0.80, 10);
    int a=2;
    int b=3;
    list->insert(&a)->insert(&b);
    list->print()->erase(&a)->erase(&b)->insert(&a)->print();
    int v[100];
    for(int i=0; i<100; i++){
        v[i]=rand()%100;
        list->insert(&v[i]);
    }
    list->print();
    cout << endl;
    cout << *list->search(&a)->key;
    delete list;
}