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

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

// For Question #1
void testSumSeries();
int sumSeries(int start, int diff, int n);

// For Question #3
#define SIZE 5
#define NUMDIR 4

const int DX[4] = {-1,0,0,1};
const int DY[4] = {0,-1,1,0};

void testFloodFill();
void read(int array[][SIZE]);
void init(int array[][SIZE], int val);
void print(int array[][SIZE]);
void fill(int grid[][SIZE], int used[][SIZE], int x, int y);
int inbounds(int x, int y);

// For Question #4
typedef struct node {
    int data;
    struct node* next;
} node;

void testLL();
void printList(node* list);
node* insertFront(node* list, int x);
void delEveryOther(node* head);

// Comment in what you want to test.
int main(void) {
    testSumSeries();
    //testFloodFill();
    //testLL();
    return 0;
}

// Wrapper test for Question 1
void testSumSeries() {
    printf("%d\n", sumSeries(7,4,5));
}

// Returns the sum of an arithmetic series with first term start, common difference diff with n terms.
int sumSeries(int start, int diff, int n) {

    // No terms = no sum.
    if (n == 0) return 0;

    // Add the first term to the rest of the series (n-1 terms starting at start+diff...)
    return start + sumSeries(start+diff, diff, n-1);
}

// Wrapper test for Question 3
void testFloodFill() {

    // Read in the grid (pipe from file quiz3dq3.in)
    int grid[SIZE][SIZE];
    read(grid);
    int used[SIZE][SIZE];
    init(used, 0);

    // Floodfill from (2, 3) and see which squares were reached.
    fill(grid, used, 2, 3);
    print(used);
}

// Just reads in numbers from standard input into array (SIZE by SIZE).
void read(int array[][SIZE]) {
    for (int i=0; i<SIZE; i++)
        for (int j=0; j<SIZE; j++)
            scanf("%d", &array[i][j]);
}

// Initializes array so all values in it equal val.
void init(int array[][SIZE], int val) {
    for (int i=0; i<SIZE; i++)
        for (int j=0; j<SIZE; j++)
            array[i][j] = val;
}

// Prints all the values in array.
void print(int array[][SIZE]) {
    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++)
            printf("%d ", array[i][j]);
        printf("\n");
    }
}

// Updates used to 1s in each slot where we the frog can reach from (x, y).
void fill(int grid[][SIZE], int used[][SIZE], int x, int y) {

    // We're here so mark it.
    used[x][y] = 1;

    // Try all directions.
    for (int i=0; i<NUMDIR; i++) {

        // Where we would go if we head in direction i.
        int nX = x + DX[i];
        int nY = y + DY[i];

        // Oops out of bounds!.
        if (!inbounds(nX, nY)) continue;

        // Frog only jumps strictly up...this won't do.
        if (grid[nX][nY] <= grid[x][y]) continue;

        // Otherwise, we're good...
        fill(grid, used, nX, nY);
    }

}

// Returns 1 iff (x, y) is in bounds, 0 otherwise.
int inbounds(int x, int y) {
    return x >= 0 && x < SIZE && y >= 0 && y < SIZE;
}

// Wrapper test for Question t.
void testLL() {

    // Fill the list up.
    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);

    // Run this three times!
    delEveryOther(mine);
    printList(mine);
    delEveryOther(mine);
    printList(mine);
    delEveryOther(mine);
    printList(mine);

    // I am cheating because I know there's only one node =)
    free(mine);
}

// Prints the contents of 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;
}

// Deletes every other node (2nd, 4th, 6th, etc.) from the list pointed to by head.
void delEveryOther(node* head) {

    // Temp pointer to start at the front of the list.
    node* cur = head;

    // Nothing to do if we're NULL or at the last node.
    while (cur != NULL && cur->next != NULL) {

        // Where we will connect to after deleting the marked node.
        node* forward = cur->next->next;

        // This is the node to be deleted.
        free(cur->next);

        // Patch from the node before to the node after.
        cur->next = forward;

        // Update our current node!
        cur = forward;
    }
}