/* File: listealt.c */
/* Time-stamp: "2001-05-08 19:28:03 calvanes" */
/* Scopo: funzioni non-elementari sulle liste realizzate attraverso l'uso delle
          funzioni elementari
*/

/* Richiede le seguenti definizioni preliminari:

   typedef ... TipoElemLista;

   struct StructLista {
     TipoElemLista info;
     struct StructLista *next;
   };
   
   typedef struct StructLista TipoNodoLista;
   typedef TipoNodoLista *TipoLista;

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

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

*/


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


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


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

  paux = malloc(sizeof(TipoNodoLista));   /* 1 */
  paux->info = elem;                      /* 2 */
  paux->next = *lis;                      /* 3 */
  *lis = paux;                            /* 4 */
}  /* InserisciTestaLista */


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


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


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

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


void InserisciCodaLista(TipoLista *lis, TipoElemLista elem)
  /* Inserisce l'elemento elem in coda alla lista lis.
     Versione iterativa. */
{
  TipoLista ultimo;   /* puntatore usato per la scansione */
  TipoLista paux;

                      /* creazione del record che contiene il nuovo elemento */
  paux = malloc(sizeof(TipoNodoLista));   /* 1 */
  paux->info = elem;
  paux->next = NULL;                 /* il record sara` l'ultimo della lista */
  if (*lis == NULL)
    *lis = paux;
  else {
    ultimo = *lis;
    while (ultimo->next != NULL)
      ultimo = ultimo->next;
                       /* concatenazione del nuovo record in coda alla lista */
    ultimo->next = paux;                  /* 2 */
  }
}  /* InserisciCodaLista */


void CopiaLista(TipoLista lis, TipoLista *copia)
  /* Restituisce una copia della lista lis.
     Versione che usa le operazioni elementari. */
{
  TipoElemLista testa;

  if (TestListaVuota(lis))
    InitLista(copia);
  else {                             /* aggiornamento di lis al resto di lis */
    TestaLista(lis, &testa);         /* memorizzazione della testa */
    RestoLista(&lis);
    CopiaLista(lis, copia);          /* copia del resto */
                                     /* inserimento della testa nella copia */
    InserisciTestaLista(copia, testa);
  }
}  /* CopiaLista */


void CancellaLista(TipoLista *lis)
  /* Pone lis uguale alla lista vuota e rende disponibile la memoria occupata.
     Versione che usa le operazioni elementari. */
{
  if (!TestListaVuota(*lis)) {
    CancellaPrimoLista(lis);
    CancellaLista(lis);
  }
}  /* CancellaLista */


void InvertiLista(TipoLista *lis)
  /* Inverte la lista lis.  Versione iterativa. */
{
  TipoLista prec = NULL; /* puntatore all'elemento che precede quello corrente */
  TipoLista suc;      /* puntatore all'elemento successivo a quello corrente */

  while (*lis != NULL) {
    suc = *lis;
    *lis = (*lis)->next;
    suc->next = prec;
    prec = suc;
  }
  *lis = prec;
}  /* 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 che usa altre operazioni. */
{
  bool trovato = FALSE;   /* indica se l'elemento e` stato trovato */
  TipoElemLista primo;

  while (!TestListaVuota(lis) && !trovato) {
    TestaLista(lis, &primo);                  /* memorizza in primo la testa */
    if (UgualeElemento(primo, elem))
      trovato = TRUE;                            /* forza l'uscita dal ciclo */
    else
      RestoLista(&lis);                 /* aggiorna lis al resto della lista */
  }
  return trovato;
}  /* EsisteInLista */


void TrovaElementoLista(TipoLista *lis, TipoElemLista elem)
  /* Aggiorna lis alla sottolista che ha elem come primo elemento.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione che usa altre operazioni. */
{
  bool trovato = FALSE;   /* indica se l'elemento e` stato trovato */
  TipoElemLista primo;

  while (!TestListaVuota(*lis) && !trovato) {
    TestaLista(*lis, &primo);
    if (UgualeElemento(primo, elem))
      trovato = TRUE;
    else
      RestoLista(lis);
  }
}  /* TrovaElementoLista */


void CancellaElementoLista(TipoLista *lis, TipoElemLista elem)
  /* Cancella la prima occorrenza dell'elemento elem dalla lista lis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione che usa le operazioni elementari. */
{
  TipoElemLista testa;

  if (!TestListaVuota(*lis)) {
    TestaLista(*lis, &testa);              /* memorizza la testa della lista */
    CancellaPrimoLista(lis);                            /* cancella la testa */
    if (!UgualeElemento(testa, elem)) {
      CancellaElementoLista(lis, elem);           /* cancella elem dal resto */
      InserisciTestaLista(lis, testa);               /* reinserisce la testa */
    }
  }
}  /* CancellaElementoLista */


void CancellaTuttiLista(TipoLista *lis, TipoElemLista elem)
  /* Cancella tutte le  occorrenze dell'elemento elem dalla lista lis.
     Versione che usa altre operazioni. */
{
  while (EsisteInLista(*lis, elem))
    CancellaElementoLista(lis, elem);
}  /* CancellaTuttiLista */


/* Funzioni che operano su liste ordinate (versioni iterative o che usano le
   operazioni elementari). */


void InserisciInListaOrdinata(TipoLista *lis, TipoElemLista elem)
  /* Inserisce l'elemento elem nella lista lis ordinata per elementi crescenti,
     mantenendo l'ordinamento.
     Chiama MinoreElemento per verificare l'ordinameto tra elementi.
     Versione che usa le operazioni elementari. */
{
  TipoElemLista testa;

  if (TestListaVuota(*lis))
    InserisciTestaLista(lis, elem);
  else {
    TestaLista(*lis, &testa);                  /* memorizzazione della testa */
    if (!MinoreElemento(testa, elem))
      InserisciTestaLista(lis, elem);
    else {                      /* inserimento di elem nel resto della lista */
      CancellaPrimoLista(lis);
      InserisciInListaOrdinata(lis, elem);
      InserisciTestaLista(lis, testa);
    }
  }
}  /* 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 *lis, TipoElemLista elem)
  /* Aggiorna lis alla sottolista che ha elem come primo elemento.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa. */
{
  bool trovato = FALSE;

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


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

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