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

#include <stdlib.h>
#include <stdbool.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 ((void *)1)         // next iteration should return head
#define ITER_INIT_TAIL ((void *)2)         // next iteration should return tail

// private functions.
static psListElem* listGetIterator(psList* list);
static int listGetIteratorIndex(psList* list);
static void listSetIterator(psList* list, int where, bool lockList);
static void listFree(psList* list);

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

    p_psMemSetDeallocator(list, (psFreeFcn) listFree);

    list->size = 0;
    list->head = list->tail = NULL;
    list->iter = ITER_INIT_HEAD;
    list->iterIndex = PS_LIST_HEAD;

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

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

    return list;
}

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

    pthread_mutex_lock(&list->lock)
    ;

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

}

bool psListAdd(psList* list, int location, void *data)
{
    psListElem* position;
    psListElem* elem;
    int cursorIndex = 0;

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

    if (data == NULL) {
        return false;
    }

    if (location <= PS_LIST_UNKNOWN) {
        // / XXX What is the better way to communicate this failure to the caller?
        psLogMsg(__func__, PS_LOG_WARN, "The given insert location (%i) for psListAdd is invalid.", location);
        return false;
    }

    elem = psAlloc(sizeof(psListElem));

    pthread_mutex_lock(&list->lock)
    ;

    if (location > 0 && location > list->size) {
        psLogMsg(__func__, PS_LOG_WARN,
                 "Invalid index %d (only %d elements in psList); assuming tail.", location, list->size);
        location = PS_LIST_TAIL;
    }

    if (location == PS_LIST_TAIL || list->size == 0) {
        // insert the element at the end of the list
        elem->prev = list->tail;
        elem->next = NULL;

        if (list->tail != NULL) {
            list->tail->next = elem;
        }

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

        list->size++;
        list->iter = elem;
        list->iterIndex = list->size - 1;
    } else {
        // move ourselves to the given position
        listSetIterator(list, location, false);
        position = listGetIterator(list);
        cursorIndex = listGetIteratorIndex(list);

        if (position == NULL) {
            psError(__func__, "%s failed to move cursor to specified location (%d)", __func__, location);
            position = list->head;         // since we no list->size != 0, this must be non-NULL
        }
        // insert our new element in front of the given position
        elem->prev = position->prev;
        elem->next = position;
        position->prev = elem;

        if (elem->prev == NULL) {          // must be front of list
            list->head = elem;
        } else {
            elem->prev->next = elem;
        }

        list->size++;
        list->iter = elem;
        list->iterIndex = cursorIndex;
    }

    elem->data = psMemIncrRefCounter(data);

    pthread_mutex_unlock(&list->lock)
    ;

    return true;
}


/*
 * Remove an element from a list
 */
bool psListRemove(psList* list, int location, void *data)
{
    psListElem* elem = NULL;    // element to remove
    int cursorIndex = 0;

    if (list == NULL) {
        psError(__func__, "list parameter found to be NULL in %s", __func__);
        return false;
    }
    // get exclusive access to list so that other threads will not get in the way.
    pthread_mutex_lock(&list->lock)
    ;

    if (location == PS_LIST_UNKNOWN) {
        // search list for the data item.

        int i = 0;              // index

        for (psListElem* ptr = list->head; ptr != NULL; ptr = ptr->next) {
            if (ptr->data == data) {
                location = i;
                break;
            }
            i++;
        }

        if (location == PS_LIST_UNKNOWN) {
            psError(__func__, "Failed to find item in given psList.");
            pthread_mutex_unlock(&list->lock)
            ;
            return false;
        }
    }
    // position the list's cursor to the desired location
    listSetIterator(list, location, false);
    elem = listGetIterator(list);
    cursorIndex = listGetIteratorIndex(list);

    if (elem == NULL) {
        psError(__func__, "Couldn't position to given index (%d) to remove element from list.", location);
        pthread_mutex_unlock(&list->lock)
        ;
        return false;
    }

    list->size--;

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

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

        // removed tail, so iter should be the last element of list to keep it valid
        if (list->size > 0) {
            list->iter = list->tail;
            list->iterIndex = list->size - 1;
        } else {
            list->iter = ITER_INIT_TAIL;
        }
    } else {
        elem->next->prev = elem->prev;
        list->iter = elem->next;
        list->iterIndex = cursorIndex;
    }

    pthread_mutex_unlock(&list->lock)
    ;

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

    return true;
}

