/*
 * $Id: list.c,v 1.1.1.1 2004/08/25 19:21:25 jan Exp $
 *
 * Copyright (c) 2002 Jan Algermissen
 * See the file "COPYING" for copying permission.
 *
 */

#include <tmlist.h>
#include <tmassert.h>
#include <tmtrace.h>
#include <stdio.h>

int tm_list_size(TMList list)
{
	long n = 0;
	for(;list;list=list->next) n++;
	return n;
}

TMList tm_list_push(TMPool pool,TMList self, void *content)
{
	TMList newItem;
	TM_NEW(pool,newItem);
	newItem->content = content;
	newItem->next = self;
	return newItem;
}

TMList tm_list_append(TMPool pool,TMList self, void *content)
{
	TMList lp,newItem;
	TM_NEW(pool,newItem);

	newItem->content = content;
	newItem->next = NULL;
	if(self == NULL)
	{
		self = newItem;
		return self;
	}
	for(lp = self; lp->next != NULL; lp=lp->next)
		;
	lp->next = newItem;
	return self;
}
TMList tm_list_pop(TMPool pool,TMList self, void **x)
{
	TMTRACE(TM_GRAPH_TRACE,"x1\n");
	if(self)
	{
		TMList head = self->next;
		if(x)
			*x = self->content;
		TM_FREE(pool,self);
		return head;
	}
	else
	{
		if(x)
			*x = NULL;
		return NULL;
	}
}

void tm_list_delete(TMPool pool,TMList *pself)
{
	TMList next;
	assert(pself);
	for( ; *pself; *pself = next)
	{
		next = (*pself)->next;
		TM_FREE(pool,*pself);
	}
}

TMList tm_list_copy(TMPool pool,TMList list)
{
	TMList n = NULL;
	if(!list)
		return NULL;
	for( ; list; list = list->next)
		n = tm_list_push(pool,n,list->content);

	return n;
}
int cmp_atom(const void *x,const void *y)
{
	if(x > y)
		return 1;
	if(x < y)
		return -1;
	return 0;


}
TMList tm_list_sort(TMList list, int cmp(const void *x,const void *y))
{
	TMList result = NULL;
	TMList lp = list;
	if(cmp == NULL)
		cmp = cmp_atom;
	while(lp)
	{
		TMList kp;
		TMList t = lp;
		lp=lp->next;
		t->next = NULL;


		if(result == NULL)
		{
			result = t;
			continue;
		}
		if(result->next == NULL)
		{
			if( cmp(result->content,t->content) > 0)
			{
				t->next = result;
				result = t;
			}
			else
			{
				result->next = t;
			}
			continue;
		}
		if( cmp(result->content,t->content) > 0)
		{
			t->next = result;
			result = t;
			continue;
		}
		for(kp=result;kp;kp=kp->next)
		{
			if( (kp->next == NULL) || ( cmp(kp->next->content,t->content) > 0) )
			{
				t->next = kp->next;
				kp->next = t;
				break;
			}
		}
	}
	return result;

}

TMList tm_list_remove(TMPool pool,TMList list, void *v, int cmp(const void *x,const void *y))
{
	TMList prev,lp;
	assert(cmp == NULL);
	if(list == NULL)
		return(NULL);
	prev = NULL;
	for(lp=list;lp;lp=lp->next)
	{
		TMList tmp = NULL;
		if( !((cmp!=NULL) && (cmp(lp->content,v)==0) )
		&&  !((cmp==NULL) && (lp->content == v))   )
		{
			prev = lp;
			continue;
		}

		if(!prev)
		{
			tmp = list;
			list = list->next;
			TM_FREE(pool,tmp);
		}
		else
		{
			assert(prev->next == lp);
			prev->next = lp->next;
			TM_FREE(pool,lp);
		}
		break;

	}
#if 0
	prev = NULL;
	for(lp=list;lp;lp=lp->next)
	{
		TMList tmp = NULL;
		if(lp->content != v )
		{
			prev = lp;
			continue;
		}

		if(!prev)
		{
			tmp = list;
			list = list->next;
			TM_FREE(tmp);
		}
		else
		{
			assert(prev->next == lp);
			prev->next = lp->next;
			TM_FREE(lp);
		}
		break;

	}
#endif
	return list;
}

