#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#if 0
#include <dmalloc.h>
#include <grass/gis.h>
#endif
#include "list.h"

LIST *listitem (size_t size);
LIST *listadd (LIST *head, LIST *elt, cmpfunc cmp);
LIST *listaddnth (LIST *head, LIST *elt, int nth);
LIST *listprep (LIST *head, LIST *elt);
LIST *listapp (LIST *head, LIST *elt);
LIST *listunlink (LIST *head, LIST *elt);
LIST *listunlinknth (LIST *head, int nth);
LIST *listdel (LIST *head, LIST *elt, freefunc func);
LIST *listdelnth (LIST *head, int nth, freefunc func);
int listcnt (LIST *head);
LIST *listdup (LIST *head, cpyfunc cpy, size_t size);
LIST *listsplit (LIST *head, LIST *elt);
LIST *listsplitnth (LIST *head, int nth);
LIST *listjoin (LIST *head, LIST *tail);
LIST *listsort (LIST *head, cmpfunc cmp);
LIST *listrev (LIST *head);
LIST *listshuffle (LIST *head);
LIST *listdelall (LIST *head, freefunc func);
LIST **list2array (LIST *head);
LIST *array2list (LIST **array);
void listforeach (LIST *head, actfunc action);
int listidx (LIST *head, LIST *elt);
LIST *listlast (LIST *head);
LIST *listnth (LIST *head, int nth);
LIST *listfind (LIST *head, LIST *elt, cmpfunc cmp);
LIST *listfinddatum (LIST *head, void *datum, cmpfunc cmp);
LIST *listbsearch (LIST *head, LIST *elt, cmpfunc cmp);
LIST *listbsearchdatum (LIST *head, const void *data, cmpfunc cmp);

static LIST *_listbsearch (LIST *min, int max, LIST *elt, cmpfunc cmp);
static LIST *_listbsearchdatum (LIST *min, int max, const void *datum,
				cmpfunc cmp);

/*
 * listitem()			allocate memory for a list item
 */

LIST *
listitem (size_t size)
{
  LIST *item;

  item = G_calloc (1, size);
  if (!item)
  {
    fprintf (stderr, "Out of memory!\n");
    exit (1);
  }

  return item;
}

/*
 * listadd()			insert item before first greater
 * (cmp == NULL) -> listapp()
 * This is VERY slow. Rather than a lineal search, we should
 * try to implement a listbapprox() function.
 */

LIST *
listadd (LIST *head, LIST *elt, cmpfunc cmp)
{
  LIST *item, *prev = NULL;

  if (elt)
    elt->next = NULL;

  if (!elt)
    return head;
  if (!head)
    return elt;
  if (!cmp)
    return listapp (head, elt);

  for (item = head; item; item = item->next)
  {
    /*
     * cmp (sample, each):
     * Answers if each is smaller/equal/greater than sample
     */
    if ((*cmp)(elt, item) > 0)
      break;
    prev = item;
  }

  if (!prev)
  {
    elt->next = head;
    head = elt;
  }
  else
  {
    elt->next = prev->next;
    prev->next = elt;
  }

  return head;
}

/*
 * listaddnth()			make new item the nth of the list
 * (nth <= 0) -> listprep(), (nth > listcnt()) -> listapp()
 */

LIST *
listaddnth (LIST *head, LIST *elt, int nth)
{
  LIST *item, *prev = NULL;
  int i;

  if (elt)
    elt->next = NULL;

  if (!head)
    return elt;
  if (!elt)
    return head;

  if (nth < 1)
  {
    elt->next = head;
    return elt;
  }

  for (i = 0, item = head; item && i < nth; item = item->next, i++)
    prev = item;

  elt->next = prev->next;
  prev->next = elt;

  return head;
}

/*
 * listprep()				prepend item on list
 */

inline LIST *
listprep (LIST *head, LIST *elt)
{
  if (elt && elt->next)
    elt->next = NULL;

  if (!head)
    return elt;
  if (!elt)
    return head;

  elt->next = head;

  return elt;
}

/*
 * listapp()				append item to list
 */

LIST *
listapp (LIST *head, LIST *elt)
{
  LIST *item;

  if (elt)
    elt->next = NULL;

  if (!head)
    return elt;
  if (!elt)
    return head;

  for (item = head; item && item->next; item = item->next)
    ;

  item->next = elt;

  return head;
}

/*
 * listunlink()				unlink item from list
 */

LIST *
listunlink (LIST *head, LIST *elt)
{
  LIST *item;

  if (!head)
    return NULL;
  if (!elt)
    return head;

  if (head == elt)
  {
    head = elt->next;
    elt->next = NULL;
    return head;
  }

  for (item = head; item && item->next != elt; item = item->next)
    ;
  if (item->next == elt)
  {
    item->next = elt->next;
    elt->next = NULL;
  }
  return head;
}

/*
 * listunlinknth()			unlink nth element from list
 * listunlinknth (head, 0) == (car (list))
 */

