temelia/release/include/linked_list.h

/*
 Temelia - 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 LINKEDLIST_H_
#define LINKEDLIST_H_

#include "iterator.h"

typedef struct _linked_list_t *linked_list_t;

/*!
 * @brief Constructor - returns a new linked list.
 * Complexity O(1)
 */
DECLSPEC linked_list_t linked_list_new(void);

/*!
 * @brief Frees the memory occupied by linked list;
 * all list's iterators become invalid.
 * Complexity O(n)
 *
 * @param Linked list
 */
DECLSPEC void linked_list_delete(linked_list_t list);

/*!
 * @brief Checks if the list is empty.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC int linked_list_is_empty(linked_list_t list);

/*!
 * @brief Returns the first key.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC void *linked_list_get_front(linked_list_t list);

/*!
 * @brief Returns the last key.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC void *linked_list_get_back(linked_list_t list);

/*!
 * @brief Returns iterator to first node of linked list.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC linked_list_iterator_t linked_list_get_begin(linked_list_t list);

/*!
 * @brief Sets list's "begin" iterator to given value.
 * Complexity O(1)
 *
 * @param Linked list
 * @param New begin iterator
 */
DECLSPEC void linked_list_set_begin(linked_list_t list, linked_list_iterator_t begin);

/*!
 * @brief Returns iterator to last node.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC linked_list_iterator_t linked_list_get_end(linked_list_t list);

/*!
 * @brief Sets list's "end" iterator to given value.
 * Complexity O(1)
 *
 * @param Linked list
 * @param New end iterator
 */
DECLSPEC void linked_list_set_end(linked_list_t list, linked_list_iterator_t end);

/*!
 * @brief Returns the size of linked list.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC int linked_list_get_size(linked_list_t list);

/*!
 * @brief Sets the size of 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 Linked list
 * @param New size
 */
DECLSPEC void linked_list_set_size(linked_list_t list, int size);

/*!
 * @brief Returns true if iterator is part of linked list.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Iterator
 */
DECLSPEC int linked_list_check(linked_list_t list, linked_list_iterator_t it);

/*!
 * @brief Returns the previous node pointed by iterator;
 * the operation if expensive because linke_list_iterator
 * has no pointer to the previous iterator in the list.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Iterator
 */
DECLSPEC linked_list_iterator_t linked_list_iterator_get_prev(linked_list_t list,
		linked_list_iterator_t it);

/*!
 * @brief Returns the iterator to specified position in linked list.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Position
 */
DECLSPEC linked_list_iterator_t linked_list_get_iterator_at(linked_list_t list,
		int position);

/*!
 * @brief Returns the value from a position in linked list.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Position
 */
DECLSPEC void *linked_list_get_key_at(linked_list_t list, int position);

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

/*!
 * @brief Searches over linked list for key and returns an iterator to the
 * first occurrence.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Key
 * @param Pointer to comparison function
 */
DECLSPEC linked_list_iterator_t linked_list_search_key(linked_list_t list, void *key,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @brief Returns the index/position of iterator in linked list.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Iterator
 */
DECLSPEC int linked_list_search_iterator(linked_list_t list, linked_list_iterator_t it);

/*!
 * @brief Removes iterator from linked list
 * Complexity O(n)
 *
 * @param Linked list
 * @param Iterator
 * @param Value on which freeing the iterator depends; 1 if you want to free the memory occupied
 * by the iterator and 0 if you don't
 */
DECLSPEC void linked_list_remove_iterator(linked_list_t list, linked_list_iterator_t it,
		int free);

/*!
 * @brief Removes and returns first node that contains key.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Key
 * @param Pointer to comparison function
 * @param Free the iterator containing that key
 */
DECLSPEC linked_list_iterator_t linked_list_remove_key(linked_list_t list, void *key,
		int compare(void *x, void *y, void *context), void *context, int free);

/*!
 * @brief Inserts key after iterator in linked list
 * Complexity O(1)
 *
 * @param Linked list
 * @param Iterator
 * @param Key
 */
DECLSPEC void linked_list_insert_after(linked_list_t list, linked_list_iterator_t it,
		void *key);

/*!
 * @brief Inserts key before iterator , in linked list.
 * Complexity O(1)
 *
 * @param Linked list
 * @param Iterator
 * @param Key
 */
DECLSPEC void linked_list_insert_before(linked_list_t list, linked_list_iterator_t it,
		void *key);

/*!
 * @brief Inserts an key to beginning of linked list.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC void linked_list_push_front(linked_list_t list, void *key);

/*!
 * @brief Inserts an key to end of linked list.
 * Complexity O(1)
 *
 * @param Linked list
 * @param Key
 */
DECLSPEC void linked_list_push_back(linked_list_t list, void *key);

/*!
 * @brief Removes the first node of current list.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC void linked_list_pop_front(linked_list_t list);

/*!
 * @brief Removes the last node of current list.
 * Complexity O(1)
 *
 * @param Linked list
 */
DECLSPEC void linked_list_pop_back(linked_list_t list);

/*! @brief Iterates over the keys of current Linked list
 * a) 1 - begin to end
 * b) -1 - end to begin.
 * Complexity O(n)
 *
 * @param Linked list
 * @param Pointer to iterating function
 * @param Context
 * @param Order
 */
DECLSPEC void linked_list_iterate(linked_list_t list, void key_handler(void *x,
		void *context), void *context, char order);

/*!
 * @brief Sorts a linked list using the bubble sort algorithm
 * Complexity O(n*n)
 *
 * @param Linked list
 * @param Pointer to comparison function.
 */
DECLSPEC void linked_list_sort(linked_list_t list, int compare(void *x, void *y,
		void *context), void *context);

/*!
 * @brief Merges two linked lists and returns the result : (list1, list2).
 * Complexity O(n1 + n2)
 *
 * @param First linked list
 * @param Second linked list
 * @param Pointer to comparison function
 */
DECLSPEC linked_list_t linked_list_merge(linked_list_t list1, linked_list_t list2,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @brief Reverses the keys from a linked list; the reverse is done "INLINE",
 * without any additional memory.
 * Complexity O(n)
 *
 * @param Linked list
 */
DECLSPEC void linked_list_reverse(linked_list_t list);

/*!
 * @brief Inserts the iterator from linked list "list2" after
 * the iterator "it1" of linked list "list1". The second
 * linked list will become invalid: all it's iterators
 * will be part of the first linked list.
 * Complexity O(1)
 *
 * @param First linked list
 * @param Second linked list
 * @param Iterator; NULL if you want to unsorted merge the lists
 */
DECLSPEC void linked_list_spice(linked_list_t list1, linked_list_t list2,
		linked_list_iterator_t it1);

#endif /* LINKED_LIST_H */