temelia/release/include/doubly_linked_list.h

/*!
 Temalia - Doubly linked list interface.

 Copyright (C) 2008 Ceata (http://cod.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.
 */

#ifndef DOUBLYLINKEDLIST_
#define DOUBLYLINKEDLIST_

#include "platform.h"
#include "iterator.h"

struct _doubly_linked_list_t;

typedef struct _doubly_linked_list_t *doubly_linked_list_t;

/*!
 * @brief Returns a new doubly linked list.
 * Complexity O(1)
 */
DECLSPEC doubly_linked_list_t doubly_linked_list_new(void);

/*!
 * @brief Frees the memory occupied by doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 */
DECLSPEC void doubly_linked_list_delete(doubly_linked_list_t list);

/*!
 * @brief Checks if the list is empty.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC int doubly_linked_list_is_empty(doubly_linked_list_t list);

/*!
 * @brief Returns first key from doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC void *doubly_linked_list_get_front(doubly_linked_list_t list);

/*!
 * @brief Returns last key from doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC void *doubly_linked_list_get_back(doubly_linked_list_t list);

/*!
 * @brief Returns iterator to first node of doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC doubly_linked_list_iterator_t doubly_linked_list_get_begin(
		doubly_linked_list_t list);

/*!
 * @brief Sets list's "begin" iterator to given value.
 * Complexity O(1)
 *
 * @param Doubly linked list
 * @param New begin iterator
 */
DECLSPEC void doubly_linked_list_set_begin(doubly_linked_list_t list,
		doubly_linked_list_iterator_t begin);

/*!
 * @brief Returns iterator to last node of doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC doubly_linked_list_iterator_t doubly_linked_list_get_end(
		doubly_linked_list_t list);

/*!
 * @brief Sets list's "end" iterator to given value.
 * Complexity O(1)
 *
 * @param Doubly linked list
 * @param New end iterator
 */
DECLSPEC void doubly_linked_list_set_end(doubly_linked_list_t list,
		doubly_linked_list_iterator_t end);

/*!
 * @brief Returns size of doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC int doubly_linked_list_get_size(doubly_linked_list_t list);

/*!
 * @brief Sets the size of doubly linked list.
 * You may use this function in conjunction with linked_list_set_begin
 * and linked_list_set_end to clear the linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 * @param New size
 */
DECLSPEC void doubly_linked_list_set_size(doubly_linked_list_t list, int size);

/*!
 * @brief Checks if iterator is part of doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterator
 */
DECLSPEC int doubly_linked_list_check(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it);

/*!
 * @brief Returns iterator to a specified position in the doubly_linked_list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Position
 */
DECLSPEC doubly_linked_list_iterator_t doubly_linked_list_get_iterator_at(
		doubly_linked_list_t list, int position);

/*!
 * @brief Returns the value from a position in doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Position
 */
DECLSPEC void *doubly_linked_list_get_key_at(doubly_linked_list_t list, int position);

/*!
 * @brief Changes the value from a linked list, given by it's position.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Position
 * @param New key reference
 */
DECLSPEC void doubly_linked_list_set_key_at(doubly_linked_list_t list, int position,
		void *new_key);

/*!
 * @brief Searches the doubly linked list for key and returns an iterator to it
 * if exists and NULL if not.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Key
 * @param Pointer to comparison function
 */
DECLSPEC 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);

/*!
 * @brief Returns the index/position of iterator in doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterator
 */
DECLSPEC int doubly_linked_list_search_iterator(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it);

/*!
 * @brief Removes node from doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterator
 * @param Free the memory occupied by given iterator
 */
DECLSPEC void doubly_linked_list_remove_iterator(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, int free);

/*!
 * @brief Removes and returns first iterator containing given key in doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Key
 * @param Pointer to comparison function
 * @param Context
 * @param Free the iterator; if 1 then the function returns NULL
 */
DECLSPEC 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);

/*!
 * @brief Inserts key before an iterator in doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterator
 * @param Key
 */
DECLSPEC void doubly_linked_list_insert_before(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, void *key);

/*!
 * @brief Inserts key after an iterator in doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterator
 * @param Key
 */
DECLSPEC void doubly_linked_list_insert_after(doubly_linked_list_t list,
		doubly_linked_list_iterator_t it, void *key);

/*!
 * @brief Inserts key to beginning of doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 * @param Key
 */
DECLSPEC void doubly_linked_list_push_front(doubly_linked_list_t list, void *key);

/*!
 * @brief Inserts key to end of doubly linked list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 * @param Key
 */
DECLSPEC void doubly_linked_list_push_back(doubly_linked_list_t list, void *key);

/*!
 * @brief Removes the first node of current list.
 * Complexity O(1)
 *
 * @param Doubly linked list
 */
DECLSPEC void doubly_linked_list_pop_front(doubly_linked_list_t list);

/*!
 * @brief Removes the last node of current list.
 * Complexity O(1)
 *
 * @param Doubly linked list.
 */
DECLSPEC void doubly_linked_list_pop_back(doubly_linked_list_t list);

/*!
 * @brief Prints keys of doubly linked list in two orders :
 * a) 1 - begin to end;
 * b) -1 - end to begin;
 * Complexity O(n)
 *
 * @param Doubly linked list
 * @param Iterating function
 * @param Context
 * @param Order value
 */
DECLSPEC void doubly_linked_list_iterate(doubly_linked_list_t list, void key_handler(
		void *x, void *context), void *context, char order);

/*!
 * @brief Sorts, using bubble sort, a doubly linked list.
 * Complexity O(n*n)
 *
 * @param Doubly linked list
 * @param Pointer to comparison function
 */
DECLSPEC void doubly_linked_list_sort(doubly_linked_list_t list, int compare(void *x,
		void *y, void *context), void *context);

/*!
 * @brief Merges two sorted doubly linked lists and returns the result.
 * Complexity O(n2)
 *
 * @param First doubly linked list
 * @param Second doubly linked list
 * @param Pointer to comparison function
 */
DECLSPEC 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);

/*!
 * @brief Reverses INLINE (no additional memory needed) the keys from doubly linked list.
 * Complexity O(n)
 *
 * @param Doubly linked list
 */
DECLSPEC void doubly_linked_list_reverse(doubly_linked_list_t list);

/*!
 * @brief Inserts after iterator, of doubly linked list list1,
 * all keys from doubly linked list list2; list2 is destroyed !
 * Complexity O(1)
 *
 * @param First doubly linked list
 * @param Second doubly linked list
 * @param Iterator
 */
DECLSPEC void doubly_linked_list_spice(doubly_linked_list_t list1,
		doubly_linked_list_t list2, doubly_linked_list_iterator_t it);

#endif /* DOUBLYLINKEDLIST_ */