LIST *
listunlinknth (LIST *head, int nth)
{
  LIST *item, *elt;
  int i;

  if (!head)
    return NULL;
  if (nth < 0)
    return head;

  if (nth == 0)
  {
    item = head->next;
    head->next = NULL;
    return item;
  }

  for (i = 0, item = head; item && item->next && i < nth - 1;
       item = item->next, i++)
    ;
  if (item->next)
  {
    elt = item->next;
    item->next = elt->next;
    elt->next = NULL;
  }
  return head;
}

/*
 * listdel()				unlink and free element from list
 */

LIST *
listdel (LIST *head, LIST *elt, freefunc func)
{
  if (!elt)
    return head;

  if (head)
    head = listunlink (head, elt);

  if (func)
    (*func)(elt);
  G_free (elt);

  return head;
}

/*
 * listdelnth()				unlink and free nth element from list
 */

LIST *
listdelnth (LIST *head, int nth, freefunc func)
{
  LIST *item, *elt;
  int i;

  if (!head || nth < 0)
    return NULL;

  if (nth == 0)
  {
    elt = head;
    head = head->next;
    listdel (NULL, elt, func);
    return head;
  }

  for (i = 0, item = head; item && item->next && i < nth - 1;
       item = item->next, i++)
    ;

  if (item && item->next)
  {
    elt = item->next;
    item->next = elt->next;
    listdel (NULL, elt, func);
  }

  return head;
}

/*
 * listcnt()				cound elements in list
 */

inline int
listcnt (LIST *head)
{
  LIST *item;
  int n = 0;

  for (item = head; item; item = item->next)
    n++;

  return n;
}

/*
 * listdup()				duplicate list
 * if cpy is NULL, create same number of empty items
 */

LIST *
listdup (LIST *head, cpyfunc cpy, size_t size)
{
  LIST *newhead = NULL, *last = NULL, *item, *elt;

  for (item = head; item; item = item->next)
  {
    elt = listitem (size);
    if (cpy)
      (*cpy)(elt, item);
    if (!newhead)
      newhead = last = elt;
    else
    {
      last->next = elt;
      last = elt;
    }
  }

  return newhead;
}

/*
 * listsplit()				make elt the head of a taillist
 */

LIST *
listsplit (LIST *head, LIST *elt)
{
  LIST *item;

  if (!head || !elt)
    return elt;

  if (head == elt)
    return NULL;

  for (item = head; item && item->next != elt; item = item->next)
    ;
  if (item->next == elt)
    item->next = NULL;

  return elt;
}

/*
 * listsplitnth()			make nth element the head of a taillist
 */

LIST *
listsplitnth (LIST *head, int nth)
{
  LIST *item, *tail = NULL;
  int i;

  if (!head || nth < 1)
    return NULL;

  for (i = 0, item = head; item && i < nth - 1; item = item->next, i++)
    ;
  if (item && item->next)
  {
    tail = item->next;
    item->next = NULL;
  }

  return tail;
}

/*
 * listjoin()				joint two lists
 */

LIST *
listjoin (LIST *head, LIST *tail)
{
  LIST *item;

  if (!head)
    return tail;
  if (!tail)
    return head;

  for (item = head; item && item->next; item = item->next)
    ;
  if (item)
    item->next = tail;

  return head;
}

/*
 * listsort()				Quick sort on list
 */

LIST *
listsort (LIST *head, cmpfunc cmp)
{
  LIST *high = NULL, *low = NULL, *item, *next;

  if (!head || !head->next)
    return head;

  for (item = head; item; )
  {
    next = item->next;
    if ((*cmp)(item, head) < 0)
    {
      item->next = low;
      low = item;
    }
    else
    {
      item->next = high;
      high = item;
    }
    item = next;
  }

  high = listsort (high, cmp);
  low = listsort (low, cmp);

  head = listjoin (high, low);

  return head;
}

/*
 * listrev()				reverse order the list
 */

LIST *
listrev (LIST *head)
{
  LIST *newhead = NULL, *item, *next;

  for (item = head; item; )
  {
    next = item->next;
    newhead = listprep (newhead, item);
    item = next;
  }

  return newhead;
}

/*
 * listshuffle()
 */
LIST *
listshuffle (LIST *head)
{
  LIST **array, *newhead = NULL;
  int n, i = 0, val;
  struct timeval tv;

  gettimeofday (&tv, NULL);
  srandom (tv.tv_usec);

  n = listcnt (head);
  array = list2array (head);

  while (i < n)
  {
    val = random () % n;

    if (array[val])
    {
      newhead = listprep (newhead, array[val]);
      array[val] = NULL;
      i++;
    }
  }

  G_free (array);

  return newhead;
}

/*
 * listdelall()				free the whole list
 */

LIST *
listdelall (LIST *head, freefunc func)
{
  LIST *item, *next;

  for (item = head; item; )
  {
    next = item->next;
    if (func)
      (*func)(item);
    G_free (item);
    item = next;
  }

  return NULL;
}

/*
 * list2array()				build an array with members of list
 * array is allocated and needs to be G_free ()ed, list not changed.
 */

