/** @file psList.c
 *  @brief Support for doubly linked lists
 *  @ingroup LinkedList
 *
 *  @author Robert Lupton, Princeton University
 *  @author Robert Daniel DeSonia, MHPCC
 *
 *  @version $Revision: 1.44 $ $Name: not supported by cvs2svn $
 *  @date $Date: 2005-10-01 02:22:15 $
 *
 *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
 */

#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>                       // we need a mutex to make this stuff thread safe.

#include "psError.h"
#include "psAbort.h"
#include "psMemory.h"
#include "psList.h"
#include "psTrace.h"
#include "psLogMsg.h"

#include "psErrorText.h"

#define ITER_INIT_HEAD ((psPtr )1)         // next iteration should return head
#define ITER_INIT_TAIL ((psPtr )2)         // next iteration should return tail

// private functions.
static void listFree(psList* list);
static void listIteratorFree(psListIterator* iter);
static psBool listIteratorRemove(psListIterator* iterator);

static void listFree(psList* list)
{
    if (list == NULL) {
        return;
    }

    pthread_mutex_lock(&list->p_lock);

    // remove the associated iterators -- any references are invalid once psList is freed.
    psArray* iterators = list->iterators;
    // ONLY orphan the iterators if the list iterators are about to be destroyed
    // a case where this is not the case is in psListSort.
    if (psMemGetRefCounter(iterators)  < 2) {
        for (int i = 0; i < iterators->n; i++) {
            // orphan iterators first to avoid any callbacks to dying list
            ((psListIterator*)iterators->data[i])->list = NULL;
            // remove all external references
            psMemSetRefCounter(iterators->data[i], 1);
        }
    }
    psFree(iterators);

    for (psListElem* ptr = list->head; ptr != NULL;) {
        psListElem* next = ptr->next;

        psFree(ptr->data);
        psFree(ptr);

        ptr = next;
    }

    pthread_mutex_unlock(&list->p_lock);

    pthread_mutex_destroy(&list->p_lock);

}

static void listIteratorFree(psListIterator* iter)
{
    if (iter == NULL) {
        return;
    }

    // remove this iterator from the parent list
    if (iter->list != NULL) {
        psArray* iters = iter->list->iterators;
        for (int lcv = 0; lcv < iters->n; lcv++) {
            if (iters->data[lcv] == iter) {
                // following is done to match SDRS.
                iters->data[lcv] = iters->data[iters->n-1];
                iters->n--;
                break;
            }
        }
    }
}

static psBool listIteratorRemove(psListIterator* iterator)
{
    if (iterator == NULL || iterator->cursor == NULL) {
        return false;
    }

    psListElem* elem = iterator->cursor;
    psList* list = iterator->list;
    int index = iterator->index;

    pthread_mutex_lock(&list->p_lock);

    if (elem == list->head) {        // head of list?
        list->head = elem->next;
    } else {
        elem->prev->next = elem->next;
    }

    if (elem == list->tail) {        // tail of list?
        list->tail = elem->prev;
    } else {
        elem->next->prev = elem->prev;
    }

    psArray* iterators = list->iterators;
    for (int i = 0; i < iterators->n; i++) {
        psListIterator* iter = (psListIterator*) iterators->data[i];
        if (iter->cursor == elem) {
            iter->cursor = NULL;
        } else if (iter->index > index && iter->index > 0) {
            iter->index--;
        }
    }

    list->n--;

    pthread_mutex_unlock(&list->p_lock)
    ;

    // OK, delete orphaned list element and its data
    psFree(elem->data);
    psFree(elem);

    return true;
}

psList* psListAlloc(psPtr data)
{
    psList* list = psAlloc(sizeof(psList));

    psMemSetDeallocator(list, (psFreeFunc) listFree);

    list->n = 0;
    list->head = list->tail = NULL;
    list->iterators = psArrayAlloc(16);
    list->iterators->n = 0;

    // create a default iterator
    psListIteratorAlloc(list,PS_LIST_HEAD,true);

    pthread_mutex_init(&(list->p_lock), NULL);

    if (data != NULL) {
        psListAdd(list, PS_LIST_TAIL, data);
    }

    return list;
}

bool psMemCheckList(psPtr ptr)
{
    return ( psMemGetDeallocator(ptr) == (psFreeFunc)listFree );
}



psListIterator* psListIteratorAlloc(psList* list, long location, bool mutable)
{
    psListIterator* iter = psAlloc(sizeof(psListIterator));

    psMemSetDeallocator(iter, (psFreeFunc) listIteratorFree);

    // initialize the attributes
    iter->list = list;
    iter->cursor = NULL;
    iter->index = 0;
    iter->offEnd = false;
    iter->mutable = mutable;

    // associate the iterator with the list
    list->iterators = psArrayAdd(list->iterators,0,iter);
    // don't want the list's array of iterators to hold a true reference
    psMemDecrRefCounter(iter);

    if (! psListIteratorSet(iter,location)) {
        psFree(iter);
        return NULL;
    }

    return iter;
}

