#include "dsl.h"
#include <stdlib.h>
#include "fatal.h"


/* START: fig12_23.txt */
        struct SkipNode
        {
            ElementType Element;
            SkipList    Right;
            SkipList    Down;
        };

        static Position Bottom = NULL;  /* Needs initialization */
        static Position Tail   = NULL;  /* Needs initialization */

        /* Initialization procedure */

        SkipList
        Initialize( void )
        {
            SkipList L;

            if( Bottom == NULL )
            {
                Bottom = malloc( sizeof( struct SkipNode ) );
                if( Bottom == NULL )
                    FatalError( "Out of space!!!" );
                Bottom->Right = Bottom->Down = Bottom;

                Tail = malloc( sizeof( struct SkipNode ) );
                if( Tail == NULL )
                    FatalError( "Out of space!!!" );
                Tail->Element = Infinity;
                Tail->Right = Tail;
            }

            /* Create the header node */
            L = malloc( sizeof( struct SkipNode ) );
            if( L == NULL )
                FatalError( "Out of space!!!" );
            L->Element = Infinity;
            L->Right = Tail;
            L->Down = Bottom;

            return L;
        }
/* END */

        void
        Output( ElementType Element )
        {
            printf( "%d\n", Element );
        }

        /* Memory reclamation is left as an exercise */
        /* Hint: Delete from top level to bottom level */
        SkipList
        MakeEmpty( SkipList L )
        {
            L->Right = Tail;
            L->Down = Bottom;
            return L;
        }

/* START: fig12_24.txt */
        /* Return Position of node containing Item, */
        /* or Bottom if not found */

        Position
        Find( ElementType Item, SkipList L )
        {
            Position Current = L;

            Bottom->Element = Item;
            while( Item != Current->Element )
                if( Item < Current->Element )
                    Current = Current->Down;
                else
                    Current = Current->Right;

            return Current;
        }
/* END */

        Position
        FindMin( SkipList L )
        {
            Position Current = L;

            while( Current->Down != Bottom )
                Current = Current->Down;

            return Current;
        }

        Position
        FindMax( SkipList L )
        {
            Position Current = L;

            while( Current->Right->Right != Tail ||
                   Current->Down != Bottom )
            {
                if( Current->Right->Right != Tail )
                    Current = Current->Right;
                else
                    Current = Current->Down;
            }

            return Current;
        }

/* START: fig12_25.txt */
        SkipList
        Insert( ElementType Item, SkipList L )
        {
            Position Current = L;
            Position NewNode;

            Bottom->Element = Item;
            while( Current != Bottom )
            {
                while( Item > Current->Element )
                    Current = Current->Right;

                /* If gap size is 3 or at bottom level */
                /* and must insert, then promote middle element */
                if( Current->Element >
                          Current->Down->Right->Right->Element )
                {
                    NewNode = malloc( sizeof( struct SkipNode ) );
                    if( NewNode == NULL )
                        FatalError( "Out of space!!!" );
                    NewNode->Right = Current->Right;
                    NewNode->Down = Current->Down->Right->Right;
                    Current->Right = NewNode;
                    NewNode->Element = Current->Element;
                    Current->Element = Current->Down->Right->Element;
                }
                else
                    Current = Current->Down;
            }

            /* Raise height of DSL if necessary */
            if( L->Right != Tail )
            {
                NewNode = malloc( sizeof( struct SkipNode ) );
                if( NewNode == NULL )
                    FatalError( "Out of space!!!" );
                NewNode->Down = L;
                NewNode->Right = Tail;
                NewNode->Element = Infinity;
                L = NewNode;
            }

            return L;
        }
/* END */

        SkipList
        Remove( ElementType Item, SkipList L )
        {
            printf( "Remove is unimplemented\n" );
            if( Item )
                return L;
            return L;
        }

        ElementType
        Retrieve( Position P )
        {
            return P->Element;
        }