LIST **
list2array (LIST *head)
{
  LIST **array, *item;
  int n, i;

  n = listcnt (head);
  if (!n)
    return NULL;

  array = (LIST **)G_calloc (n + 1, sizeof (LIST *));
  if (!array)
  {
    fprintf (stderr, "Out of memory\n");
    exit (1);
  }

  for (i = 0, item = head; item; item = item->next, i++)
    array[i] = item;

  return array;
}

/*
 * array2list()				link the elements of an array in order
 */

LIST *
array2list (LIST **array)
{
  LIST *head = NULL, *item = NULL;
  int i;

  if (array)
    head = item = array[0];

  for (i = 1; array && array[i]; i++)
  {
    item->next = array[i];
    item = item->next;
  }
  item->next = NULL;

  return head;
}

/*
 * listforeach()			execute action on each item
 */

inline void
listforeach (LIST *head, actfunc action)
{
  LIST *item;

  if (!head || !action)
    return;

  for (item = head; item; item = item->next)
    (*action)(item);
}

/*
 * listidx()				find offset of item from head
 * head is offset (index) zero.
 */

int
listidx (LIST *head, LIST *elt)
{
  LIST *item;
  int i;

  if (!elt)
    return -1;

  for (i = 0, item = head; item; item = item->next, i++)
    if (item == elt)
      break;

  if (!item)
    return -1;

  return i;
}

/*
 * listlast()				find last item in list.
 */

inline LIST *
listlast (LIST *head)
{
  LIST *item;

  for (item = head; item && item->next; item = item->next)
    ;

  return item;
}

/*
 * listnth()				find nth item in list.
 */

LIST *
listnth (LIST *head, int nth)
{
  LIST *item;
  int i;

  if (!head || nth < 0)
    return NULL;

  for (i = 0, item = head; item; item = item->next, i++)
    if (i == nth)
      break;

  return item;
}

/*
 * listfind()			linear search giving structure as sample
 */

LIST *
listfind (LIST *head, LIST *elt, cmpfunc cmp)
{
  LIST *item;

  for (item = head; item; item = item->next)
    if (!(*cmp)(elt, item))
      break;

  return item;
}

/*
 * listfinddatum()		linear search giving sample by pointer
 */

LIST *
listfinddatum (LIST *head, void *datum, cmpfunc cmp)
{
  LIST *item;

  for (item = head; item; item = item->next)
    if (!(*cmp)(datum, item))
      break;

  return item;
}

static LIST *
_listbsearch (LIST *min, int max, LIST *elt, cmpfunc cmp)
{
  LIST *item;
  int i, n, result;

  if (!min)
    return NULL;

  n = max / 2;

  for (i = 0, item = min; item && i < n; item = item->next, i++)
    ;

  result = (*cmp)(item, elt);
  if (result == 0)
    return item;
  if (n == 0)
  {
    if (max == 1 && item->next && !(*cmp)(item->next, elt))
      return item->next;
    return NULL;
  }

  if (result < 0)
    item = _listbsearch (min, n, elt, cmp);
  else
    item = _listbsearch (item->next, max - n - 1, elt, cmp);

  return item;
}

/*
 * listbsearch()			binary search with struct as sample
 */

LIST *
listbsearch (LIST *head, LIST *elt, cmpfunc cmp)
{
  LIST *item;
  int n, max, result;

  if (!head || !elt || !cmp)
    return NULL;

  max = listcnt (head);

  n = max / 2;
  item = listnth (head, n);
  result = (*cmp)(item, elt);

  if (result == 0)
    return item;

  if (result < 0)
    item = _listbsearch (head, n, elt, cmp);
  else
    item = _listbsearch (item->next, max - n - 1, elt, cmp);

  return item;
}

static LIST *
_listbsearchdatum (LIST *min, int max, const void *datum, cmpfunc cmp)
{
  LIST *elt;
  int i, n, result;

  if (!min)
    return NULL;

  n = max / 2;

  for (i = 0, elt = min; elt && i < n; elt = elt->next, i++)
    ;

  result = (*cmp)(datum, elt);
  if (result == 0)
    return elt;
  if (n == 0)
  {
    if (max == 1 && elt->next && !(*cmp)(datum, elt->next))
      return elt->next;
    return NULL;
  }

  if (result < 0)
    elt = _listbsearchdatum (min, n, datum, cmp);
  else
    elt = _listbsearchdatum (elt->next, max - n - 1, datum, cmp);

  return elt;
}

/*
 * listbsearchdatum()				binary search for sample by ptr
 */

LIST *
listbsearchdatum (LIST *head, const void *datum, cmpfunc cmp)
{
  LIST *elt;
  int n, max, result;

  if (!head || !datum || !cmp)
    return NULL;

  max = listcnt (head);

  n = max / 2;
  elt = listnth (head, n);
  result = (*cmp)(datum, elt);

  if (result == 0)
    return elt;

  if (result < 0)
    elt = _listbsearchdatum (head, n, datum, cmp);
  else
    elt = _listbsearchdatum (elt->next, max - n - 1, datum, cmp);

  return elt;
}