#include <iostream>
#include <string.h>
#include <cstdlib>
#include <stdlib.h>
#include <ctime>
#include <conio.h>
#include <stdio.h>


using namespace std;
//int LMAX=10;

struct skiplist{
        int key;
        int height;
        char litera;
        struct skiplist **next;
};

int random_level(int LMAX)
{
        int level=1;
        while((rand()%100<0.5*100)&(level<LMAX))
        {
                level++;
        }
        return(level);
}


bool insert(skiplist* head, int new_key, int LMAX)
{
        skiplist* x=head;
        int height=random_level(LMAX);
        skiplist* update[height];


        for(int i=height-1;i>=0;i--)
        {
                while(x->next[i]->key < new_key)
                {
                        x=x->next[i];
                }
                update[i]=x;

        }
        x=x->next[0];
        if(x->key==new_key)
        {
                x->litera='D';
                return false;
        }
        skiplist* new_node = new skiplist;
        new_node->next=new skiplist*[height];

        new_node->key=new_key;
        new_node->height=height;

        for(int i=0; i<new_node->height;i++)
        {
                new_node->next[i]=update[i]->next[i];
                update[i]->next[i]=new_node;
                new_node->litera='T';
        }
        return true;
}

skiplist *createSkipList(int LMAX)
{
        skiplist* skip = new skiplist;
        skiplist* tail = new skiplist;
        skip->next=new skiplist*[LMAX];
        tail->next=new skiplist*[LMAX];
        int height=LMAX;

        skip->key=-2147483647;
        skip->height=LMAX;

        tail->key=2147483647;
        tail->height=LMAX;
        for(int i=0;i<height;i++)
        {
            skip->next[i]=tail;
            tail->next[i]=nullptr;
        }
        return skip;
}

bool search(skiplist* head, int key)
{
        skiplist* x = new skiplist;
        x = head;
        int height=x->height;
        for(int i=height-1;i>=0;i--)
        {
                while(x->next[i]->key<key)
                {
                        x=x->next[i];
                }
        }
        x=x->next[0];
        if(x->key==key)
        {
                return(true);
        }
        return(false);
}

void insert_all(skiplist* head, int N, int LMAX)
{
        int liczba;
        for(int i=0; i<N;i++)
        {
                do
                {
                        liczba = (rand() % 99900)+ 99;
                }while(insert(head,liczba, LMAX)==false);
        }
}


string usun(skiplist* head, int key, int LMAX)
{
        skiplist* x=head;
        skiplist* update[10];
        for(int i=LMAX-1; i>=0;i--)
        {
                while(x->next[i]->key<key)
                {
                        x=x->next[i];
                }
                update[i]=x;
        }
        x=x->next[0];
        if(x->key>key)
        {
                return("blad");
        }
        for(int i=0; i<x->height; i++)
        {
                update[i]->next[i]=x->next[i];
        }
        delete(x);
        return("OK");
}

string delete_all(skiplist* head)
{
        skiplist* element=head;
        skiplist* tmp;

        while(element)
        {
                tmp=element->next[0];
                delete(element->next);
                delete(element);
                element=tmp;
        }

}

void wypisz(skiplist* head, int Y, int height)
{
        skiplist* x=head;
        /*for(int i=0; i<Y; i++)
        {
                if(x->key==-2147483647)
                {
                        x=x->next[0];
                }
                if(x->height>=height)
                {
                      cout<< x->key<< endl;
                      x=x->next[0];
                      continue;
                }
                else
                {
                        while(x->height<height)
                        {
                                x=x->next[0];
                        }
                        cout<< x->key<<endl;
                        x=x->next[0];
                }


        }*/
        for(int i=0; i<Y; i++)
        {
                x=x->next[height-1];
                cout<<x->key<<endl;
        }


}

int liczba_wezlow(skiplist* head)
{
        int licznik=1;
        skiplist* x=head;
        while(x->next[0]!=nullptr)
        {
                x=x->next[0];
                licznik++;
        }
        licznik=licznik-2;
        return licznik;
}



int main()
{
        int LMAX=7;
        //2001 7 13666 4 7 -1 100001
        srand((unsigned int)time(NULL));
        int N=2001;
        int k1=13666;
        int k2=4;
        int k3=7;
        int k4=-1;
        int k5=100001;


        clock_t begin, end;
        double time_spent;
        begin = clock();

        skiplist* head= new skiplist;

        head=createSkipList(LMAX);

        insert_all(head,N,LMAX);


        if(search(head,101)==false)
        {
                cout<<"Nie znaleziono"<<endl;
        }
        else
        {
                cout<<"Znaleziono klucz k1"<<endl;
        }



        search(head,100);
        insert(head,100,LMAX);

        skiplist* wyswietl=head;
        for(int i=0;i<13;i++)
        {
                cout<<wyswietl->key<<" "<<wyswietl->litera<<" "<< wyswietl->height<<" "<<" "<<wyswietl<<" "<< wyswietl->next[0]<<" ";
                if(wyswietl->height>=2)
                {
                        cout<<wyswietl->next[2]<<" ";
                }
                if(wyswietl->height>=2)
                {
                        cout<<wyswietl->next[1]<<endl;
                }
                wyswietl=wyswietl->next[0];
        }
        cout << "" <<endl;

        usun(head,100,LMAX);


        //wypisz(head, 10, 3);

        wyswietl=head;



        int licznik;

        licznik=liczba_wezlow(head);

        delete_all(head);

        cout << "Liczba wezlow:" << licznik << endl;

        time_spent = (double)(end-begin) / CLOCKS_PER_SEC;
        cout << "Czas wykonania:" << time_spent << endl;



        return 0;
}