/*
 * Pointer Array
 *
 * Author:
 *   Aaron Bockover (abockover@novell.com)
 *   Gonzalo Paniagua Javier (gonzalo@novell.com)
 *   Jeffrey Stedfast (fejj@novell.com)
 *
 * (C) 2006,2011 Novell, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
 
#include <stdlib.h>
#include <glib.h>

typedef struct _GPtrArrayPriv {
	gpointer *pdata;
	guint len;
	guint size;
} GPtrArrayPriv;

static void 
g_ptr_array_grow(GPtrArrayPriv *array, guint length)
{
	guint new_length = array->len + length;

	g_return_if_fail(array != NULL);

	if(new_length <= array->size) {
		return;
	}

	array->size = 1;

	while(array->size < new_length) {
		array->size <<= 1;
	}

	array->size = MAX(array->size, 16);
	array->pdata = g_realloc(array->pdata, array->size * sizeof(gpointer));
}

GPtrArray *
g_ptr_array_new(void)
{
	return g_ptr_array_sized_new(0);
}

GPtrArray *
g_ptr_array_sized_new(guint reserved_size)
{
	GPtrArrayPriv *array = g_new0(GPtrArrayPriv, 1);

	array->pdata = NULL;
	array->len = 0;
	array->size = 0;

	if(reserved_size > 0) {
		g_ptr_array_grow(array, reserved_size);
	}

	return (GPtrArray *)array;
}

gpointer *
g_ptr_array_free(GPtrArray *array, gboolean free_seg)
{
	gpointer *data = NULL;
	
	g_return_val_if_fail(array != NULL, NULL);

	if(free_seg) {
		g_free(array->pdata);
	} else {
		data = array->pdata;
	}

	g_free(array);
	
	return data;
}

void
g_ptr_array_set_size(GPtrArray *array, gint length)
{
	g_return_if_fail(array != NULL);

	if((size_t)length > array->len) {
		g_ptr_array_grow((GPtrArrayPriv *)array, length);
		memset(array->pdata + array->len, 0, (length - array->len) 
			* sizeof(gpointer));
	}

	array->len = length;
}

void
g_ptr_array_add(GPtrArray *array, gpointer data)
{
	g_return_if_fail(array != NULL);
	g_ptr_array_grow((GPtrArrayPriv *)array, 1);
	array->pdata[array->len++] = data;
}

gpointer
g_ptr_array_remove_index(GPtrArray *array, guint index)
{
	gpointer removed_node;
	
	g_return_val_if_fail(array != NULL, NULL);
	g_return_val_if_fail(index >= 0 || index < array->len, NULL);

	removed_node = array->pdata[index];

	if(index != array->len - 1) {
		g_memmove(array->pdata + index, array->pdata + index + 1,
			(array->len - index - 1) * sizeof(gpointer));
	}
	
	array->len--;
	array->pdata[array->len] = NULL;

	return removed_node;
}

gpointer
g_ptr_array_remove_index_fast(GPtrArray *array, guint index)
{
	gpointer removed_node;

	g_return_val_if_fail(array != NULL, NULL);
	g_return_val_if_fail(index >= 0 || index < array->len, NULL);

	removed_node = array->pdata[index];

	if(index != array->len - 1) {
		g_memmove(array->pdata + index, array->pdata + array->len - 1,
			sizeof(gpointer));
	}

	array->len--;
	array->pdata[array->len] = NULL;

	return removed_node;
}

gboolean
g_ptr_array_remove(GPtrArray *array, gpointer data)
{
	guint i;

	g_return_val_if_fail(array != NULL, FALSE);

	for(i = 0; i < array->len; i++) {
		if(array->pdata[i] == data) {
			g_ptr_array_remove_index(array, i);
			return TRUE;
		}
	}

	return FALSE;
}

gboolean
g_ptr_array_remove_fast(GPtrArray *array, gpointer data)
{
	guint i;

	g_return_val_if_fail(array != NULL, FALSE);

	for(i = 0; i < array->len; i++) {
		if(array->pdata[i] == data) {
			array->len--;
			if (array->len > 0)
				array->pdata [i] = array->pdata [array->len];
			else
				array->pdata [i] = NULL;
			return TRUE;
		}
	}

	return FALSE;
}

void 
g_ptr_array_foreach(GPtrArray *array, GFunc func, gpointer user_data)
{
	guint i;

	for(i = 0; i < array->len; i++) {
		func(g_ptr_array_index(array, i), user_data);
	}
}

void
g_ptr_array_sort(GPtrArray *array, GCompareFunc compare)
{
	g_return_if_fail(array != NULL);
	qsort(array->pdata, array->len, sizeof(gpointer), compare);
}

static void
g_qsort_swap (char *a, char *b, size_t n)
{
	char *an = a + n;
	char tmp;
	
	do {
		tmp = *a;
		*a++ = *b;
		*b++ = tmp;
	} while (a < an);
}

static char *
g_qsort_median (char *a, char *b, char *c, GCompareDataFunc compare, gpointer user_data)
{
	if (compare (a, b, user_data) < 0) {
		/* a < b < c */
		if (compare (b, c, user_data) < 0)
			return b;
		
		/* a < c < b */
		if (compare (a, c, user_data) < 0)
			return c;
		
		/* c < a < b */
		return a;
	} else {
		/* b < a < c */
		if (compare (a, c, user_data) < 0)
			return a;
		
		/* b < c < a */
		if (compare (b, c, user_data) < 0)
			return c;
		
		/* c < b < a */
		return b;
	}
}

void
g_qsort_with_data (gpointer base, size_t nmemb, size_t size, GCompareDataFunc compare, gpointer user_data)
{
	char *middle = ((char *) base) + (nmemb / 2) * size;
	char *last = ((char *) base) + (nmemb - 1) * size;
	char *first = (char *) base;
	register char *i = first + size;
	register char *k = last;
	register char *pivot;
	
	if (nmemb <= 1)
		return;
	
	/* determine which element contains the median value */
	pivot = g_qsort_median (first, middle, last, compare, user_data);
	
	if (pivot != first) {
		/* swap pivot value into first element (so the location stays constant) */
		g_qsort_swap (first, pivot, size);
		pivot = first;
	}
	
	do {
		/* find the first element with a value > pivot value */
		while (i < k && compare (i, pivot, user_data) <= 0)
			i += size;
		
		/* find the last element with a value <= pivot value */
		while (k>= i && compare (k, pivot, user_data) > 0)
			k -= size;
		
		if (k <= i)
			break;
		
		g_qsort_swap (i, k, size);
	} while (1);
	
	if (k != pivot) {
		/* swap the pivot with the last element in the first partition */
		g_qsort_swap (pivot, k, size);
	}
	
	/* sort the first partition */
	g_qsort_with_data (first, (k - first) / size, size, compare, user_data);
	
	/* sort the second partition */
	g_qsort_with_data (k + size, (last - k) / size, size, compare, user_data);
}

void
g_ptr_array_sort_with_data (GPtrArray *array, GCompareDataFunc compare, gpointer user_data)
{
	g_return_if_fail (array != NULL);
	
	g_qsort_with_data (array->pdata, array->len, sizeof (gpointer), compare, user_data);
}