// Week 8 Monday Lecture
// Create a list with nodes by adding nodes with data 0..9 to the 
// tail of an empty list
// Use a loop to insert nodes at the tail of a new list
// We will leave the function to free nodes until later
// For now we will have a memory leak in this program

// Continued on Thursday Lecture
// Wrote and tested code to insert at any position

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

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

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
int list_length(struct node *head);
struct node * insert_at_tail(struct node *head, int data);  
struct node *insert_middle(struct node *head, int data);
struct node *insert_at_pos(struct node *head, int data, int pos);

int main(void) {
    // A temporary variable we will use
    // when creating new nodes
    struct node *new_node = NULL;

    // Declare and initialise our list
    // Right now this is an empty list but we will add nodes to it
    printf("List 1 elements inserted at start:\n");
    struct node *head = NULL;  
    print_list(head);
    for (int i = 0; i < 10; i++) {
        new_node = create_node(i, head);
        if(new_node == NULL) {
            printf("No more memory\n");
            return 1;
        }
        head = new_node;
        print_list(head);
    }

    
    //create a node with data value i using function
    //add node to tail/end of list
    printf("List 2 elements inserted at start:\n");
    struct node *head2 = NULL;
    printf("Size %d\n", list_length(head2));   
    print_list(head2);
    for (int i = 0; i < 10; i++) {
        head2 = insert_at_tail(head2, i);
        printf("Size %d\n", list_length(head2));
        print_list(head2); 
    }

    // Insert at tail 13 17 42 5
    printf("\nInsert middle\n");
    struct node *head3 = NULL;
    head3 = insert_at_tail(head3, 13);
    head3 = insert_at_tail(head3, 17);
    head3 = insert_at_tail(head3, 42);
    head3 = insert_at_tail(head3, 5);
    print_list(head3);

    printf("\nInsert middle -9\n");
    head3 = insert_middle(head3, -9);
    print_list(head3);
    printf("\nInsert middle 23\n");
    head3 = insert_middle(head3, 23);
    print_list(head3);

    printf("Insert middle 0..9 in a new empty list\n");
    struct node *head4 = NULL;
    for (int i = 0; i < 10; i++) {
        head4 = insert_middle(head4, i);
        print_list(head4);
    } 

    printf("\nInsert at position:\n");
    struct node *head5 = NULL;

    // Insert into a NULL list
    head5 = insert_at_pos(head5, 5, 0);
    print_list(head5);

    // Insert into a size 1 list NOT WORKING
    head5 = insert_at_pos(head5, 7, 0);
    print_list(head5);

    // Insert between 2 nodes
    head5 = insert_at_pos(head5, 9, 1);
    print_list(head5);

    head5 = insert_at_pos(head5, 19, 2);
    print_list(head5);

    // Insert at end 
    head5 = insert_at_pos(head5, 21, 4);
    print_list(head5);
     

    // Insert past the end CRASH.
    head5 = insert_at_pos(head5, 3, 1000);
    print_list(head5);
    

    return 0;
}
 


struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        return NULL;
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

//                  NULL
struct node *insert_at_tail(struct node *head, int data) {
    struct node *new_node = create_node(data, NULL);
    
    // The list is empty
    if (head == NULL ) {
        head = new_node;
    } else {
        struct node *current = head; //NULL
        
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
    return head;
}

int list_length(struct node *head) {
    int counter = 0;
    struct node *curr = head;
    while (curr != NULL) {
        counter++;
        curr = curr->next;
    }
    return counter;
}

struct node *insert_middle(struct node *head, int data) {
    struct node *new_node = create_node(data, NULL);
    int middle = list_length(head)/2;

    if (head == NULL) {
        head = new_node;
    } else {
        struct node *current = head;
        int counter = 0;
        while (counter < middle -1) {
            counter++;
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;    
    }
    return head;
}

struct node *insert_at_pos(struct node *head, int data, int pos) {
    struct node *new_node = create_node(data, NULL);

    if (head == NULL || pos <= 0) {
        new_node->next = head;
        head = new_node;
    } else {
        struct node *current = head;
        int counter = 0;
        while (current->next != NULL && counter < pos - 1) {
            counter++;
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;    
    }
    return head;
}