/** Check if list contains v.
 * Equality is checked trough
 * pointer euality
 * @param list the list
 * @param v pointer to content
 * @return Return 1 if v is in list else 0
 */
int tm_list_contains(TMList list, const void *v,int cmp(const void *x,const void *y))
{
	if(!list)
		return 0;	
	
	for( ; list ; list = list->next)
		if(cmp && cmp(list->content,v) == 0 )
			return 1;
		else if(list->content == v)
			return 1;

	return 0;

}

#if 0

/**
 * Create a new list from the items in the variable argument list.
 * Note that the arguments have to be casted to (void *) 
 * <pre>
 * list = GWList_list(gw,"elem1","elem2","elem3"
 * </pre>
 *
 * @param gw the GW handle
 * @param x,... the items to build the list from
 * @return the new list
 */

GWList_T GWList_list(GW gw,void *x,...)
{
	GWList_T list, *p = &list;
	va_list ap;

	va_start(ap,x);

	for( ; x; x = va_arg(ap,void*))
	{
		GW_NEW(gw,*p);
		(*p)->content = x;
		p = &(*p)->next;
	}
	*p = NULL;
	va_end(ap);
	return list;

}

/** Checks two lists for equality.
 * GWList items are compared by pointer equality.
 * @param l1 list1
 * @param l2 list2
 * @return 1 if lists are equal, 0 if they are not
 */
/*
int GWList_equals(GW gw,GWList_T l1, GWList_T l2)
{
	GWList_T p1,p2;

	for(p1 = l1; p1; p1 = p1->next)
	{
		int found;
		found = 0;
		for(p2 = l2; p2; p2 = p2->next)
		{
			if(p1->content == p2->content)
			{
				found = 1;	
				break;
			}
		}
		if(!found)
			return 0;
	}
	for(p2 = l2; p2; p2 = p2->next)
	{
		int found;
		found = 0;
		for(p1 = l1; p1; p1 = p1->next)
		{
			if(p1->content == p2->content)
			{
				found = 1;	
				break;
			}
		}
		if(!found)
			return 0;
	}

	return 1;
}
*/
/** Check if the intersection of l1 nd l2 is the empty set.
 * @param l1 list1
 * @param l2 list2
 * @param cmp compare function
 * @return 1 if intersection 
 */
int GWList_intersectionEmpty(GW gw,GWList_T l1,GWList_T l2,int cmp(const void *x,const void *y))
{
	GWList_T p1,p2;

	for(p1 = l1; p1; p1 = p1->next)
	{
		for(p2 = l2; p2; p2 = p2->next)
		{
			if(cmp(p1->content,p2->content) == 0)
			{
				return 0;
			}
		}
	}
	for(p2 = l2; p2; p2 = p2->next)
	{
		for(p1 = l1; p1; p1 = p1->next)
		{
			if(cmp(p1->content,p2->content) == 0)
			{
				return 0;
			}
		}
	}

	return 1;

}
/** Concatenate two lists.
 * This will add all the elements of l2 to l1,
 * returning the resulting list.
 * l2 isn't changed. 
 * @param l1 the list to concat to
 * @param l2 the concated list
 * @return l1 (as in push) 
 */

GWList_T GWList_concat(GW gw,GWList_T l1,GWList_T l2)
{
	for(;l2;l2=l2->next)
	{
		l1 = GWList_push(gw,l1,l2->content);
	}
	return l1;

}
/** Apply a function
 *
 * @param gw the GW handle
 * @param list the list
 * @param apply pointer to a function that is to be applied to
 * each list element. 
 * 
 */
void GWList_apply(GW gw,GWList_T list, void apply(void **x, void *cl), void *cl)
{
	assert(apply);
	for(;list;list=list->next)
		apply(&list->content,cl);
}


#endif