/***********************************
  (C) Copyright 1992-1993; dit/upm
  Distributed under the conditions stated in the
  TOPO General Public License (see file LICENSE)
  ***********************************/

/***********************************

  David Larrabeiti Lopez

  30-1-1990

  Module to manage dynamic lists of data
  of any type.

  COMPILATION OPTIONS: The behaviour of this module can be modified
  by the following compilation flags:

  SDEBUG : activate debugging mode
  DEBUGMEM : activate control of deallocated memory


  21-07-92 David
  New function : Last_list.

  ************************************/

/* LINTLIBRARY */


/* KJT 12/02/12: Added */
#include <stdlib.h>
#include "listdh.h"
#include "lilists.h"
#include "limisc.h"
#include "listrbk.h"


/******************************************************************
 *                                                                                                *
 *              nodes creation and deletion management                    *
 *                                                                                                *
 *******************************************************************/


/******************************************************************
 *
 * Account of list nodes used and released.
 *
 *******************************************************************/

static int new_node_count      = 0;
static int released_node_count = 0;
static int max_node_count      = 0;

static ListTyp New_Node_list()
{
  ListTyp n;
  n = (ListTyp) NewCellM( sizeof(ListNodeTyp) );
#ifdef SDEBUG
  ++new_node_count;
  max_node_count = MAX( max_node_count, new_node_count-released_node_count );
#endif
  return n;
}

/*----------------------------------------------------------------*/

/* CreateNode_list
 * Create a single node list.
 */
ListTyp CreateNode_list()
{
  ListTyp n;
  n = New_Node_list();
  n->next = NULL;
  n->info = 0;
  return n;
}

/*----------------------------------------------------------------*/

/* DispNode_list
 * Deallocates the memory used by the node n.
 */
void DispNode_list( n )
     ListTyp n;
{
  LASSERT( n != NULL );
  FreeCellM((void*)n,sizeof(ListNodeTyp));
#ifdef SDEBUG
  released_node_count++;
#endif
}

/*----------------------------------------------------------------*/

/* Disp_list
 * Frees the memory allocated by the nodes of the list l.
 * See Free_list(l) to deallocate the memory used by the information.
 */
void Disp_list(  l  )
     ListTyp  l;
{
  if ( l!=NULL ){
    Disp_list( l->next );
    FreeCellM((void*)l,sizeof(ListNodeTyp));
#ifdef SDEBUG
    released_node_count++;
#endif
  }
}

/*----------------------------------------------------------------*/

/* Free_list
 * Frees the memory allocated by the list l.
 * Functions f deallocates the information in each node.
 */
void Free_list( l, f )
     ListTyp  l;
     void    (*f)();
{
  ListTyp aux;

  while (l != NULL) {
    if (f)
      (*f)(l->info);
    aux = l;
    l   = l->next;
    FreeCellM((void*)aux,sizeof(ListNodeTyp));
#ifdef SDEBUG
    released_node_count++;
#endif
  }
}


/******************************************************************
 *                                                                                                *
 *              lists management                                                          *
 *                                                                                                *
 *******************************************************************/

/* Insert_list
 * Inserts the element e in the list l (at the head) and returns the new list.
 */
ListTyp Insert_list( e , l )
     DataListTyp  e;
     ListTyp l;
{
  ListTyp aux;

  aux       = New_Node_list();
  aux->info = e;
  aux->next = l;
  return aux;
}

/*----------------------------------------------------------------*/

/* Add_IfNotIn_list
 * Unlike Add_list the element is not Added if it is already in the list.
 * f == NULL => integer comparison.
 */
ListTyp Add_IfNotIn_list( e, l, f )
     DataListTyp  e;
     ListTyp l;
     boolean (*f)();
{
  register ListTyp aux, prev;

  if (l==NULL)
    return Insert_list(e,Create_list());
  if ( f==NULL ) {
    for ( aux=l; aux!=NULL; prev=aux, aux=aux->next )
      if (e==aux->info)
	return l;
  }
  else
    for ( aux=l; aux!=NULL; prev=aux, aux=aux->next )
      if ((*f)(e,aux->info))
	return l;
  if (aux==NULL)
    prev->next=Insert_list(e,Create_list());

  return l;
}

