/* Frame based linked list V2.14 31/1/08
   See fbll.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 _FBLL_C
#define _FBLL_C

#include <stdlib.h>
#include "fbll.h"

fbll *fbll_new(int fsize)
{
	fbll *f;
	if (fsize < 1)
		return 0;
	f = malloc(sizeof(fbll));
	if (f == 0)
		return 0;
	f->head = f->tail = 0;
	f->top = f->bottom = f->size = 0;
	f->fsize = fsize;
	return f;
}

void fbll_delete(fbll *h)
{
	fbll_frame *f;
	if (h == 0)
		return;
	while (h->head)
	{
		f = h->head;
		h->head = f->next;
		free(f);
	}
	free(h);
}

int fbll_addhead(fbll *h,void *i)
{
	fbll_frame *a;
	if (h->head == 0)
	{
		h->head = h->tail = malloc(sizeof(fbll_frame)+4*h->fsize);
		if (h->head == 0)
			return 1;
		h->head->next = h->head->prev = 0;
	}
	h->head->items[h->top++] = i;
	if (h->top == h->fsize)
	{
		a = malloc(sizeof(fbll_frame)+4*h->fsize);
		if (a == 0)
		{
			h->top--;
			return 1;
		}
		a->next = h->head;
		a->prev = 0;
		h->head = a;
		a->next->prev = a;
		/* Don't have to worry about h's tail pointer since there is at least one frame */
		h->top = 0; /* Top frame is empty */
	}
	h->size++;
	return 0;
}

int fbll_addtail(fbll *h,void *i)
{
	fbll_frame *a;
	if (h->tail == 0)
	{
		h->tail = h->head = malloc(sizeof(fbll_frame)+4*h->fsize);
		if (h->tail == 0)
			return 1;
		h->tail->next = h->tail->prev = 0;
		h->top = 1; /* Bottom value is filled */
		h->bottom = 0;
		h->size = 1;
		h->head->items[0] = i;
		return 0;
	}
	h->bottom--;
	if (h->bottom < 0)
	{
		a = malloc(sizeof(fbll_frame)+4*h->fsize);
		if (a == 0)
		{
			h->bottom++;
			return 1;
		}
		a->next = 0;
		a->prev = h->tail;
		h->tail = a;
		a->prev->next = a;
		/* Don't have to worry about h's head pointer since there is at least one frame */
		h->bottom = h->fsize-1;
	}
	h->tail->items[h->bottom] = i; /* Set entry */
	h->size++;
	return 0;
}

void fbll_removehead(fbll *h)
{
	fbll_frame *a;
	/* Remove head item */
	if (h->size == 0)
		return;
	/* ... so at least 1 nonempty stack frame exists */
	h->top--;
	if (h->top < 0)
	{
		/* emptied top frame, so dispose of it */
		if (h->head == h->tail)
		{
			/* prevent last frame from vanishing */
			h->top = h->bottom = h->size = 0;
			return;
		}
		a = h->head->next;
		free(h->head);
		a->prev = 0;
		h->head = a;
		h->top = h->fsize-1;
	}
	h->size--;
}

void fbll_removetail(fbll *h)
{
	fbll_frame *a;
	/* Remove tail item */
	if (h->size == 0)
		return;
	/* ... so at least 1 nonempty stack frame exists */
	h->bottom++;
	if (h->bottom >= h->fsize)
	{
		/* emptied botom frame, so dispose of it */
		if (h->head == h->tail)
		{
			/* prevent last frame from vanishing */
			h->top = h->bottom = h->size = 0;
			return;
		}
		a = h->tail->prev;
		free(h->tail);
		a->next = 0;
		h->tail = a;
		h->bottom = 0;
	}
	h->size--;
}

void *fbll_head(fbll *h)
{
	/* Return head item */
	if (h->size == 0) /* No items? */
		return 0;
	if (h->top == 0) /* Top frame is empty */
		return h->head->next->items[h->fsize-1];
	return h->head->items[h->top-1];
}

void *fbll_tail(fbll *h)
{
	/* Return tail item */
	if (h->size == 0) /* No items? */
		return 0;
	return h->tail->items[h->bottom];
}

