/*
 * Implementation of list.h.
 */

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

List* NewList() {
    List* rtn;
    rtn = (List*) malloc(sizeof(struct ListStruct));
    rtn->first = null;
    rtn->last = null;
    rtn->size = 0;
    rtn->ref_count = 0;
    rtn->enum_elem = null;
    return rtn;
}

List* NewList1(ListElemData* e) {
    List* l = NewList();
    PutList(l, e);
    return l;
}

bool ListEquals(List* l1, List* l2) {
    return ListEqualsWithFunction(l1, l2, null);
}

bool ListEqualsWithFunction(List* l1, List* l2,
	bool (*equals_func)(ListElemData*, ListElemData*)) {
    ListElem *e1, *e2;

    if ((l1 == null) || (l2 == null) || (l1->size != l2->size)) return false;
    for (e1 = l1->first, e2 = l2->first; e1 != null;
	    e1 = e1->next, e2 = e2->next) {
	if (equals_func == null) {
	    if (e1->data != e2->data) return false;
	}
	else {
	    if (! equals_func(e1->data, e2->data)) return false;
	}
    }

    return true;
}

List* CopyList(List* l) {
    return CopyListWithFunction(l, null);
}

List* CopyListWithFunction(List* l, void* (*copy_func)(ListElemData*)) {
    List* newl;
    ListElem* e;

    if (l == null) return;
    newl = NewList();
    for (e = l->first; e != null; e = e->next) {
        if (copy_func == null)  {
	    PutList(newl, e->data);
	}
	else {
	    PutList(newl, copy_func(e->data));
	}
    }

    return newl;
}

void DelList(List* l) {
    DelListWithFunction(l, null);
}

void DelListWithFunction(List* l, void (*del_func)(ListElemData*)) {
    ListElem* elem, *elem_to_free;

    if (l == null) return;
    for (elem = l->first; elem; ) {
	free(elem->data);
        elem_to_free = elem;
	elem = elem->next;
	if (del_func == null) {
	    free(elem_to_free);
	}
	else {
	    del_func(elem_to_free);
	}
    }
    free(l);
}

void DelListNodesOnly(List* l) {
    ListElem* elem, *elem_to_free;

    if (l == null) return;
    for (elem = l->first; elem; ) {
        elem_to_free = elem;
	elem = elem->next;
	free(elem_to_free);
    }
    free(l);
}

List* PutList(List* l, ListElemData* e) {
    ListElem* newe;

    if (l == null) return;
    newe = (ListElem*) malloc(sizeof(struct ListElemStruct));
    newe->data = e;
    newe->next = null;
    newe->prev = l->last;
    if (l->last != null)
	l->last->next = newe;
    l->last = newe;
    if (l->first == null) {
	l->first = newe;
	l->enum_elem = l->first;
    }
    l->size++;

    return l;
}

ListElemData* PullList(List* l) {
    ListElem* elem = l->first;
    ListElemData* data;

    if ((l == null) || (l->size == 0)) return null;
    if (l->first == l->last) {
	l->first = l->last = l->enum_elem = null;
	l->size = 0;
	data = elem->data;
	free(elem);
	return data;
    }
    l->first = l->enum_elem = elem->next;
    l->first->prev = 0;
    l->size--;
    data = elem->data;
    free(elem);
    return data;
}

List* PushList(List* l, ListElemData* e) {
    ListElem* newe = (ListElem*) malloc(sizeof(struct ListElemStruct));

    if (l == null) return
    newe->data = e;
    newe->prev = null;
    newe->next = l->first;
    if (l->first)
	l->first->prev = newe;
    l->enum_elem = l->first = newe;
    if (! l->last)
	l->last = newe;
    l->size++;

    return l;
}

ListElemData* PopList(List* l) {
    ListElem* elem = l->last;
    ListElemData* data;

    if ((l == null) || (l->size == 0)) return null;
    if (l->first == l->last) {
	l->first = l->last = l->enum_elem = null;
	l->size = 0;
	data = elem->data;
	free(elem);
	return data;
    }
    l->enum_elem = l->first;
    l->last = elem->prev;
    l->last->next = 0;
    l->size--;
    data = elem->data;
    free(elem);
    return data;
}

ListElemData* GetListNth(List* l, int n) {
    int size;
    ListElem* elem;

    if ((l == null) || ((size = l->size) == 0) ||
	(n < 1) || (n > size)) return null;
    if (n < size/2) {
	elem = l->first;
	while(--n)
	    elem = elem->next;
    }
    else {
	elem = l->last;
	while(++n <= size)
	    elem = elem->prev;
    }
    l->enum_elem = l->first;
    return elem->data;
}

ListElemData* DelListNth(List* l, int n) {
    int size;
    ListElem* elem, *prev;
    ListElemData* data;

    if ((l == null) || ((size = l->size) == 0) ||
	(n < 1) || (n > size)) return null;
    if (n == 1)
	return PullList(l);
    if (n == size)
	return PopList(l);
    if (n < size/2) {
	elem = l->first;
	while(--n)
	    elem = elem->next;
    }
    else {
	elem = l->last;
	while(++n <= size)
	    elem = elem->prev;
    }
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
    l->enum_elem = l->first;
    l->size--;
    data = elem->data;
    free(elem);

    return data;
}

List* SubList(List* l, int m, int n) {
    int size, i;
    List* rtn;
    ListElem* e;

    if ((l == null) || ((size = l->size) == 0) ||
	(m < 1) || (m > size) || (n < 1) || (n > size) || (m > n)) return null;
    rtn = NewList();
    for (i = 1, e = l->first; i < m; i++, e = e->next) ;
    for (; i <= n; i++, e = e->next) {
	PutList(rtn, e->data);
    }
    rtn->ref_count = 0;
    rtn->size = n - m + 1;
    return rtn;
}

List* ConcatLists(List* l1, List* l2) {
    List* newl;
    ListElem* e;

    if ((l1 == null) && (l2 == null)) return null;
    newl = NewList();

    if (l1 != null) {
	for (e = l1->first; e != null; e = e->next) {
	    PutList(newl, e->data);
	}
    }
    if (l2 != null) {
	for (e = l2->first; e != null; e = e->next) {
	    PutList(newl, e->data);
	}
    }

    newl->ref_count = 0;
    newl->enum_elem = newl->first;

    return newl;
}

int InList(List* l, ListElemData* e) {
    return InListWithFunction(l, e, null);
}

int InListWithFunction(List* l, ListElemData* e,
        bool (*compare_func)(ListElemData*, ListElemData*)) {
    ListElem* elem;
    bool comparison;
    int pos;

    if ((l == null) || (l->size == 0)) return 0;
    for (elem = l->first, pos = 1; elem; elem = elem->next, pos++) {
	if (compare_func == null) {
	    comparison = e == elem->data;
	}
	else {
	    comparison = compare_func(e, elem->data);
	}
	if (comparison == true) {
	    return pos;
	}
    }
    return 0;
}

int ListLen(List* l) {
    if (! l)
	return 0;
    return l->size;
}

ListElemData* EnumList(List* l) {
    ListElem* elem;

    if (! l)
	return null;

    if (elem = l->enum_elem) {
	l->enum_elem = l->enum_elem->next;
	return elem->data;
    }
    else {
	l->enum_elem = l->first;
	return null;
    }
}

void ResetListEnum(List* l) {
    l->enum_elem = l->first;
}

int IncrListRefs(List* l) {
    return ++(l->ref_count);
}

int DecrListRefs(List* l) {
    return --(l->ref_count);
}

void PrintList(List* l, void (*print_func)(ListElemData*)) {
    ListElem* elem;

    printf("[");
    for (elem = l->first; elem; elem = elem->next) {
	if (elem->next) {
	    print_func(elem->data);
	    printf(", ");
	}
	else {
	    print_func(elem->data);
	    printf("]", elem->data);
	}
    }
}