/*----------------------------------------------------------------*/

/* GetInfo_list
 * Picks up the data stored in the actual node (of the list) n.
 * Sets the information stored in n to NULL.
 * If node is NULL then return NULL.
 */
DataListTyp GetInfo_list( l )
     ListTyp l;
{
  DataListTyp aux;

  if (l==NULL)
    return NULL;
  aux = l->info;
  l->info = NULL;
  return aux;
}

/*----------------------------------------------------------------*/

/* In_list
 * Explores the list l and returns the boolean "e in l"
 * f is a boolean function to decide when two elements are equal.
 * f == NULL => integer comparison.
 */
boolean In_list( e, l, f )
     DataListTyp  e;
     register ListTyp l;
     boolean (*f)();
{
  if ( f == NULL ) {
    for ( ; l !=NULL; l=l->next )
      if (e==l->info)
	return TRUE;
    return FALSE;
  }
  for ( ; l !=NULL; l=l->next )
    if ((*f)(e,l->info))
      return TRUE;
  return FALSE;
}

/*----------------------------------------------------------------*/

/* LookFor_list
 * Explores the list l and returns the first node where element e is found.
 * If e is not in l, then returns NULL.
 * Function f is a boolean function to decide when two elements are equal.
 * f == NULL => integer comparison.
 */
ListTyp LookFor_list( e, l, f )
     DataListTyp  e;
     register ListTyp l;
     boolean (*f)();
{
  if ( f==NULL ) {
    for ( ; (l!=NULL) && (e!=l->info); l=l->next )
      ;
    return l;
  }
  for ( ; (l!=NULL) && !((*f)(e,l->info)); l=l->next )
    ;
  return l;
}

/*----------------------------------------------------------------*/

/* Apply_Proc_list
 * Applies procedure p to all the data stored in the list l.
 */
void Apply_Proc_list( l , p )
     ListTyp l;
     void (*p)();
{
  if (p)
    while (l != NULL) {
      (*p)(l->info);
      l=l->next;
    }
}

/*----------------------------------------------------------------*/

/* Apply_Func_list
 * Applies the function f to all the data stored in the list l.
 * The data stored in the list will be updated with the value returned by f.
 */
void Apply_Func_list( l , f )
     ListTyp l;
     DataListTyp (*f)();
{
  while (l != NULL) {
    l->info = (*f)(l->info);
    l       = l->next;
  }
}

/*----------------------------------------------------------------*/

/* Join_list
 * Returns the concatenation l1.l2.
 * warning: do not attempt to free l2 after Joinning.
 */
ListTyp Join_list( l1 , l2 )
     ListTyp l1, l2;
{
  ListTyp aux;

  if ( l1 != NULL )
    { for (aux = l1; aux->next != NULL;aux=aux->next );
      aux->next= l2;
      return (l1);
    }
  else
    return (l2);
}

/*----------------------------------------------------------------*/

/* Copy_list
 * Returns a copy of list l.
 * f is used to copy the data stored in the nodes.
 * f == NULL => integer echoing.
 */
ListTyp Copy_list ( l, f )
     register ListTyp l;
     DataListTyp (*f)();
{
  ListTyp res,last;

  res = Create_list();
  if ( l!=NULL )
    if ( f!=NULL ){
      res = CreateNode_list();
      PutInfo_list(res,(*f)(l->info));
      for ( last=res, l=l->next; l!=NULL; last=last->next, l=l->next ) {
	last->next = CreateNode_list();
	PutInfo_list(last->next,(*f)(l->info));
      }
    }
    else{
      res = CreateNode_list();
      PutInfo_list(res,l->info);
      for ( last=res, l=l->next; l!=NULL; last=last->next, l=l->next ) {
	last->next = CreateNode_list();
	PutInfo_list(last->next,l->info);
      }
    }
  return res;
}

/*----------------------------------------------------------------*/