unsigned long fbll_size(fbll *h)
{
	return h->size;
}

void *fbll_peekhead(fbll *h,signed long ofs)
{
	fbll_frame *a;
	/* Return item 'ofs', where 0=head */
	if ((ofs >= h->size) || (ofs < 0))
		return 0; /* Outside range */
	a = h->head;
	ofs = h->top - (ofs+1);
	/* Now go through frames until ofs becomes positive */
	while (ofs < 0)
	{
		a = a->next;
		ofs += h->fsize;
	}
	return a->items[ofs];
}

void *fbll_peektail(fbll *h,signed long ofs)
{
	/* Return item 'ofs' where 0=tail */
	return fbll_peekhead(h,h->size - (ofs+1)); /* Translate it to use other function */
}

int fbll_findhead(fbll *h,void *i)
{
	int o;
	fbll_frame *a;
	int p;
	int min,max;
	a = h->head;
	o = 0; /* Current offset */
	/* Check frames */
	while (a) {
		if (a->prev == 0)
			max = h->top-1;
		else
			max = h->fsize-1;
		if (a->next == 0)
			min = h->bottom;
		else
			min = 0;
		for (p=max;p>=min;p--)
			if (a->items[p] == i)
				return o;
			else
				o++;
		a = a->next;
	}
	return -1;
}

int fbll_findtail(fbll *h,void *i)
{
	int o;
	fbll_frame *a;
	int p;
	int min,max;
	a = h->tail;
	o = 0; /* Current offset */
	/* Check frames */
	while (a) {
		if (a->prev == 0)
			max = h->top-1;
		else
			max = h->fsize-1;
		if (a->next == 0)
			min = h->bottom;
		else
			min = 0;
		for (p=min;p<max;p++)
			if (a->items[p] == i)
				return o;
			else
				o++;
		a = a->next;
	}
	return -1;
}

static int (*fbll_sortfunc)(const void *a,const void *b);

static int fbll_sort2(const void *a,const void *b)
{
	return (fbll_sortfunc)(*((void **) a),*((void **) b));
}

int fbll_sort(fbll *h,int (*func)(const void *,const void *))
{
	void **ar;
	int o,min,max,p;
	fbll_frame *a;
	if (h->size < 2)
		return 0;
	ar = malloc(4*h->size);
	if (ar == 0)
		return 1;
	/* Copy the data into the array */
	a = h->head;
	o = 0;
	while (a) {
		if (a->prev == 0)
			max = h->top-1;
		else
			max = h->fsize-1;
		if (a->next == 0)
			min = h->bottom;
		else
			min = 0;
		for (p=max;p>=min;p--)
			ar[o++] = a->items[p];
		a = a->next;
	}
	/* Sort */
	fbll_sortfunc = func;
	qsort(ar,h->size,4,fbll_sort2);
	/* Copy back */
	a = h->head;
	o = 0;
	while (a) {
		if (a->prev == 0)
			max = h->top-1;
		else
			max = h->fsize-1;
		if (a->next == 0)
			min = h->bottom;
		else
			min = 0;
		for (p=max;p>=min;p--)
			a->items[p] = ar[o++];
		a = a->next;
	}
	free(ar);
	return 0;
}

void *fbll_removeheadn(fbll *h,int i)
{
	if((i<0) || (i>=h->size))
		return 0;
	fbll_frame *a;
	void *v;
	a = h->head;
	i = h->top-(i+1);
	/* Go through frames until i becomes positive */
	while(i<0)
	{
		a = a->next;
		i += h->fsize;
	}
	/* Result is a->items[i]
	   Remove it! */
	v = a->items[i];
	do {
		while(i>0)
		{
			a->items[i] = a->items[i-1];
			i--;
		}
		if(a->next)
			a->items[0] = a->next->items[h->fsize-1];
		i = h->fsize-1;
		a = a->next;
	} while(a);
	/* We've reached the end - just use removetail() for simplicity */
	fbll_removetail(h);
	return v;
}

void *fbll_removetailn(fbll *h,int i)
{
	return fbll_removeheadn(h,(h->size-1)-i);
}

#endif
