/*-------------------------------------------------------------------------
 *
 * list.c
 *	  POSTGRES generic list package
 *
 *
 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /var/lib/cvs/pgsql-server/src/backend/nodes/list.c,v 1.54 2003/08/08 21:41:44 momjian Exp $
 *
 * NOTES
 *	  XXX a few of the following functions are duplicated to handle
 *		  List of pointers and List of integers separately. Some day,
 *		  someone should unify them.			- ay 11/2/94
 *	  This file needs cleanup.
 *
 * HISTORY
 *	  AUTHOR			DATE			MAJOR EVENT
 *	  Andrew Yu			Oct, 1994		file creation
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "nodes/parsenodes.h"


/*
 *	makeInteger
 */
Value *
makeInteger(long i)
{
	Value	   *v = makeNode(Value);

	v->type = T_Integer;
	v->val.ival = i;
	return v;
}

/*
 *	makeFloat
 *
 * Caller is responsible for passing a palloc'd string.
 */
Value *
makeFloat(char *numericStr)
{
	Value	   *v = makeNode(Value);

	v->type = T_Float;
	v->val.str = numericStr;
	return v;
}

/*
 *	makeString
 *
 * Caller is responsible for passing a palloc'd string.
 */
Value *
makeString(char *str)
{
	Value	   *v = makeNode(Value);

	v->type = T_String;
	v->val.str = str;
	return v;
}


/*
 *	makeBitString
 *
 * Caller is responsible for passing a palloc'd string.
 */
Value *
makeBitString(char *str)
{
	Value	   *v = makeNode(Value);

	v->type = T_BitString;
	v->val.str = str;
	return v;
}

static List *
new_list(NodeTag type)
{
	List *retval;

	retval = palloc(sizeof(*retval));
	retval->type = type;
	retval->head = NULL;
	retval->tail = NULL;
	retval->length = 0;

	return retval;
}

/*
 * Add a new, and as yet undefined, head element to the list, which
 * must be non-NIL. The list is mutated in place. The caller should
 * fill in the value of the new head element.
 */
static List *
new_head_elem(List *list)
{
	ListCell *new_head;

	new_head = palloc(sizeof(*new_head));
	new_head->next = list->head;
	list->head = new_head;

	/*
	 * If this is the only element in the list, it is both the head
	 * and the tail, so we need to update the tail pointer as well
	 */
	if (list->tail == NULL)
		list->tail = list->head;

	list->length++;
}

/*
 * Add a new, and as yet undefined, tail element to the list, which
 * must be non-NIL. The list is mutated in place. The caller should
 * fill in the value of the new tail element.
 */
static List *
new_tail_elem(List *list)
{
	ListCell *new_tail;

	new_tail = palloc(sizeof(*new_tail));
	new_tail->next = NULL;
	list->tail->next = new_tail;
	list->tail = new_tail;

	/*
	 * If this is the only element in the list, it is both the tail
	 * and the head, so we need to update the head pointer as well
	 */
	if (list->head == NULL)
		list->head = list->tail;

	list->length++;
}

#ifdef USE_ASSERT_CHECKING
/*
 * This should probably be made into a macro...
 */
static void
check_invariant(List *list)
{
	if (list == NIL)
		return;

	/*
	 * An empty list MUST be represented as NIL
	 */
	Assert(list->length > 0);

	/*
	 * Since the list is non-empty, its head and tail must be defined
	 */
	Assert(list->head != NULL);
	Assert(list->tail != NULL);

	if (list->length == 1)
		Assert(list->tail == list->head);

	/*
	 * The list must have a valid tag
	 */
	Assert(list->type == T_List ||
		   list->type == T_IntList ||
		   list->type == T_OidList);

	/*
	 * XXX: We could iterate through the list here and check if the
	 * list's length field is actually correct
	 */
}

#else

#define check_invariant(l)

#endif /* USE_ASSERT_CHECKING */

List *
lcons(void *datum, List *list)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_List);

	new_head_elem(list);
	value(list->head) = datum;

	return list;
}

List *
lconsi(int datum, List *list)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_IntList);

	new_head_elem(list);
	ivalue(list->head) = datum;

	return list;
}

List *
lconso(Oid datum, List *list)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_OidList);

	new_head_elem(list);
	ovalue(list->head) = datum;

	return list;
}

List *
lappend(List *list, void *datum)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_List);

	new_tail_elem(list);
	value(list->tail) = datum;

	return list;
}

List *
lappendi(List *list, int datum)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_IntList);

	new_tail_elem(list);
	ivalue(list->tail) = datum;

	return list;
}

