/*
 * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *        notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *        notice, this list of conditions and the following disclaimer in the
 *        documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the author nor the names of any co-contributors
 *        may be used to endorse or promote products derived from this software
 *        without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

#include "tlog.h"
#include "tmalloc.h"

#include "glist.h"

static GList*
checkGList(GList *l) {
	if ( l==NULL ) 
		l = t0malloc(sizeof(GList));

	tassert( GLIST_LENGTH(l) >= 0 );
	tassert( 
		( GLIST_LENGTH(l) == 0 && GLIST_HEAD(l) == NULL && GLIST_TAIL(l) == NULL ) ||
		( GLIST_LENGTH(l) > 0  && GLIST_HEAD(l) != NULL && GLIST_TAIL(l) != NULL )
	);

	return l;
}

static GListCell*
makeCell(void *ptr) {
	GListCell	*cell = tmalloc(sizeof(GListCell));
	cell->data = ptr;
	return cell;
}

static GList*
insertCell(GList *l, GListCell *prev, GListCell *cell) {
	l = checkGList(l);

	if ( prev == NULL ) {
		/* insert into head */
		if ( GLIST_LENGTH(l) == 0 ) {
				l->head = l->tail = cell;
				cell->next = cell->prev = NULL;
		} else {
			cell->next = l->head;
			cell->prev = NULL;
			l->head->prev = cell;
			l->head = cell;
		}
	} else if ( prev == l->tail ) {
		/* insert into tail */

		tassert( GLIST_LENGTH(l) > 0 );
		cell->next = NULL;
		cell->prev = l->tail;
		l->tail->next = cell;
		l->tail = cell;
	} else {
		tassert( GLIST_LENGTH(l) > 0 );
		cell->next = prev->next;
		cell->next->prev = cell;
		cell->prev = prev;
		prev->next = cell;
	}

	l->length++;	

	return l;
}

GList*
GListInsert(GList *l, GListCell *prev, void *ptr) {
	return insertCell(l, prev, makeCell(ptr));
}

GList*
GListPush(GList *l, void *ptr) {
	return insertCell(l, GLIST_TAIL(l), makeCell(ptr));
}

GList*
GListPushCell(GList *l, GListCell* c) {
	return insertCell(l, GLIST_TAIL(l), c);
}

GList*
GListUnshift(GList *l, void *ptr) {
	return insertCell(l, NULL, makeCell(ptr));
}

GList*
GListUnshiftCell(GList *l, GListCell* c) {
	return insertCell(l, NULL, c);
}

GList*
GListDelete(GList *l, GListCell *c) {
	if (GLIST_LENGTH(l) <= 0)
		return l;

	if ( l->head == c ) {
		tassert( c->prev == NULL );
		l->head = c->next;
		if ( l->head ) 
			l->head->prev = NULL;
		else
			l->tail = NULL;
	} else if ( l->tail == c ) {
		tassert( c->next == NULL );
		l->tail = c->prev;
		if ( l->tail )
			l->tail->next = NULL;
		else
			l->head = NULL;
	} else {
		c->prev->next = c->next;
		c->next->prev = c->prev;
	}

	c->prev = c->next = NULL;

	l->length--;

	return l;
}

GListCell*
GListPop(GList *l) {
	GListCell	*c = NULL;

	if (GLIST_LENGTH(l) > 0) {
		c = l->tail;
		GListDelete(l, c);
	}

	return c;
}

GListCell*
GListShift(GList *l) {
	GListCell	*c = NULL;

	if (GLIST_LENGTH(l) > 0) {
		c = l->head;
		GListDelete(l, c);
	}

	return c;
}

GListCell*
GListGet(GList *l, int n) {
	GListCell	*c;

	GListForeach(c, l) {
		if ( n-- == 0 )
			return c;
	}

	return NULL;
}

