/* linklist.m,
 *
 * Yet more linked-list code.
 */

#include <assert.h>
#include <stdlib.h>
#include "linklist.h"


struct ListItem {
    struct ListItem *next, *prev;
    id item;
};

/*------------------------------------------------------------*/

@implementation ListIterator
- initWithList:(struct ListItem *)list
{
    [super init];
    current_node = list;
    return self;
}

- (id) getItem { return current_node->item; }

- (ListIterator *) next
{
    current_node = current_node->next;
    if (current_node != NULL)
	return self;
    else {
	[self free];
	return nil;
    }
}

- (ListIterator *) prev
{
    current_node = current_node->prev;
    if (current_node != NULL)
	return self;
    else {
	[self free];
	return nil;
    }
}
@end

/*------------------------------------------------------------*/

@implementation List
- init
{
    [super init];
    the_list = NULL;
    end_item = NULL;
    return self;
}

- initWithDebug:(char *)file :(int)line
{
    [self init];
#ifdef DEBUG_LINKLIST
    _source_file = file;
    _source_line = line;
    printf("New  list %p created by %s at line %d\n", self, file, line);
#else
    (void)file;
    (void)line;
#endif
    return self;
}

- free
{
    /* This will free the items in a list, unlike remove item. */

#ifdef DEBUG_LINKLIST
    printf("Free list %p created by %s at line %d\n", self, _source_file, _source_line);
#endif

    while (the_list) {
	struct ListItem *n = the_list->next;
	[the_list->item free];
	free(the_list);
	the_list = n;
    }
    return [super free];
}

	/* Inserting. */
- (struct ListItem *) allocateSpaceFor:(id)item
{
    struct ListItem *n = malloc(sizeof(struct ListItem));
    assert(item);
    assert(n && "[Linklist] Error allocating memory for new item.");

    n->item = item;
    return n;
}

- (void) insertItem:(id)item
{
    /* Add to the start of the list. */
    struct ListItem *old_head = the_list;
    struct ListItem *new_head = [self allocateSpaceFor:item];
    new_head->next = old_head;
    new_head->prev = NULL;

    if (old_head) {
	assert(old_head->prev == NULL && "[Linklist] Memory leak!");
	old_head->prev = new_head;
    }
    else
	end_item = new_head;

    the_list = new_head;
}

- (void) insertItem:(id)item before:(id)item2
{
    struct ListItem *l, *n;

    for (l = the_list; l; l = l->next) {
	if (l->item == item2)
	    break;
    }

    /* If item2 doesn't exist or we are at the start of the list, just
       add it to the start of the list. */
    if (!l || l == the_list) {
	[self insertItem:item];
	return;
    }

    n = [self allocateSpaceFor:item];
    n->next = l;
    n->prev = l->prev;
    l->prev->next = n;
    l->prev = n;
}

- (void) insertItem:(id)item after:(id)item2
{
    struct ListItem *l, *n;

    for (l = the_list; l; l = l->next) {
	if (l->item == item2)
	    break;
    }

    /* If item2 doesn't exist or we are at the end of the list, just
       add it to the end of the list. */
    if (!l || l == end_item) {
	[self insertItemAtEnd:item];
	return;
    }

    n = [self allocateSpaceFor:item];
    n->prev = l;
    n->next = l->next;
    l->next->prev = n;
    l->next = n;
}

- (void) insertItemAtEnd:(id)item
{
    struct ListItem *new_item;

    /* If the list doesn't contain anything, just add it. */
    if (!the_list) {
	[self insertItem:item];
	return;
    }

    new_item = [self allocateSpaceFor:item];
    new_item->next = NULL;
    new_item->prev = end_item;
    assert(end_item->next == NULL && "[Linklist] Memory leak!");
    end_item->next = new_item;
    end_item = new_item;
}

	/*----- Removing. -----*/
- (BOOL) removeItem:(id)item
{
    /* This function only unlinks an item, but does not destroy it. */
    struct ListItem *l;

    for (l = the_list; l; l = l->next) {
	if (l->item != item)
	    continue;

	if (l->next)
	    l->next->prev = l->prev;
	if (l->prev)
	    l->prev->next = l->next;
	if (l == the_list)
	    the_list = l->next;
	if (l == end_item)
	    end_item = l->prev;

	free(l);
	return YES;
    }

    return NO;
}

- (void) removeAllItems
{
    /* This function only unlinks items, but does not destroy them. */
    struct ListItem *l, *n;

    for (l = the_list; l; l = n) {
	n = l->next;
	free(l);
    }
    the_list = NULL;
    end_item = NULL;
}

- (ListIterator *) getIterator;
{
    if (the_list)
	return [[ListIterator alloc] initWithList:the_list];
    else
	return nil;
}

- (BOOL) isEmpty { return (the_list ? NO : YES); }

- (int) length
{
    struct ListItem *l;
    int n = 0;

    for (l = the_list; l; l = l->next)
	n++;
    return n;
}
@end


/*------------------------------------------------------------*/

#ifdef TEST

@interface A: Object
@end

@implementation A
@end

void log_list(List *list)
{
    ListIterator *it;

    printf("---\n");
    foreach (it, list)
	printf(" %p\n", [it getItem]);
    printf("\n");
}

int main()
{
    List *list = [LIST_NEW];
    A *item1 = [A new];
    A *item2 = [A new];
    A *item3 = [A new];

    printf("List initialized.\n");
    log_list(list);

    printf("Inserting item %p at the start of the list.\n", item1);
    [list insertItem:item1];
    log_list(list);

    printf("Removing item %p.\n", item1);
    [list removeItem:item1];
    log_list(list);

    printf("Inserting item %p before %p (non-existant).\n", item2, item1);
    [list insertItem:item2 before:item1];
    log_list(list);

    printf("Inserting item %p after %p (non-existant).\n", item3, item1);
    [list insertItem:item3 after:item1];
    log_list(list);

    printf("Inserting item %p at the end of the list.\n", item1);
    [list insertItemAtEnd:item1];
    log_list(list);

    printf("Removing item %p.\n", item3);
    [list removeItem:item3];
    log_list(list);

    printf("Inserting item %p at the end of the list.\n", item3);
    [list insertItemAtEnd:item3];
    log_list(list);

    printf("Freeing entire list.\n");
    list = [list free];
    log_list(list);

    return 0;
}

#endif
