/**
 * @file linkedList.h
 * @ingroup collection
 *
 * Linked list module.
 *
 * @author Geoff Davis <geoff@circlemudsquared.org>
 *
 * @par Copyright:
 *   Copyright (C) 2006 Geoff Davis <geoff@circlemudsquared.org><br>
 *                      Greg Buxton <greg@circlemudsquared.org>
 *
 * @par
 *   Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University<br>
 *   CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991.
 *
 * @par
 *   All rights reserved.  See license.doc for complete information.
 *
 * @package cs
 * @version 1.0
 */

#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__

#include "base.h"

/**
 * An alias for struct _linkedList_t.
 * @typedef struct _linkedList_t
 */
typedef struct _linkedList_t linkedList_t;

/**
 * An alias for struct _linkedListEntry_t.
 * @typedef struct _linkedListEntry_t
 */
typedef struct _linkedListEntry_t linkedListEntry_t;

/**
 * An alias for struct _linkedListIterator_t.
 * @typedef struct _linkedListIterator_t
 */
typedef struct _linkedListIterator_t linkedListIterator_t;

/**
 * The linked list structure.
 * @{
 */
struct _linkedList_t {
  linkedListEntry_t *firstEntry;        /**< the first entry in the list    */
  freeFunction_t     freeFunction;      /**< the function to free elements. */
  linkedListEntry_t *lastEntry;         /**< the last entry in the list.    */
  size_t             size;              /**< the number of list entries.    */
};
/** @} */

/**
 * The linked list entry structure.
 * @{
 */
struct _linkedListEntry_t {
  void              *element;           /**< the element.                   */
  linkedListEntry_t *nextEntry;         /**< the next entry in the list.    */
  linkedListEntry_t *previousEntry;     /**< the previous entry in the list.*/
};
/** @} */

/**
 * The list iterator structure.
 * @{
 */
struct _linkedListIterator_t {
  linkedListEntry_t *currentEntry;      /**< the current entry in the list. */
  linkedListEntry_t *lastReturned;      /**< the last entry returned by iter*/
  linkedList_t      *list;              /**< the list being iterated over.  */
};
/** @} */

/*
 * list functions
 */

/**
 * Removes all elements from a linked list.
 * @param list the linked list to be cleared
 * @return none
 */
void linkedList_clear(linkedList_t *list);

/**
 * Returns whether a linked list contains a particular element.
 * @param list the linked list to be tested
 * @param element the element for which to test
 * @return TRUE if the linked list contains a matching element;
 *         FALSE otherwise
 */
bool linkedList_contains(linkedList_t *list, void *element);

/**
 * Constructs a new linked list.
 * @param freeFunction the function to be called to free elements
 * @return a new linked list or NULL
 */
linkedList_t *linkedList_create(freeFunction_t freeFunction);

/**
 * Frees a linked list.
 * @param list the linked list to be freed
 * @return none
 */
void linkedList_free(linkedList_t *list);

/**
 * Returns the size of a linked list.
 * @param list the linked list to be tested
 * @return the size of the linked list, or zero (0)
 */
size_t linkedList_getSize(linkedList_t *list);

/**
 * Returns whether a linked list is empty.
 * @param list the linked list to be tested
 * @return TRUE if the linked list is empty; FALSE otherwise
 */
bool linkedList_isEmpty(linkedList_t *list);

/**
 * Returns the last element in a linked list.
 * @param list the linked list whose last element is to be retreived
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the last element, or NULL
 */
void *linkedList_peekBack(linkedList_t *list, void *defaultValue);

/**
 * Returns the first element in a linked list.
 * @param list the linked list whose first element is to be retreived
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the first element, or NULL
 */
void *linkedList_peekFront(linkedList_t *list, void *defaultValue);

/**  
 * Removes and returns the last element in a linked list.
 * @param list the linked list whose last element is to be popped   
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the last element, or NULL   
 */ 
void *linkedList_popBack(linkedList_t *list, void *defaultValue);

/**  
 * Removes and returns the first element in a linked list.
 * @param list the linked list whose first element is to be popped   
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the first element, or NULL   
 */ 
void *linkedList_popFront(linkedList_t *list, void *defaultValue);

/**
 * Adds an element at the end of a linked list.
 * @param list the linked list into which an element is to be inserted
 * @param element the element to be inserted
 * @return TRUE if the size of the linked list was changed by this function;
 *         FALSE otherwise
 */
bool linkedList_pushBack(linkedList_t *list, void *element);

/**
 * Adds an element at the beginning of a linked list.
 * @param list the linked list into which an element is to be inserted
 * @param element the element to be inserted
 * @return TRUE if the size of the linked list was changed by this function;
 *         FALSE otherwise
 */
bool linkedList_pushFront(linkedList_t *list, void *element);

/**
 * Removes an element from a linked list.
 * @param list the linked list from which to remove an element
 * @param element the element to be removed
 * @return TRUE if the size of the linked list was changed by this function;
 *         FALSE otherwise
 */
bool linkedList_remove(linkedList_t *list, void *element);

/*
 * linked list iterator functions
 */

/**
 * @ingroup collection
 * @example linkedListIterator_example.c
 */

/**
 * Constructs a new linked list iterator.
 * @param list the linked list to be iterated
 * @return a new linked list iterator, or NULL
 */
linkedListIterator_t *linkedListIterator_create(linkedList_t *list);

/**
 * Frees a linked list iterator.
 * @param iter the linked list iterator to be freed
 * @return none
 */
void linkedListIterator_free(linkedListIterator_t *iter);

/**
 * Returns whether a linked list iterator has more elements.
 * @param iter the linked list iterator to be tested
 * @return TRUE if there are more elements to be iterated;
 *         FALSE otherwise
 */
bool linkedListIterator_hasNext(linkedListIterator_t *iter);

/**
 * Returns the current element and advances the linked list iterator.
 * @param iter the linked list iterator
 * @return the current element, or NULL
 */
void *linkedListIterator_next(linkedListIterator_t *iter);

/**
 * Removes the last element returned by a linked list iterator.
 * @param iter the linked list iterator from which to remove an element
 * @return none
 */
void linkedListIterator_remove(linkedListIterator_t *iter);

/**
 * Removes a linked list entry from a linked list and updates the linked list
 * size.
 * @param list the linked list whose entry is to be unlinked
 * @param entry the entry to be removed
 * @param freeIt if the linked list entry element is to be freed
 * @return none
 */
void linkedListPrivate_removeEntry(linkedList_t *list,
  linkedListEntry_t *entry, bool freeIt);

#endif /* __LINKEDLIST_H__ */