temelia/src/doubly_linked_list.c

/*!
 Temelia - Doubly Linked List implementation source file.

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

 @author Dascalu Laurentiu, Macovei Alexandru

 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/doubly_linked_list.h"
#include "include/common.h"
#include "include/list_common.h"
#include <stdlib.h>

struct _doubly_linked_list_t
{
	struct _doubly_linked_list_iterator_t *begin;
	struct _doubly_linked_list_iterator_t *end;
	int size;
};

static void _doubly_linked_list_reverse_aux(doubly_linked_list_iterator_t it);

doubly_linked_list_t doubly_linked_list_new(void)
{
	doubly_linked_list_t list;

	LIST_NEW(doubly_linked_list_t, list);

	return list;
}

doubly_linked_list_t doubly_linked_list_clone(doubly_linked_list_t list,
		void *(*clone)(void *key, void *context), void *context)
{
	doubly_linked_list_t clone_list;
	doubly_linked_list_iterator_t it;

	LIST_CLONE(doubly_linked_list, list, it, clone_list, clone, context);

	return clone_list;
}

void doubly_linked_list_delete(doubly_linked_list_t list)
{
	doubly_linked_list_iterator_t crt, prc;

	LIST_DELETE(list, crt, prc, doubly_linked_list_iterator);
}

int doubly_linked_list_is_empty(doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	return list->size == 0;
}

void *doubly_linked_list_get_front(doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(list->size, <=, 0, INVALID_INPUT, NULL);

	return doubly_linked_list_iterator_get_key(list->begin);
}

void *doubly_linked_list_get_back(doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(list->size, <=, 0, INVALID_INPUT, NULL);

	return doubly_linked_list_iterator_get_key(list->end);
}

doubly_linked_list_iterator_t doubly_linked_list_get_begin(
		doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);

	return list->begin;
}

void doubly_linked_list_set_begin(doubly_linked_list_t list,
		doubly_linked_list_iterator_t begin)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->begin = begin;
}

doubly_linked_list_iterator_t doubly_linked_list_get_end(
		doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);

	return list->end;
}

void doubly_linked_list_set_end(doubly_linked_list_t list,
		doubly_linked_list_iterator_t end)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->end = end;
}

int doubly_linked_list_get_size(doubly_linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	return list->size;
}

void doubly_linked_list_set_size(doubly_linked_list_t list, int size)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->size = size;
}

int doubly_linked_list_check(doubly_linked_list_t list,
		doubly_linked_list_iterator_t p)
{
	doubly_linked_list_iterator_t it_left, it_right;

	_ASSERT(list, ==, NULL, NULL_POINTER, -1);
	_ASSERT(p, ==, NULL, NULL_POINTER, -1);

	for (it_left = list->begin, it_right = list->end; it_left != it_right;)
	{
		it_left = doubly_linked_list_iterator_get_next(it_left);
		it_right = doubly_linked_list_iterator_get_prev(it_right);
	}

	if (it_left == it_right)
		return 1;
	return 0;
}

doubly_linked_list_iterator_t doubly_linked_list_get_iterator_at(
		doubly_linked_list_t list, int position)
{
	doubly_linked_list_iterator_t it;
	int i;

	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(position, <, 0, INVALID_INPUT, NULL);
	_ASSERT(position, >=, list->size, INVALID_INPUT, NULL);

	it = NULL;

	// If position is in the first half, then move from beginning to it.
	if (position < list->size / 2)
		for (i = 0, it = list->begin; i < position && it != NULL; i++, it
				= doubly_linked_list_iterator_get_next(it))
			;

	// Else, move from the end to it. Although the complexity is the same with
	// the search from beginning in any case, O(n), the constant is not the same.
	else
		for (i = list->size - 1, it = list->end; i > position && it != NULL; i--, it
				= doubly_linked_list_iterator_get_prev(it))
			;

	return it;
}

void *doubly_linked_list_get_key_at(doubly_linked_list_t list, int position)
{
	doubly_linked_list_iterator_t it = doubly_linked_list_get_iterator_at(list,
			position);

	if (it)
		return doubly_linked_list_iterator_get_key(it);
	return NULL;
}

void doubly_linked_list_set_key_at(doubly_linked_list_t list, int position,
		void *new_key)
{
	doubly_linked_list_iterator_t it = doubly_linked_list_get_iterator_at(list,
			position);

	if (it)
		doubly_linked_list_iterator_set_key(it, new_key);
}

doubly_linked_list_iterator_t doubly_linked_list_search_key(
		doubly_linked_list_t list, void *key, int compare(void *x, void *y,
				void *context), void *context)
{
	doubly_linked_list_iterator_t it_left, it_right;

	for (it_left = list->begin, it_right = list->end; it_left != it_right;)
	{
		if (!compare(doubly_linked_list_iterator_get_key(it_left), key, context))
			return it_left;

		if (!compare(doubly_linked_list_iterator_get_key(it_right), key,
				context))
			return it_right;

		it_left = doubly_linked_list_iterator_get_next(it_left);
		it_right = doubly_linked_list_iterator_get_prev(it_right);
	}

	return NULL;
}

int doubly_linked_list_search_iterator(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it)
{
	int i_left, i_right;
	doubly_linked_list_iterator_t it_left, it_right;

	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	for (it_left = list->begin, it_right = list->end, i_left = 0, i_right
			= list->size - 1; it_left != it_right;)
	{
		if (it_left == it)
			return i_left;

		if (it_right == it)
			return i_right;

		it_left = doubly_linked_list_iterator_get_next(it_left);
		it_right = doubly_linked_list_iterator_get_prev(it_right);
	}

	return -1;
}

void doubly_linked_list_remove_iterator(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, int delete_iterator)
{
	doubly_linked_list_iterator_t aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(it, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, ==, 0, EMPTY,);

	if (it == list->begin)
	{
		list->begin = doubly_linked_list_iterator_get_next(list->begin);
		doubly_linked_list_iterator_set_prev(list->begin, NULL);
	}
	else if (it == list->end)
	{
		aux = doubly_linked_list_iterator_get_prev(list->end);
		doubly_linked_list_iterator_set_next(aux, NULL);
		list->end = aux;
	}
	else
	{
		aux = doubly_linked_list_iterator_get_prev(it);
		doubly_linked_list_iterator_set_next(aux,
				doubly_linked_list_iterator_get_next(
						doubly_linked_list_iterator_get_next(aux)));
		doubly_linked_list_iterator_set_prev(
				doubly_linked_list_iterator_get_next(aux), aux);
	}

	list->size--;

	if (delete_iterator)
		_delete(it);
}

doubly_linked_list_iterator_t doubly_linked_list_remove_key(
		doubly_linked_list_t list, void *key, int compare(void *x, void *y,
				void *context), void *context, int free)
{
	doubly_linked_list_iterator_t it = doubly_linked_list_search_key(list, key,
			compare, context);

	if (it)
	{
		doubly_linked_list_remove_iterator(list, it, free);

		if (free)
			return NULL;
		return it;
	}

	return NULL;
}

void doubly_linked_list_insert_before(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, void *key)
{
	doubly_linked_list_iterator_t new_node;

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

	new_node = doubly_linked_list_iterator_new(key, NULL, NULL);

	if (list->size == 0)
	{
		if (it == NULL)
			list->begin = list->end = new_node;
		else
		{
			doubly_linked_list_iterator_delete(new_node);
			_ASSERT(NULL, ==, NULL, INVALID_INPUT,);
		}
	}
	else if (it == list->begin)
	{
		doubly_linked_list_iterator_set_next(new_node, it);
		doubly_linked_list_iterator_set_prev(it, new_node);
		list->begin = new_node;
	}
	else if (it == NULL)
	{
		doubly_linked_list_iterator_set_prev(new_node, list->end);
		doubly_linked_list_iterator_set_next(list->end, new_node);
		list->end = new_node;
	}
	else
	{
		doubly_linked_list_iterator_join(doubly_linked_list_iterator_get_prev(
				it), new_node, it);

		if (list->size == 1)
			list->begin = new_node;
	}
	list->size++;
}

void doubly_linked_list_insert_after(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, void *key)
{
	doubly_linked_list_iterator_t new_node;

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

	new_node = doubly_linked_list_iterator_new(key, NULL, NULL);
	_ASSERT(new_node, ==, NULL, NULL_POINTER,);

	if (list->size == 0)
	{
		if (it == NULL)
			list->begin = list->end = new_node;
		else
		{
			doubly_linked_list_iterator_delete(new_node);
			return;
		}
	}
	else if (it == list->end)
	{
		doubly_linked_list_iterator_set_next(it, new_node);
		doubly_linked_list_iterator_set_prev(new_node, it);
		list->end = new_node;
	}
	else if (it == NULL)
	{
		doubly_linked_list_iterator_set_prev(list->begin, new_node);
		doubly_linked_list_iterator_set_next(new_node, list->begin);
		list->begin = new_node;
	}
	else
	{
		doubly_linked_list_iterator_join(it, new_node,
				doubly_linked_list_iterator_get_next(it));

		if (list->size == 1)
			list->end = new_node;
	}
	list->size++;
}

void doubly_linked_list_push_front(doubly_linked_list_t list, void *key)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	doubly_linked_list_insert_before(list, list->begin, key);
}

void doubly_linked_list_push_back(doubly_linked_list_t list, void *key)
{
	doubly_linked_list_iterator_t new_node;

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

	new_node = doubly_linked_list_iterator_new(key, NULL, NULL);

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

	if (list->size == 0)
	{
		list->begin = list->end = new_node;
		list->size = 1;
		return;
	}

	doubly_linked_list_iterator_join(list->end, new_node, NULL);
	list->end = new_node;
	list->size++;
}

void doubly_linked_list_pop_front(doubly_linked_list_t list)
{
	doubly_linked_list_iterator_t aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, <=, 0, INVALID_INPUT,);

	aux = list->begin;
	if (list->size == 1)
		list->begin = list->end = NULL;
	else
	{
		list->begin = doubly_linked_list_iterator_get_next(list->begin);
		doubly_linked_list_iterator_set_prev(list->begin, NULL);
	}

	_delete(aux);
	list->size--;
}

void doubly_linked_list_pop_back(doubly_linked_list_t list)
{
	doubly_linked_list_iterator_t aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, <=, 0, INVALID_INPUT,);

	aux = list->end;
	if (list->size == 1)
		list->begin = list->end = NULL;
	else
	{
		list->end = doubly_linked_list_iterator_get_prev(list->end);
		doubly_linked_list_iterator_set_next(list->end, NULL);
	}

	_delete(aux);
	list->size--;
}

void doubly_linked_list_iterate(doubly_linked_list_t list, void key_handler(
		void *x, void *context), void *context, int order)
{
	doubly_linked_list_iterator_t p;

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

	if (order == 1)
		for (p = list->begin; p != NULL; p
				= doubly_linked_list_iterator_get_next(p))
			key_handler(doubly_linked_list_iterator_get_key(p), context);
	else if (order == -1)
		for (p = list->end; p != NULL; p
				= doubly_linked_list_iterator_get_prev(p))
			key_handler(doubly_linked_list_iterator_get_key(p), context);
	else
		temelia_errno = INVALID_INPUT;
}

void doubly_linked_list_sort(doubly_linked_list_t list, int compare(void *x,
		void *y, void *context), void *context)
{
	void *aux;
	doubly_linked_list_iterator_t it;

	LIST_SORT(list, it, aux, compare, context, doubly_linked_list_iterator);
}

doubly_linked_list_t doubly_linked_list_merge(doubly_linked_list_t list1,
		doubly_linked_list_t list2,
		int compare(void *x, void *y, void *context), void *context)
{
	doubly_linked_list_t L3;
	doubly_linked_list_iterator_t it1, it2;
	void *key1, *key2;

	_ASSERT(list1, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(list2, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	L3 = doubly_linked_list_new();

	it1 = list1->begin;
	it2 = list2->begin;

	LIST_MERGE(L3, it1, it2, key1, key2, doubly_linked_list, compare, context);

	return L3;
}

void doubly_linked_list_reverse(doubly_linked_list_t list)
{
	void *aux;

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

	_doubly_linked_list_reverse_aux(list->begin);

	/*
	 * Swaps "begin" with "end" for a consistent reverse;
	 * also sets "end's" next iterator pointer to NULL
	 */
	aux = list->begin;
	list->begin = list->end;
	list->end = aux;
	doubly_linked_list_iterator_set_next(list->end, NULL);
	doubly_linked_list_iterator_set_prev(list->begin, NULL);
}

