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

/* START: fig12_27.txt */
            /* Returned for failures */
        Position NullNode = NULL;  /* Needs more initialization */

        struct AANode
        {
            ElementType Element;
            AATree      Left;
            AATree      Right;
            int         Level;
        };

        AATree
        Initialize( void )
        {
            if( NullNode == NULL )
            {
                NullNode = malloc( sizeof( struct AANode ) );
                if( NullNode == NULL )
                    FatalError( "Out of space!!!" );
                NullNode->Left = NullNode->Right = NullNode;
                NullNode->Level = 0;
            }
            return NullNode;
        }
/* END */

        AATree
        MakeEmpty( AATree T )
        {
            if( T != NullNode )
            {
                MakeEmpty( T->Left );
                MakeEmpty( T->Right );
                free( T );
            }
            return NullNode;
        }

        Position
        Find( ElementType X, AATree T )
        {
            if( T == NullNode )
                return NullNode;
            if( X < T->Element )
                return Find( X, T->Left );
            else
            if( X > T->Element )
                return Find( X, T->Right );
            else
                return T;
        }

        Position
        FindMin( AATree T )
        {
            if( T == NullNode )
                return NullNode;
            else
            if( T->Left == NullNode )
                return T;
            else
                return FindMin( T->Left );
        }

        Position
        FindMax( AATree T )
        {
            if( T != NullNode )
                while( T->Right != NullNode )
                    T = T->Right;

            return T;
        }

        /* This function can be called only if K2 has a left child */
        /* Perform a rotate between a node (K2) and its left child */
        /* Update heights, then return new root */

        static Position
        SingleRotateWithLeft( Position K2 )
        {
            Position K1;

            K1 = K2->Left;
            K2->Left = K1->Right;
            K1->Right = K2;

            return K1;  /* New root */
        }

        /* This function can be called only if K1 has a right child */
        /* Perform a rotate between a node (K1) and its right child */
        /* Update heights, then return new root */

        static Position
        SingleRotateWithRight( Position K1 )
        {
            Position K2;

            K2 = K1->Right;
            K1->Right = K2->Left;
            K2->Left = K1;

            return K2;  /* New root */
        }

/* START: fig12_29.txt */
        /* If T's left child is on the same level as T, */
        /* perform a rotation */

        AATree
        Skew( AATree T )
        {
            if( T->Left->Level == T->Level )
                T = SingleRotateWithLeft( T );
            return T;
        }

        /* If T's rightmost grandchild is on the same level, */
        /* rotate right child up */

        AATree
        Split( AATree T )
        {
            if( T->Right->Right->Level == T->Level )
            {
                T = SingleRotateWithRight( T );
                T->Level++;
            }
            return T;
        }
/* END */




/* START: fig12_36.txt */
        AATree
        Insert( ElementType Item, AATree T )
        {
            if( T == NullNode )
            {
                /* Create and return a one-node tree */
                T = malloc( sizeof( struct AANode ) );
                if( T == NULL )
                    FatalError( "Out of space!!!" );
                else
                {
                    T->Element = Item; T->Level = 1;
                    T->Left = T->Right = NullNode;
                }
            }
            else
            if( Item < T->Element )
                T->Left = Insert( Item, T->Left );
            else
            if( Item > T->Element )
                T->Right = Insert( Item, T->Right );

            /* Otherwise it's a duplicate; do nothing */

            T = Skew( T );
            T = Split( T );
            return T;
        }
/* END */

/* START: fig12_38.txt */
        AATree
        Remove( ElementType Item, AATree T )
        {
            static Position DeletePtr, LastPtr;

            if( T != NullNode )
            {
                /* Step 1: Search down tree */
                /*         set LastPtr and DeletePtr */
                LastPtr = T;
                if( Item < T->Element )
                    T->Left = Remove( Item, T->Left );
                else
                {
                    DeletePtr = T;
                    T->Right = Remove( Item, T->Right );
                }

                /* Step 2: If at the bottom of the tree and */
                /*         item is present, we remove it */
                if( T == LastPtr )
                {
                    if( DeletePtr != NullNode &&
                             Item == DeletePtr->Element )
                    {
                        DeletePtr->Element = T->Element;
                        DeletePtr = NullNode;
                        T = T->Right;
                        free( LastPtr );
                    }
                }

                /* Step 3: Otherwise, we are not at the bottom; */
                /*         rebalance */
                else
                    if( T->Left->Level < T->Level - 1 ||
                        T->Right->Level < T->Level - 1 )
                    {
                        if( T->Right->Level > --T->Level )
                            T->Right->Level = T->Level;
                        T = Skew( T );
                        T->Right = Skew( T->Right );
                        T->Right->Right = Skew( T->Right->Right );
                        T = Split( T );
                        T->Right = Split( T->Right );
                    }
            }
            return T;
        }
/* END */

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