/* $Id: lists.c,v 1.8 2003/02/26 10:55:45 aa5779 Exp $ */
/* lists.c -- routines for processing generic lists */
/*
	Copyright (C) 2001, 2002 Artem V. Andreev (artem@AA5779.spb.edu)

    This program 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 2 of the License, or
    (at your option) any later version.

    This program 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 this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>
#include "util.h"
#include "lists.h"
/*** \file
This file contains routines for generic list maninpulation.
\include[lists.h]
*/

/*** \group[Functions] */

/*** \function
Destroys a single item of a list
\arg[item] the pointer to a given item
\arg[destroy] user-supplied destruction function, may be NULL
\arg[size] actual size of an item
*/
void list_free(list_t item, list_destroy_t destroy, int size)
{
	if(destroy)
		destroy(item);
	if(size)
		free_chunk(item, size);
}

/*** \function
Prepends an item \var[base] to a list \var[new]
\note both may be NULLs
\returns a new list
*/
list_t list_add(list_t base, list_t new)
{
	if(!new)
		return base;
	((baselist_t *)new)->next = base;
	return new;
}

/*** \function
Finds the first item in a list matching \var[key] according to \var[predicate]
\returns the item found, or NULL if none
*/
list_t list_find(list_t base, void *key, list_predicate_t predicate)
{
	baselist_t *iter = base;
	if(!predicate)
		fatal_error("predicate == NULL in list_find");
	for(; iter; iter = iter->next)
	{
		if(predicate(iter, key))
			return iter;
	}
	return NULL;
}

/**** \function
\returns the length of a list
*/
int list_length(list_t l)
{
	baselist_t *iter = l;
	int len;

	for(len = 0; iter; iter = iter->next, len++)
		;
	return len;
}

/*** \function
\returns \var[n]th item of a list (starting with 0), 
NULL if the list contains less than \code[n + 1] items
*/
list_t list_nth(list_t l, int n)
{
	baselist_t *iter = l;

	for(; iter; iter = iter->next, n--)
	{
		if(!n)
			return iter;
	}
	return NULL;
}

/**** \function
Executes \var[iterator] for each item in \var[base]
*/
void list_foreach(list_t base, list_iterator_t iterator, void *extra)
{
	baselist_t *iter = base;
	for(; iter; iter = iter->next)
		iterator(iter, extra);
}

/**** \function
Inserts a \var[new] item into \var[base] list after an item matching \var[after].
If no such item is found, no insertion is performed.
If \var[after] is NULL, the function is equivalent to \see[functions][list_add]
\returns a new list
*/
list_t list_insert(list_t base, void *after, list_t new, list_predicate_t predicate)
{
	baselist_t *item;
	if(!after)
		return list_add(base, new);
	item = list_find(base, after, predicate);
	if(item)
	{
		((baselist_t *)new)->next = item->next;
		item->next = new;		
	}
	return base;
}

/**** \function
Appends a \var[new] item to the list
\returns \var[base]
*/
list_t list_append(list_t base, list_t new)
{
	baselist_t *item;	
	if(!base)
		return new;
	for(item = base; item->next; item = item->next)
		;
	item->next = new;
	return base;
}

/**** \function
Discards the head of the list, calling \see[functions][list_free] on it
\returns the tail of the list
*/
list_t list_pop(list_t base, list_destroy_t destroy, int elsize)
{
	list_t next;
	if(!base)
		return NULL;
	next = ((baselist_t *)base)->next;
	list_free(base, destroy, elsize);
	return next;
}

/**** \function
Removes the first item matching \var[key], calling \see[functions][list_free] on it.
If no such item is found, nothing happens
\returns a new list
*/
list_t list_remove(list_t base, void *key, list_predicate_t predicate, list_destroy_t destroy, int elsize)
{
	baselist_t *item, *prev = NULL;
	for(item = base; item; prev = item, item = item->next)
	{
		if(predicate(item, key))
		{
			if(prev)
				prev->next = item->next;
			else base = item->next;
			list_free(item, destroy, elsize);
			break;
		}
	}
	return base;
}

/*** \function
Like the previous, but removes all the items matching \var[key]
*/
list_t list_remove_all(list_t base, void *key, list_predicate_t predicate, list_destroy_t destroy, int elsize)
{
	baselist_t *item, *prev = NULL, *temp;
	for(item = base; item; item = temp)
	{
		temp = item->next;
		if(!predicate(item, key))
			prev = item;
		else
		{
			if(prev)
				prev->next = temp;
			else base = temp;
			list_free(item, destroy, elsize);
		}
	}
	return base;
}

/*** \function
Destroys all the items of the list, calling \see[functions][list_free] on them.
*/
void list_delete(list_t base, list_destroy_t destroy, int elsize)
{
	baselist_t *iter, *temp;

	for(iter = base; iter; iter = temp)
	{
		temp = iter->next;
		list_free(iter, destroy, elsize);
	}
}

/*** \function
Reverses the order of items in a list without producing a new list
*/
list_t list_reversip(list_t src)
{
	baselist_t *iter, *prev = NULL, *temp;

	for(iter = src; iter; iter = temp)
	{
		temp = iter->next;
		iter->next = prev;
		prev = iter;
	}
	return prev;
}