// Arup Guha
// 2/18/2022
// Code for Question #3 All Versions COP 3502 Quiz 2

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

typedef struct numNode {
    int digit;
    struct node* next;
} numNode;

numNode* makeNum(char* num);
numNode* makeNode(int d);
int getDigit(numNode* num1, int location);
int getValue(numNode* number);
int compare(numNode* num1, numNode* num2);

// Run whatever tests you want to run in here.
int main(void) {

    numNode* x = makeNum("265");
    numNode* y = makeNum("271");

    printf("digit 1 in 265 is %d, digit 2 is %d\n", getDigit(x, 1), getDigit(x, 2));

    return 0;
}

// Creates a linked list storing num as specified and returns a pointer
// to the front of the list (pointing to least significant digit).
numNode* makeNum(char* num) {

    // Get MSD and length.
    numNode* front = makeNode(num[0]-'0');
    int len = strlen(num);

    // Insert rest into front, forming number as we're supposed to.
    for (int i=1; i<len; i++) {
        numNode* tmp = makeNode(num[i]-'0');
        tmp->next = front;
        front = tmp;
    }

    // Return a pointer to the front of the list.
    return front;
}

// Returns the digit at location location in num1.
int getDigit(numNode* num1, int location) {

    // Doesn't exist.
    if (num1 == NULL) return -1;

    // We're here!
    if (location == 0) return num1->digit;

    // Recursively we are looking for the location-1 slot in the rest
    // of the number.
    return getDigit(num1->next, location-1);
}

// Returns a node storing the digit d.
numNode* makeNode(int d) {
    numNode* res = malloc(sizeof(numNode));
    res->digit = d;
    res->next = NULL;
    return res;
}

// Returns the value of the number pointed to by number.
int getValue(numNode* number) {

    // No value.
    if (number == NULL) return 0;

    // Digit's value is set, rest of the number is "shifted" by a
    // multiplicative value of 10.
    return number->digit + 10*getValue(number->next);
}


// Returns a negative int if num1 < num2, 0 if equal and a positive int
// if num1 > num2.
int compare(numNode* num1, numNode* num2) {

    // Base cases are for equality or different # of digits.
    if (num1 == NULL && num2 == NULL) return 0;
    if (num1 == NULL) return -1;
    if (num2 == NULL) return 1;

    // If we can break the tie with the "rest of the number", do so.
    int tmp = compare(num1->next, num2->next);
    if (tmp != 0) return tmp;

    // Otherwise, it comes down to the least significant digit.
    return num1->digit - num2->digit;
}