// list.h - Linked List ADT

#ifndef _LIST_H_
#define _LIST_H_
struct List;
typedef struct ListNode *Position;
List *ListConstruct();  // NULL if fails
void ListDestroy(List *l);
bool ListEmpty(const List *l);
Position ListHead(const List *l);
Position ListFirst(const List *l);
Position ListLast(const List *l);
Position ListAdvance(const List *l, Position p);
Position ListPrevious(const List *l, Position p);
void *ListRetrieve(const List *l, Position p);
bool ListInsert(List *l, Position p, void *item);
void ListDelete(List *l, Position p);
typedef void ListCallback(const void *);
void ListTraverse(const List *l, ListCallback *fn, bool fwd);
#endif

// list.cpp - Linked List ADT

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

struct List {
    ListNode *head;
};

struct ListNode {
    void *item;
    ListNode *next;
};

static void reverse(Position p, ListCallback fn);

List *ListConstruct() {
    List *l;

    l = (List *)malloc(sizeof(List));
    if (l == NULL) {
        return NULL;  // No memory
    }
    l->head = NULL;
    return l;
}

void ListDestroy(List *l) {
    while (!ListEmpty(l)) {
        ListDelete(l, ListFirst(l));
    }
    free(l); 
}

bool ListEmpty(const List *l) {
    return l->head == NULL;
}

Position ListHead(const List *l) {
    return NULL;
}

Position ListFirst(const List *l) {
    return l->head;
}

Position ListLast(const List *l) {
    Position p;

    p = l->head;
    if (p == NULL) {
       return NULL;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    return p;
}

Position ListAdvance(const List *l, Position p) {
    if (p == NULL) {
		p = l->head;
	}
	else {
        p = p->next;
    }
    return p;
}

Position ListPrevious(const List *l, Position p) {
    ListNode *tmp;

    if (p == NULL || l->head == p) {
        return NULL;
    }
    tmp = l->head;
    while (tmp != NULL && tmp->next != p) {
        tmp = tmp->next;
    }
    return tmp;
}

void *ListRetrieve(const List *l, Position p) {
    if (p == NULL ) {
        return NULL;
    }
    return p->item;
}

bool ListInsert(List *l, Position p, void *item) {
    ListNode *tmp;

    tmp = (ListNode *)malloc(sizeof(ListNode));
    if (tmp == NULL) {
        return false;  // No memory
    }
    tmp->item = item;
    if (p == NULL) { // insert at head
        tmp->next = l->head;
        l->head = tmp;
    }
    else {
        tmp->next = p->next;
        p->next = tmp;
    }
    return true;
}

void ListDelete(List *l, Position p) {
    ListNode *prev;

    if (p == NULL) {
        return;  // For safety
    }
    prev = ListPrevious(l, p);
    if (prev == NULL) {  // must be head node
        l->head = p->next;
    }
    else {
        prev->next = p->next;
    }
    free(p);
}

void ListTraverse(const List *l, ListCallback fn, bool fwd) {
    ListNode *p;

    if (fwd) {
        for (p = l->head; p != NULL; p = p->next) {
            fn(p->item);
        }
    }
    else { 
        reverse(l->head, fn);
    }
}

static void reverse(Position p, ListCallback fn) {
    if (p != NULL) {
        reverse(p->next, fn);
        fn(p->item);
    }
}

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

//the callback function
void printname(void *ptr) {
	printf("%s\n", (char *)ptr);
}

int main() {
	List *l;
		position p;

		if  ((l = ListConstruct()) == NULL) {
		exit(EXIT_FAILURE); 	//unable to create list
	}
	p = ListHead(l); // start at front of enpty list
	
	//insert an item at the front
	if (!ListInsert(l,p, "Freddy")) {
		exit(EXIT_FAILURE);
	}
	//insert another item after that - move position first

	p = ListNext(l,p);
	if (!ListInsert(l, p, "Billy")) {
		exit(EXIT_FAILURE);
	}

	//now insert a third one before the last
	if (!ListInsert(l, p, "Johnny")) {
		exit(EXIT_FAILURE);
	}

	//Finally the last one at the end
	p=ListLast(l);
	if (!ListInsert(l, p, "Mickey")) {
		exit(EXIT_FAILURE);
	}

	// Now print out the list in the forward direction

	ListTraverse(l, printname, true);

	//destroy the list before finishing
	ListDestroy(l);
	return 0;
}