List *
lappendo(List *list, Oid datum)
{
	check_invariant(list);

	if (list == NIL)
		list = new_list(T_OidList);

	new_tail_elem(list);
	ovalue(list->tail) = datum;

	return list;
}

List *
nconc(List *l1, List *l2)
{
	check_invariant(l1);
	check_invariant(l2);

	/*
	 * XXX: memory allocation is ambiguous here: does the caller free
	 * the memory for l1 or l2?
	 */
	if (l1 == NIL)
		return l2;
	if (l2 == NIL)
		return l1;
	if (l1 == l2)
		elog(ERROR, "cannot nconc a list to itself");

	l1->tail->next = l2->head;
	l1->tail = l2->tail;
	l1->length += l2->length;

	return l1;
}

void *
nth(int n, List *list)
{
	ListCell *match;

	check_invariant(list);

	Assert(n >= 0);
	Assert(n < list->length);

	/*
	 * Does the caller actually mean to fetch the tail?
	 */
	if (n == list->length - 1)
		return value(list->tail);

	for (match = list->head; n-- > 0; match = match->next)
		;

	return value(match);
}

/*
 *	freeList
 *
 *	Free the List nodes of a list
 *	The pointed-to nodes, if any, are NOT freed.
 *	This works for integer and Oid lists too.
 */
void
freeList(List *list)
{
	while (list != NIL)
	{
		List	   *l = list;

		list = lnext(list);
		pfree(l);
	}
}

/*
 * equali
 *	  compares two lists of integers
 */
bool
equali(List *list1, List *list2)
{
	List	   *l;

	foreach(l, list1)
	{
		if (list2 == NIL)
			return false;
		if (lfirsti(l) != lfirsti(list2))
			return false;
		list2 = lnext(list2);
	}
	if (list2 != NIL)
		return false;
	return true;
}

/*
 * equalo
 *	  compares two lists of Oids
 */
bool
equalo(List *list1, List *list2)
{
	List	   *l;

	foreach(l, list1)
	{
		if (list2 == NIL)
			return false;
		if (lfirsto(l) != lfirsto(list2))
			return false;
		list2 = lnext(list2);
	}
	if (list2 != NIL)
		return false;
	return true;
}

/*
 * Generate the union of two lists,
 * ie, l1 plus all members of l2 that are not already in l1.
 *
 * NOTE: if there are duplicates in l1 they will still be duplicate in the
 * result; but duplicates in l2 are discarded.
 *
 * The result is a fresh List, but it points to the same member nodes
 * as were in the inputs.
 */
List *
set_union(List *l1, List *l2)
{
	List	   *retval = listCopy(l1);
	List	   *i;

	foreach(i, l2)
	{
		if (!member(lfirst(i), retval))
			retval = lappend(retval, lfirst(i));
	}
	return retval;
}

/* set_union for Oid lists */
List *
set_uniono(List *l1, List *l2)
{
	List	   *retval = listCopy(l1);
	List	   *i;

	foreach(i, l2)
	{
		if (!oidMember(lfirsto(i), retval))
			retval = lappendo(retval, lfirsto(i));
	}
	return retval;
}

/* set_union when pointer-equality comparison is sufficient */
List *
set_ptrUnion(List *l1, List *l2)
{
	List	   *retval = listCopy(l1);
	List	   *i;

	foreach(i, l2)
	{
		if (!ptrMember(lfirst(i), retval))
			retval = lappend(retval, lfirst(i));
	}
	return retval;
}

/*
 * Generate the intersection of two lists,
 * ie, all members of both l1 and l2.
 *
 * NOTE: if there are duplicates in l1 they will still be duplicate in the
 * result; but duplicates in l2 are discarded.
 *
 * The result is a fresh List, but it points to the same member nodes
 * as were in the inputs.
 */
#ifdef NOT_USED
List *
set_intersect(List *l1, List *l2)
{
	List	   *retval = NIL;
	List	   *i;

	foreach(i, l1)
	{
		if (member(lfirst(i), l2))
			retval = lappend(retval, lfirst(i));
	}
	return retval;
}
#endif

/*
 * member()
 *	nondestructive, returns t iff l1 is a member of the list l2
 */
bool
member(void *l1, List *l2)
{
	List	   *i;

	foreach(i, l2)
	{
		if (equal((Node *) l1, (Node *) lfirst(i)))
			return true;
	}
	return false;
}

/*
 * like member(), but use when pointer-equality comparison is sufficient
 */
