/*******************************************************************
 *
 * Name: Hector Colon
 * Program: bigint.c - Homework Assignment #1
 * Date: Wednesday Jan 27, 2010
 *
 *******************************************************************/

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

//This struct contains an array of single integer digits.
//It is usefull to hold large integers that do not fit
//in the primitive int data type
struct integer 
{
	int* digits;
	int size;
};

//Function definitions. Please check each function below
//for more info.
struct integer* read_integer(char* stringInt);
void print(struct integer *p);
struct integer* add(struct integer *p, struct integer *q);
struct integer* subtract(struct integer *p, struct integer *q);
int compare(struct integer *p, struct integer *q);

int main (void) 
{
   FILE * infile;                     //the bigint.txt file to be opened
   
   struct integer first, second;      //the two integer numbers
   struct integer answer;             //the answer to the integer operations
   int operation, operationNum;       //the number and type of operations
   
   char stringNum[200];               //string to store a large integer 
      
   int i, j;                          //loop counters
   
   //open the bigint.txt file  
   infile  = fopen("bigint.txt", "r");
   
   //read the number of operations on the first line
   fscanf(infile, "%d", &operationNum);
      
   //The main prgram loop.
   //This loop will process the input from one line and
   //output the answer to the screeen.
   for(j = 0; j < operationNum; j++)
   {
       //read the first number that describes what operation to do
       fscanf(infile, "%d", &operation);
       
       //read the first operand and process it
       fscanf(infile, "%s", &stringNum);
       first = *read_integer(stringNum);
       
       //read the second operand and process it
       fscanf(infile, "%s", &stringNum);
       second = *read_integer(stringNum);
       
       //These if statements determine whether we are adding or
       //subtracting and will print the appropriate output.
       if(operation == 1)
       {
            //addition
            answer = *add(&first, &second);
            print(&first);
            printf(" + ");
            print(&second);;
            printf(" = ");
            print(&answer);                            
        }
        if(operation == 2)
        {
             //subtraction
             answer = *subtract(&first, &second);
             if(compare(&first, &second) == -1)
             {
                   print(&second);
                   printf(" - ");
                   print(&first);
                   printf(" = ");
                   print(&answer);
             }
             else
             {
                   print(&first);
                   printf(" - ");
                   print(&second);
                   printf(" = ");
                   print(&answer);
             }
        }
        
        printf("\n");
   }
                      
   fclose(infile); 
   system("pause");
   return 0;
}     

//Preconditions: the first parameter is a string that stores
//               only digits, doesn't start with
//               0, and is 200 or fewer characters long.
//Postconditions: The function will read the digits of the
//	              large integer character by character, 
//	              convert them into integers and return a 
//                pointer to the appropriate struct integer.

struct integer* read_integer(char* stringInt)
{
       int length = strlen(stringInt);
       struct integer* temp;
       
       //dynamically create memory to store the temp integer
       temp = (struct integer*)malloc(sizeof(struct integer));
       temp->digits = (int*)malloc(length * sizeof(int));
       temp->size = length;
       
       //this loop will place the digits in the temp integer array
       //in reverse order. This will make it easier to preform arithmetic
       //operations on the arrays.
       int i;
       for(i = 0; i < length; i ++)
       {
             temp->digits[i] = stringInt[length - 1 - i] - '0';
       }
       
       return temp;
}

//Preconditions: p is a pointer to a big integer.
//Postconditions: The big integer pointed to by p is 
//                printed out.

void print(struct integer *p)
{
     //We must print the integer in reverse order so it will make sense
     //to the user.
     int i;
     for(i = (p -> size) - 1; i > -1; i--)
     {
           printf("%d", p->digits[i]);
     }
}

//Preconditions: p and q are pointers to struct integers.
//Postconditions: A new struct integer is created that 
//                stores the sum of the integers pointed to 
//                by p and q and a pointer to it is 
//                returned.

struct integer* add(struct integer *p, struct integer *q)
{
       int i;                      //loop counter
       int length, min;            //length of the integers
       int sum, carry, digit;      //ints to help sum the integer digits
       carry = 0;
       
       struct integer* temp;
       
       //set length to the size of the larger integer
       //set min to the length of the smaller integer
       if(compare(p, q) == 1)
       {
           length = p -> size;
           min    = q -> size;
       } 
       else
       {
           length = q -> size;
           min    = p -> size;
       }
       
       //dynamically create memory to store the temp integer
       temp = (struct integer*)malloc(sizeof(struct integer));
       temp -> digits = (int*)malloc(length * sizeof(int));
       temp -> size = length;
       
       //sum the digits until the smaller array has 
       //no more elements
       for(i = 0; i < min; i ++)
       {
             sum = p -> digits[i] + q -> digits[i] + carry;  
             carry = sum / 10;
             digit = sum % 10;   
             temp -> digits[i] = digit;
       }
       
