// GetDP - Copyright (C) 1997-2018 P. Dular and C. Geuzaine, University of Liege
//
// See the LICENSE.txt file for license information. Please report all
// bugs and problems to the public mailing list <getdp@onelab.info>.
//
// Contributor(s):
//   Marc Ume
//

#include "GetDPConfig.h"
#if !defined(HAVE_NO_STDINT_H)
#include <stdint.h>
#elif defined(HAVE_NO_INTPTR_T)
typedef unsigned long intptr_t;
#endif
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include "MallocUtils.h"
#include "ListUtils.h"
#include "TreeUtils.h"
#include "Message.h"

#if !defined(HAVE_GMSH)

int fcmp_int(const void *a, const void *b)
{
  return (*(int *)a - *(int *)b);
}

int fcmp_absint(const void *a, const void *b)
{
  return (abs(*(int *)a) - abs(*(int *)b));
}

int fcmp_double(const void *a, const void *b)
{
  double cmp;

  cmp = *(double *)a - *(double *)b;
  if(cmp > 1.e-16)
    return 1;
  else if(cmp < -1.e-16)
    return -1;
  else
    return 0;
}

List_T *List_Create(int n, int incr, int size)
{
  List_T *liste;

  if(n <= 0)
    n = 1;
  if(incr <= 0)
    incr = 1;

  liste = (List_T *) Malloc(sizeof(List_T));

  liste->nmax = 0;
  liste->incr = incr;
  liste->size = size;
  liste->n = 0;
  liste->isorder = 0;
  liste->array = NULL;

  List_Realloc(liste, n);
  return (liste);
}

void List_Delete(List_T * liste)
{
  if(!liste)
    return;
  Free(liste->array);
  Free(liste);
}

void List_Realloc(List_T * liste, int n)
{
  if(n <= 0)
    return;

  if(liste->array == NULL) {
    // This does not permit to allocate lists smaller that liste->incr:
    //liste->nmax = ((n - 1) / liste->incr + 1) * liste->incr;
    // So this is much better
    liste->nmax = n;
    liste->array = (char *)Malloc(liste->nmax * liste->size);
  }
  else if(n > liste->nmax) {
    liste->nmax = ((n - 1) / liste->incr + 1) * liste->incr;
    liste->array = (char *)Realloc(liste->array, liste->nmax * liste->size);
  }
}

void List_Add(List_T * liste, void *data)
{
  liste->n++;

  List_Realloc(liste, liste->n);
  liste->isorder = 0;
  memcpy(&liste->array[(liste->n - 1) * liste->size], data, liste->size);
}

int List_Nbr(List_T * liste)
{
  return (liste) ? liste->n : 0;
}

void List_Read(List_T * liste, int index, void *data)
{
  if((index < 0) || (index >= liste->n))
    Message::Fatal("Wrong list index (read)");
  memcpy(data, &liste->array[index * liste->size], liste->size);
}

void List_Write(List_T * liste, int index, void *data)
{
  if((index < 0) || (index >= liste->n))
    Message::Error("Wrong list index (write)");
  else {
    liste->isorder = 0;
    memcpy(&liste->array[index * liste->size], data, liste->size);
  }
}

void List_Put(List_T * liste, int index, void *data)
{
  if(index < 0)
    Message::Error("Wrong list index (put)");
  else {
    if(index >= liste->n) {
      liste->n = index + 1;
      List_Realloc(liste, liste->n);
      List_Write(liste, index, data);
    }
    else {
      List_Write(liste, index, data);
    }
  }
}

void List_Pop(List_T * liste)
{
  if(liste->n > 0)
    liste->n--;
}

void *List_Pointer(List_T * liste, int index)
{
  if((index < 0) || (index >= liste->n))
    Message::Fatal("Wrong list index (pointer)");

  liste->isorder = 0;
  return (&liste->array[index * liste->size]);
}

void *List_Pointer_NoChange(List_T * liste, int index)
{
  if((index < 0) || (index >= liste->n))
    Message::Fatal("Wrong list index (pointer)");

  return (&liste->array[index * liste->size]);
}

void *List_Pointer_Fast(List_T * liste, int index)
{
  return (&liste->array[index * liste->size]);
}

void *List_Pointer_Test(List_T * liste, int index)
{
  if(!liste || (index < 0) || (index >= liste->n))
    return NULL;

  liste->isorder = 0;
  return (&liste->array[index * liste->size]);
}

