/*
 * Minimal support for doubly linked lists
 */
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "psLib.h"

static psDlistElem *dlistElemAlloc(void)
{
    return(psAlloc(sizeof(psDlistElem)));
}

static void dlistElemFree(psDlistElem *elem)
{
    psFree(elem);
}

/*****************************************************************************/

psDlist *psDlistAlloc(void *data)	// initial data item; may be NULL
{
    psDlist *list = psAlloc(sizeof(psDlist));

    list->n = 0;
    list->head = list->tail = NULL;
    list->iter = NULL;
    if (data != NULL) {
	psDlistAdd(list, data, PS_DLIST_TAIL);
    }

    return list;
}

void psDlistFree(psDlist *list,		// list to destroy
		 void (*elemFree)(void *)) // destructor for data on list
{
    if (list == NULL) {
	return;
    }

    psDlistElem *ptr = list->head;
    while (ptr != NULL) {
	psDlistElem *next = ptr->next;

	if (elemFree == NULL) {
	    psMemDecrRefCounter(ptr->data);
	} else {
	    elemFree(psMemDecrRefCounter(ptr->data));
	}
	dlistElemFree(ptr);
	
	ptr = next;
    }

    psFree(list);
}

/*****************************************************************************/
/*
 * Add an element to a list
 */
psDlist *psDlistAdd(psDlist *list,	// list to add to; may be NULL
		    void *data,		// data to add
		    int where)		// where to add data. PS_DLIST_HEAD,
					// PS_DLIST_TAIL, or an integer
{
    psDlistElem *elem = dlistElemAlloc();

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

    if (where > list->n) {		// XXX need better diagnostic here
	fprintf(stderr, "Invalid index %d (only %d elements)\n",
		where, list->n);
	dlistElemFree(elem);		// cleanup
	
	return list;
    }

    if (where == PS_DLIST_HEAD) {	// easy
	elem->prev = NULL;
	elem->next = list->head;
	elem->data = psMemIncrRefCounter(data);

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

	list->head = elem;
	if (list->tail == NULL) {
	    list->tail = elem;
	}
	list->n++;
    } else if (where == PS_DLIST_TAIL) { // also easy
	elem->prev = list->tail;
	elem->next = NULL;
	elem->data = psMemIncrRefCounter(data);

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

	list->tail = elem;
	if (list->head == NULL) {
	    list->head = elem;
	}
	list->n++;
    } else {				// XXX
	fprintf(stderr, "Insertion into psDlists is not yet supported\n");
	return psDlistAdd(list, data, PS_DLIST_TAIL);
    }

    return list;
}

/*****************************************************************************/

psDlist *psDlistAppend(psDlist *list,	// list to add to; may be NULL
		       void *data)	// data to add at end
{
    return psDlistAdd(list, data, PS_DLIST_TAIL);
}

/*****************************************************************************/
/*
 * Remove an element from a list
 */
void *psDlistRemove(psDlist *list,	// list to remove element from
		    void *data,		// data item to remove (or NULL)
		    int which)		// index of item, if known.
					// PS_DLIST_UNKNOWN, or PS_DLIST_HEAD,
					// or PS_DLIST_TAIL
{
    psDlistElem *elem = NULL;		// element to remove
    assert (list != NULL);

    if (data != NULL) {
	assert (which == PS_DLIST_UNKNOWN);

	int i = 0;			// index
	for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) {
	    if (ptr->data == data) {
		return psDlistRemove(list, NULL, i);
	    }
	}

	psTrace("utils.dlist.remove", 5, "Failed to find 0x%x on psDlist 0x%x", data, list);
	
	return NULL;
    }

    if (which == PS_DLIST_HEAD || which == 0) {
	if (list->head == NULL) {
	    return NULL;
	} else {
	    elem = list->head;
	    
	    if (list->head->next != NULL) {
		list->head->next->prev = NULL;
	    }
	    list->head = list->head->next;
	    list->n--;

	    if (list->head == NULL) {
		list->tail = NULL;
	    }
	}
    } else if (which == PS_DLIST_TAIL || which == list->n - 1) {
	if (list->tail == NULL) {
	    return NULL;
	} else {
	    elem = list->tail;
	    if (list->tail->prev != NULL) {
		list->tail->prev->next = NULL;
	    }
	    list->tail = list->tail->prev;
	    list->n--;

	    if (list->tail == NULL) {
		list->head = NULL;
	    }
	}
    } else if (which != PS_DLIST_UNKNOWN) { // an index in the middle of the list
	assert (which != 0 && which != list->n - 1);
	
	if (which < 0 || which >= list->n) { // out of bounds
	    psError(__func__, PS_ERR_BAD_INDEX, 1, "Index %d is not in range [0..%d] for list 0x%x", which, list->n, list);
	    return NULL;
	}
	
	int i = 0;			// index
	for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) {
	    if (i == which) {
		ptr->prev->next = ptr->next;
		ptr->next->prev = ptr->prev;

		elem = ptr;		
	    }
	}
    }
    /*
     * OK, delete list element and return the data
     */
    assert (elem != NULL);
    data = elem->data;
    dlistElemFree(elem);

    return psMemDecrRefCounter(data);
}

