/* File: listeord.c */
/* Time-stamp: "2001-05-09 00:46:06 calvanes" */
/* Scopo: funzioni non-elementari sulle liste che necessitano di effettuare il
          confronto di ordinamento tra elementi
*/

/* Richiede le seguenti definizioni preliminari:

   typedef ... TipoElemLista;

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

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

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

*/


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'ordinamento tra elementi.
     Versione iterativa. Utilizza nodo generatore. */
{
  TipoLista corr,         /* usato per la scansione della lista */
            paux;

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

                /* ricerca della posizione in cui inserire il nuovo elemento */
  corr = *lis;
  while (corr->next != NULL && MinoreElemento(corr->next->info, elem))
    corr = corr->next;

                                        /* concatenazione del nuovo elemento */
  paux = malloc(sizeof(NodoLista));          /* 1 */
  paux->info = elem;                         /* 2 */
  paux->next = corr->next;                   /* 3 */
  corr->next = paux;                         /* 4 */

                                         /* eliminazione del nodo generatore */
  paux = *lis;
  *lis = paux->next;
  free(paux);
}  /* 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 */