void psListSetIterator(psList* list, int where)
{
    listSetIterator(list, where, true);
}

static void listSetIterator(psList* list, int where, bool lockList)
{
    psListElem* cursor;
    int position;

    if (list == NULL) {
        psError(__func__, "Unexpected null pointer for psList parameter (%s:%d).", __FILE__, __LINE__);
        return;
    }

    if (where == PS_LIST_CURRENT) {
        return;
    }

    if (lockList) {
        pthread_mutex_lock(&list->lock)
        ;
        // don't want the list changing on us while we move about
    }

    if (where >= (int)list->size) {
        list->iter = NULL;
        if (lockList) {
            pthread_mutex_unlock(&list->lock)
            ;
        }
        return;
    }

    switch (where) {
    case PS_LIST_HEAD:
        list->iter = ITER_INIT_HEAD;
        break;

    case PS_LIST_TAIL:
        list->iter = ITER_INIT_TAIL;
        break;

    case PS_LIST_PREVIOUS:
        cursor = listGetIterator(list);
        position = listGetIteratorIndex(list);

        if (cursor != NULL) {
            list->iter = cursor->prev;
            list->iterIndex = position - 1;
        }
        break;

    case PS_LIST_NEXT:
        cursor = listGetIterator(list);
        position = listGetIteratorIndex(list);

        if (cursor != NULL) {
            list->iter = cursor->next;
            list->iterIndex = position + 1;
        }
        break;

    case PS_LIST_CURRENT:
        break;

    default:
        if (where <= PS_LIST_HEAD) {   // bascially same as PS_LIST_UNKNOWN above
            psError(__func__, "Can't move to an unknown position.  Not moving the iterator position.");
        } else {
            cursor = listGetIterator(list);
            if (cursor == NULL) {      // reset the iterator if it is invalid
                list->iter = ITER_INIT_HEAD;
                list->iterIndex = 0;
            }

            int position = listGetIteratorIndex(list);

            if (where < position) {
                int diff = position - where;

                for (int count = 0; count < diff; count++) {
                    listSetIterator(list, PS_LIST_PREVIOUS, false);
                }
            } else {
                int diff = where - position;

                for (int count = 0; count < diff; count++) {
                    listSetIterator(list, PS_LIST_NEXT, false);
                }
            }
        }
        break;
    }

    if (lockList) {
        pthread_mutex_unlock(&list->lock)
        ;
    }
}

psListElem* listGetIterator(psList* list)
{
    if (list == NULL) {
        return NULL;
    }

    if (list->iter == ITER_INIT_HEAD) {
        return list->head;
    } else if (list->iter == ITER_INIT_TAIL) {
        return list->tail;
    } else {
        return list->iter;
    }
}

int listGetIteratorIndex(psList* list)
{
    if (list->iter == ITER_INIT_HEAD) {
        return 0;
    } else if (list->iter == ITER_INIT_TAIL) {
        return list->size - 1;
    } else {
        return list->iterIndex;
    }
}

void *psListGet(psList* list, int location)
{
    psListElem* element;

    psListSetIterator(list, location);
    element = listGetIterator(list);

    if (element == NULL) {
        return NULL;
    } else {
        return element->data;
    }
}

/*
 * and now return the previous/next element of the list
 */
void *psListGetNext(psList* list)
{
    return psListGet(list, PS_LIST_NEXT);
}

void *psListGetPrevious(psList* list)
{
    return psListGet(list, PS_LIST_PREVIOUS);
}

void *psListGetCurrent(psList* list)
{
    return psListGet(list, PS_LIST_CURRENT);
}

/*
 * Convert a psList to/from a psVoidPtrArray
 */
psArray* psListToArray(psList* restrict list)
{
    psListElem* ptr;
    unsigned int 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 (int i = 0; i < n; i++) {
        arr->data[i] = psMemIncrRefCounter(ptr->data);
        ptr = ptr->next;
    }

    return arr;
}

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

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

    list = psListAlloc(NULL);
    n = arr->n;
    for (int 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);
    psFree(list);

    arr = psArraySort(arr, compare);

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

    return list;
}
