// Arup Guha
// 6/7/2020
// Code for Solution to E1-LL portion of the first COP 3502 Exam (Summer 2020)

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

typedef struct node {
    int coeff;
    struct node* next;
} node;

node* getNextRow(node* curRowPtr);
node* makeNewNode(int value);
void freeList(node* listPtr);
void print(node* ptr);

int main(void) {

    // Here is row 0.
    node* row = makeNewNode(1);
    print(row);
    printf("\n");

    // Now do the next 10 rows.
    for (int i=1; i<=10; i++) {
        row = getNextRow(row);
        print(row);
        printf("\n");
    }

    // This is the only allocated memory not freed.
    freeList(row);

    return 0;
}

// Pre-condition: curRowPtr is a pointer to the front of a linked list storing a non-empty row of
//                Pascal's Triangle.
// Post-condition: The next row of Pascal's Triangle is created and stored in a linked list, the memory
//                 associated with the linked list pointed to by curRowPtr is freed, and a pointer to the
//                 front of the linked list storing the next row is returned.

node* getNextRow(node* curRowPtr) {

    // Make the first and last nodes.
    node* front = makeNewNode(1);
    node* back = makeNewNode(1);

    // Store the pointer to the front of the input list so we can free it later.
    node* saveOrig = curRowPtr;

    // We'll use this to build our list.
    node* cur = front;

    // This makes sure we don't go the end of the list.
    while (curRowPtr->next != NULL) {

        // These are the two consecutive values we want to add.
        node* tmp = makeNewNode(curRowPtr->coeff + curRowPtr->next->coeff);

        // Add this new node to connect to the rest of the list formed so far.
        cur->next = tmp;

        // Update the back of the current list being formed.
        cur = tmp;

        // Go to the next node in the original list.
        curRowPtr = curRowPtr->next;
    }

    // This patches the last calculated node to the last one.
    cur->next = back;

    // Frees the old list.
    freeList(saveOrig);

    // This is what we return.
    return front;
}

// Returns a newly created node storing value.
node* makeNewNode(int value) {
    node* res = malloc(sizeof(node));
    res->coeff = value;
    res->next = NULL;
    return res;
}

// Frees all the memory associated with the linked list pointed to by listPtr.
void freeList(node* listPtr) {
    if (listPtr != NULL) {
        freeList(listPtr->next);
        free(listPtr);
    }
}

// Prints the items in the linked list pointed to by ptr.
void print(node* ptr) {
    if (ptr != NULL) {
        printf("%d ", ptr->coeff);
        print(ptr->next);
    }
}