#include <fstream>
#include <iostream>
#include <ctime>


const int C_NULL = -1;

struct node
{
    node ( ) : value ( C_NULL ), left ( C_NULL ), right ( C_NULL ),
        height ( C_NULL ), parent ( C_NULL ), location ( C_NULL ) { };

    node ( int v, int l, int r, int h, int p, int loc )
        : value ( v ), left ( l ), right ( r ),
        height ( h ), parent ( p ), location ( loc ) { };

    node ( std::fstream & file, const int loc ) { read ( file, loc ); };

    int value, left, right, height, parent, location;

    void read ( std::fstream & file, const int loc );

    void write ( std::fstream & file );

    void print ( )
    {
        std::cout.width ( 10 );
        std::cout << value;
        std::cout.width ( 10 );
        std::cout << left;
        std::cout.width ( 10 );
        std::cout << right;
        std::cout.width ( 10 );
        std::cout << parent;
        std::cout.width ( 10 );
        std::cout << height;
        std::cout.width ( 10 );
        std::cout << location << 'n';
    }
};

const int C_NODE_SIZE = sizeof ( node );

void node::read ( std::fstream & file, const int loc )
{
    if ( loc != C_NULL )
    {
        file.seekg ( loc * C_NODE_SIZE );

        file.read ( (char*) this, C_NODE_SIZE );
    }

    else * this = node ( );
}

void node::write ( std::fstream & file )
{
    if ( location != C_NULL )
    {
        file.seekp ( location * C_NODE_SIZE );

        file.write ( (char*) this, C_NODE_SIZE );
    }
}


node seedTree ( std::ifstream & input, std::fstream & output );

bool insertValue ( std::fstream & file, const int value, const int numNodes, node & root, node & newNode );

void UpdateHeightAndCheckBalance ( std::fstream & file, node & parent, node & child, const int height );

void rebalanceLeft ( std::fstream & file, node & left, node & parent, const node & right );

void rebalanceRight ( std::fstream & file, const node & left, node & parent, node & right );

void fixRootLocation ( std::fstream & file, node & root );

void getSelectValues ( std::fstream & file, int & smallest, int & biggest );

void printNodes ( std::fstream & file );


int main ( int argc, char * argv[] )
{
    if ( argc < 3 ) return 0;


    std::ifstream input ( argv[1] );

    std::fstream output ( argv[2], std::fstream::in | std::fstream::out |
                          std::fstream::trunc | std::fstream::binary );


    if ( !input || !output ) return 0; // file open fail


    // insert first two numbers to get things started
    node root = seedTree ( input, output ), child;


    if ( root.height > 0 )
    {
        int value, nodes = root.height + 1;


        while ( input >> value )
        {
            if ( insertValue ( output, value, nodes++, root, child ) )
                UpdateHeightAndCheckBalance ( output, root, child, 2 );

            fixRootLocation ( output, root );
        }
    }


    int smallest, biggest;

    getSelectValues ( output, smallest, biggest );

    std::cout << "Height: " << root.height
              << "nRoot Value: " << root.value
              << "nSmallest Leaf Value: " << smallest
              << "nBiggest Leaf Value: " << biggest
              << "nTime: " << clock ( ) / CLOCKS_PER_SEC;

    printNodes ( output );

    std::cin.ignore ( );
}


node seedTree ( std::ifstream & input, std::fstream & output )
{
    node root ( C_NULL, C_NULL, C_NULL, 0, C_NULL, 0 );

    input >> root.value;


    if ( input ) // if there is at least one number in the file
    {
        node child ( C_NULL, C_NULL, C_NULL, 0, 0, 1 );

        input >> child.value;


        if ( input ) // if there is a second number
        {
            root.height = 1;


            if ( root.value < child.value ) // second = right child of first
                root.right = 1;

            else // second = left child of first
                root.left = 1;


            child.write ( output );
        }


        root.write ( output );
    }


    return root;
}


