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

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

// Functions for question 1.
void runSorted();
int isSorted(int* values, int k, int max);

// Struct, functions for question 3.
typedef struct stack {
    int* stackItems;
    int capacity;
    int top;
} stack;

void runStack();
void init(stack* sPtr, int initSize);
int pop(stack* sPtr);
void push(stack* sPtr, int value);

// Struct and functions for questions 4, 5.
typedef struct charnode {
    char letter;
    struct charnode* next;
} charnode;

void testString();
char* convert(charnode* word);
charnode* insertFront(charnode* list, char c);
void freeList(charnode* list);

// Comment in whichever test you want.
int main(void) {
    runSorted();
    //runStack();
    //testString();
    return 0;
}

// Wrapper to run isSorted function.
void runSorted() {
    int vals[7] = {2,3,4,5,5,8,6};
    printf("%d\n", isSorted(vals, 6, 8));
    printf("%d\n", isSorted(vals, 6, 7));
    printf("%d\n", isSorted(vals, 7, 10));
}

// Returns 1 iff values[0..k-1] is sorted and all values less than or equal to max.
int isSorted(int* values, int k, int max) {

    // Trivially true.
    if (k == 0) return 1;

    // Definitely false.
    if (values[k-1] > max) return 0;

    // Rest of the array has to be sorted and less than or equal to the value in index k-1.
    return isSorted(values, k-1, values[k-1]);
}

// Tests stack code.
void runStack() {

    stack myStack;
    init(&myStack, 10);

    // Push 21 items, forcing two reallocs.
    for (int i=0; i<21; i++)
        push(&myStack, i);

    // Pop those 21 items.
    for (int i=0; i<21; i++)
        printf("Popping %d\n", pop(&myStack));

    // This needs to be freed.
    free(myStack.stackItems);
}

// Initializes the stack to be empty with an initial capacity of initSize.
void init(stack* sPtr, int initSize) {
    sPtr->stackItems = calloc(initSize, sizeof(int));
    sPtr->capacity = initSize;
    sPtr->top = 0;
}

// Pre-condition: stack pointed to by sPtr is NOT empty.
// Post-condition: pops and returns the top item from the stack.
int pop(stack* sPtr) {
    sPtr->top--;
    return sPtr->stackItems[sPtr->top];
}

// Pushes value onto the stack pointed to by sPtr.
void push(stack* sPtr, int value) {

    // Array is full double its size.
    if (sPtr->top == sPtr->capacity)
        sPtr->stackItems =
        realloc(sPtr->stackItems, 2*sPtr->capacity*sizeof(int));

    // Put value on top of stack and update top.
    sPtr->stackItems[sPtr->top] = value;
    sPtr->top++;
}

// Test the string function.
void testString() {

    // Create a linked list storing "letters"
    charnode* myword = NULL;
    myword = insertFront(myword, 's');
    myword = insertFront(myword, 'r');
    myword = insertFront(myword, 'e');
    myword = insertFront(myword, 't');
    myword = insertFront(myword, 't');
    myword = insertFront(myword, 'e');
    myword = insertFront(myword, 'l');

    // Convert, print and free.
    char* word = convert(myword);
    printf("%s\n", word);
    free(word);
    freeList(myword);
}

// Returns a string storing what the linked list pointed to by word stores.
char* convert(charnode* word) {

    // First get the length by iterating.
    int len = 0;
    charnode* tmp = word;
    while (tmp != NULL) {
        tmp = tmp->next;
        len++;
    }

    // Allocate space.
    char* res = malloc(sizeof(char)*(len+1));

    // Copy in each letter.
    for (int i=0; i<len; i++) {
        res[i] = word->letter;
        word = word->next;
    }

    // Null terminate and return.
    res[len] = '\0';
    return res;
}

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

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