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

// Insert the given value into the list at Node head.
// Return the location of insertion.
Node * list_insert(Node * head, int value)
{
    Node * newnode;
    Node * retval;

    newnode = (Node *)malloc(sizeof(Node));
    newnode -> value = value;

    retval = head;

    if (head == NULL) {
        newnode -> prev = NULL;
        newnode -> next = NULL;
        retval = newnode;
    } else {
        Node * current = head;
        while ((current -> next != NULL) && 
               (current -> value < newnode -> value)) {
            current = current -> next;
        }
        
        if (current -> next == NULL) {
            if (current -> value < newnode -> value) {
                current -> next = newnode;
                newnode -> prev = current;
                newnode -> next = NULL;
            } else {
                newnode -> next = current;
                newnode -> prev = current -> prev;
                current -> prev -> next = newnode;
                current -> prev = newnode;
            }
        } else if (current -> prev == NULL) {
            newnode -> next = current;
            newnode -> prev = current -> prev;
            current -> prev = newnode;
            retval = newnode;
        } else {
            newnode -> next = current;
            newnode -> prev = current -> prev;
            current -> prev -> next = newnode;
            current -> prev = newnode;
        }
    }
    return retval;
}

// Remove the first occurrance of value from the list
// starting with Node head.
int list_remove(Node * head, int value)
{
    Node * current;
    int retval;

    current = head;
    while ((current != NULL) && (current -> value != value)) {
        current = current -> next;
    }
    
    if (current == NULL) {
        retval = 0;
    } else {
        if (current == head) {
            //at the head of the list
            head = head -> next;
            head -> prev = NULL;
            free(current);
            retval = 1;
        } else if (current -> next == NULL) {
            current -> prev -> next = NULL;
            free(current);
            retval = 1;
        } else {
            current -> prev -> next = current -> next;
            current -> next -> prev = current -> prev;
            free(current);
            retval = 1;
        }
    }
    return retval;
}


// Return the length of the list at Node head.
int list_length(Node * head)
{
    int retval;
    Node * current;

    current = head;
    retval = 0;

    while (current != NULL) {
        retval++;
        current = current -> next;
    }
    return retval;
}

// Print the contents of the list in format [v0 v1 v2 ... vn]
void list_toString(Node * head)
{
    Node * current;

    current = head;
    printf("[");
    while( current -> next != NULL ) {
        printf("%d ", current -> value);
        current = current -> next;
    }
    printf("%d]", current -> value);
}