/***********************************************************************
* linkedlist.h
*
* Header file for a simple inplementation of a singly-linked list
*
* Written by Paul Bonamy - 30 September 2009
* Re-written using pure C - 10 November 2009
************************************************************************/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

/***********************************************************************
 * C doesn't understand classes, so use a struct for the node
 ***********************************************************************/
typedef struct Node {
    // note that we aren't explicitly declaring these public
    // struct members are always automatically public
    int value;          // value stored in the list
    struct Node * next; // next node in the list. set to 0 if last node
    // note that there's no longer a constructor. We'll have
    // to set up next = 0 on our own from here on out.
} LLIST;

/***********************************************************************
 * the LinkedList class used to live here. We can't use classes, though
 * so we'll have global functions and a pointer in main, instead
 ***********************************************************************/

/***********************************************************************
 * void insert(Node**head, int v)
 *
 * Insert a given value into the list in sorted order
 *
 * head -> pointer to head pointer for list
 * v -> value to add to list
 * no return
 ***********************************************************************/
void list_insert(LLIST **head, int v) {
    // we receive a pointer to a pointer because we may need to
    // change what the head pointer is pointing to, not just
    // thing pointer to by the head pointer
    
    // set up the new node and assign it the correct value
    LLIST * newbie = (LLIST *)malloc(sizeof(LLIST));
    newbie->value = v;
    
    if (*head == 0) {
        // the list is empty, so insert is trivially easy
        *head = newbie;
    }
    else {
        // the list isn't empty, so we'll have to be careful
        if ((*head)->value > newbie->value) {
            // the inserted value should be at the beginning
            newbie->next = *head;
            *head = newbie;
        }
        else {
            // we'll be inserting somewhere in the middle of the list
            LLIST * curr = *head; // start from the beginning of the list

            while (curr->next != 0) {
                // run through the list looking for boundary between
                // values <= newbie->value and values > newbie->value
                if (curr->next->value > newbie->value) {
                    break;
                }
                curr = curr->next;
            }

            // at this point, we know curr is the last node with value <=
            // the value of newbie (it may be the last node)
            newbie->next = curr->next; // don't lose things after curr
            curr->next = newbie; // add the new node after curr
        }
    }    
    
    return;
}

/***********************************************************************
 * bool list_lookup(LLIST *head, int v) 
 *
 * Check to see if a given value is present in the list. Return
 * a boolean with the answer
 *
 * head -> head pointer for list 
 * v -> value we're looking for
 * return: bool answer to "is v in the list?"
 ***********************************************************************/

char list_lookup(LLIST *head, int v) {
    // we only need a pointer to the head node, rather than
    // a pointer to a pointer because we won't change which
    // node is the head node
    
    LLIST * curr;       // current place in the list
    
    curr = head;        // begin at the beginning
    
    while(curr != 0) {  // and when you get to the end, stop
        if(curr->value == v) {  
            return 1;    // we hit the value we want, return true
        }
        if(curr->value > v) {
            break;      // values are in order, break if we passed it
        }
        curr = curr->next;
    }
    
    return 0;       // we didn't find it, so return false
}

/***********************************************************************
 * void list_remove(LLIST **head, int v)
 *
 * Remove all instances of a given value from the list
 *
 * head -> pointer to head pointer for list 
 * v -> value to delete from list / no return
 ***********************************************************************/

void list_remove(LLIST **head, int v) {
    // we receive a pointer to a pointer because we may need to
    // change what the head pointer is pointing to, not just
    // thing pointer to by the head pointer
    
    LLIST * curr;        // current place in the list
    LLIST * prev;        // previous place in the list
    
    // start by dealing with the case of v being the first value
    while(*head != 0) {
        if ((*head)->value != v) {
            break;          // head->value no longer equals v, so stop
        }
        curr = (*head)->next;  // don't lose the rest of the list
        free (*head);        // delete the head node
        *head = curr;        // update the head pointer
    }
    
    // list is (now) empty, so return
    if (head == 0) { return;}
    
    // we know the head node doesn't have the value we need
    // so start with the next one and hunt through the list
    prev = *head;
    curr = (*head)->next;
    while (curr != 0) {
        if(curr->value == v) {
            // we need to delete this node
            prev->next = curr->next;    // remove curr from the list
            free(curr);                 // delete curr
            curr = prev->next;          // point curr at the next value
        }
        else {
            // this is not the node you're looking for
            prev = curr;                // update prev
            curr = curr->next;          // update curr
        }
    }
    
    return;
}

/***********************************************************************
 * void list_empty(LLIST **head)
 *
 * Delete all nodes in the list and return
 *
 * head -> pointer to head pointer for list
 * no return
 ***********************************************************************/

void list_empty(LLIST **head) {
    // we receive a pointer to a pointer because we need to
    // change what the head pointer is pointing to, not just
    // thing pointer to by the head pointer
    
    LLIST *curr = *head; // start from the beginning of the list
    *head = 0;           // no need for the head pointer any more
    LLIST *next;        // use this to not get lost in the list
    
    // start at the beginning of the list and delete to the end
    while (curr != 0) {     // note that while (curr) would also work here
        next = curr->next;  // figure out the next node
        free(curr);         // delete the current node
        curr = next;        // make the next node the current node
    }
    
    return;
}

/***********************************************************************
 * void list_print(LLIST **head)
 *
 * Print the contents of all nodes, in the order in which they appear
 *
 * head -> pointer to head pointer for list 
 * no return
 ***********************************************************************/
void list_print(LLIST *head) {
    // we only need a pointer to the head node, rather than
    // a pointer to a pointer because we won't change which
    // node is the head node
    
    LLIST * curr = head; // start from the beginning of the list
    
    // start at the beginning of the list and print to the end
    while (curr != 0) {     // note that while (curr) would also work here
        printf("%d ", curr->value);
//        cout << curr->value << " ";
        curr = curr->next;        // make the next node the current node
    }
    
    if (head == 0) {
        printf("empty");
//        cout << "empty";
    }
    
//    cout << endl;
    printf("\n");   // print a newline when we're done
    
    return;
}

#endif