/* File: listealt.c */
/* Time-stamp: "2002-05-20 18:48:01 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 *plis)
  /* Inizializza *plis 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 *plis. */
{
  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 *plis al resto di *plis.
     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 iterativa. */
{
  TipoLista ultimo;   /* puntatore usato per la scansione */
  TipoLista aux;

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


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

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


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


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

  while (*plis != NULL) {
    succ = *plis;
    *plis = (*plis)->next;
    succ->next = prec;
    prec = succ;
  }
  *plis = 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 *plis, TipoElemLista elem)
  /* Aggiorna *plis 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(*plis) && !trovato) {
    TestaLista(*plis, &primo);
    if (UgualeElemento(primo, elem))
      trovato = TRUE;
    else
      RestoLista(plis);
  }
}  /* 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 che usa le operazioni elementari. */
{
  TipoElemLista testa;

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


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


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


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'ordinameto tra elementi.
     Versione che usa le operazioni elementari. */
{
  TipoElemLista testa;

  if (TestListaVuota(*plis))
    InserisciTestaLista(plis, elem);
  else {
    TestaLista(*plis, &testa);                 /* memorizzazione della testa */
    if (!MinoreElemento(testa, elem))
      InserisciTestaLista(plis, elem);
    else {                      /* inserimento di elem nel resto della lista */
      CancellaPrimoLista(plis);
      InserisciInListaOrdinata(plis, elem);
      InserisciTestaLista(plis, 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 *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 */