GListCell*
GListFind(GList *l, void *ptr) {
	GListCell    *c;

	if ( l && l->cmpFunc ) {
		GListForeach(c, l) {
			if ( l->cmpFunc(ptr, c->data) == 0 )
				return c;
		}
	} else {
		GListForeach(c, l) {
			if ( ptr == c->data )
				return c;
		}
	}

	return NULL;
}

static GListCellComparator curComparator;

static int
compareData( const void *a, const void *b ) {
	if ( *(void**)a == *(void**)b )
		return 0;
	return curComparator( *(void**)a, *(void**)b );
}

GList*
GListSort(GList *l) {
	GListCell	*c;
	void	**arrptr, **array;

	if (GLIST_LENGTH(l) <= 1)
		return l;
		
	tassert(l->cmpFunc != NULL);

	arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
	GListForeach(c, l) 
		*arrptr++ = c->data;

	tassert( arrptr - array == GLIST_LENGTH(l) );

	curComparator = l->cmpFunc;
	qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData); 

	arrptr = array;
	GListForeach(c, l)
		c->data = *arrptr++;

	tfree(array);

	return l;
}

GList*
GListUniq(GList *l) {
	GListCell   *c;

	GListForeach(c, l) {
		for(;;) {
			GListCell	*next = c->next;

			if ( next == NULL )
				break;

			if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
				GListDelete( l, next );
				GListFreeCell( l, next );
			} else
				break;
		}
		
	}

	return l;
}

void
GListFree(GList *l) {
	GListCell   *c = GLIST_HEAD(l), *tmp;

	while( c != NULL ) {
		tmp = c->next;
		GListFreeCell(l, c);
		c = tmp;
	}

	if (l)
		tfree(l);
}

void
GListFreeCell(GList *l, GListCell* c) {
	if (l && l->freeFunc) 
		l->freeFunc(c->data);

	tfree(c);
}

GList*
GListTruncate(GList *l, int n) {
	while( GLIST_LENGTH(l) > n ) {
		GListCell	*c = l->tail;

		GListDelete(l, c);
		GListFreeCell(l, c);
	}

	return l;
}

GList*
GListCopy(GList *l) {
	GList	*n = NULL;
	GListCell	*c;

	GListForeach(c,l) 
		n = GListPush(n, c->data);	

	if ( n && l) {
		n->cmpFunc = l->cmpFunc;
		n->freeFunc = l->freeFunc;
	}

	return n;
}

GList*
GListConcat(GList *l1, GList *l2) {

	if ( l1 == l2 )
		tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
	if ( GLIST_LENGTH(l1) == 0 )
		return l2;
	if ( GLIST_LENGTH(l2) == 0 ) {
		GListFree(l2);
		return l1;
	}

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

	l2->head = l2->tail = NULL;
	l2->length=0;
	GListFree(l2);

	return l1;
}

GList*
GListDifference(GList *l1, GList *l2) {
	GList	*l = NULL;
	GListCell	*c;

	if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
		tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");

	if (GLIST_LENGTH(l2) == 0 )
		return GListCopy(l1);

	GListForeach(c,l1) {
		if ( GListFind(l2, c->data) == NULL )
			l = GListPush(l, c->data);
	}

	return l;
}

GList*
GListUnion(GList *l1, GList *l2) {
	GList	*l = GListCopy(l1);
	GListCell	*c;

	if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
		tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");

	if (GLIST_LENGTH(l2) == 0 )
		return l;
	
	GListForeach(c,l2) {
		if ( GListFind(l1, c->data) == NULL )
			l = GListPush(l, c->data);
	}

	return l;
}

GList*
GListIntersect(GList *l1, GList *l2) {
	GList   *l = checkGList(NULL);
	GListCell   *c;

	if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
		tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");

	if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
		return l;

	GListForeach(c,l1) {
		if ( GListFind(l2, c->data) != NULL )
			l = GListPush(l, c->data);
	}

	return l;
}