bool
ptrMember(void *l1, List *l2)
{
	List	   *i;

	foreach(i, l2)
	{
		if (l1 == lfirst(i))
			return true;
	}
	return false;
}

/*
 * membership test for integer lists
 */
bool
intMember(int l1, List *l2)
{
	List	   *i;

	foreach(i, l2)
	{
		if (l1 == lfirsti(i))
			return true;
	}
	return false;
}

/*
 * membership test for Oid lists
 */
bool
oidMember(Oid l1, List *l2)
{
	List	   *i;

	foreach(i, l2)
	{
		if (l1 == lfirsto(i))
			return true;
	}
	return false;
}

/*
 * lremove
 *	  Removes 'elem' from the linked list (destructively changing the list!).
 *	  (If there is more than one equal list member, the first is removed.)
 *
 *	  This version matches 'elem' using simple pointer comparison.
 *	  See also LispRemove.
 */
List *
lremove(void *elem, List *list)
{
	List	   *l;
	List	   *prev = NIL;
	List	   *result = list;

	foreach(l, list)
	{
		if (elem == lfirst(l))
			break;
		prev = l;
	}
	if (l != NIL)
	{
		if (prev == NIL)
			result = lnext(l);
		else
			lnext(prev) = lnext(l);
		pfree(l);
	}
	return result;
}

/*
 *	LispRemove
 *	  Removes 'elem' from the linked list (destructively changing the list!).
 *	  (If there is more than one equal list member, the first is removed.)
 *
 *	  This version matches 'elem' using equal().
 *	  See also lremove.
 */
List *
LispRemove(void *elem, List *list)
{
	List	   *l;
	List	   *prev = NIL;
	List	   *result = list;

	foreach(l, list)
	{
		if (equal(elem, lfirst(l)))
			break;
		prev = l;
	}
	if (l != NIL)
	{
		if (prev == NIL)
			result = lnext(l);
		else
			lnext(prev) = lnext(l);
		pfree(l);
	}
	return result;
}

/*
 *	lremovei
 *		lremove() for integer lists.
 */
List *
lremovei(int elem, List *list)
{
	List	   *l;
	List	   *prev = NIL;
	List	   *result = list;

	foreach(l, list)
	{
		if (elem == lfirsti(l))
			break;
		prev = l;
	}
	if (l != NIL)
	{
		if (prev == NIL)
			result = lnext(l);
		else
			lnext(prev) = lnext(l);
		pfree(l);
	}
	return result;
}

/*
 * ltruncate
 *		Truncate a list to n elements.
 *		Does nothing if n >= length(list).
 *		NB: the list is modified in-place!
 */
List *
ltruncate(int n, List *list)
{
	List	   *ptr;

	if (n <= 0)
		return NIL;				/* truncate to zero length */

	foreach(ptr, list)
	{
		if (--n == 0)
		{
			lnext(ptr) = NIL;
			break;
		}
	}
	return list;
}

/*
 *	set_difference
 *
 *	Return l1 without the elements in l2.
 *
 * The result is a fresh List, but it points to the same member nodes
 * as were in l1.
 */
List *
set_difference(List *l1, List *l2)
{
	List	   *result = NIL;
	List	   *i;

	if (l2 == NIL)
		return listCopy(l1);	/* slightly faster path for empty l2 */

	foreach(i, l1)
	{
		if (!member(lfirst(i), l2))
			result = lappend(result, lfirst(i));
	}
	return result;
}

/*
 *	set_differenceo
 *
 *	Same as set_difference, but for Oid lists
 */
List *
set_differenceo(List *l1, List *l2)
{
	List	   *result = NIL;
	List	   *i;

	if (l2 == NIL)
		return listCopy(l1);	/* slightly faster path for empty l2 */

	foreach(i, l1)
	{
		if (!oidMember(lfirsto(i), l2))
			result = lappendo(result, lfirsto(i));
	}
	return result;
}

/*
 *	set_ptrDifference
 *
 *	Same as set_difference, when pointer-equality comparison is sufficient
 */
List *
set_ptrDifference(List *l1, List *l2)
{
	List	   *result = NIL;
	List	   *i;

	if (l2 == NIL)
		return listCopy(l1);	/* slightly faster path for empty l2 */

	foreach(i, l1)
	{
		if (!ptrMember(lfirst(i), l2))
			result = lappend(result, lfirst(i));
	}
	return result;
}

/*
 * Reverse a list, non-destructively
 */
#ifdef NOT_USED
List *
lreverse(List *l)
{
	List	   *result = NIL;
	List	   *i;

	foreach(i, l)
		result = lcons(lfirst(i), result);
	return result;
}

#endif