// skipList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <windows.h>
#include <string>




namespace ZStl
{

    template <class T>
    class SkipList
    {
        template <class T>
        struct SLNode 
        {
        public:
            T Data;                     /* user's data */
            SLNode<T> *Forward[1];   /* skip list forward pointer */
        };


        SLNode<T> *NIL;                  /* invalid node ptr */
        SLNode<T> *Hdr;                  /* List Header */
        SLNode<T>** update; //temporary update list
        int ListLevel;              /* current level of list */
        int maxLevel;

    public:

        SLNode<T>* Begin()
        {
            return Hdr;
        }

        class Iterator
        {
            SLNode<T>* hdr;
            SLNode<T>* current;
        public:

            Iterator(SLNode<T>* hdr)
            {
                this->hdr = hdr;
                this->current = this->hdr;
            }

            Iterator& operator =(SLNode<T>* hdr)
            {
                this->hdr = hdr;
                this->current = this->hdr;
                return (*this);
            }

            bool Next()
            {
                return ((current=current->Forward[0]) != hdr);
            }

            operator T(){return current->Data;}
        };

        

        ~SkipList()
        {
            delete[] update;
            Clear();
            delete[] this->Hdr;
        }

        /**************************
        *  initialize skip list  *
        **************************/
        SkipList(int maxLevel) 
        {
            this->maxLevel = maxLevel;
            
            if ((this->Hdr = new SLNode<T>[this->maxLevel+1]) == 0) 
            {
                printf ("insufficient memory (InitList)\n");
                exit(1);
            }

            this->NIL = this->Hdr;

            for (int i = 0; i <= maxLevel; i++)
            {
                this->Hdr->Forward[i] = NIL;
            }

            this->ListLevel = 0;

            this->update = new SLNode<T>*[this->maxLevel+1];
        }

        SLNode<T> *InsertNode(T Data) 
        {
            int i;
            /***********************************************
            *  allocate node for Data and insert in list  *
            ***********************************************/

            /* find where data belongs */
            SLNode<T> *X = this->Hdr;
            for (i = this->ListLevel; i >= 0; i--) 
            {
                while (X->Forward[i] != NIL && (X->Forward[i]->Data < Data))
                {
                    X = X->Forward[i];
                }
                update[i] = X;
            }
            
            X = X->Forward[0];
            
            if (X != NIL && (X->Data == Data)) 
            {
                return X;
            }

            /* determine level */
            int NewLevel = 0;

            while (rand() < RAND_MAX/2)
            {
                NewLevel++;
            }
            if (NewLevel > this->maxLevel) 
                NewLevel = this->maxLevel;

            if (NewLevel > this->ListLevel) 
            {
                for (i = this->ListLevel + 1; i <= NewLevel; i++)
                {
                    update[i] = NIL;
                }
                this->ListLevel = NewLevel;
            }

            /* make new node */
            if ((X = new SLNode<T>[NewLevel+1]) == 0) 
            {
                printf ("insufficient memory (InsertNode)\n");
                exit(1);
            }
            X->Data = Data;

            /* update forward links */
            for (i = 0; i <= NewLevel; i++) 
            {
                X->Forward[i] = update[i]->Forward[i];
                update[i]->Forward[i] = X;
            }

            return X;
        }

        void DeleteNode(T Data) 
        {
            int i;
            /*******************************************
            *  delete node containing Data from list  *
            *******************************************/

            /* find where data belongs */
            SLNode<T> *X = this->Hdr;
            for (i = this->ListLevel; i >= 0; i--) 
            {
                while (X->Forward[i] != NIL && (X->Forward[i]->Data < Data))
                {
                    X = X->Forward[i];
                }
                update[i] = X;
            }

            X = X->Forward[0];
            
            if (X == NIL || !(X->Data == Data))
            {
                return;
            }

            /* adjust forward pointers */
            for (i = 0; i <= this->ListLevel; i++) 
            {
                if (update[i]->Forward[i] != X)
                {
                    break;
                }
                update[i]->Forward[i] = X->Forward[i];
            }

            delete[] X;

            /* adjust header level */
            while ((this->ListLevel > 0) && (this->Hdr->Forward[this->ListLevel] == NIL))
            {
                this->ListLevel--;
            }

        }

        SLNode<T> *FindNode(T Data) 
        {
            /*******************************
            *  find node containing Data  *
            *******************************/
            SLNode<T> *X = this->Hdr;
            for (int i = this->ListLevel; i >= 0; i--) 
            {
                while (X->Forward[i] != NIL && (X->Forward[i]->Data < Data))
                {
                    X = X->Forward[i];
                }
            }
            
            X = X->Forward[0];
            
            if (X != NIL && (X->Data == Data))
            {
                return (X);
            }

            return NULL;
        }


        void Clear()
        {
            SLNode<T> *Next=NIL;
            SLNode<T> *X = this->Hdr->Forward[0];

            while(X!=NIL)
            {
                Next=X->Forward[0];
                delete[] X;
                X=Next;
            }
            
            for(int x=0;x<=this->maxLevel;x++)
                this->Hdr->Forward[x] = NIL;

            ListLevel=0;
        }
    };
} 





class ZString
{
public:
    std::string val;

    ZString(){}
    ZString(const char *val)
    {
        this->val=val;
    }

    inline operator const char *(){return val.c_str();}

    bool operator <(ZString &b)
    {
        return strcmp(val.c_str(),b.val.c_str()) < 0;
    }

    bool operator ==(ZString &b)
    {
        return strcmp(val.c_str(),b.val.c_str()) == 0;
    }
};




int _tmain(int argc, _TCHAR* argv[])
{
 
    ZStl::SkipList<int> intList(10);

    for(int x=0;x<150;x++)
    {
        intList.InsertNode(rand()%(x+1));
    }

    ZStl::SkipList<int>::Iterator intListIter(intList.Begin());
    
    printf("int list:\n");
    while(intListIter.Next())
    {
        printf("int output\t%d\n",(int)intListIter);
    }


    ZStl::SkipList<ZString> strList(10);

    strList.InsertNode("itchy");
    strList.InsertNode("scratchy");
    strList.InsertNode("scooby");
    strList.InsertNode("hank");
    strList.InsertNode("bobby");
    strList.InsertNode("lisa");
    strList.InsertNode("bart");
    strList.InsertNode("kenny");
    strList.InsertNode("millhouse");
    

    ZStl::SkipList<ZString>::Iterator strListIter(strList.Begin());
    
    while(strListIter.Next())
    {
        printf("string output\t%s\n",((ZString)strListIter).val.c_str());
    }

	return 0;
}