{ File: listecon.pas }

{ Scopo: operazioni su liste collegate semplici:
         - versione iterativa delle operazioni che richiedono confronti di
           uguaglianza tra elementi
}

{ Richiede le seguenti definizioni preliminari:

  type
    TipoElemLista   = ...;
    TipoLista       = ^TipoRecordLista;
    TipoRecordLista = record
                        info : TipoElemLista;
                        next : TipoLista
                      end;

  function UgualeElemento (elem1, elem2: TipoElemLista): boolean;
  begin
    ...
  end;

}


function EsisteInLista (lis: TipoLista; elem: TipoElemLista): boolean;
{ Restituisce TRUE se l'elemento elem compare nella lista lis,
  FALSE altrimenti.
  Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
  Versione iterativa. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
begin
  trovato := FALSE;
  while (lis <> NIL) and (not trovato) do
    if UgualeElemento(lis^.info, elem) then
      trovato := TRUE       { forza l'uscita dal ciclo }
    else
      lis := lis^.next;
  EsisteInLista := trovato
end; { EsisteInLista }


procedure TrovaElementoLista (var lis: TipoLista; elem: TipoElemLista);
{ Aggiorna lis alla sottolista che ha elem come primo elemento.
  Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
  Versione iterativa. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
begin
  trovato := FALSE;
  while (lis <> NIL) and (not trovato) do
    if UgualeElemento(lis^.info, elem) then
      trovato := TRUE
    else
      lis := lis^.next
end; { TrovaElementoLista }


procedure CancellaElementoLista (var lis: TipoLista; elem: TipoElemLista);
{ Cancella la prima occorrenza dell'elemento elem dalla lista lis.
  Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
  Versione iterativa senza utilizzo di record generatore. }
var
  prec,                { puntatore all'elemento precedente }
  corr    : TipoLista; { puntatore all'elemento corrente }
  trovato : boolean;   { booleano usato per terminare la scansione }
begin
  if lis <> NIL then
    if UgualeElemento(lis^.info, elem) then
    begin { cancellazione del primo elemento }
      prec := lis;
      lis := lis^.next;
      dispose(prec)
    end
    else
    begin { scansione della lista e cancellazione dell'elemento }
      prec := lis;
      corr := prec^.next;             { 1 }
      trovato := FALSE;
      while (corr <> NIL) and (not trovato) do
        if UgualeElemento(corr^.info, elem) then
        begin { cancellazione dell'elemento }
          trovato := TRUE;            { forza l'uscita dal ciclo }
          prec^.next := corr^.next;   { 2 }
          dispose(corr)               { 3 }
        end
        else
        begin { avanzamento dei due puntatori }
          prec := prec^.next;
          corr := prec^.next          { 1 }
        end
    end
end; { CancellaElementoLista }


procedure CancellaTuttiLista (var lis: TipoLista; elem: TipoElemLista);
{ Cancella tutte le occorrenze dell'elemento elem dalla lista lis.
  Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
  Versione iterativa. Utilizza 1 puntatore e record generatore. }
var
  prec,             { puntatore usato per la scansione della lista }
  aux : TipoLista;  { puntatore ausiliario }
begin
  { creazione del record generatore }
  new(prec);                     { 1 }
  prec^.next := lis;             { 2 }
  lis := prec;                   { 3 }

  { scansione della lista e cancellazione degli elementi }
  while prec^.next <> NIL do
    if UgualeElemento(prec^.next^.info, elem) then
    begin
      aux := prec^.next;         { 4 }
      prec^.next := aux^.next;   { 5 }
      dispose(aux)               { 6 }
    end
    else
      prec := prec^.next;

  { eliminazione del record generatore }
  prec := lis;
  lis := prec^.next;
  dispose(prec)
end; { CancellaTuttiLista }