bool insertValue ( std::fstream & file, const int value, const int numNodes, node & root, node & newNode )
{
    newNode = node ( value, C_NULL, C_NULL, 0, C_NULL, numNodes );

    bool balanceIssue = true;


    while ( true )
    {
        if ( root.value < newNode.value ) // move right
        {
            if ( root.right == C_NULL ) // write new node
            {
                if ( root.height == 0 ) root.height = 1;

                else balanceIssue = false; // if the parent height isn't updated, the tree will not become unbalanced

                root.right = numNodes;

                root.write ( file );


                newNode.parent = root.location;

                newNode.write ( file );


                break;
            }

            else root.read ( file, root.right ); // move down tree
        }

        else // move left
        {
            if ( root.left == C_NULL ) // write new node
            {
                if ( root.height == 0 ) root.height = 1;

                else balanceIssue = false; // if the parent height isn't updated, the tree will not become unbalanced

                root.left = numNodes;

                root.write ( file );


                newNode.parent = root.location;

                newNode.write ( file );


                break;
            }

            else root.read ( file, root.left ); // move down tree
        }
    }


    if ( balanceIssue )
    {
        newNode = root;

        root.read ( file, root.parent );
    }

    return balanceIssue;
}

void UpdateHeightAndCheckBalance ( std::fstream & file, node & parent, node & child, const int height )
{
    if ( parent.height < height )
    {
        parent.height = height; // update parent height

        parent.write ( file ); // write parent to file
    }

    else return;


    { // check balance
        node left, right;

        if ( parent.left == child.location )
        {
            left = child;

            right.read ( file, parent.right );
        }

        else
        {
            left.read ( file, parent.left );

            right = child;
        }


        const int balance = left.height - right.height;


        if ( balance > 1 ) // left heavy
            return rebalanceLeft ( file, left, parent, right );

        else if ( balance < -1 ) // right heavy
            return rebalanceRight ( file, left, parent, right );
    }


    if ( parent.parent == C_NULL ) return;


    child = parent;

    parent.read ( file, parent.parent );

    UpdateHeightAndCheckBalance ( file, parent, child, height + 1 );
}


void rebalanceLeft ( std::fstream & file, node & left, node & parent, const node & right )
{
    node grandparent ( file, parent.parent );

    const node leftleft ( file, left.left );

    node leftright ( file, left.right );


    if ( node ( file, left.left ).height < leftright.height ) // left right case
    {
        if ( grandparent.left == parent.location )
            grandparent.left = leftright.location;

        else grandparent.right = leftright.location;


        parent.parent = leftright.location;

        parent.left = leftright.right;


        left.parent = leftright.location;

        left.right = leftright.left;


        leftright.parent = grandparent.location;

        leftright.left = left.location;

        leftright.right = parent.location;



        { // set 'left' height and left.right.parent
            node newleftright ( file, left.right );

            newleftright.parent = left.location;

            newleftright.write ( file );

            if ( leftleft.height > newleftright.height ) left.height = leftleft.height + 1;

            else  left.height = newleftright.height + 1;
        }

        { // set 'parent' height and parent.left.parent
            node newrightleft ( file, parent.left );

            newrightleft.parent = parent.location;

            newrightleft.write ( file );

            if ( newrightleft.height > right.height ) parent.height = newrightleft.height + 1;

            else parent.height = right.height + 1;
        }


        if ( left.height < parent.height ) leftright.height = parent.height + 1;

        else leftright.height = left.height + 1;
    }

    else // left left case
    {
        if ( grandparent.left == parent.location )
            grandparent.left = left.location;

        else grandparent.right = left.location;


        parent.parent = left.location;

        parent.left = left.right;


        left.parent = grandparent.location;

        left.right = parent.left;


        leftright.parent = parent.location;


        // set 'parent' height
        if ( leftright.height > right.height ) parent.height = leftright.height + 1;
        else parent.height = right.height + 1;

        // set 'left' height
        if ( leftleft.height > parent.height ) left.height = leftleft.height + 1;
        else left.height = parent.height + 1;
    }


    grandparent.write ( file );

    parent.write ( file );

    left.write ( file );

    leftright.write ( file );
}

