/* Generic doubly linked list V2.05 1/5/05
   See gdll.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.
   WOUM is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   You should have received a copy of the GNU General Public License
   along with WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _GDLL_C
#define _GDLL_C

#include <stdlib.h>

#include "gdll.h"

gdll *gdll_create(void *me)
{
	gdll *h;
	h = malloc(sizeof(gdll));
	if (h == 0)
		return 0;
	h->head = h->tail = 0;
	h->size = 0;
	h->me = me;
	return h;
}

gdll_item *gdll_createitem(void *me)
{
	gdll_item *i;
	i = malloc(sizeof(gdll_item));
	if (i == 0)
		return 0;
	i->next = i->prev = 0;
	i->parent = 0;
	i->me = me;
	return i;
}

int gdll_kill(gdll *h,int anditems)
{
	if (h == 0)
		return 1;
	while (h->size)
		if (anditems)
			gdll_killitem(h->head);
		else
			gdll_remove(h->head);
	free(h);
	return 0;
}

int gdll_killitem(gdll_item *i)
{
	if (i == 0)
		return 1;
	if (i->parent)
		gdll_remove(i);
	free(i);
	return 0;
}

void gdll_remove(gdll_item *i)
{
	if (i->parent == 0)
		return;
	if (i->next)
		i->next->prev = i->prev;
	else
		i->parent->tail = i->prev;
	if (i->prev)
		i->prev->next = i->next;
	else
		i->parent->head = i->next;
	i->parent->size--;
	i->parent = 0;
	i->next = 0;
	i->prev = 0;
}

void gdll_addhead(gdll *h,gdll_item *i)
{
	if (i->parent)
		gdll_remove(i);
	i->parent = h;
	i->next = h->head;
	h->head = i;
	if (i->next)
		i->next->prev = i;
	else
		h->tail = i;
	h->size++;
}

void gdll_addtail(gdll *h,gdll_item *i)
{
	if (i->parent)
		gdll_remove(i);
	i->parent = h;
	i->prev = h->tail;
	h->tail = i;
	if (i->prev)
		i->prev->next = i;
	else
		h->head = i;
	h->size++;
}

void gdll_addnext(gdll_item *i,gdll_item *n)
{
	/* Insert i into n's list so that n is next after i */
	if (i->parent)
		gdll_remove(i);
	if ((n == 0) || (n->parent == 0))
		return;
	i->next = n;
	i->prev = n->prev;
	i->parent = n->parent;
	n->prev = i;
	if (i->prev)
		i->prev->next = i;
	else
		i->parent->head = i;
	i->parent->size++;
}

void gdll_addprev(gdll_item *i,gdll_item *p)
{
	/* Insert i into p's list so that p is next before i */
	if (i->parent)
		gdll_remove(i);
	if ((p == 0) || (p->parent == 0))
		return;
	i->prev = p;
	i->next = p->next;
	i->parent = p->parent;
	p->next = i;
	if (i->next)
		i->next->prev = i;
	else
		i->parent->tail = i;
	i->parent->size++;
}

unsigned long gdll_size(gdll *h)
{
	if (h)
		return h->size;
	return 0;
}

gdll_item *gdll_head(gdll *h)
{
	if (h)
		return h->head;
	return 0;
}

gdll_item *gdll_tail(gdll *h)
{
	if (h)
		return h->tail;
	return 0;
}

gdll_item *gdll_next(gdll_item *i)
{
	if (i)
		return i->next;
	return 0;
}

gdll_item *gdll_prev(gdll_item *i)
{
	if (i)
		return i->prev;
	return 0;
}

gdll *gdll_parent(gdll_item *i)
{
	if (i)
		return i->parent;
	return 0;
}

static int (*gdll_sortfunc)(const void *,const void *);

static int gdll_sort2(const void *a,const void *b)
{
	const void *a2,*b2;
	a2 = (*((gdll_item **) a))->me; b2 = (*((gdll_item **) b))->me;
	return (gdll_sortfunc)(a2,b2);
}

int gdll_sort(gdll *h,int (*func)(const void *,const void *))
{
	gdll_item **ar;
	gdll_item *i;
	int n;
	if (h->size < 2)
		return 0;
	ar = malloc(4*h->size);
	if (ar == 0)
		return 1;
	i = h->head;
	n=0;
	while (i)
	{
		ar[n++] = i;
		i = i->next;
	}
	gdll_sortfunc = func;
	qsort(ar,h->size,4,gdll_sort2);
	h->head = ar[0];
	h->tail = ar[h->size-1];
	for (n=0;n<h->size;n++)
	{
		if (n > 0)
			ar[n]->prev = ar[n-1];
		else
			ar[n]->prev = 0;
		if (n < h->size-1)
			ar[n]->next = ar[n+1];
		else
			ar[n]->next = 0;
	}
	free(ar);
	return 0;
}

gdll_item *gdll_findhead(gdll *h,void *i)
{
	gdll_item *it;
	if (h == 0)
		return 0;
	it = h->head;
	while (it)
	{
		if (it->me == i)
			return it;
		it = it->next;
	}
	return 0;
}

gdll_item *gdll_findtail(gdll *h,void *i)
{
	gdll_item *it;
	if (h == 0)
		return 0;
	it = h->tail;
	while (it)
	{
		if (it->me == i)
			return it;
		it = it->prev;
	}
	return 0;
}

void **gdll_array(gdll *h)
{
	gdll_item *i;
	int j;
	void **a;
	if (h == 0)
		return 0;
	a = malloc(4*h->size);
	if (a == 0)
		return 0;
	i = h->head;
	for (j=0;j<h->size;j++)
	{
		a[j] = i->me;
		i = i->next;
	}
	return a;
}

#endif
