/*
    basiclist.c
    An implementation of the ADT described in "basiclist.h"
    cmc, updated 10/23/08
*/

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "basiclist.h"

/* private data structure for a list node */
typedef struct NodeTag {
    InfoPointer info;
    struct NodeTag *link;
} NodeType, *NodePointer;

/* definition of structure for whole list */
struct ListTag{
    int constructed;  /* boolean to prevent null pointer problems */
    NodePointer first; /* points to first node or NULL for empty list */
    NodePointer last;  /* points to last node or NULL for empty list */
    NodePointer current; /* points to "current" node or NULL for empty list*/
};

/* constructor - must be used before any other list functions
                 i.e., precondition of all functions below is that
                       this function is executed first */
ListPointer createList(void) {
    ListPointer list;
    if ((list = (ListPointer)malloc(sizeof(struct ListTag))) == NULL) {
        printf("out of memory");
        exit(1);
    }
    else {
        list->first = list->last = list->current = NULL;
        list->constructed = 1;
    }
    return list;
}

/* macro, OK, is used to verify that list has been constructed */
#define OK(list)  ((list)->constructed)

/* true if list has no items */
int emptyList(ListPointer list) {
    assert(OK(list));
    return list->first == NULL;
}

/* clear all items in list - make it empty */
void clearList(ListPointer list) {
    assert(OK(list));
    while (list->first != NULL)
        deleteFirst(list);
    list->last = list->current = NULL;
}

/* returns pointer to info of first item */
InfoPointer firstInfo(ListPointer list) {
    assert(OK(list));
    if (list->first != NULL) {
        list->current = list->first;
        return list->first->info;
    }
    else return NULL;
}

/* returns pointer to info of last item */
InfoPointer lastInfo(ListPointer list) {
    assert(OK(list));
    if (list->last != NULL) {
        list->current = list->last;
        return list->last->info;
    }
    else return NULL;
}

/* returns pointer to current info */
InfoPointer currentInfo(ListPointer list) {
    assert(OK(list));
    if (list->current != NULL)
        return list->current->info;
    else
        return NULL;
}

/* private utility function to create a new node */
NodePointer createNode(const InfoPointer info) {
    NodePointer n;
    if ((n = (NodePointer)malloc(sizeof(NodeType))) == NULL) {
        fprintf(stderr, "out of memory");
        exit(1);
    }
    else {
        n->info = info;
        n->link = NULL;
    }
    return n;
}

/* inserts new first item containing the info passed */
void insertFirst(InfoPointer info, ListPointer list) {
    NodePointer n;
    assert(OK(list));
    n = createNode(info);
    if (emptyList(list))
        list->first = list->last = list->current = n;
    else {
        n->link = list->first;
        list->first = list->current = n;
    }
}

/* inserts new last item containing the info passed */
void insertLast(InfoPointer info, ListPointer list) {
    NodePointer n;
    assert(OK(list));
    n = createNode(info);
    if (emptyList(list))
        list->first = list->last = list->current = n;
    else {
        list->last->link = n;
        list->last = list->current = n;
    }
}
    
/* insert new item before current item */
void insertBeforeCurrent(InfoPointer info, ListPointer list) {
    NodePointer n;
    InfoPointer temp;
    assert(OK(list));

    if (emptyList(list))
        insertFirst(info, list);

    else {
        /* trick to keep from searching: insert after, then swap info */
        n = list->current;
        insertAfterCurrent(info, list);
        if (n != NULL) {
           temp = n->info;
           n->info = list->current->info;
           list->current->info = temp;
        }
        list->current = n; /* point to original node, with new info */
    }
}

/* insert new item after current item */
void insertAfterCurrent(InfoPointer info, ListPointer list) {
    NodePointer n;
    assert(OK(list));
    if (list->current == list->last)
        insertLast(info, list);
    else {
        n = createNode(info);
        n->link = list->current->link;
        list->current->link = n;
        list->current = n;
    }
}

/* deletes the first item, and frees storage used by node */
InfoPointer deleteFirst(ListPointer list) {
    NodePointer n;
    InfoPointer info;
    assert(OK(list));
    if (emptyList(list))
        info = NULL;
    else {
        n = list->first;
        if (list->last == n) /* just one node is a special case */
           list->last = NULL;
        list->first = list->current = n->link;
        info = n->info;
        free(n);
    }
    return info;
}

/* deletes the last item, and frees storage used by node */
InfoPointer deleteLast(ListPointer list) {
    NodePointer n, nprev;
    InfoPointer info;
    assert(OK(list));
    if (emptyList(list))
        info = NULL;
    else {
        n = list->last;
        if (list->first == n) /* just one node */
           list->first = list->last = list->current = NULL;
        else {
            for (nprev=list->first; nprev->link != n; nprev=nprev->link)
                ;    /* find second to last node */
            nprev->link = NULL;
            list->last = list->current = nprev;
        }
        info = n->info;
        free(n);
    }
    return info;
}

/* deletes current item from list, and frees storage used by node */
InfoPointer deleteCurrent(ListPointer list) {
    NodePointer n;
    InfoPointer info;
    assert(OK(list));
    if (list->current == list->first)
        info = deleteFirst(list);
    else if (list->current == list->last)
        info = deleteLast(list);
    else {
        for (n=list->first; n->link != list->current; n=n->link)
            ;    /* find node just prior */
        n->link = list->current->link;
        info = list->current->info;
        free(list->current);
        list->current = n;
    }
    return info;    
}

/* sets current to first item */
void resetCurrent(ListPointer list) {
    assert(OK(list));
    list->current = list->first;
}

/* sets current pointer to next information, or
   does nothing if current already points to last */
void advanceCurrent(ListPointer list) {
    assert(OK(list));
    if (list->current != list->last)
        list->current = list->current->link;
}

/* returns true if list is not empty, and
           current information is not last information */
int hasMoreInfo(ListPointer list) {
    assert(OK(list));
    return list->current != list->last;
}