void List_Sort(List_T * liste, int (*fcmp) (const void *a, const void *b))
{
  if(!liste) return;
  qsort(liste->array, liste->n, liste->size, fcmp);
}

int List_Search(List_T * liste, void *data,
                int (*fcmp) (const void *a, const void *b))
{
  void *ptr;

  if(liste->isorder != 1) {
    List_Sort(liste, fcmp);
    liste->isorder = 1;
  }
  ptr = (void *)bsearch(data, liste->array, liste->n, liste->size, fcmp);
  if(ptr == NULL)
    return (0);
  return (1);
}

int List_ISearchSeq(List_T * liste, void *data,
                    int (*fcmp) (const void *a, const void *b))
{
  int i;

  if(!liste)
    return -1;
  i = 0;
  while((i < List_Nbr(liste)) && fcmp(data, (void *)List_Pointer(liste, i)))
    i++;
  if(i == List_Nbr(liste))
    i = -1;
  return i;
}

void *List_PQuery(List_T * liste, void *data,
                  int (*fcmp) (const void *a, const void *b))
{
  void *ptr;

  if(liste->isorder != 1)
    List_Sort(liste, fcmp);
  liste->isorder = 1;
  ptr = (void *)bsearch(data, liste->array, liste->n, liste->size, fcmp);
  return (ptr);
}

int List_PSuppress(List_T * liste, int index)
{
  char *ptr;
  int len;

  ptr = (char *)List_Pointer_NoChange(liste, index);
  if(ptr == NULL)
    return (0);

  liste->n--;
  len = liste->n - (((intptr_t)ptr - (intptr_t)liste->array) / liste->size);
  if(len > 0)
    memmove(ptr, ptr + liste->size, len * liste->size);
  return (1);
}

void List_Invert(List_T * a, List_T * b)
{
  int i, N;
  N = List_Nbr(a);
  for(i = 0; i < N; i++) {
    List_Add(b, List_Pointer(a, N - i - 1));
  }
}

void List_Reset(List_T * liste)
{
  if(!liste)
    return;
  liste->n = 0;
}

void List_Action(List_T * liste, void (*action) (void *data, void *dummy))
{
  int i, dummy;

  for(i = 0; i < List_Nbr(liste); i++)
    (*action) (List_Pointer_NoChange(liste, i), &dummy);
}

void List_Copy(List_T * a, List_T * b)
{
  int i, N;
  N = List_Nbr(a);
  for(i = 0; i < N; i++) {
    List_Add(b, List_Pointer(a, i));
  }
}

List_T *ListOfDouble2ListOfInt(List_T *dList)
{
  int n = List_Nbr(dList);
  List_T *iList = List_Create(n, n, sizeof(int));
  for(int i = 0; i < n; i++){
    double d;
    List_Read(dList, i, &d);
    int j = (int)d;
    List_Add(iList, &j);
  }
  return iList;
}

int List_Suppress(List_T *liste, void *data,
		 int (*fcmp)(const void *a, const void *b))
{
  char *ptr;
  int len;

  ptr = (char*)List_PQuery(liste,data,fcmp) ;
  if (ptr == NULL) return(0);

  liste->n--;
  len = liste->n - (((intptr_t)ptr - (intptr_t)liste->array) / liste->size);
  if (len > 0) memmove(ptr, ptr + liste->size, len * liste->size);
  return(1);
}


#endif

// These are not defined in Gmsh:

static int safe_fwrite(const void *ptr, size_t size, size_t nmemb, FILE * stream)
{
  size_t result = fwrite(ptr, size, nmemb, stream);

  if(result < nmemb) {
    Message::Error(strerror(errno));
    if(fflush(stream) < 0)
      Message::Error("EOF reached");
    if(fclose(stream) < 0)
      Message::Error(strerror(errno));
    return 1;
  }
  return 0;
}

