/* List.c: generic doubly linked linear lists */

#include "DList.h"
#include "private.h"
#include "pools.h"

#ifndef NOPOOLS
static POOL *dlistPool = (POOL *)NULL;
#define NEWDLIST()  	(DLIST *)NewPoolCell(sizeof(DLIST), 0, "GDT DList cells", &dlistPool)
#define DISPOSEDLIST(ptr) Dispose((unsigned char *)(ptr), &dlistPool)
#else /*NOPOOLS*/
#define NEWDLIST()	(DLIST *)Alloc(sizeof(DLIST))
#define DISPOSEDLIST(ptr) Free((char *)ptr, sizeof(DLIST))
#endif /*NOPOOLS*/


#ifndef NODLISTMACROS
void *__pdlistel__;	/* wordt gebruikt in de DlistNext() macro */
#endif /*NODLISTMACROS*/

#ifdef NODLISTMACROS
/* creates an empty list */
DLIST *DListCreate(void)
{
  return (DLIST *)NULL;
}
#endif /*NODLISTMACROS*/

/* prepends the element to the list, returns the modified list */
DLIST *DListAdd(DLIST *dlist, void *pelement)
{
  DLIST *newdlist;

  /* weiger NULL-pointers in de lijst */
  if (pelement == (void *)NULL)
    return dlist;

  newdlist = NEWDLIST();
  newdlist->pelement = pelement;
  newdlist->next = dlist;
  newdlist->prev = (DLIST *)NULL;
  
  if (dlist)
    dlist->prev = newdlist;
  
  return newdlist;
}

/* counts the number of elements in the list */
int DListCount(DLIST *dlist)
{
  int count = 0;
  
  while (dlist) {
    count++;
    dlist = dlist->next;
  }
  
  return count;
}

/* returns the index-th element if there is one, or NULL if there are less then
 * 'index' elements. index counts from 0 */
void *DListGet(DLIST *dlist, int index)
{
  while (dlist && index > 0) {
    dlist = dlist->next;
    index--;
  }
  
  if (!dlist)
    return (void *)NULL;
  else
    return dlist->pelement;
}

#ifdef NODLISTMACROS
void *DListNext(DLIST **dlist)
{
  void *pelement = (void *)NULL;
  
  if (*dlist) {
    pelement = (*dlist)->pelement;
    *dlist = (*dlist)->next;
  } else
    pelement = (void *)NULL;

  return pelement;
}
#endif /*NODLISTMACROS*/

/* merges the lists: dlist2 comes before dlist1 in reverse order. Modified dlist1 
 * is returned. */
DLIST *DListMerge(DLIST *dlist1, DLIST *dlist2)
{
  void *pelement = (void *)NULL;
  
  while ((pelement = DListNext(&dlist2)))
    dlist1 = DListAdd(dlist1, pelement);
  
  return dlist1;
}

/* duplicates the list. The elements are not duplicated: a pointer to them is copied. */
DLIST *DListDuplicate(DLIST *dlist)
{
  DLIST *newdlist = (DLIST *)NULL;
  void *pelement = (void *)NULL;
  
  while ((pelement = DListNext(&dlist)))
    newdlist = DListAdd(newdlist, pelement);
  
  return newdlist;
}

/* removes p from the list. */
DLIST *DListRemoveCell(DLIST *dlist, DLIST *p)
{
  if (p == dlist) {
    dlist = dlist->next;
    dlist->prev = (DLIST *)NULL;
    DISPOSEDLIST(p);
  } else {
    if (p->prev) p->prev->next = p->next;
    if (p->next) p->next->prev = p->prev;
    DISPOSEDLIST(p);
  }

  return dlist;
}

/* same as above but firsts checks if the element is really in the list
 * and so on ... */
DLIST *DListRemove(DLIST *dlist, void *pelement)
{
  DLIST *p;

  /* als de lijst ledig is */
  if (!dlist) {
    GdtError("DlistRemove", "attempt to remove an element from an empty dlist");
    return dlist;	/* voor het geval we ooit besluiten tolerant te zijn */
  }
  
  /* zoek het element in de lijst */
  for (p = dlist; p && p->pelement != pelement; p = p->next) {}

  /* als p de NULL pointer is komt het te verwijderen element niet in de lijst
   * voor: fout */
  if (!p) {
    GdtError("DlistRemove", "attempt to remove a nonexisting element from a dlist");
    return dlist;
  }

  /* in het andere geval is p een wijzer naar de lijst-cel die eruit gehaald moet
   * worden */
  return DListRemoveCell(dlist, p);
}

/* simple insertion sort */
DLIST *DListSort(DLIST *list, int (*compare)(void *, void *))
{
  DLIST *p, *next, *q;

  if (!list)
    return list;

  p = list->next;	/* second element in list */
  while (p) {
    next = p->next;

    /* find first element q equal or larger than p */
    q=list;
    while (q!=p && compare(p->pelement, q->pelement) >= 0) {
      q=q->next;
    }

    if (q!=p) {
      /* detach p */
      p->prev->next = p->next;
      if (p->next) p->next->prev = p->prev;

      /* insert p before q */
      p->prev = q->prev;
      p->next = q;
      if (p->prev) p->prev->next = p; else list = p;
      p->next->prev = p;
    }

    p = next;
  }

  return list;
}

/* The use of "ForAllInDList" is highly recommended instead of these old iterators! */

#ifdef NODLISTMACROS
void DListIterate(DLIST *dlist, void (*proc)(void *))
{
  void *pelement;
  
  while (dlist) {
    pelement = dlist->pelement;
    dlist = dlist->next;
    proc(pelement);
  }		
}
#endif /*NODLISTMACROS*/

#ifdef NODLISTMACROS
void DListIterate1A(DLIST *dlist, void (*proc)(void *, void *), void *extra)
{
  void *pelement;
  
  while (dlist) {
    pelement = dlist->pelement;
    dlist = dlist->next;
    proc(pelement, extra);
  }		
}
#endif /*NODLISTMACROS*/

#ifdef NODLISTMACROS
void DListIterate1B(DLIST *dlist, void (*proc)(void *, void *), void *extra)
{
  void *pelement;
  
  while (dlist) {
    pelement = dlist->pelement;
    dlist = dlist->next;
    proc(extra, pelement);
  }		
}
#endif /*NODLISTMACROS*/

/* destroys the list, but does not dispose of the elements. */
void DListDestroy(DLIST *dlist)
{
  DLIST *p;
  
  while (dlist) {
    p = dlist->next;
    DISPOSEDLIST(dlist);
    dlist = p;
  }
}