       //sum the rest of the larger array with
       //any left over carry
       if(compare(p, q) == 1)
       {
           for(i = min; i < length; i++)
           {
                 sum = p -> digits[i] + carry;  
                 carry = sum / 10;
                 digit = sum % 10;   
                 temp -> digits[i] = digit;                           
           }
       } 
       //a second case is needed if q has more elements than p
       else
       {
           for(i = min; i < length; i++)
           {
                 sum = q -> digits[i] + carry;  
                 carry = sum / 10;
                 digit = sum % 10;   
                 temp -> digits[i] = digit;                           
           }           
       }
       
       //if there is still a carry, increase the size of temp and
       //add the carry to the array.
       if(carry)
       {
                temp -> digits = (int*)realloc(temp -> digits, (length + 1) * sizeof(int));
                temp -> digits[length] = carry;
                temp -> size++;
       }
       
       return temp;
}

//Preconditions: p and q are pointers to struct integers.
//Postconditions: A new struct integer is created that 
//                stores the absolute value of the 
//                difference between the two and a pointer 
//                to this is returned.

struct integer* subtract(struct integer *p, struct integer *q)
{
       int i;                      //loop counter
       int length, min;            //size of the integers
       int sub, carry;             //ints to help subtract
       
       carry = 0;
       
       struct integer* temp;       //store the integer we will return
       struct integer* big;        //stores the larger of p and q
       struct integer* small;      //stores the smaller
       struct integer* smallZeros; //fills in the smaller integer with zeros
       
       //find the larger of p and q and set the 
       //variables appropriately
       if(compare(p, q) == 1)
       {
           big = p;
           small = q;
           length = big -> size;
           min  = small -> size;;
       }
       else
       {
           big = q;
           small = p;
           length = big -> size;
           min  = small -> size;
       }
       
       //dynamically create memory for temp
       //it is the size of the larger integer
       temp = (struct integer*)malloc(sizeof(struct integer));
       temp -> digits = (int*)malloc(length * sizeof(int));
       temp -> size = length;
       
       //dynamically create memory for smallZeros
       //it is the size of the larger integer
       smallZeros = (struct integer*)malloc(sizeof(struct integer));
       smallZeros -> digits = (int*)malloc(length * sizeof(int));
       smallZeros -> size = length;
       
       //fill in smallZeros with leading 0s
       //this makes the logic easier for subtracting
       for(i = 0; i < min; i++)
       {
             smallZeros -> digits[i] = small -> digits[i];
       }
       for(i = min; i < length; i++)
       {
             smallZeros -> digits[i] = 0;
       }
        
       //this loop subtracts the two integers
       //and stores the result in temp      
       for(i = 0; i < length; i++)
       {
             //sub is set as the digit of the larger array
             //minus 1 if there is any carry from the 
             //previous digit. Eventually, sub will
             //equal the difference between sub and the 
             //smaller integer digit.
             sub = big -> digits[i] - carry;
             
             //if sub is larger then find the difference
             if(sub > smallZeros -> digits[i])
             {
                    sub = sub - smallZeros -> digits[i];
                    carry = 0;                 
             }
             //if sub is smaller, borrow from the next digit
             else if(sub < smallZeros -> digits[i])
             {
                 sub += 10;
                 carry = 1;
                 sub = sub - smallZeros -> digits[i]; ;
             }
             //if they are equal then the result is 0
             else 
             {
                 sub = 0;
                 carry = 0;
             }
             
             temp -> digits[i] = sub;
       }
       
       //this loop removes any leading zeros from the answer
       i = length - 1;
       while(i > -1 && temp -> digits[i] == 0)
       {
               //we shrink the array as long
               //as the loop finds leading zeros
               temp -> size--;
               i--;
       }
       //if the entire integer is zeros, then we 
       //want an integer of 1 zero
       if(temp -> size == 0)
               temp -> size++;
       
       //shrink size of array of the integer if needed        
       temp -> digits = (int*)realloc(temp -> digits, (temp -> size) * sizeof(int));      
       
       return temp;
}

//Preconditions: Both parameters of the function are 
//	             pointers to struct integer. 
//Postconditions: The function compares the digits of two 
//	              numbers and returns: 
//                -1 if the first number is smaller than the second, 
//                0 if the first number is equal to the second number,
//                1 if the first number is greater than the second.  

int compare(struct integer *p, struct integer *q)
{
    int i;
    
    //if p has more digits than q, return 1
    if((p -> size) > (q -> size))
         return 1;
    //if q has more digits than p, return -1
    if((p -> size) < (q -> size))
         return -1;
    
    //p and q have the same number of digits, so compare each one
    //starting from the most significant digit.
    else
        for(i = (p -> size) - 1; i > -1; i--)
        {
              if((p -> digits[i]) > (q -> digits[i]))
                    return 1;
              if((p -> digits[i]) < (q -> digits[i]))
                    return -1;
        }
        
    //if the function has made it this far, then p and q are eaqual
    return 0;
}