#if !defined(PS_LIST_H)
#define PS_LIST_H

/** @file psList.h
 *  @brief Support for doubly linked lists
 *
 *  @author Robert Lupton, Princeton University
 *  @author Robert Daniel DeSonia, MHPCC
 *
 *  @ingroup LinkedList
 *
 *  @version $Revision: 1.15 $ $Name: not supported by cvs2svn $
 *  @date $Date: 2004-09-09 02:23:27 $
 *
 *  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
 */

#include <pthread.h>                   // we need a mutex to make this stuff thread safe.
#include <stdbool.h>                   // we use the bool type.

#include "psCompare.h"
#include "psArray.h"

/** @addtogroup LinkedList
 *  @{
 */

/** Special values of index into list
 *
 *  This list of possible list position values should be contiguous non-positive values ending with
 *  PS_LIST_UNKNOWN.  Any value less-than-or-equal-to PS_LIST_UNKNOWN is considered a undefined position.
 *
 */
enum {
    PS_LIST_HEAD = 0,                  ///< at head
    PS_LIST_TAIL = -1,                 ///< at tail
    PS_LIST_PREVIOUS = -2,             ///< previous element
    PS_LIST_CURRENT = -3,              ///< current element
    PS_LIST_NEXT = -4,                 ///< next element
    PS_LIST_UNKNOWN = -5               ///< unknown position (should be last in enum list)
};

/** Doubly-linked list element */
typedef struct psListElem
{
    struct psListElem* prev;           ///< previous link in list
    struct psListElem* next;           ///< next link in list
    void *data;                        ///< real data item
}
psListElem;

/** The psList Linked list structure.  User should not allocate this struct
 *  directly; rather the psListAlloc should be used.
 *
 *  @see psListAlloc, psListFree
 */
typedef struct
{
    unsigned int size;                 ///< number of elements on list
    psListElem* head;                  ///< first element on list (may be NULL)
    psListElem* tail;                  ///< last element on list (may be NULL)
    psListElem* iter;                  ///< iteration cursor
    unsigned int iterIndex;            ///< the numeric position of the iteration cursor in the list
    pthread_mutex_t lock;              ///< mutex to lock a node during changes
}
psList;

/** Creates a psList linked list object.
 *
 *  @return psList* A new psList object.
 */
psList* psListAlloc(
    void *data
    ///< initial data item; may be NULL if no an empty psList is desired
)
;

/** Adds an element to a psList at position given.
 *
 *  @return psList* The psList with added data item.  If list parameter is
 *                      NULL, the return value will also be NULL.
 */
bool psListAdd(
    psList* restrict list,             ///< list to add to (if NULL, nothing is done)
    int location,                      ///< index, PS_LIST_HEAD, PS_LIST_TAIL, or numbered location.
    void *data                         ///< data item to add.  If NULL, list is not modified.
);

/** Remove an item from a list.  If location parameter is PS_LIST_UNKNOWN,
 *
 *  @return bool        TRUE if element is successfully removed, otherwise FALSE.
 */
bool psListRemove(
    psList* restrict list,
    ///< list to remove element from
    int location,
    ///< index of item, or PS_LIST_UNKNOWN, PS_LIST_NEXT, PS_LIST_PREV, or numbered location.
    void *data
    ///< if location is PS_LIST_UNKNOWN, data item to find and remove, otherwise this is ignored.
);

/** Retrieve an item from a list.
 *
 *  @return void*       the item corresponding to the location parameter.  If
 *                      location is invalid (e.g., a numbered index greater
 *                      than the list size or if the list is empty), a
 *                      NULL is returned.
 */
void *psListGet(
    psList* restrict list,             ///< list to retrieve element from
    int location                       ///< index number, or PS_LIST_NEXT, PS_LIST_PREV, PS_LIST_UNKNOWN
);

/** Set the iterator of the list to a given position.  If location is invalid the
 *  iterator position is not changed.
 *
 */
void psListSetIterator(
    psList* restrict list,             ///< list to retrieve element from
    int location                       ///< index number, PS_LIST_HEAD, or PS_LIST_TAIL
);

/** Get next element relative to the iterator.  This also moves the iterator to
 *  the next list position.
 *
 *  @return void*       the data item next on the list or NULL if the iterator
 *                      is already pointing to the last element or the list
 *                      parameter was NULL.
 */
void *psListGetNext(
    psList* restrict list              ///< list to retrieve element from
);

/** Get current element according to the psList's iterator cursor.  This does
 *  not move the iterator location.
 *
 *  @return void*       the data item cooresponding to current iterator
 *                      cursor position of the list, or NULL if either the
 *                      iterator is not valid or list parameter was NULL.
 */
void *psListGetCurrent(
    psList* restrict list              ///< list to retrieve element from
);

/** Get previous element relative to list's iterator. This also moves the
 *  iterator to the previous list position.
 *
 *  @return void*       the data item previous on the list or NULL if the iterator
 *                      is already pointing to the first element or the list
 *                      parameter was NULL.
 */
void *psListGetPrevious(
    psList* restrict list              ///< list to retrieve element from
);

/** Convert a linked list to an array
 *
 *  @return psArray* A new psArray populated with elements from the list,
 *                      or NULL if the given dlist parameter is NULL.
 */
psArray* psListToArray(
    psList* dlist                      ///< List to convert
);

/** Convert array to a doubly-linked list
 *
 *  @return psList* A new psList populated with elements formt the psArray,
 *                      or NULL is the given arr parameter is NULL.
 */
psList* psArrayToList(
    psArray* arr                       ///< vector to convert
);

/** Sort a list via a comparison function.
 *
 *  The comparison function must return an integer less than, equal to, or 
 *  greater than zero if the first argument is considered to be respectively 
 *  less than, equal to, or greater than the second. 
 *
 *  If two members compare as equal, their order in the sorted array is 
 *  undefined.
 *
 *  @return psList*     Sorted list.
 */
psList* psListSort(
    psList* list,                      ///< the list to sort
    psComparePtrFcn compare            ///< the comparison function
);

/// @} End of DataGroup Functions

#endif
