/*
 * 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;
}