temelia/src/vector.c

/*!
 Temelia - Vector implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/vector.h"
#include "include/common.h"
#include <string.h>

struct _vector_t
{
	/*! vector's capacity, maximum keys number */
	int capacity;

	/*! vector's keys number */
	int size;

	/*! vector's capacity increment, when it becomes full */
	int capacity_increment;

	/*! array of references stored in vector */
	void **data;
};

// (!) The methods implemented here are trivial, so they're not well commented.

//   Private functions. Because those methods are private,
// no assertion is done in their definition.

/* Randomized Quick Sort algorithm is used for sorting the vector. */
static void _quick_sort(void **data, int p, int r, int(*compare)(void *x,
		void *y, void *context), void *context);
static int _partition(void **data, int p, int r, int(*compare)(void *x,
		void *y, void *context), void *context);

vector_t vector_new(int capacity)
{
	vector_t vector;
	int i;

	_ASSERT(capacity, <=, 0, INVALID_INPUT, NULL);

	vector = (struct _vector_t *) _new(sizeof(struct _vector_t));

	/*
	 * Check if the memory allocation fail; if so then
	 * recover from this failure.
	 */
	_ASSERT(vector, ==, NULL, MEMORY_ALLOCATION, NULL);

	vector->size = 0;
	vector->capacity = capacity;
	vector->capacity_increment = capacity;

	vector->data = (void **) _new(capacity * sizeof(void *));

	if (vector->data == NULL)
	{
		temelia_errno = MEMORY_ALLOCATION;
		_delete(vector);
		return NULL;
	}

	for (i = 0; i < capacity; i++)
		vector->data[i] = NULL;

	return vector;
}

vector_t vector_clone(vector_t vector,
		void *(*clone)(void *key, void *context), void *context)
{
	vector_t cloned_vector;
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);

	cloned_vector = vector_new(vector->capacity);

	if (clone != NULL)
	{
		for (i = 0; i < vector->size; i++)
			cloned_vector->data[i] = clone(vector->data[i], context);
	}
	else
	{
		for (i = 0; i < vector->size; i++)
			cloned_vector->data[i] = vector->data[i], context;
	}
	cloned_vector->size = vector->size;

	return cloned_vector;
}

void vector_delete(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER,);

	vector->size = vector->capacity = vector->capacity_increment = 0;
	_delete(vector->data);
	_delete(vector);
}

void vector_clear(vector_t vector)
{
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);

	for (i = 0; i < vector->size; i++)
		vector->data[i] = NULL;
	vector->size = 0;
}

int vector_get_capacity(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, -1);

	return vector->capacity;
}

int vector_get_size(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, -1);

	return vector->size;
}

int vector_get_capacity_increment(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, 0);

	return vector->capacity_increment;
}

void *vector_get_internal_representation(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, 0);

	return vector->data;
}

void vector_set_size(vector_t vector, int new_size)
{
	int i;

	// Should not receive a null pointer, a negative new keys number or
	// a bigger new keys then current vector's capacity.
	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(new_size, <, 0, INVALID_INPUT,);
	_ASSERT(new_size, >, vector->capacity, INVALID_INPUT,);

	if (new_size < vector->size)
	{
		for (i = new_size; i < vector->size; i++)
			vector->data[i] = NULL;
	}
	else if (new_size < vector->capacity)
	{
		for (i = vector->size; i < new_size; i++)
			vector->data[i] = NULL;
	}
	vector->size = new_size;
}

void vector_set_capacity_increment(vector_t vector, int new_capacity_increment)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(new_capacity_increment, <, 0, NULL_POINTER,);

	vector->capacity_increment = new_capacity_increment;
}

void vector_set_key_at(vector_t vector, int position, void *key)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(position, <, 0, INVALID_INPUT,);
	_ASSERT(position, >=, vector->size, INVALID_INPUT,);

	vector->data[position] = key;
}

void *vector_get_key_at(vector_t vector, int position)
{
	_ASSERT(vector, ==, NULL, INVALID_INPUT, NULL);
	_ASSERT(position, <, 0, INVALID_INPUT, NULL);
	_ASSERT(position, >=, vector->size, INVALID_INPUT, NULL);

	return vector->data[position];
}

void vector_swap(vector_t vector, int index1, int index2)
{
	void *aux;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(index1, <, 0, INVALID_INPUT,);
	_ASSERT(index1, >=, vector->size, INVALID_INPUT,);
	_ASSERT(index2, <, 0, INVALID_INPUT,);
	_ASSERT(index2, >=, vector->size, INVALID_INPUT,);

	aux = vector->data[index1];
	vector->data[index1] = vector->data[index2];
	vector->data[index2] = aux;
}

void vector_push_front(vector_t vector, void *key)
{
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);

	if (vector->capacity == vector->size)
	{
		_ASSERT(vector->capacity_increment, ==, 0, FULL,);

		vector->capacity += vector->capacity_increment;
		vector->data
				= _realloc(vector->data, vector->capacity * sizeof(void *));

		_ASSERT (vector->data, ==, NULL, NULL_POINTER,);
	}

	for (i = vector->size; i >= 1; i--)
		vector->data[i] = vector->data[i - 1];

	vector->data[0] = key;
	vector->size++;
}

