/* File: listecon.c */
/* Time-stamp: "2002-05-20 18:21:58 calvanes" */
/* Scopo: funzioni non-elementari sulle liste che necessitano di effettuare il
          confronto di uguaglianza tra elementi
*/

/* Richiede le seguenti definizioni preliminari:

   typedef ... TipoElemLista;

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

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

*/


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 iterativa. */
{
  bool trovato = FALSE;   /* indica se l'elemento e` stato trovato */

  while (lis != NULL && !trovato)
    if (UgualeElemento(lis->info, elem))
      trovato = TRUE;                            /* forza l'uscita dal ciclo */
    else
      lis = lis->next;
  return trovato;
}  /* EsisteInLista */


void TrovaElementoLista(TipoLista *plis, 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;    /* indica se l'elemento e` stato trovato */

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


void CancellaElementoLista(TipoLista *plis, 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 all'elemento precedente */
  TipoLista corr;    /* puntatore all'elemento corrente */
  bool trovato;      /* usato per terminare la scansione */

  if (*plis != NULL)
    if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */
      prec = *plis;
      *plis = (*plis)->next;
      free(prec);
    } else {         /* scansione della lista e cancellazione dell'elemento */
      prec = *plis;
      corr = prec->next;                      /* 1 */
      trovato = FALSE;
      while (corr != NULL && !trovato)
        if (UgualeElemento(corr->info, elem)) {       /* cancella l'elemento */
          trovato = TRUE;                        /* forza l'uscita dal ciclo */
          prec->next = corr->next;            /* 2 */
          free(corr);                         /* 3 */
        } else {                            /* avanzamento dei due puntatori */
          prec = prec->next;
          corr = prec->next;                  /* 1 */
        }
    }
}  /* CancellaElementoLista */


void CancellaElementoLista_1p_NoRG(TipoLista *plis, 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 corr;    /* puntatore ausiliario */
  bool trovato;      /* booleano usato per terminare la scansione */

  if (*plis != NULL)
    if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */
      corr = *plis;
      *plis = (*plis)->next;
      free(corr);
    } else {          /* scansione della lista e cancellazione dell'elemento */
      prec = *plis;
      trovato = FALSE;
      while (prec->next != NULL && !trovato)
        if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */
          trovato = TRUE;                        /* forza l'uscita dal ciclo */
          corr = prec->next;         /* 1 */
          prec->next = corr->next;   /* 2 */
          free(corr);                /* 3 */
        } else
          prec = prec->next;
    }
}  /* CancellaElementoLista */


void CancellaElementoLista_RG(TipoLista *plis, TipoElemLista elem)
  /* Cancella la prima occorrenza dell'elemento elem dalla lista lis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa con utilizzo di nodo generatore. */
{
  TipoLista prec;            /* puntatore usato per la scansione della lista */
  TipoLista corr;            /* puntatore ausiliario */
  bool trovato = FALSE;      /* usato per terminare la scansione */

                                            /* creazione del nodo generatore */
  prec = malloc(sizeof(NodoLista));
  prec->next = *plis;
  *plis = prec;

                      /* scansione della lista e cancellazione dell'elemento */
  while (prec->next != NULL && !trovato)
    if (UgualeElemento(prec->next->info, elem)) {     /* cancella l'elemento */
      trovato = TRUE;                            /* forza l'uscita dal ciclo */
      corr = prec->next;
      prec->next = corr->next;
      free(corr);
    } else
      prec = prec->next;
                                         /* eliminazione del nodo generatore */
  prec = *plis;
  *plis = prec->next;
  free(prec);
}  /* CancellaElementoLista */


void CancellaTuttiLista(TipoLista *plis, TipoElemLista elem)
  /* Cancella tutte le occorrenze dell'elemento elem dalla lista lis.
     Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
     Versione iterativa. Utilizza 1 puntatore e nodo generatore. */
{
  TipoLista prec;   /* puntatore usato per la scansione della lista */
  TipoLista corr;   /* puntatore ausiliario */

                                            /* creazione del nodo generatore */
  prec = malloc(sizeof(NodoLista));       /* 1 */
  prec->next = *plis;                     /* 2 */
  *plis = prec;                           /* 3 */

                     /* scansione della lista e cancellazione degli elementi */
  while (prec->next != NULL)
    if (UgualeElemento(prec->next->info, elem)) {
      corr = prec->next;                  /* 4 */
      prec->next = corr->next;            /* 5 */
      free(corr);                         /* 6 */
    } else
      prec = prec->next;

                                         /* eliminazione del nodo generatore */
  prec = *plis;
  *plis = prec->next;
  free(prec);
}  /* CancellaTuttiLista */