/*
 * File:   struct integer.c
 * Author: Andrew Levenson
 * Course: COP 3502
 * Professor: Jonathan Cazalas
 * Description: Assignment in using Linked Lists
 * in order to perform bigint addition and subtraction.
 *
 * Created on September 1, 2010, 11:38 AM
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// Constant Definitions
#define ADD 1
#define SUB 2

// Output file
char *fName = "out.txt";
FILE *outFile;


/*
 * Create a prototype of a single
 * node in the Linked List.
 * Each node will represent a single
 * integer comprising one part of a struct integer.
 */
struct integer
{
    int digit;

    struct integer *next;
};


// Function Prototypes
struct integer* read_integer( char *stringInt );
struct integer* add( struct integer *p, struct integer *q );
struct integer* subtract( struct integer *p, struct integer *q);
struct integer* stripLeadingZeros( struct integer *p );

int compare( struct integer *p, struct integer *q );

void print( struct integer *p );
void reverse( struct integer **p );


// Main function
int main( )
{
    //Variable initialization

    /*
     * Initialize pointers to the linked lists.
     * One, *head, will always point to the
     * first element, the head, of the list.
     * The other element, *curr, will point to the
     * node currently being accessed, and will be
     * used to traverse the list.
     */
    struct integer* pHead;
    struct integer* qHead;
    struct integer* tHead; // Used to contain the total

    int numOps, oper, i;
    char *fileName = "input.txt";
    char bigintstr[200];
    FILE *inputFile;

    // Open output file
    outFile = fopen(fName, "a+");


    // Open up the input file for reading
    inputFile = fopen(fileName, "r");

    // Read in the number of operations to be performed
    fscanf(inputFile, "%d", &numOps);

    /*
     * For each operation that must be performed,
     * construct a linked list for each of the
     * struct integers in the file. Then, perform the operation
     * indicated by the digit preceding them.
     */
    for( i = 0; i < numOps; i++ )
    {
        // Read in the number that dictates operation
        fscanf(inputFile, "%d", &oper);

        // Read in the first struct integer into a string
        fscanf(inputFile, "%s", bigintstr);

        /*
         * Pass the struct integer string to read_integer()
         * in order to construct a linked list out of it.
         */
        pHead = read_integer( bigintstr );

        // Read in second struct integer into a string
        fscanf(inputFile, "%s", bigintstr);

        /*
         * Pass the struct integer str to read_integer()
         * in order to construct a linked list out of it.
         */
        qHead = read_integer( bigintstr );

        /*
         * Depending on the operation to be performed,
         * call the corresponding function.
         */
        if( oper == ADD )
        {
            tHead = add( pHead, qHead );
            print( pHead );
            fprintf(outFile, " + ");
            print( qHead );
            fprintf(outFile, " = ");
            reverse( &tHead );
            print( tHead );
            fprintf(outFile, "\n");
        }
        else if( oper == SUB )
        {
            /*
             * Before you can subtract, you must
             * compare the two bigints being subtracted.
             * Because we are only dealing with
             * positive integers, we must first
             * determine which is the larger of the
             * two operands. This operand becomes
             * the bigint from which we subtract.
             */
            if( compare( pHead, qHead ) > 0 ) // p > q
            {
                tHead = subtract( pHead, qHead );
                print( pHead );
                fprintf(outFile, " - ");
                print( qHead );
                fprintf(outFile, " = ");
                reverse( &tHead );
                print( tHead );
                fprintf(outFile, "\n");
            }
            else if( compare( pHead, qHead ) == 0 ) // p == q
            {
                tHead->digit = 0;
                tHead->next = NULL;

                print( pHead );
                fprintf(outFile, " - ");
                print( qHead );
                fprintf(outFile, " = ");
                reverse( &tHead );
                print( tHead );
                fprintf(outFile, "\n");
            }
            else // p < q
            {
                tHead = subtract( qHead, pHead );

                print( qHead );
                fprintf(outFile, " - ");
                print( pHead );
                fprintf(outFile, " = ");
                reverse( &tHead );
                print( tHead );
                fprintf(outFile, "\n");
            }
         }
    }
    fclose(inputFile);
    fclose(outFile);

    //system(PAUSE);
    return 0;
}


// Function Definitions

/*
 * Function read_integer
 *
 * @Parameter CHAR* stringInt
 *
 * Parameter contains a string representing a struct integer.
 * Tokenizes the string by each character, converts each char
 * into an integer, and constructs a backwards linked list out
 * of the digits.
 *
 * @Return STRUCT* Integer
 */
struct integer* read_integer( char* stringInt )
{
    int i, n;
    struct integer *curr, *head;

    int numDigits = strlen( stringInt ); // Find the length of the struct integer
    head = NULL;

    for( i = 0; i < numDigits; i++ )
    {
        n = stringInt[i] - '0'; // Convert char to an integer

        curr = (struct integer *) malloc (sizeof( struct integer )); // Allocate memory for node
        curr->digit = n; // Digit of current node is assigned to n
        curr->next = head; // Move to the next node in the list.
        head = curr; // Move head up to the front of the list.
    }

    return head; // Return a pointer to the first node in the list.
}

/*
 * Function reverse
 *
 * @Parameter STRUCT** Integer
 *
 * Reverses a linked list by creating a new
 * reversed linked list and then returning the
 * head of the newly formed list.
 */
void reverse (struct integer **p)
{
    struct integer *oldList = *p;
    struct integer *newList = NULL;

    while( oldList )
    {
        struct integer *oldNext = oldList->next;
        oldList->next = newList;
        newList = oldList;

        oldList = oldNext;
    }

    *p = newList;
}