/* Equal_list
 * Returns the boolean: "list l1 == list l2".
 * The order of the elements must be the same.
 * eq is a function that returns the equality of two elements of the list
 * boolean eq( e1, e2 )
 * Use "eq" equal to NULL for integer comparation.
 */
boolean Equal_list( l1, l2, eq )
     register ListTyp l1,l2;
     boolean (*eq)();
{
  boolean equal;

  equal=TRUE;
  while ((l1!=NULL)&&(l2!=NULL)&&equal) {
    if (eq==NULL)
      equal = l1->info == l2->info;
    else
      equal = eq( l1->info, l2->info );
    l1=l1->next;
    l2=l2->next;
  }
  return (l1 == l2) && equal;

}

/*----------------------------------------------------------------*/

/* Print_list
 * Prints a list in the format: info1, info2, ..., infoN
 * "f" is a function that returns a string of char with the information
 * of the node.
 * "pstr" is the function used to print the value returned by "f".
 * BE CAREFULL: the strings returned by "f" are not disposed.
 */
void Print_list( l, f, pstr )
     ListTyp l;
     char * (*f)();
     void (*pstr)();
{
  if (l!=NULL){
    while ( l->next != NULL ) {
      pstr(f(l->info));
      pstr(", ");
      l=l->next;
    }
    pstr(f(l->info) );
  }
}

/*----------------------------------------------------------------*/

/* SPrint_list
 * return a char string with list l with the format:
 *   f(info1),f(info2), ...,infoN
 * f is a function that makes a string of char with the information
 * of the node. The strings generated by f are disposed.
 */
char * SPrint_list( l, f )
     ListTyp l;
     char * (*f)();
{
  char    * str;
  StrBckTyp strBck;

  strBck = CreateStrBck();
  while ( l!=NULL ){
    str  = f( LookInfo_list(l) );
    strBck  = ConcatStrBck( strBck, str );
    free( str );
    l = l->next;
    if ( l!=NULL )
      strBck = ConcatStrBck( strBck, "," );
  }
  str = GetStrStrBck( strBck) ;
  FreeStrBck( strBck );
  return str;
}

/*----------------------------------------------------------------*/

/* Reverse_list
 * Reverse a list l.
 */
ListTyp Reverse_list(l)
     ListTyp l;
{
  ListTyp last,nxt;

  if ( l==NULL )
    return NULL;
  last = Create_list();
  for ( nxt=l->next; nxt!=NULL; l=nxt, nxt=nxt->next ) {
    l->next = last;
    last    = l;
  }
  l->next = last;
  return l;
}

/*----------------------------------------------------------------*/

/* Diff_list
 * returns the difference l1-l2.
 * Equal decides whether two elements are equal.
 * FreeInfo is used to release the info of the rest in l1.
 * ( l1 is modified ; l2 remains unchanged. )
 */
ListTyp Diff_list( l1, l2, Equal, FreeInfo )
     register ListTyp l1,l2;
     boolean (*Equal)();
     void (*FreeInfo)();
{
  ListTyp l;

  for ( ; l2 != NULL; l2=l2->next ) {
    for ( l = l1; l != NULL; l=l->next )
      if ((*Equal)(l2->info,l->info))
	break;
    if (l!=NULL) {
      FreeInfo(l->info);
      l1 = DeleteNode_list( l, l1 );
    }
  }
  return l1;
}

/*----------------------------------------------------------------*/

/* SubSet_list
 * Determine if all the elements of list l1 are included in list l2.
 * Example: SubSet_list( a-b-c-a-b, a-b-c-d-e-f-g, EqInt ) -> TRUE
 */
boolean SubSet_list( l1, l2, Eq )
     ListTyp l1,l2;
     boolean (*Eq)();
{
  register ListTyp aux;
  boolean equal;

  for ( ; l1 !=NULL; l1=l1->next ) {
    equal = FALSE;
    for ( aux=l2; aux!=NULL && !equal; aux=aux->next )
      equal = (*Eq)(l1->info,aux->info);
    if ( !equal )
      return FALSE;
  }
  return TRUE;
}

