/* File: listeric.c */
/* Time-stamp: "2002-05-20 18:48:24 calvanes" */
/* Scopo: funzioni non-elementari sulle liste realizzate in modo ricorsivo */

/* Richiede le seguenti definizioni preliminari:

   typedef ... TipoElemLista;

   struct nodoLista {
     TipoElemLista info;
     struct nodoLista *next;
   };
   
   typedef struct nodoLista NodoLista;
   typedef NodoLista *TipoLista;

   bool UgualeElemento(TipoElemLista elem1, TipoElemLista elem2)
   {
     ...
   }

   bool MinoreElemento(TipoElemLista elem1, TipoElemLista elem2)
   {
     ...
   }

*/


void InitLista(TipoLista *plis)
  /* Inizializza lis alla lista vuota. */
{
  *plis = NULL;
}  /* InitLista */


bool TestListaVuota(TipoLista lis)
  /* Restituisce TRUE se lis e` la lista vuota, FALSE altrimenti. */
{
  return (lis == NULL);
}  /* TestListaVuota */


void InserisciTestaLista(TipoLista *plis, TipoElemLista elem)
  /* Inserisce l'elemento elem in testa alla lista lis. */
{
  TipoLista aux;

  aux = malloc(sizeof(NodoLista));       /* 1 */
  aux->info = elem;                      /* 2 */
  aux->next = *plis;                     /* 3 */
  *plis = aux;                           /* 4 */
}  /* InserisciTestaLista */


void TestaLista(TipoLista lis, TipoElemLista *pelem)
  /* Restituisce in *pelem l'elemento in testa alla lista lis. */
{
  if (lis != NULL)
    *pelem = lis->info;
}  /* TestaLista */


void RestoLista(TipoLista *plis)
  /* Aggiorna lis al resto di lis.
     La memoria occupata dal primo elemento non viene rilasciata. */
{
  if (*plis != NULL)
    *plis = (*plis)->next;
}  /* RestoLista */


void CancellaPrimoLista(TipoLista *plis)
  /* Cancella il primo elemento dalla lista *plis. */
{
  TipoLista aux;

  if (*plis != NULL) {
    aux = *plis;              /* 1 */
    *plis = (*plis)->next;    /* 2 */
    free(aux);                /* 3 */
  }
}  /* CancellaPrimoLista */


void InserisciCodaLista(TipoLista *plis, TipoElemLista elem)
  /* Inserisce l'elemento elem in coda alla lista *plis.
     Versione ricorsiva. */
{
  if (*plis == NULL) {      /* restituzione della lista contenente solo elem */
    *plis = malloc(sizeof(NodoLista));
    (*plis)->info = elem;
    (*plis)->next = NULL;
  } else
    InserisciCodaLista(&(*plis)->next, elem);
}  /* InserisciCodaLista */


void CopiaLista(TipoLista lis, TipoLista *copia)
  /* Restituisce una copia della lista lis.
     Versione ricorsiva. */
{
  if (lis == NULL)
    *copia = NULL;
  else {
    *copia = malloc(sizeof(NodoLista));          /* copia del primo elemento */
    (*copia)->info = lis->info;                           /* copia del resto */
    CopiaLista(lis->next, &(*copia)->next);
  }
}  /* CopiaLista */


void CancellaLista(TipoLista *plis)
  /* Pone *plis uguale alla lista vuota e rende disponibile la memoria
     occupata.
     Versione ricorsiva che usa un puntatore ausiliario. */
{
  TipoLista aux;

  if (*plis != NULL) {
    aux = (*plis)->next;   /* memorizza il puntatore all'elemento successivo */
    free(*plis);                               /* dealloca il primo elemento */
    CancellaLista(&aux);                    /* cancella il resto della lista */
    *plis = NULL;
  }
}  /* CancellaLista */


void InvertiLista(TipoLista *plis)
  /* Inverte la lista *plis. Versione ricorsiva. */
{
  TipoLista aux;

  if (*plis != NULL) {
    if ((*plis)->next != NULL) {
      aux = *plis;
      *plis = (*plis)->next;
      InvertiLista(plis);
      aux->next->next = aux;
      aux->next = NULL;
    }
  }
}  /* InvertiLista */


/* Funzioni che necessitano di effettuare il confronto di uguaglianza tra
   elementi. */


bool EsisteInLista(TipoLista lis, TipoElemLista elem)
  /* Restituisce TRUE se l'elemento elem compare nella lista lis,
     FALSE altrimenti.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione ricorsiva. */
{
  if (lis == NULL)
    return FALSE;
  else if (UgualeElemento(lis->info, elem))
    return TRUE;
  else
    return (EsisteInLista(lis->next, elem));
}  /* EsisteInLista */


