//This is the implementation file
//Include the implementation of anything defined in the header file
// This is the same implementation file we used in Week 07
// This week we are looking at inserting into a linked list at any point
// Sasha Vassar Week08 Lecture 13

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

//Define a node 
struct node {
    int data;
    struct node *next;
};

//Function that creates a node

struct node *create_node(int data, struct node *next) {
    //create a pointer to a node of type struct node 
    //by using malloc to allocate memory
    
    //(4, NULL)
    // new_node = some address that points to that node
    //(2, head) 
    struct node *new_node = malloc(sizeof(struct node)); 
    
    //Initialise the data by setting it to the given int
    //new_node (int data) = 4
    //new_node (int data) = 2
    new_node->data = data;
    
    //Initialise next pointer to point to the next node given
    //new_node (struct node *next) = NULL
    // new_node(struct node *next) = head (4) 
    new_node->next = next;
    
    //What will I need to return?
    return new_node;
}

//Function that prints a list
void print_list(struct node *head) {
//create a way to keep track of where we are in the list
    struct node *current = head;
    
    while (current != NULL) {
        //print out the node value
        printf("%d -> ", current->data);
        //increment to the next node
        current = current->next;
    }
    printf("X\n");
}


//Function to insert node in the middle of a list (between two other nodes
//that exist)
//Inputs and outputs
//Inputs: int data, head
//Outputs: head
struct node *insert_middle(int data, struct node *head) {
    //create a pointer and point it to the head of the list
    //that will keep track of where you are
    struct node *current = head;
    //create the new node that you want to insert by using 
    //the create_node function we wrote last week
    struct node *new_node = create_node(data, NULL); 
    //Start traversing through my list by checking if I am at NULL 
    //which signals the end of the list
    while (current != NULL) {
        //Check where to insert 
        //(this decision assumes nodes are in numerical order)
        
        /*ANOTHER EASTER EGG - Now that you have seen a whole bunch of 
        / different ways that we can do our while loop condition to 
        / search for the needed node, can you fix the condition on 
        / line 79? Can you combine it with line 71's while loop?
        */
        if (current->data < data && current->next->data > data) {
            new_node->next = current->next;
            current->next = new_node;
        }
        //increment to the next node - otherwise you have an infinite loop!
        current = current->next;
    }
    //current = NULL
    //return the head of the list with the new node attached in
    return head;  
}


//Function to insert node at the end of a list
//Inputs and outputs
//Inputs: int data, head
//Outputs: head 
struct node *insert_endnode(int data, struct node *head) {
    //create a pointer and point it to the head of the list
    //that will keep track of where you are
    struct node *current = head;
    //create the new node that you want to insert by using 
    //the create_node function we wrote last week
    struct node *new_node = create_node(data, NULL);
    //Loop through until you get to the last node in the list
    //You want to stop at the last node and not go past it
    while (current->next != NULL) {
        current = current->next;
    }
    //Set the new node as the last node, but pointing the current node to it
    current->next = new_node;
    new_node->next = NULL;
    
    return head;  
}

//Inputs and Outputs?
//
struct node *delete_node (int data, struct node *head) {
    //TODO: create a current pointer that is set to the head of the list
    struct node *current = head;
    // TODO: Boundary conditions:
    // 1) if there is nothing in the list 
    if (current == NULL) {
        return NULL;
    // 2) if the item we want to delete is at the head of the list
    // or if there is only one item in the list  
    // Therefore, deleting at the head of the list
    } else if (current->data == data) {
        struct node *new_head = current->next;
        free(current);
        return new_head;
    // if there is only one node in the list and it is the one to be deleted
    // above will capture it.
    } 
    //TODO: Otherwise start looping through the list to find the data 
    //1. find the previous node to the one you want to delete
    while (current->next->data != data && current->next->next != NULL) {
        current = current->next;
    }
    //2. if the next node is the one to be deleted 
    if (current->next->data == data) {
        // create a pointer to the new next
        struct node *new_next = current->next->next;
        // 3. free the node to be deleted
        free(current->next);
        //point the next node to the new pointer
        current->next = new_next;
    }
    return head;
}

void free_list(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        struct node *free_node = current;
        current = current->next;
        free(free_node);
    }
}