/*
 * Function print
 *
 * @Parameter STRUCT* Integer
 *
 * Given a linked list, will traverse through
 * the nodes and print out, one at a time,
 * the digits comprising the struct integer that the
 * linked list represents.
 *
 * TODO: Print to file
 */
void print( struct integer *p )
{
    struct integer *curr = p;

    curr = stripLeadingZeros( curr );

    reverse( &curr );

    while( curr )
    {
        fprintf(outFile, "%d", curr->digit);
        curr = curr->next;
    }

}

/*
 * Function add
 *
 * @Paramater STRUCT* Integer
 * @Parameter STRUCT* Integer
 *
 * Takes two linked lists representing
 * big integers stored in reversed order,
 * and returns a linked list containing
 * the sum of the two integers.
 *
 * @Return STRUCT* Integer
 *
 * TODO Comment me
 */
struct integer* add( struct integer *p, struct integer *q )
{
    int carry = 0;

    struct integer *sHead, *sCurr;
    struct integer *pHead, *qHead;

    pHead = p;
    qHead = q;

    sHead = NULL;

    while( p )
    {
        sCurr = ( struct integer* ) malloc (sizeof(struct integer));
        sCurr->digit = p->digit + q->digit + carry;
        sCurr->next = sHead;
        sHead = sCurr;

        carry = 0;

        /*
         * If the current digits sum to greater than 9,
         * create a carry value and replace the current
         * value with value mod 10.
         */
        if( sCurr->digit > 9 )
        {
            carry = 1;
            sCurr->digit = sCurr->digit % 10;
        }

        /*
         * If the most significant digits of the numbers
         * sum to 10 or greater, create an extra node
         * at the end of the sum list and assign it the
         * value of 1.
         */
        if( carry == 1 && sCurr->next == NULL )
        {
            struct integer *sCarry = ( struct integer* ) malloc (sizeof(struct integer));
            sCarry->digit = 1;
            sCarry->next = NULL;
            reverse( &sCurr );
            sCurr->next = sCarry;
            reverse( &sCurr );
        }

        p = p->next;
        if( q->next ) q = q->next;
        else q->digit = 0;
    }

    return sHead;
}

/*
 * Function subtract
 *
 * @Parameter STRUCT* Integer
 * @Parameter STRUCT* Integer
 *
 * Takes two linked lists representing struct integers.
 * Traverses through the lists, subtracting each
 * digits from the subsequent nodes to form a new
 * struct integer, and then returns the newly formed
 * linked list.
 *
 * @Return STRUCT* Integer
 *
 * TODO Comment me
 */
struct integer* subtract( struct integer *p, struct integer *q )
{
    int borrow = 0;

    struct integer *dHead, *dCurr;
    struct integer *pHead, *qHead;

    pHead = p;
    qHead = q;

    dHead = NULL;

    while( p )
    {
        dCurr = (struct integer*) malloc (sizeof(struct integer));
        if( q )
        {
            dCurr->digit = p->digit - q->digit - borrow;
        }
        else
        {
            dCurr->digit = p->digit - borrow;
        }
        dCurr->next = dHead;
        dHead = dCurr;

        if( dCurr->digit < 0 )
        {
            dCurr->digit += 10;
            borrow = 1;
        }

        if( dCurr->next == NULL && borrow == 1 )
        {
            struct integer *dBorrow = (struct integer*) malloc (sizeof(struct integer));
            dBorrow->digit = -1;
            dBorrow->next = NULL;
            dCurr->next = dBorrow;
        }

        p = p->next;
        if( q->next) q = q->next;
        else q->digit = 0;
    }

    return dHead;
}

/*
 * Function compare
 *
 * @Parameter STRUCT* Integer
 * @Parameter STRUCT* Integer
 *
 * Takes in two linked lists representing struct integers.
 * Traverses the lists one at a time, comparing the
 * digits.
 *
 * Case: p < q
 * @Return -1
 *
 * Case: p == q
 * @Return 0
 *
 * Case: p > q
 * @Return 1
 *
 * TODO Comment me
 */
int compare( struct integer *p, struct integer *q )
{
    struct integer *pHead, *qHead;
    int comp = 0, pCount = 0, qCount = 0;

    pHead = p;
    qHead = q;

    // Get the length of p
    while( p )
    {
        pCount++;
        p = p->next;
    }

    // Get the length of q
    while( q )
    {
        qCount++;
        q = q->next;
    }

    if( pCount > qCount ) // p > q
    {
        return 1;
    }
    if( pCount < qCount ) // p < q
    {
        return -1;
    }

    while( p )
    {
        if( p->digit > q->digit )
        {
            comp = 1;
        }

        if( p->digit < q->digit )
        {
            comp = -1;
        }

        p = p->next;
        if( q->next ) q = q->next;
        else q->digit = 0;
    }

    return comp;
}

/*
 * Function stripLeadingZeros
 *
 * @Parameter STRUCT* Integer
 *
 * Step through a linked list, recursively unlinking
 * all leading zeros and making the first
 * non-zero integer the head of the list.
 *
 * @Return STRUCT* Integer
 */
struct integer* stripLeadingZeros( struct integer *p )
{
    reverse( &p );

    // Are we at the end of the list?
    if( p == NULL ) return NULL;

    // Are we deleting the current node?
    //Also it should not strip last 0
    if( p->digit == 0 && p->next != NULL)
    {
        struct integer *pNext;

        pNext = p->next;

        // Deallocate the node
        free( p );

        // Try to strip zeros on pointer to the next node and return that pointer
        return stripLeadingZeros(pNext);
    }

    reverse( &p );

    return p;
}