void TrovaElementoLista(TipoLista *plis, TipoElemLista elem)
  /* Aggiorna *plis alla sottolista che ha elem come primo elemento.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione ricorsiva. */
{
  if (*plis != NULL) {
    if (!UgualeElemento((*plis)->info, elem)) {
      *plis = (*plis)->next;
      TrovaElementoLista(plis, elem);
    }
  }
}  /* TrovaElementoLista */


void CancellaElementoLista(TipoLista *plis, TipoElemLista elem)
  /* Cancella la prima occorrenza dell'elemento elem dalla lista *plis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione ricorsiva. */
{
  TipoLista aux;

  if (*plis != NULL)
    if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */
      aux = *plis;
      *plis = (*plis)->next;
      free(aux);
    } else                                        /* cancella elem dal resto */
      CancellaElementoLista(&(*plis)->next, elem);
}  /* CancellaElementoLista */


void CancellaTuttiLista(TipoLista *plis, TipoElemLista elem)
  /* Cancella tutte le occorrenze dell'elemento elem dalla lista *plis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione ricorsiva. */
{
  TipoLista aux;

  if (*plis != NULL)
    if (UgualeElemento((*plis)->info, elem)) {
                                         /* cancellazione del primo elemento */
      aux = *plis;
      *plis = (*plis)->next;
      free(aux);
                              /* cancellazione di elem dal resto della lista */
      CancellaTuttiLista(plis, elem);
    } else
      CancellaTuttiLista(&(*plis)->next, elem);
}  /* CancellaTuttiLista */


/* Funzioni che operano su liste ordinate (versioni ricorsive o iterative). */


void InserisciInListaOrdinata(TipoLista *plis, TipoElemLista elem)
  /* Inserisce l'elemento elem nella lista *plis ordinata per elementi
     crescenti, mantenendo l'ordinamento.
     Chiama MinoreElemento per verificare l'ordinamento tra elementi.
     Versione ricorsiva. */
{
  TipoLista aux;

  if (*plis == NULL) {
    aux = malloc(sizeof(NodoLista));
    aux->info = elem;
    aux->next = NULL;
    *plis = aux;
  } else if (!MinoreElemento((*plis)->info, elem)) {
                          /* l'elemento in testa e` maggiore o uguale a elem */
    aux = malloc(sizeof(NodoLista));
    aux->info = elem;
    aux->next = *plis;
    *plis = aux;
  } else                            /* l'elemento in testa e` minore di elem */
    InserisciInListaOrdinata(&(*plis)->next, elem);
}  /* InserisciInListaOrdinata */


bool EsisteInListaOrdinata(TipoLista lis, TipoElemLista elem)
  /* Restituisce TRUE se l'elemento elem compare nella lista ordinata lis,
     FALSE altrimenti.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa. */
{
  bool trovato = FALSE;   /* indica se elem e` stato trovato */
  bool continua = TRUE;   /* indica se la scansione deve contiuare */

  while (lis != NULL && continua) {
    if (UgualeElemento(lis->info, elem)) {
      trovato = TRUE;                               /* elem e` stato trovato */
      continua = FALSE;                       /* la scansione puo` terminare */
    } else if (MinoreElemento(elem, lis->info))
      continua = FALSE;              /* la scansione puo` terminare in quanto
                                        elem non puo` piu` comparire */
    else
      lis = lis->next;
  }
  return trovato;
}  /* EsisteInListaOrdinata */


void TrovaElementoListaOrdinata(TipoLista *plis, TipoElemLista elem)
  /* Aggiorna *plis alla sottolista che ha elem come primo elemento.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa. */
{
  bool trovato = FALSE;

  while (*plis != NULL && !trovato)
    if (UgualeElemento((*plis)->info, elem))
      trovato = TRUE;
    else if (MinoreElemento((*plis)->info, elem))
      *plis = NULL;
    else
      *plis = (*plis)->next;
}  /* TrovaElementoListaOrdinata */


void CancellaElementoListaOrdinata(TipoLista *plis, TipoElemLista elem)
  /* Cancella la prima occorrenza dell'elemento elem dalla lista *plis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa senza utilizzo di nodo generatore. */
{
  TipoLista prec;     /* puntatore usato per la scansione */
  TipoLista aux;
  bool continua;      /* usato per terminare la scansione */

  if (*plis != NULL)
    if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */
      aux = *plis;
      *plis = (*plis)->next;
      free(aux);
    } else {          /* scansione della lista e cancellazione dell'elemento */
      prec = *plis;
      continua = TRUE;
      while (prec->next != NULL && continua)
        if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */
          aux = prec->next;
          prec->next = aux->next;
          free(aux);
          continua = FALSE;
        }
        else if (MinoreElemento(elem, prec->next->info))
          continua = FALSE;
        else
          prec = prec->next;
    }
}  /* CancellaElementoListaOrdinata */