/*****************************************************************************/
/*
 * Retrieve an element from the list, or iterate over list.
 *
 * If which is psDlist{Next,Prev} return the next/previous
 * data and move the iteration cursor 
 *
 * If which is psDlist{Head,Tail} initialise the iteration pointer
 * and return the head/tail
 *
 * Otherwise, return the desired element
 */
#define ITER_INIT_HEAD ((void *)1)	// next iteration should return head
#define ITER_INIT_TAIL ((void *)2)	// next iteration should return tail

void *psDlistGet(
    const psDlist *list,		// list to retrieve element from
    int which)				// index of item, or PS_DLIST_NEXT,
					// or PS_DLIST_PREV
{
    assert (list != NULL);

    switch (which) {
      case PS_DLIST_HEAD:		// easy
	((psDlist *)list)->iter = ITER_INIT_HEAD;
	return (list->head == NULL) ? NULL : list->head->data;
      case PS_DLIST_TAIL:		// also easy
	((psDlist *)list)->iter = ITER_INIT_TAIL;
	return (list->tail == NULL) ? NULL : list->tail->data;
      case PS_DLIST_PREV:		// use iterator
      case PS_DLIST_NEXT:
	if (list->iter == NULL) {
	    return NULL;
	} else if (list->iter == ITER_INIT_HEAD) {
	    ((psDlist *)list)->iter = list->head;
	} else if (list->iter == ITER_INIT_TAIL) {
	    ((psDlist *)list)->iter = list->tail;
	} else if (which == PS_DLIST_PREV) {
	    ((psDlist *)list)->iter = list->iter->prev;
	} else if (which == PS_DLIST_NEXT) {
	    ((psDlist *)list)->iter = list->iter->next;
	} else {
	    fprintf(stderr,"You cannot get here\n");
	    abort();
	}

	if (list->iter == NULL) {
	    return NULL;
	}
	return list->iter->data;	// XXX what if data is NULL?

	break;
      default:				// XXX
	fprintf(stderr,
		"Retrieval from psDlists by index is not yet supported\n");
	return NULL;
    }
}

/*****************************************************************************/
/*
 * Some wrappers for those iteration calls using psDlistGet.
 *
 * First a call to set the iteration pointer to the head of the list
 */
void psDlistSetIterator(psDlist *list,	// the list in question
			int where,	// where on the list should I start?
			int which)	// @notused@ the desired iterator
{
    if (where != PS_DLIST_HEAD && where != PS_DLIST_TAIL) {
	psError(__func__, PS_ERR_UNKNOWN, 1, "Invalid where argument: %d; assuming PS_DLIST_HEAD", where);
	where = PS_DLIST_HEAD;
    }
    
    psDlistGet(list, where);	// initialise iterator at head/tail
}

/*
 * and now return the previous/next element of the list
 */
void *psDlistGetNext(psDlist *list,	// the list in question
		     int which)		// @notused@ the desired iterator
{
    return psDlistGet(list, PS_DLIST_NEXT);
}

void *psDlistGetPrev(psDlist *list,	// the list in question
		     int which)		// @notused@ the desired iterator
{
    return psDlistGet(list, PS_DLIST_PREV);
}

/*****************************************************************************/
/*
 * Convert a psDlist to/from a psVoidPtrArray
 */
psVector *psDlistToArray(psDlist *restrict dlist)
{
    if (dlist == NULL) {
	return NULL;
    }
    
    psVector *restrict arr = psVectorAlloc(dlist->n, PS_TYPE_OTHER);

    psDlistElem *ptr = dlist->head;
    for (int i = 0, n = dlist->n; i < n; i++) {
	arr->data.V[i] = ptr->data;
	ptr->data = NULL;
	ptr = ptr->next;
    }

    psDlistFree(dlist, NULL);

    return arr;    
}

psDlist *psArrayToDlist(psVector *arr)
{
    psDlist *list = psDlistAlloc(NULL);	// list of elements

    assert (arr != NULL);
    if (arr->n > 0) {
       assert (arr->type.dimen == PS_DIMEN_VECTOR && arr->type.type == PS_TYPE_OTHER);
    }
    
    for (int i = 0, n = arr->n; i < n; i++) {
	psDlistAppend(list,
		      psMemDecrRefCounter(arr->data.V[i])); // it\'s already Incr
	arr->data.V[i] = NULL;
    }

    psVectorFree(arr, NULL);

    return list;
}
