//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 have three problems to do as revision
// Sasha Vassar Week10, Lecture 17

#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) {
    
    struct node *new_node = malloc(sizeof(struct node)); 
    new_node->data = data;
    new_node->next = next;

    return new_node;
}

//Function that prints a list
void print_list(struct node *head) {
    
    struct node *current = head;
    
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("X\n");
}


//Function to insert node in the middle of a list (between two other nodes
//that exist)
struct node *insert_middle(int data, struct node *head) {
    
    struct node *current = head;
    struct node *new_node = create_node(data, NULL); 
    
    while (current != NULL) {
        /*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;
        }
        current = current->next;
    }
   
    return head;  
}

//Function to insert node at the end of a list
struct node *insert_endnode(int data, struct node *head) {
   
    struct node *current = head;
    struct node *new_node = create_node(data, NULL);
    
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
    new_node->next = NULL;
    
    return head;  
}

struct node *delete_node (int data, struct node *head) {

    struct node *current = head;

    if (current == NULL) {
        return NULL;
    } else if (current->data == data) {
        struct node *new_head = current->next;
        free(current);
        return new_head;
    } 
    while (current->next->data != data && current->next->next != NULL) {
        current = current->next;
    }
    if (current->next->data == data) {
        struct node *new_next = current->next->next;
        free(current->next);
        current->next = new_next;
    }
    return head;
}

//Function to free the whole list (deallocate all the memory)
void free_list(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        struct node *free_node = current;
        current = current->next;
        free(free_node);
    }
}

//TODO: Function to find the nodes that are divisible by specified number
void find_divisible(int divisor, struct node *head){
    // divisor == "the number we're testing divisibility by"
    // head == "the start of the linked list"
    
    // DONE: Set the node that you will use to traverse through the list
    struct node *current = head;
    
    while (current != NULL) { // DONE: What condition do you need to traverse through the whole list?
        if (current->data % divisor == 0) { // DONE: When should we stop and print out a node?
            printf("%d\n", current->data);
        }
        current = current->next;
    }
    
    // current is equal to NULL here.
}

//TODO: Function to find the nodes that are divisible by specified number and then delete the node
struct node *delete_divisible(int divisor, struct node *head){
    
    //TODO: Boundary cases
    // what about a NULL list?  DONE
    // what about a list with 1 node; and I have to delete that node? DONE
    // what if I have to delete the head? DONE
    // what if I have to delete the tail?
    // what if there's nothing to delete?
    
    // TODO: test a list like: 9 -> 9 -> ...
   
   if (head == NULL) {
       // List is empty.
       
       return NULL; // or head
   }
   
   if (head->data % divisor == 0) {
       // Deleting the head node...
       struct node *new_head = head->next;
       free(head);
   
       return new_head;
   }
   
    //TODO: Set the node that you will use to traverse through the list
    // It may be useful to keep track of a previous node here as well so that 
    // when you get to the node you want to delete, you have kept track of 
    // previous 
    struct node *current = head;
    struct node *previous = NULL;
    
    while (current != NULL && current->data % divisor != 0) {
        previous = current;
        current = current->next;
    }
    // EITHER: current == NULL (so, end of the list)
    // OR:     current->data % divisor == 0 (so we found something)
        
    if (current == NULL) {
        return head;
    }
    
    // YAY! we can delete something
    
    previous->next = current->next;
    free(current);
   
  
    return head;
}


//TODO: Function to find range of a list (largest number minus smallest number)
int find_range(struct node *head) {
    //TODO: Any boundaries?
    if (head == NULL) {
        return 0;
    }
  
    //TODO: Otherwise, you may need some helpers! 
    int smallest = find_smallest(head);
    int largest = find_largest(head);
    
    return largest - smallest;        
}


//TODO: Helper function to find smallest element of a list
int find_smallest(struct node *head){
    struct node *current = head;
    int smallest = current->data;
    
    while (current != NULL) {
        if (current->data < smallest) {
            smallest = current->data;
        }
    
        current = current->next;
    }
  
    return smallest;
}
//TODO: Helper function to find largest element of a list
int find_largest(struct node *head){
    struct node *current = head;
    int largest = current->data;
    
    while (current != NULL) {
        if (current->data > largest) {
            largest = current->data;
        }
        
        current = current->next;
    }
    
    return largest;
}


//TODO: Function to insert in the middle of a linked list 
struct node *insert_mid(int data, struct node *head) {
    
    //TODO: Find how many nodes there are in this list
    
    
    //TODO: Where does the middle node occur?
    
    //TODO: Insert after that node by creating the new node and then inserting
    
    return head;
}