/*----------------------------------------------------------------*/

/* DeleteNode_list
 * Deletes the current node n of list l.
 * Returns the new list.
 * Conditions:
 *   n must belong to l.
 *   n !=NULL. l !=NULL.
 */
ListTyp DeleteNode_list( n, l )
     ListTyp n,l;
{
  ListTyp pNode;

  LASSERT ((n!=NULL)&&(l!=NULL));/* alt: if ((n==NULL)||(l==NULL)) return l; */
  if (l==n)
    l=l->next;
  else {
    for ( pNode=l ; (pNode != NULL) && (pNode->next != n) ; pNode=pNode->next )
      ;
    if (pNode!=NULL)
      pNode->next = n->next;
    else
      Error("Node to be deleted doesn't belong to the list.");
  }
  n->next = NULL;
  Disp_list( n );
  return l;
}

/*----------------------------------------------------------------*/

/* ExtractNode_list
 * Takes out the current node n of list l.
 * Returns the new list. It works like DeleteNode_list, but n is not deleted.
 * Conditions:
 *   n must belong to l.
 *   n !=NULL. l !=NULL.
 */
ListTyp ExtractNode_list( n, l )
     ListTyp n,l;
{
  register ListTyp pNode;

  LASSERT ((n!=NULL)&&(l!=NULL)); /*alt: if ((n==NULL)||(l==NULL)) return l; */
  if (l==n)
    l=l->next;
  else {
    for ( pNode=l ;(pNode->next != n) && (pNode != NULL); pNode=pNode->next );
    if (pNode!=NULL)
      pNode->next = n->next;
    else
      Error("Node to be extracted doesn't belong to the list.");
  }
  n->next = NULL;
  return l;
}

/*----------------------------------------------------------------*/

/* InsertBeforeNode_list
 * Insert element e before node n in list l
 */
ListTyp InsertBeforeNode_list( e, l, n )
     DataListTyp e;
     ListTyp l,n;
{
  ListTyp n1;
  register ListTyp prev;

  LASSERT( n!=NULL );

  n1 = Insert_list( e, Create_list());
  if (n==l) {
    n1->next=n;
    return n1;
  }

  for ( prev=l; prev->next!=n; prev=prev->next )
    if (prev->next==NULL)
      Error("AppendBeforeNode_list: node does not belong to the list");

  prev->next = n1;
  n1->next   = n;

  return l;
}

/*----------------------------------------------------------------*/

/* Join_ifnotIn_list
 * Selective Join_list.
 * Alike Join_list those elements of list l2 already in list l1 are not
 * appended , but disposed.
 */
/*
   ListTyp Join_ifnotIn_list( l1, l2, Eq, FreeInfo )
   ListTyp l;
   boolean (*Eq)();
   void (*FreeInfo)();
   {
   ToMake("Join_ifnotIn_list");
   }
   */

/*----------------------------------------------------------------*/

/* Length_list
 * list length
 */
int Length_list(l)
     register ListTyp l;
{
  int i;

  for (i=0;l!=NULL;i++)
    l=l->next;

  return i;
}

/*----------------------------------------------------------------*/

/* Stat_list
 * statistics about list nodes:
 *   *pin = total list nodes allocation queries.
 *   *pid = list node releases
 *   *pim = max list nodes used during execution
 */
void Stat_list( pin, pid, pim )
     int *pin, *pid, *pim;
{
  *pin = new_node_count;
  *pid = released_node_count;
  *pim = max_node_count;
}

/*----------------------------------------------------------------*/

/* Last_list
 * returns the last list node
 */
ListTyp Last_list( l )
     ListTyp l;
{
  LASSERT( l!=NULL );
  while ( l->next!=NULL )
    l = l->next;
  return l;
}

/*----------------------------------------------------------------*/


/* Init_list
 * Initialize the module
 */
void Init_list()
{
#ifdef SDEBUG
  new_node_count      = 0;
  released_node_count = 0;
  max_node_count = 0;
#endif
}



