/** @file psList.c
 *  @brief Support for doubly linked lists
 *  @ingroup LinkedList
 *
 *  @author Robert Lupton, Princeton University
 *  @author Robert Daniel DeSonia, MHPCC
 *
 *  @version $Revision: 1.34 $ $Name: not supported by cvs2svn $
 *  @date $Date: 2005-02-17 19:26:23 $
 *
 *  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 "psCollectionsErrors.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->lock)
    ;

    // remove the free function of iterators to avoid double removal from list
    psArray* iterators = list->iterators;
    for (int i = 0; i < iterators->n; i++) {
        p_psMemSetDeallocator(iterators->data[i], NULL);
    }

    psFree(list->iterators);

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

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

        ptr = next;
    }

    pthread_mutex_unlock(&list->lock)
    ;

    pthread_mutex_destroy(&list->lock)
    ;

}

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

    // remove this iterator from the parent list
    psArrayRemove(iter->list->iterators,iter);

}

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->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->size--;

    pthread_mutex_unlock(&list->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));

    p_psMemSetDeallocator(list, (psFreeFcn) listFree);

    list->size = 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->lock), NULL)
    ;

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

    return list;
}

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

    p_psMemSetDeallocator(iter, (psFreeFcn) listIteratorFree);

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

    // add to the list's array of iterators
    psArray* listIterators = list->iterators;
    int num = listIterators->n;
    if ( num >= listIterators->nalloc) {
        // need to resize the array to make more room for another iterator.
        list->iterators = psArrayRealloc(listIterators,listIterators->nalloc*2);
        listIterators = list->iterators;
    }
    listIterators->data[num] = iter;
    listIterators->n = num+1;

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

    return iter;
}

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

    psList* list = iterator->list;

    if (location == PS_LIST_TAIL) {
        iterator->cursor = list->tail;
        iterator->index = list->size - 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->size + location;
    }

    if (location < 0 || location >= (int)list->size) {
        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->size/2) { // closer to tail or head?
            cursor = list->tail;
            index = list->size - 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;
}

psBool psListAdd(psList* list, psS32 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->size) {
        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->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->size++;

    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->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->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->size++;

    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->lock)
    ;

    return true;
}

psBool psListRemove(psList* list,
                    psS32 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);
}

psBool 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, psS32 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->size-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(psList* restrict list)
{
    psListElem* ptr;
    psU32 n;
    psArray* restrict arr;

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

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

    arr->n = list->size;

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

    return arr;
}

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

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

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

    return list;
}

psList* psListSort(psList* list, psComparePtrFcn compare)
{
    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, compare);

    // 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;
}