bool psListIteratorSet(psListIterator* iterator,
                       long location)
{
    if (iterator == NULL) {
        return false;
    }

    psList* list = iterator->list;

    if (location == PS_LIST_TAIL) {
        iterator->cursor = list->tail;
        iterator->index = list->n - 1;
        iterator->offEnd = false;
        return true;
    }

    if (location == PS_LIST_HEAD) {
        iterator->cursor = list->head;
        iterator->index = 0;
        iterator->offEnd = false;
        return true;
    }

    if (location < 0) {
        location = list->n + location;
    }

    if (location < 0 || location >= (int)list->n) {
        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
                PS_ERRORTEXT_psList_LOCATION_INVALID,
                location);
        return false;
    }

    psListElem* cursor = iterator->cursor;
    int index = iterator->index;
    if (cursor == NULL) {      // set the cursor to the head if it is NULL
        if (location > list->n/2) { // closer to tail or head?
            cursor = list->tail;
            index = list->n - 1;
        } else {
            cursor = list->head;
            index = 0;
        }
    }

    if (location < index) {
        psS32 diff = index - location;

        for (psS32 count = 0; count < diff; count++) {
            cursor = cursor->prev; // shouldn't need to check for NULL
        }
    } else {
        psS32 diff = location - index;

        for (psS32 count = 0; count < diff; count++) {
            cursor = cursor->next; // shouldn't need to check for NULL
        }
    }
    iterator->cursor = cursor;
    iterator->index = location;
    iterator->offEnd = false;

    return true;
}

bool psListAdd(psList* list, long location, psPtr data)
{

    if (list == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_LIST_NULL);
        return false;
    }

    if (data == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_DATA_NULL);
        return false;
    }

    if (location > 0 && location >= (int)list->n) {
        psLogMsg(__func__,PS_LOG_WARN,
                 "Specified location, %d, is beyond the end of the list.  "
                 "Adding data item to tail.",
                 location);
        location = PS_LIST_TAIL;
    }

    // move ourselves to the given position
    if (! psListIteratorSet(list->iterators->data[0],location)) {
        return false;
    }

    if (location == PS_LIST_TAIL) {
        // insert the element at the end of the list
        return psListAddAfter(list->iterators->data[0],data);
    } else {
        return psListAddBefore(list->iterators->data[0],data);
    }
}

bool psListAddAfter(psListIterator* iterator, void* data)
{
    if (data == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_DATA_NULL);
        return false;
    }

    if (iterator == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_ITERATOR_NULL);
        return false;
    }

    // Check if the list pointed by the iterator can be changed
    if (!iterator->mutable) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_ITERATOR_NONMUTABLE);
        return false;
    }

    psListElem* cursor = iterator->cursor;
    psList* list = iterator->list;

    if (cursor == NULL && list->head != NULL) {
        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
                PS_ERRORTEXT_psList_ITERATOR_INVALID);
        return false;
    }

    psListElem* elem = psAlloc(sizeof(psListElem));

    pthread_mutex_lock(&list->p_lock);

    // set the new list element's attributes
    if (cursor == NULL) { // must be an empty list
        elem->prev = NULL;
        elem->next = NULL;
        list->head = elem;
        list->tail = elem;
    } else {
        elem->prev = cursor;
        elem->next = cursor->next;
        cursor->next = elem;
        if (elem->next == NULL) {
            list->tail = elem;
        } else {
            elem->next->prev = elem;
        }
    }

    elem->data = psMemIncrRefCounter(data);

    list->n++;

    if (cursor == list->tail) {
        list->tail = elem;
    }

    psArray* iterators = list->iterators;
    int index = iterator->index;
    for (int i = 0; i < iterators->n; i++) {
        psListIterator* iter = (psListIterator*) iterators->data[i];
        if (iter->index > index) {
            iter->index++;
        }
    }

    pthread_mutex_unlock(&list->p_lock);

    return true;
}

bool psListAddBefore(psListIterator* iterator, void* data)
{
    if (data == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_DATA_NULL);
        return false;
    }

    if (iterator == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_ITERATOR_NULL);
        return false;
    }

    // Check if the list pointed by the iterator can be changed
    if (!iterator->mutable) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_ITERATOR_NONMUTABLE);
        return false;
    }

    psListElem* cursor = iterator->cursor;
    psList* list = iterator->list;

    if (cursor == NULL && list->head != NULL) {
        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
                PS_ERRORTEXT_psList_ITERATOR_INVALID);
        return false;
    }

    psListElem* elem = psAlloc(sizeof(psListElem));

    pthread_mutex_lock(&list->p_lock);

    // set the new list element's attributes
    if (cursor == NULL) { // empty list.
        elem->prev = NULL;
        elem->next = NULL;
        list->head = elem;
        list->tail = elem;
    } else {
        elem->prev = cursor->prev;
        elem->next = cursor;
        cursor->prev = elem;
        if (elem->prev == NULL) {
            list->head = elem;
        } else {
            elem->prev->next = elem;
        }
    }

    elem->data = psMemIncrRefCounter(data);

    list->n++;

    if (cursor == list->head) {
        list->head = elem;
    }

    psArray* iterators = list->iterators;
    int index = iterator->index;
    for (int i = 0; i < iterators->n; i++) {
        psListIterator* iter = (psListIterator*) iterators->data[i];
        if (iter->index >= index) {
            iter->index++;
        }
    }

    pthread_mutex_unlock(&list->p_lock);

    return true;
}

