#include "linked_list.h"

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

void append(struct list_item *first, int x) {
    // find the last element
    struct list_item *current = first;
    while (current->next) {
        current = current->next;
    }
    // insert after
    struct list_item *new = malloc(sizeof(struct list_item));
    new->value = x;
    new->next = NULL;
    current->next = new;
}

void prepend(struct list_item *first, int x) {
    // the first element is a head-element so we insert after it
    struct list_item *new = malloc(sizeof(struct list_item));
    new->value = x;
    new->next = first->next;
    first->next = new;
}

void print(struct list_item *first) {
    // skip printing the head
    struct list_item *current = first->next;
    while (current) {
        printf("%d ", current->value);
        current = current->next;
    }
    printf("\n");
}

void input_sorted(struct list_item *first, int x) {
    struct list_item *current = first;
    // find the first element in the list larger than x
    // (we check current->next since we want to insert after current)
    // if we reach the end (!current->next) we insert after current
    while (current->next && current->next->value <= x) {
        current = current->next;
    }
    struct list_item *new = malloc(sizeof(struct list_item));
    new->value = x;
    new->next = current->next;
    current->next = new;
}

void clear(struct list_item *first) {
    // don't clear head
    struct list_item *current = first->next;
    if (!current) {
        // empty list, don't free anything
        return;
    }
    struct list_item *next;
    while (current) {
        next = current->next;
        free(current);
        current = next;
    }
    first->next = NULL;
}

int main(int argc, char **argv) {
    // head element
    struct list_item root;
    root.value = -1;
    root.next = NULL;

    // empty clears
    clear(&root);
    clear(&root);
    print(&root);

    // short append
    append(&root, 1);
    append(&root, 2);
    append(&root, 3);
    print(&root);
    clear(&root);

    // short prepend
    prepend(&root, 1);
    prepend(&root, 2);
    prepend(&root, 3);
    print(&root);
    clear(&root);

    // mix append prepend
    append(&root, 1);
    append(&root, 2);
    prepend(&root, 4);
    append(&root, 3);
    prepend(&root, 5);
    print(&root);
    clear(&root);

    //// input_sorted
    append(&root, 10);
    append(&root, 20);
    append(&root, 30);
    print(&root);
    // in the middle
    input_sorted(&root, 15);
    input_sorted(&root, 25);
    // at the back (new largest element)
    input_sorted(&root, 35);
    // at the front
    input_sorted(&root, 5);
    print(&root);
    clear(&root);
    print(&root);
}