void List_WriteToFile(List_T * liste, FILE * file, int format)
{
  int i, n;

  if(!(n = List_Nbr(liste)))
    return;

  switch (format) {
  case LIST_FORMAT_ASCII:
    if(liste->size == sizeof(double))
      for(i = 0; i < n; i++)
        fprintf(file, " %.16g", *((double *)&liste->array[i * liste->size]));
    else if(liste->size == sizeof(float))
      for(i = 0; i < n; i++)
        fprintf(file, " %.16g", *((float *)&liste->array[i * liste->size]));
    else if(liste->size == sizeof(int))
      for(i = 0; i < n; i++)
        fprintf(file, " %d", *((int *)&liste->array[i * liste->size]));
    else if(liste->size == sizeof(char))
      for(i = 0; i < n; i++)
        fputc(*((char *)&liste->array[i * liste->size]), file);
    else
      Message::Error("Bad type of data to write list to file (size = %d)",
                     liste->size);
    break;
  case LIST_FORMAT_BINARY:
    safe_fwrite(liste->array, liste->size, n, file);
    break;
  default:
    Message::Error("Unknown list format");
    break;
  }
}

int List_Query(List_T *liste, void *data,
		 int (*fcmp)(const void *a, const void *b))
{
  void *ptr;

  if (liste->isorder != 1) List_Sort(liste,fcmp);
  liste->isorder = 1;
  ptr = (void *) bsearch(data,liste->array,liste->n,liste->size,fcmp);
  if (ptr == NULL) return(0);

  memcpy(data,ptr,liste->size);
  return (1);
}

void List_Insert(List_T *liste, void *data,
		 int (*fcmp)(const void *a, const void *b))
{
  if (List_Search(liste,data,fcmp) == 0)
    List_Add(liste,data);
}

List_T *List_Copy(List_T *src)
{
  List_T *dest = (List_T *)Malloc(sizeof(List_T));
  dest->nmax = src->nmax;
  dest->incr = src->incr;
  dest->size = src->size;
  dest->n = src->n;
  dest->isorder = src->isorder;
  dest->array = (char *)Malloc(src->nmax * src->size);
  memcpy(dest->array, src->array, src->nmax * src->size);
  return dest;
}

int List_ISearch(List_T * liste, void *data,
                 int (*fcmp) (const void *a, const void *b))
{
  void *ptr;

  if (!liste)  return -1 ;
  if(liste->isorder != 1)
    List_Sort(liste, fcmp);
  liste->isorder = 1;
  ptr = (void *)bsearch(data, liste->array, liste->n, liste->size, fcmp);
  if(ptr == NULL)
    return (-1);
  return (((intptr_t)ptr - (intptr_t)liste->array) / liste->size);
}

int List_ISearchSeqPartial(List_T *liste, void * data, int i_Start,
                           int (*fcmp)(const void *a, const void *b))
{
  int i ;

  if (!liste)  return -1 ;
  i = i_Start ;
  while ((i < List_Nbr(liste)) &&
         fcmp(data, (void *)List_Pointer(liste, i)) )  i++ ;
  if (i == List_Nbr(liste))  i = -1 ;
  return i ;
}

int List_Replace(List_T *liste, void *data,
		 int (*fcmp)(const void *a, const void *b))
{
  void *ptr;

  if (liste->isorder != 1) List_Sort(liste,fcmp);
  liste->isorder = 1;
  ptr = (void *) bsearch(data,liste->array,liste->n,liste->size,fcmp);
  if (ptr == NULL) {
    List_Add(liste,data);
    return(0);
  }
  else {
    memcpy(ptr,data,liste->size);
    return (1);
  }
}

static void *lolofind(void *data, void *array, int n, int size,
		      int (*fcmp)(const void *a, const void *b) )
{
  char *ptr;
  int i;

  ptr = (char*)array;
  for (i = 0; i < n; i++) {
    if (fcmp(ptr,data) == 0) break;
    ptr += size;
  }
  if (i < n) return(ptr);
  return(NULL);
}

static char *startptr = NULL;

int List_LQuery(List_T *liste, void *data,
		 int (*fcmp)(const void *a, const void *b), int first)
{
  char *ptr;

  if (first == 1) {
    ptr = (char *) lolofind(data,liste->array,liste->n,liste->size,fcmp);
  }
  else {
    if (startptr != NULL)
      ptr = (char *) lolofind(data,startptr,
			      liste->n - (startptr-liste->array)/liste->size,
			      liste->size,fcmp);
    else
      return(0);
  }

  if (ptr == NULL) return(0);

  startptr =  ptr + liste->size;
  if ( startptr >= ( liste->array + liste->n * liste->size))
    startptr = NULL;
  memcpy(data,ptr,liste->size);
  return (1);
}