// Arup Guha
// 9/28/2021
// Code for Quiz 2 Version A COP 3502 (Fall 2021)

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

#define NUMSLOTS 5

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

// For Question #1
void testEven();
int sumEvenValues(int* values, int k);

// For Question #3
void printJayson();
void printJaysonRec(int odometer[], int k, int n);
void print(int array[], int n);

// For Question #4
void testLL();
void printList(node* list);
node* insertFront(node* list, int x);
node* backToFront(node* listPtr);
void freeList(node* list);

// Comment in whatever you want to see.
int main(void) {
    testEven();
    //printJayson();
    //testLL();
    return 0;
}

// Hard-coded test for sumEvenValues function.
void testEven() {
    int vals[10] = {2, 6, 7, 9, 3, 119, 212, 47, 16, 8};
    printf("sum even = %d\n", sumEvenValues(vals, 10));
}

// Returns the sum of the even integers in values[0..k-1].
int sumEvenValues(int* values, int k) {

    // Nothing to add, so 0.
    if (k == 0) return 0;

    // Either put 0 or values[k-1] in res, depending on whether it's even or not.
    int res = 0;
    if (values[k-1]%2 == 0) res += values[k-1];

    // Then add this to the sum for the rest of the array.
    return res + sumEvenValues(values, k-1);
}

// Test for the Jayson odometer question.
void printJayson() {
    int odometer[NUMSLOTS];
    printJaysonRec(odometer, 0, NUMSLOTS);
}

// Prints out each valid setting of Jayson's odometer with the first k digits fixed.
void printJaysonRec(int odometer[], int k, int n) {

    // Done filling it out, print.
    if (k == n) {
        print(odometer, n) ;
        return ;
    }

    // Try each digit.
    for (int i=0; i<10; i++) {

        // If we're not on the first digit and this digit is equal to the last one, we skip it!
        if ( k>0 && odometer[k-1] == i ) continue;

        // Otherwise, we do the regular odometer stuff.
        odometer[k] = i ;
        printJaysonRec(odometer, k+1, n) ;
    }
}

// Prints array[0..n-1].
void print(int array[], int n) {
    for (int i=0; i<n; i++)
        printf("%d", array[i]);
    printf("\n");
}

// Hard-coded test for the linked list question.
void testLL() {
    node* mine = NULL;
    mine = insertFront(mine, 12);
    mine = insertFront(mine, 8);
    mine = insertFront(mine, 22);
    mine = insertFront(mine, 13);
    mine = insertFront(mine, 5);
    mine = insertFront(mine, 77);
    mine = insertFront(mine, 2);
    printList(mine);
    mine = backToFront(mine);
    printList(mine);
    freeList(mine);
}

// Prints each item in the list pointed to by list.
void printList(node* list) {
    while (list!= NULL) {
        printf("%d ", list->data);
        list = list->next;
    }
    printf("\n");
}

// Inserts a new node storing x in the front of list and returns the new front of the list.
node* insertFront(node* list, int x) {
    node* tmp = malloc(sizeof(node));
    tmp->data = x;
    tmp->next = list;
    return tmp;
}

// Moves the last node to the front of the list pointed to by listPtr and returns the new front of the list.
node* backToFront(node* listPtr) {

    // No work to be done in these cases.
    if (listPtr == NULL || listPtr->next == NULL)
        return listPtr;

    // Iterate back to be the second to last node in the list.
    node* back = listPtr;
    while (back->next->next != NULL)
        back = back->next;

    // This will be the new front of the list.
    node* newfront = back->next;

    // NULL this out.
    back->next = NULL;

    // Patch the new front to the old front and return the new front.
    newfront->next = listPtr;
    return newfront;
}

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