/* List.c: generic linear lists */

#include "List.h"
#include "private.h"
#include "pools.h"

#ifndef NOPOOLS
static POOL *listPool = (POOL *)NULL;
#define NEWLIST()  	(LIST *)NewPoolCell(sizeof(LIST), 0, "GDT list cells", &listPool)
#define DISPOSELIST(ptr) Dispose((unsigned char *)(ptr), &listPool)
#else /*NOPOOLS*/
#define NEWLIST()	(LIST *)Alloc(sizeof(LIST))
#define DISPOSELIST(ptr) Free((char *)ptr, sizeof(LIST))
#endif /*NOPOOLS*/


#ifndef NOLISTMACROS
void *__plistel__;	/* wordt gebruikt in de ListNext() macro */
#endif /*NOLISTMACROS*/

#ifdef NOLISTMACROS
/* creeert een lege lijst */
LIST *ListCreate(void)
{
	return (LIST *)NULL;
}
#endif /*NOLISTMACROS*/

/* voegt het element vooraan aan de lijst toe, geeft de nieuwe wijzer naar 
 * de lijst terug */
LIST *ListAdd(LIST *list, void *pelement)
{
	LIST *newlist;

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

	newlist = NEWLIST();
	newlist->pelement = pelement;
	newlist->next = list;

	return newlist;
}

/* telt het aantal elementen in de lijst */
int ListCount(LIST *list)
{
	int count = 0;

	while (list) {
		count++;
		list = list->next;
	}

	return count;
}

/* geeft het index-ste element uit de lijst terug of NULL als er
 * geen index elementen in de lijst zijn. index telt vanaf 0. */
void *ListGet(LIST *list, int index)
{
	while (list && index > 0) {
		list = list->next;
		index--;
	}

	if (!list)
		return (void *)NULL;
	else
		return list->pelement;
}

#ifdef NOLISTMACROS
/* het eerste argument is het adres van een LIST *. 
 * Aanvankelijk moet deze LIST * naar het begin van een lijst wijzen.
 * Bij herhaaldelijke oproepen zal de lijst doorlopen worden.
 * De functie geeft bij herhaaldelijk oproepen een na een alle
 * elementen van de lijst terug. Indien de lijst doorlopen is,
 * wordt een NULL wijzer teruggegeven */
void *ListNext(LIST **list)
{
	void *pelement = (void *)NULL;

	if (*list) {
		pelement = (*list)->pelement;
		*list = (*list)->next;
	} else
		pelement = (void *)NULL;

	return pelement;
}
#endif /*NOLISTMACROS*/

/* voegt twee lijsten samen: de elementen van lijst list2 komen voor de elementen van 
 * lijst list1. Een wijzer naar de verlengde lijst list1 wordt teruggegeven. */
LIST *ListMerge(LIST *list1, LIST *list2)
{
	void *pelement = (void *)NULL;

	while ((pelement = ListNext(&list2)))
		list1 = ListAdd(list1, pelement);

	return list1;
}

/* dupliceert een lijst: de elementen zelf worden niet gedupliceerd */
LIST *ListDuplicate(LIST *list)
{
	LIST *newlist = (LIST *)NULL;
	void *pelement = (void *)NULL;

	while ((pelement = ListNext(&list)))
		newlist = ListAdd(newlist, pelement);

	return newlist;
}

/* verwijdert een element uit de lijst. Geeft een pointer naar de gewijzigde 
 * lijst terug */
LIST *ListRemove(LIST *list, void *pelement)
{
	LIST *p, *q;

/* als de lijst ledig is */
	if (!list) {
		GdtError("ListRemove", "attempt to remove an element from an empty list");
		return list;	/* voor het geval we ooit besluiten tolerant te zijn */
	}

/* als het eerste element verwijderd moet worden */
	if (pelement == list->pelement) {
		p = list->next;
		DISPOSELIST(list);
		return p;
	}

/* chasing pointers: */
	q = list;
	p = list->next;
	while (p && p->pelement != pelement) {
		q = p;
		p = p->next;
	}

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

/* in het andere geval is p een wijzer naar de lijst-cel die eruit gehaald moet
 * worden */
	else {
		q->next = p->next;
		DISPOSELIST(p);
	}

/* geef een (ongewijzigde) wijzer naar de gewijzigde lijst terug */
	return list;
}

/* Iterates over the list, conditionally removing elements. Elements are
 * removed if the routine 'func' returns nonzero. They are kept in the list
 * if the routine returns zero. 'func' is reponsible for disposing memory
 * pointed to from the list if an element needs to be deleted as
 * this routine only disposes of the LIST structure pointing to the
 * actual element. Returns the updated list. */
LIST *ListIterateRemove(LIST *list, int (*func)(void *))
{
  LIST *p, *q;

  /* check the first element of the list */
  while (list && func(list->pelement) != 0) {
    /* the first element needs to be deleted. */
    p = list;
    list = list->next;
    DISPOSELIST(p);
  }

  if (!list)
    return list;	/* return the empty list */

  /* the other situation: the list contains at least one element and the first
   * element is not to be deleted. Chasing pointers... (the first element of 
   * the list remains unchanged). */
  q = list;
  p = list->next;
  while (p) {
    if (func(p->pelement) != 0) {
      /* delete the element */
      q->next = p->next;
      DISPOSELIST(p);
      p = q->next;
    } else {
      /* don't delete the element */
      q = p; p = p->next;
    }
  }

  return list;
}

#ifdef NOLISTMACROS
/* iterator: voer de procedure uit vooral alle elementen van de lijst.
 * De procedure heeft als argument een wijzer naar een element */
void ListIterate(LIST *list, void (*proc)(void *))
{
	void *pelement;

	while (list) {
		pelement = list->pelement;
		list = list->next;
		proc(pelement);
	}		
}
#endif /*NOLISTMACROS*/

#ifdef NOLISTMACROS
/* iterator: voer de procedure uit vooral alle elementen van de lijst.
 * De procedure heeft twee argumenten: eerst een wijzer naar
 * het element, dan een wijzer naar andere data de gelijk is voor alle
 * elementen */
void ListIterate1A(LIST *list, void (*proc)(void *, void *), void *extra)
{
	void *pelement;

	while (list) {
		pelement = list->pelement;
		list = list->next;
		proc(pelement, extra);
	}		
}
#endif /*NOLISTMACROS*/

#ifdef NOLISTMACROS
/* iterator: voer de procedure uit vooral alle elementen van de lijst.
 * De procedure heeft twee argumenten: eerst een wijzer naar
 * data die gelijk is voor alle elementen, dan een wijzer naar het element */
void ListIterate1B(LIST *list, void (*proc)(void *, void *), void *extra)
{
	void *pelement;

	while (list) {
		pelement = list->pelement;
		list = list->next;
		proc(extra, pelement);
	}		
}
#endif /*NOLISTMACROS*/

/* een volledige lijst vernietigen: vernietigt niet de elementen! */
void ListDestroy(LIST *list)
{
	LIST *p;

	while (list) {
		p = list->next;
		DISPOSELIST(list);
		list = p;
	}
}

#ifdef TEST
#include <stdio.h>

static int odd(void *bla)
{
  int num = (int)bla;
  return (num%2 == 1);
}

static void print(void *bla)
{
  fprintf(stderr, "%d ", (int)bla);
}

int main(int argc, char **argv)
{
  LIST *list = ListCreate();
  int n;

  fprintf(stderr, "ListIterateRemove() test: removes all odd number from a list:\n\n");
  fprintf(stderr, "Enter a series of integer numbers. Terminate the list with a 0 (zero):\n");
  
  scanf("%d", &n);
  while (n != 0) {
    list = ListAdd(list, (void *)n);
    scanf("%d", &n);
  }

  fprintf(stderr, "The list you entered is (reversed and without terminating zero):\n");
  ListIterate(list, print);
  fprintf(stderr, "\n");

  fprintf(stderr, "Now removing all odd numbers ... \n");
  list = ListIterateRemove(list, odd);
	  
  fprintf(stderr, "The result should contain all even numbers of the list:\n");
  ListIterate(list, print);
  fprintf(stderr, "\n");

  return 0;
}

#endif /*TEST*/