void doubly_linked_list_spice(doubly_linked_list_t list1,
		doubly_linked_list_t list2, doubly_linked_list_iterator_t it)
{
	doubly_linked_list_iterator_t next_node;

	_ASSERT(list1, ==, NULL, NULL_POINTER,);
	_ASSERT(list2, ==, NULL, NULL_POINTER,);

	if (it == NULL)
	{
		/*
		 * => list2 -> list1
		 */
		if (list1->end == NULL || list1->begin == list1->end)
			list1->end = list2->end;
		doubly_linked_list_iterator_join(list2->end, list1->begin,
				doubly_linked_list_iterator_get_next(list1->begin));
		list1->begin = list2->begin;
	}
	else if (list1->size > 0)
	{
		if (it == list1->end)
		{
			doubly_linked_list_iterator_join(list1->end, list2->begin,
					doubly_linked_list_iterator_get_next(list2->begin));
			list1->end = list2->end;
		}
		else
		{
			// Finally, we can use the given iterator :-)
			next_node = doubly_linked_list_iterator_get_next(it);

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

			doubly_linked_list_iterator_join(it, list2->begin,
					doubly_linked_list_iterator_get_next(list2->begin));
			doubly_linked_list_iterator_join(
					doubly_linked_list_iterator_get_prev(list2->end),
					list2->end, next_node);
		}
	}
	else if (list1->size == 0)
	{
		// Simply copies the two pointers
		list1->begin = list2->begin;
		list1->end = list2->end;
	}

	list1->size += list2->size;
	_delete(list2);
}

static void _doubly_linked_list_reverse_aux(doubly_linked_list_iterator_t it)
{
	static doubly_linked_list_iterator_t _aux;

	if (it == NULL)
		return;

	_doubly_linked_list_reverse_aux(doubly_linked_list_iterator_get_next(it));
	_aux = doubly_linked_list_iterator_get_next(it);
	doubly_linked_list_iterator_set_next(_aux, it);
	doubly_linked_list_iterator_set_prev(it, _aux);
}