/* "generic" lists */

#include <stdlib.h>

#include "list.h"

#if 01
typedef struct node *node;

struct _list {
  node head, tail;
  node state; // allows one iterator per list
};

struct node {
  void *element;
  node next;
};
#endif

fd_list fd_list_new()
{
  fd_list l = malloc(sizeof(struct _list));

  if (l)
    l->head = l->tail = 0;

  return l;
}

int fd_list_empty(fd_list list)
{
  return list->head == 0;
}

/* insert ELEMENT at the head of LIST */
int fd_list_insert(fd_list list, void *element)
{
  node n = malloc(sizeof(struct node));

  if (n == 0)
    return 0;

  n->element = element;
  n->next = list->head;

  list->head = n;
  if (list->tail == 0)
    list->tail = n;

  return 1;
}

/* append ELEMENT to LIST */
int fd_list_append(fd_list list, void *element)
{
  node n = malloc(sizeof(struct node)); // XXX: check for NULL

  if (n == 0)
    return 0;

  n->element = element;
  n->next = 0;

  if (list->tail == 0)
    list->head = n;
  else
    list->tail->next = n;

  list->tail = n;

  return 1;
}

/* insert ELEMENT in LIST, sorted according to COMPARE, without repetitions */
int fd_list_sorted_insert(fd_list list, void *element, int (*compare)(void *, void *))
{
  node new, prev, cur;
  int cmp;

  cur = list->head;

  while (cur && (cmp = compare(cur->element, element)) < 0)
    {
      prev = cur;
      cur = cur->next;
    }

  if (cur && cmp == 0)
    return 0;

  new = malloc(sizeof(struct node)); // XXX: check for NULL

  new->next = cur;
  new->element = element;

  if (cur == list->head)
    {
      list->head = new;

      if (list->tail == 0)
	list->tail = new;
    }
  else
    prev->next = new;

  return 1;
}

/* remove and return the first element from LIST */
void *fd_list_remove(fd_list list)
{
  void *element;
  node first;

  if (list->head == 0)
    return 0;

  first = list->head;

  element = first->element;

  list->head = first->next;

  free(first);

  if (list->head == 0)
    list->tail = 0;

  return element;
}

/* return the first element from LIST */
void *fd_list_head(fd_list list)
{
  return (list->head == 0) ? 0 : list->head->element;
}

/* return the last element from LIST */
void *fd_list_tail(fd_list list)
{
  return (list->head == 0) ? 0 : list->tail->element;
}

/* iterator (one per list) */
void fd_list_iterate(fd_list list)
{
  list->state = list->head;
}

int fd_list_has_next(fd_list list)
{
  return list->state != 0;
}

void *fd_list_next_element(fd_list list)
{
  void *element = list->state->element;

  list->state = list->state->next;

  return element;
}

/* return an iterator for LIST */
fd_list_iterator fd_list_iterate2(fd_list list)
{
  return list->head;
}

int fd_list_has_next2(fd_list_iterator iterator)
{
  return iterator != 0;
}

void *fd_list_next_element2(fd_list_iterator *iterator)
{
  void *element = (*iterator)->element;

  *iterator = (*iterator)->next;

  return element;
}

/* free the space occupied by LIST */
void fd_list_dispose(fd_list list)
{
  struct node *n, *m;

  n = list->head;

  while (n)
    {
      m = n->next;
      free(n);
      n = m;
    }

  free(list);
}

/* free the space occupied by LIST and by its elements */
void fd_list_dispose_deep(fd_list list, void (*free_element)(void *))
{
  struct node *n, *m;

  n = list->head;

  while (n)
    {
      free_element(n->element);
      m = n->next;
      free(n);
      n = m;
    }

  free(list);
}

/* empty LIST */
void fd_list_empty_list(fd_list list)
{
  struct node *n;

  while (n = list->head)
    {
      list->head = n->next;
      free(n);
    }

  list->tail = 0;
}

/* empty LIST and free the space occupied by its elements */
void fd_list_empty_list_deep(fd_list list, void (*free_element)(void *))
{
  struct node *n;

  while (n = list->head)
    {
      free_element(n->element);
      list->head = n->next;
      free(n);
    }

  list->tail = 0;
}

// XXX: not to be used
int fd_list_length(fd_list list)
{
  struct node *n;
  int l = 0;

  for (n = list->head; n; n = n->next)
    l++;

  return l;
}