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

typedef struct _Node { // canonical name struct _Node
    int value;
    struct _Node* next; // need to use canonical name
// invalid: Node* next;
/*
linked_list.c:8:2: error: unknown type name ‘Node’
  Node* next;
  ^~~~
*/
} Node; // shortcut name: Node

void print_linked_list(Node* head) {
    // loop to iterate the linked list
    // we could write this as a while loop
    // per CQ, its better to write as a for loop
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        printf("[%d]", cur->value);
        printf("%s", cur->next == NULL ? "\n" : "->");
    }
}


void insert(int value, Node** a_head, int index) {
    Node* new_node = malloc(sizeof(*new_node));
    // normally initializer is prefered, but this is valid
    new_node->value = value;
    new_node->next = NULL;

    if (*a_head == NULL || index == 0) {
        new_node->next = *a_head;
        *a_head = new_node;
    } else {
        // step 1: find the location to insert
        Node* insert_after = *a_head;
        for (int cur_idx = 1; cur_idx < index; cur_idx++) {
            insert_after = insert_after->next;
            // TODO: if index is bigger than size of list
            // this will segfault
        }
        // step 2: insert the node
        new_node->next = insert_after->next;
        // pitfall: doing this line first means we lose
        // the old insert_after->next
        insert_after->next = new_node;
        // pitfall: this statement has no impact
        // insert_after = new_node
    }
}


void destroy_linked_list(Node** a_head) {
    Node* cur = *a_head;
    while (cur != NULL) {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
    *a_head = NULL;
}

int main(int argc, char* argv[]) {
    // linked list of size 0
    // NULL
    Node* head = NULL;
    print_linked_list(head);
    assert(head == NULL);

    // linked list of size 1
    // [5]->NULL
    insert(5, &head, 0);
    print_linked_list(head);
    assert(head != NULL);
    assert(head->next == NULL);

    // linked list of size 2
    // [5]->[7]->NULL
    insert(7, &head, 1);
    printf("Insert 7 at 1: ");
    print_linked_list(head);
    assert(head->next != NULL);
    assert(head != head->next);
    assert(head->next->next == NULL);

    // linked list of size 3
    // [9]->[5]->[7]->NULL
    insert(9, &head, 0);
    printf("Insert 9 at 0: ");
    print_linked_list(head);
    assert(head->next->next != NULL);
    assert(head->next->next->next == NULL);

    // linked list of size 4
    // [9]->[5]->[1]->[7]->NULL
    insert(1, &head, 2);
    printf("Insert 1 at 2: ");
    print_linked_list(head);
    assert(head->next->next->next != NULL);
    assert(head->next->next->next->next == NULL);

    // a later node in a linked list is a valid linked list
    print_linked_list(head->next);

    destroy_linked_list(&head);
    assert(head == NULL);

    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */