#include<stdlib.h>
/* TODO: malloc.  */
#include"List.h"

/*
 *  doubly-linked list.
 *  interfaces of these routines is based on glib.
 *
 *  Usage:
 *  create new list.
 *  	list = NULL
 *  add new data
 *  	list = _listAddFirst(list, data)
 *  remove data from the list
 *  	list = _listRemove(list, data)
 *  get n-th data
 *  	data = _listGetnthData(list, n)
 *
 *
 *  NOTE:
 *  Although `struct List' is a doubly-linked List, the List
 *  is made as a Ring.  An User's variable is treated as a
 *  head of the list.  And head->prev is last.  And then if
 *  list have only one data, both next and prev field of
 *  head will point to oneself.
 *  If the variable is NULL, it means no data.
 */

List *
_listAddFirst(List* top, void *data)
{
	List *newlist;
	List *last;
	newlist = malloc(sizeof(struct _List));
	newlist->data = data;

	if (!top) {
		newlist->next = newlist;
		newlist->prev = newlist;
		return newlist;
	}
	last = top->prev;
	newlist->next = top;
	newlist->prev = last;

	top->prev = newlist;
	last->next = newlist;
	return newlist;
}

List *
_listRemove(List *top, void *data)
{
	List *t;
	if (top->data==data) {
		if (top->next==top) {
			free(top);
			return NULL;
		}
		List *newtop = top->next;
		top->next->prev = top->prev;
		top->prev->next = top->next;
		free(top);
		return newtop;
	}
	for (t=top->next; t!=top; t=t->next) {
		if (t->data==data) {
			t->next->prev = t->prev;
			t->prev->next = t->next;
			free(t);
			return top;
		}
	}
	return top;
}

void *
_listGetnthData(List *top, int n)
{
	List *t;

	for (t=top; n>0; n--) {
		t = t->next;
		if (t==top) return NULL;
	}

	return t->data;
}
void *
_listGetLastData(List *top)
{
	if (!top) return NULL;
	return top->prev->data;
}

List *
_listMoveLasttoFirst(List *top)
{
	if (!top) return NULL;
	return top->prev;
}

void
_listApply(List *top, ApplyFn fn, void *arg)
{
	List *t = top;
	do {
		fn(t->data, arg);
		t = t->next;
	} while ( t!=top );
}

/*
 *  Iterator's functions.
 *
 *  iter = _listIterator(list);
 *  while ( (data=_listIterNext(iter)!=NULL ) {
 *  	exe(data);
 *  	if (data...) {
 *  		list = _listIterRemove(iter);
 *  	}
 *  }
 */
ListIter *
_listIterator(List *top)
{
	ListIter *iter;
	iter = malloc(sizeof(struct _ListIter));
	iter->head = top;
	iter->next = top;
	return iter;
}

void *
_listIterNext(ListIter *iter)
{
	void *rtn;
	if (!iter->next) return NULL;

	rtn = iter->next->data;
	iter->next = iter->next->next;
	if (iter->next==iter->head) {
		iter->next = NULL;
	}
	return rtn;
}

void
_listIterEnd(ListIter *iter)
{
	free(iter);
}

List *
_listIterRemoveCurrent(ListIter *iter)
{
	List *cur, *p, *n;
	if (!iter->head) return NULL;
	else if (!iter->next) cur = iter->head->prev;
	else cur = iter->next->prev;

	if (cur==iter->head) {
		if (cur->next==iter->head) {
			free(iter->head);
			return NULL;
		}
		iter->head = iter->head->next;
	}
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;

	free(cur);
	return iter->head;
}


/*
 *  for DEBUG
 */

int
_listRingCheck(List *head)
{
	List *cur = head;

	if (cur->prev->next!=cur) return 0;
	if (cur->next->prev!=cur) return 0;
	do {
		if (cur->prev->next!=cur) return 0;
		if (cur->next->prev!=cur) return 0;
		cur = cur->prev;
	} while (cur!=head);

	if (cur->prev->next!=cur) return 0;
	if (cur->next->prev!=cur) return 0;
	cur = cur->next;
	if (cur->prev->next!=cur) return 0;
	if (cur->next->prev!=cur) return 0;

	return 1;
}