void rebalanceRight ( std::fstream & file, const node & left, node & parent, node & right )
{
    node grandparent ( file, parent.parent );

    node rightleft ( file, right.left );

    const node rightright ( file, right.right );


    if ( rightleft.height > node ( file, right.right ).height ) // right left case
    {
        if ( grandparent.left == parent.location )
            grandparent.left = rightleft.location;

        else grandparent.right = rightleft.location;


        parent.parent = rightleft.location;

        parent.right = rightleft.left;


        right.parent = rightleft.location;

        right.left = rightleft.right;


        rightleft.parent = grandparent.location;

        rightleft.left = parent.location;

        rightleft.right = right.location;


        { // set 'parent' height and parent.right.parent
            node newleftright ( file, parent.right );

            newleftright.parent = parent.location;

            newleftright.write ( file );

            if ( left.height > newleftright.height ) parent.height = left.height + 1;

            else parent.height = newleftright.height + 1;
        }

        { // set 'right' height and right.left.parent
            node newrightleft ( file, right.left );

            newrightleft.parent = right.location;

            newrightleft.write ( file );

            if ( newrightleft.height > rightright.height ) right.height = newrightleft.height + 1;

            else right.height = rightright.height + 1;
        }


        if ( parent.height < right.height ) rightleft.height = right.height + 1;

        else rightleft.height = parent.height + 1;
    }

    else // right right case
    {
        if ( grandparent.left == parent.location )
            grandparent.left = right.location;

        else grandparent.right = right.location;


        parent.parent = right.location;

        parent.right = right.left;


        right.parent = grandparent.location;

        right.left = parent.location;


        rightleft.parent = parent.location;


        // set 'parent' height
        if ( left.height > rightleft.height ) parent.height = left.height + 1;
        else parent.height = rightleft.height + 1;

        // set 'right' height
        if ( parent.height > rightright.height ) right.height = parent.height + 1;
        else right.height = rightright.height + 1;
    }


    grandparent.write ( file );

    parent.write ( file );

    right.write ( file );

    rightleft.write ( file );
}


void fixRootLocation ( std::fstream & file, node & root )
{
    root.read ( file, 0 );


    if ( root.parent != C_NULL )
    {
        node newRoot ( file, root.parent );

        root.location = newRoot.location;

        newRoot.location = 0;

        root.parent = 0;

        if ( newRoot.left == 0 )
        {
            newRoot.left = root.location;

            node temp ( file, newRoot.right );

            temp.parent = 0;

            temp.write ( file );
        }

        else
        {
            newRoot.right = root.location;

            node temp ( file, newRoot.left );

            temp.parent = 0;

            temp.write ( file );
        }

        root.write ( file );

        newRoot.write ( file );


        if ( root.left != C_NULL )
        {
            node temp ( file, root.left );

            temp.parent = root.location;

            temp.write ( file );
        }

        if ( root.right != C_NULL )
        {
            node temp ( file, root.right );

            temp.parent = root.location;

            temp.write ( file );
        }


        root = newRoot;
    }
}


void getSelectValues ( std::fstream & file, int & smallest, int & biggest )
{
    // set starting values
    smallest = INT_MAX;
    biggest = INT_MIN;


    file.seekg ( 0, std::fstream::end ); // seek to end of file

    int fSize = int ( file.tellg ( ) ); // get file size


    if ( fSize > C_NODE_SIZE ) // check that file has more than one node
    {
        node temp ( file, 1 ); // start at first node after root


        while ( file.tellg ( ) < fSize )
        {
            temp.read ( file, int ( file.tellg ( ) ) / C_NODE_SIZE );


            if ( temp.height == 0 )
            {
                if ( temp.value < smallest ) smallest = temp.value;

                if ( temp.value > biggest ) biggest = temp.value;
            }
        }
    }

    else
    {
        node root ( file, 0 );

        smallest = root.value;

        biggest = root.value;
    }
}


void printNodes ( std::fstream & file )
{
    // print header
    std::cout << 'n';
    std::cout.width ( 10 );
    std::cout << "Value";
    std::cout.width ( 10 );
    std::cout << "Left";
    std::cout.width ( 10 );
    std::cout << "Right";
    std::cout.width ( 10 );
    std::cout << "Parent";
    std::cout.width ( 10 );
    std::cout << "Height";
    std::cout.width ( 10 );
    std::cout << "Location" << 'n';


    file.seekg ( 0, std::ios_base::end ); // seek to end of file

    int fSize = int ( file.tellg ( ) ); // get file size

    file.seekg ( 0 ); // seek to start of file

    // print nodes
    while ( file.tellg ( ) < fSize ) node ( file, int ( file.tellg ( ) ) / C_NODE_SIZE ).print ( );
}