/* File: listeord.c */
/* Time-stamp: "2002-05-20 18:52:57 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 *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 iterativa. Utilizza nodo generatore. */
{
  TipoLista corr,         /* usato per la scansione della lista */
            aux;

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

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

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

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