void vector_push_back(vector_t vector, void *key)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER,);

	if (vector->capacity == vector->size)
	{
		_ASSERT(vector->capacity_increment, ==, 0, FULL,);
		vector->capacity += vector->capacity_increment;
		vector->data
				= _realloc(vector->data, vector->capacity * sizeof(void *));

		_ASSERT (vector->data, ==, NULL, NULL_POINTER,);
	}
	vector->data[vector->size++] = key;
}

void vector_push_before(vector_t vector, void *key, void *another_key,
		int compare(void *x, void *y, void *context), void *context)
{
	int i, k;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);

	k = vector_search(vector, another_key, compare, context);

	// If i can't find F, then i push it in the vector's front.
	if (k == -1)
	{
		vector_push_front(vector, key);
		return;
	}

	if (vector->size == vector->capacity)
	{
		_ASSERT(vector->capacity_increment, ==, 0, FULL,);

		vector->capacity += vector->capacity_increment;
		vector->data
				= _realloc(vector->data, vector->capacity * sizeof(void *));

		_ASSERT (vector->data, ==, NULL, NULL_POINTER,);
	}

	for (i = vector->size; i > k; i--)
		vector->data[i] = vector->data[i - 1];
	vector->data[k] = key;
	vector->size++;
}

void vector_push_after(vector_t vector, void *E, void *F, int compare(void *x,
		void *y, void *context), void *context)
{
	int i, k;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);

	k = vector_search(vector, F, compare, context);

	// If i can't find F, then i push it in the vector's back.
	if (k == -1)
	{
		vector_push_back(vector, E);
		return;
	}

	if (vector->size == vector->capacity)
	{
		_ASSERT(vector->capacity_increment, ==, 0, FULL,);

		vector->capacity += vector->capacity_increment;
		vector->data
				= _realloc(vector->data, vector->capacity * sizeof(void *));

		_ASSERT (vector->data, ==, NULL, NULL_POINTER,);
	}

	for (i = vector->size; i > k + 1; i--)
		vector->data[i] = vector->data[i - 1];
	vector->data[k + 1] = E;
	vector->size++;
}

void *vector_remove_key(vector_t vector, void *key, int compare(void *x,
		void *y, void *context), void *context)
{
	return vector_remove_key_at(vector, vector_search(vector, key, compare,
			context));
}

void *vector_remove_key_at(vector_t vector, int index)
{
	int i;
	void *key;

	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(index, <, 0, ELEMENT_NOT_FOUND, NULL);
	_ASSERT(index, >=, vector->size, ELEMENT_NOT_FOUND, NULL);
	_ASSERT(vector->size, ==, 0, EMPTY, NULL);

	key = vector->data[index];

	for (i = index; i < vector->size - 1; i++)
		vector->data[i] = vector->data[i + 1];
	vector->size--;

	return key;
}

void *vector_pop_back(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vector->size, <=, 0, NULL_POINTER, NULL);

	return vector->data[--vector->size];
}

void *vector_pop_front(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);

	return vector_remove_key_at(vector, 0);
}

int vector_search(vector_t vector, void *key, int compare(void *x, void *y,
		void *context), void *context)
{
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	for (i = 0; i < vector->size; i++)
		if (!compare(vector->data[i], key, context))
			return i;
	return -1;
}

int vector_is_empty(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, -1);

	return vector->size == 0;
}

int vector_is_full(vector_t vector)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER, -1);

	return vector->size == vector->capacity;
}

void vector_sort(vector_t vector, int compare(void *x, void *y, void *context),
		void *context)
{
	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(vector->size, <, 1, INVALID_INPUT,);

	// 1 key vector needs no sort :-)
	if (vector->size == 1)
		return;

	_quick_sort(vector->data, 0, vector->size - 1, compare, context);
}

void vector_iterate(vector_t vector, void(*key_handler)(void *key,
		void *context), void *context)
{
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	for (i = 0; i < vector->size; i++)
		key_handler(vector->data[i], context);
}

void *vector_min(vector_t vector, int compare(void *x, void *y, void *context),
		void *context)
{
	void *min;
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vector->size, <=, 0, EMPTY, NULL);

	min = vector->data[0];
	for (i = 1; i < vector->size; i++)
		if (compare(min, vector->data[i], context) > 0)
			min = vector->data[i];
	return min;
}

void *vector_max(vector_t vector, int compare(void *x, void *y, void *context),
		void *context)
{
	void *max;
	int i;

	_ASSERT(vector, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vector->size, <=, 0, EMPTY, NULL);

	max = vector->data[0];
	for (i = 1; i < vector->size; i++)
		if (compare(max, vector->data[i], context) < 0)
			max = vector->data[i];
	return max;
}

static void _quick_sort(void **data, int p, int r, int(*compare)(void *,
		void *, void *context), void *context)
{
	int q;

	if (p < r)
	{
		q = _partition(data, p, r, compare, context);
		_quick_sort(data, p, q, compare, context);
		_quick_sort(data, q + 1, r, compare, context);
	}
}

static int _partition(void **data, int p, int r, int(*compare)(void *x,
		void *y, void *context), void *context)
{
	int i, j;
	void *pivot, *aux;

	pivot = data[p + _rand() % (r - p)];
	i = p - 1;
	j = r + 1;

	while (1)
	{
		do
		{
			i++;
		} while (compare(data[i], pivot, context) < 0 && i < r);

		do
		{
			j--;
		} while (compare(data[j], pivot, context) > 0 && j > p);

		if (i >= j)
			return j;

		aux = data[i];
		data[i] = data[j];
		data[j] = aux;
	}
}