bool psListRemove(psList* list,
                  long location)
{
    if (list == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_LIST_NULL);
        return false;
    }

    // move ourselves to the given position
    psListIterator* defaultIterator = list->iterators->data[0];
    if (! psListIteratorSet(defaultIterator,location)) {
        return false;
    }

    return listIteratorRemove(defaultIterator);
}

bool psListRemoveData(psList* list,
                      psPtr data)
{
    if (list == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_LIST_NULL);
        return false;
    }

    if (data == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_DATA_NULL);
        return false;
    }

    psListElem* elem = list->head;
    int index = 0;
    while (elem != NULL && elem->data != data) {
        elem = elem->next;
        index++;
    }
    if (elem == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_DATA_NOT_FOUND);
        return false;
    }

    psListIterator* iterator = (psListIterator*)list->iterators->data[0];
    iterator->index = index;
    iterator->cursor = elem;

    return listIteratorRemove(iterator);
}

psPtr psListGet(psList* list, long location)
{
    if (list == NULL) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psList_LIST_NULL);
        return NULL;
    }

    if (list->head == NULL) { // list empty?
        return NULL;
    }

    psListIterator* iterator = list->iterators->data[0];

    if (! psListIteratorSet(iterator,location)) {
        psError(PS_ERR_BAD_PARAMETER_VALUE, true,
                PS_ERRORTEXT_psList_LOCATION_INVALID,
                location);
        return NULL;
    }

    return iterator->cursor->data;
}

/*
 * and now return the previous/next element of the list
 */
psPtr psListGetAndIncrement(psListIterator* iterator)
{
    if (iterator == NULL ) {
        return NULL;
    }
    if (( iterator->cursor == NULL) && (iterator->offEnd)) {
        return NULL;
    }
    if ( (iterator->cursor == NULL) && (!iterator->offEnd)) {
        iterator->cursor = iterator->list->head;
        iterator->index = 0;
        return NULL;
    }

    psPtr data = iterator->cursor->data;

    iterator->cursor = iterator->cursor->next;
    iterator->index++;
    if (iterator->cursor == NULL) {
        iterator->offEnd = true;
    }

    return data;
}

psPtr psListGetAndDecrement(psListIterator* iterator)
{
    if (iterator == NULL ) {
        return NULL;
    }
    if ((iterator->cursor == NULL) && (!iterator->offEnd))  {
        psLogMsg(__func__,PS_LOG_WARN,"Attempt to get previous with itertator cursor NULL and offEnd false");
        return NULL;
    }
    if ( (iterator->cursor == NULL) && (iterator->offEnd) ) {
        iterator->cursor = iterator->list->tail;
        iterator->index = iterator->list->n-1;
        iterator->offEnd = false;
        return NULL;
    }

    psPtr data = iterator->cursor->data;

    iterator->cursor = iterator->cursor->prev;
    iterator->index--;

    return data;
}

/*
 * Convert a psList to/from a psVoidPtrArray
 */
psArray* psListToArray(const psList* restrict list)
{
    psListElem* ptr;
    psU32 n;
    psArray* restrict arr;

    if (list == NULL) {
        return NULL;
    }

    if (list->n > 0) {
        arr = psArrayAlloc(list->n);
    } else {
        arr = psArrayAlloc(1);
    }

    arr->n = list->n;

    ptr = list->head;
    n = list->n;
    for (psS32 i = 0; i < n; i++) {
        arr->data[i] = psMemIncrRefCounter(ptr->data);
        ptr = ptr->next;
    }

    return arr;
}

psList* psArrayToList(const psArray* array)
{
    psU32 n;
    psList* list;               // list of elements

    if (array == NULL) {
        return NULL;
    }

    list = psListAlloc(NULL);
    n = array->n;
    for (psS32 i = 0; i < n; i++) {
        psListAdd(list, PS_LIST_TAIL, array->data[i]);
    }

    return list;
}

psList* psListSort(psList* list, psComparePtrFunc func)
{
    psArray* arr;

    if (list == NULL) {
        return NULL;
    }
    // convert to indexable vector for use by qsort.
    arr = psListToArray(list);
    psArray* iterators = psMemIncrRefCounter(list->iterators);
    psFree(list);

    arr = psArraySort(arr, func);

    // convert back to linked list
    list = psArrayToList(arr);
    psFree(list->iterators);
    list->iterators = iterators;
    psFree(arr);

    // sorting should invalidate all iterator positions.
    for (int i = 0; i < iterators->n; i++) {
        ((psListIterator*)iterators->data[i])->cursor = NULL;
    }

    return list;
}

