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

/*
 *
 *  UserInterface
 *
 *  list = createList();
 *  addFirst(list, data);
 *  addLast(list, data);
 *  getFirst(list, data);
 *  getLast(list, data);
 *  destroyList(list);
 *
 *  iter = createIterator(list);
 *  while (HasNext(iter)) {
 *    data = Next(iter);
 *    if (data->l...)
 *      Remove(iter);
 *  }
 *  destroyListIter(iter);
 *
 *
 *  from JavaDoc java.util.Iterator<E>
 *    boolean hasNext() Returns true if the iteration has more elements.
 *    E       next()    Returns the next element in the iteration.
 *    void    remove()  Removes from the underlying collection the last element returned by the iterator.
 *
 *
 * ユーザは常にcreateList()で生成されたList構造体をもつ
 * このbaseだけは特別で何もデータを所持していない
 *   base->nextは最初の要素
 *   base->prevは最後の要素を指している
 * それ以外のListは通常どおり、
 *   list->nextは次の要素
 *   list->prevは前の要素を指す
 * 最初の要素のlist->prev, 際の要素のlist->nextはNULL.
 * baseを指したりしない
 *
 *
 */


List *
createList()
{
	List *newlist;
	newlist = malloc(sizeof(List));
	newlist->next = NULL;
	newlist->prev = NULL;
	return newlist;
}

void
destroyList(List *list)
{
}

int
listEmpty(List *base)
{
	return (base->next==NULL);
}

void
listAddFirst(List *base, void *data)
{
	List *head, *new;
	head = base->next;

	new = malloc(sizeof(List));
	new->data = data;
	new->next = head;
	new->prev = NULL;

	if (head) {
		head->prev = new;
	} else {
		base->prev = new;
	}
	base->next = new;

	return;
}

void
listAddLast(List *base, void *data)
{
	List *tail, *new;
	tail = base->prev;

	new = malloc(sizeof(List));
	new->data = data;
	new->prev = tail;
	new->next = NULL;

	if (tail) {
		tail->next = new;
	} else {
		base->next = new;
	}
	base->prev = new;

	return;
}

void *
listGetLast(List *base)
{
	if (base->prev)
		return base->prev->data;
	else
		return NULL;
}

void *
listGetFirst(List *base)
{
	if (base->next)
		return base->next->data;
	else
		return NULL;
}


void *
listPollLast(List *base)
{
	List *last, *newlast;
	void *data;
	last = base->prev;

	if (!last) {
		return NULL;
	}

	newlast = last->prev;
	data = last->data;
	free(last);

	if (newlast) {
		newlast->next = NULL;
	} else {
		base->next = NULL;
	}
	base->prev = newlast;

	return data;
}

void *
listPollFirst(List *base)
{
	List *head, *newhead;
	void *data;
	head = base->next;

	if (!head) {
		return NULL;
	}

	newhead = head->next;
	data = head->data;
	free(head);

	if (newhead) {
		newhead->next = NULL;
	} else {
		base->next = NULL;
	}
	base->next = newhead;

	return data;
}

void
listRemove(List *base, void *data)
{
	List *list;
	list = base->next;
	for (list=base->next; list; list=list->next) {
		if (list->data!=data) continue;

		if (list->prev) {
			list->prev->next = list->next;
		} else {
			base->next = list->next;
		}

		if (list->next) {
			list->next->prev = list->prev;
		} else {
			base->prev = list->prev;
		}
		free(list);
		return;
	}
	return;
}

ListIter *
createIterator(List *base)
{
	ListIter *iter;
	iter = malloc(sizeof(ListIter));
	iter->list = base;
	iter->current = base;
	return iter;
}
void
destroyIterator(ListIter *iter)
{
	free(iter);
}

int
listIterhasNext(ListIter *iter)
{
	return iter->current->next!=NULL ;
}

void *
listIterNext(ListIter *iter)
{
	iter->current = iter->current->next;
	return iter->current->data;
}

void
listIterRemove(ListIter *iter)
{
	List *list, *removed;
	list = iter->list;
	removed = iter->current;

	if (removed->prev) {
		removed->prev->next = removed->next;
		iter->current = removed->prev;
	} else {
		iter->list->next = removed->next;
		iter->current = iter->list;
	}

	if (removed->next) {
		removed->next->prev = removed->prev;
	} else {
		iter->list->prev = removed->prev;
	}
	free(removed);
}