{ File: listealt.pas }

{ Scopo: operazioni su liste collegate semplici:
         - versione delle operazioni non elementari che fa uso delle operazioni
           elementari
}

{ 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 MinoreElemento (elem1, elem2: TipoElemLista): boolean;
  begin
    ...
  end;

}


procedure InitLista (var lis: TipoLista);
{ Inizializza lis alla lista vuota. }
begin
  lis := NIL
end; { InitLista }


function TestListaVuota (lis: TipoLista): boolean;
{ Restituisce TRUE se lis e` la lista vuota, FALSE altrimenti. }
begin
  TestListaVuota := (lis = NIL)
end; { TestListaVuota }


procedure InserisciTestaLista (var lis: TipoLista; elem: TipoElemLista);
{ Inserisce l'elemento elem in testa alla lista lis. }
var
  paux : TipoLista;
begin
  new(paux);           { 1 }
  paux^.info := elem;  { 2 }
  paux^.next := lis;   { 3 }
  lis := paux          { 4 }
end; { InserisciTestaLista }


procedure TestaLista (lis: TipoLista; var elem: TipoElemLista);
{ Restituisce in elem l'elemento in testa alla lista lis. }
begin
  if lis <> NIL then
    elem := lis^.info
end; { TestaLista }


procedure RestoLista (var lis: TipoLista);
{ Aggiorna lis al resto di lis.
  La memoria occupata dal primo elemento non viene rilasciata. }
begin
  if lis <> NIL then
    lis := lis^.next
end; { RestoLista }


procedure CancellaPrimoLista (var lis: TipoLista);
{ Cancella il primo elemento dalla lista lis. }
var
  paux : TipoLista;
begin
  if lis <> NIL then
  begin
    paux := lis;       { 1 }
    lis := lis^.next;  { 2 }
    dispose(paux)      { 3 }
  end
end; { CancellaPrimoLista }


procedure InserisciCodaLista (var lis: TipoLista; elem: TipoElemLista);
{ Inserisce l'elemento elem in coda alla lista lis.
  Versione iterativa. }
var
  ultimo,              { puntatore usato per la scansione }
  paux    : TipoLista;
begin
  { creazione del record che contiene il nuovo elemento }
  new(paux);                   { 1 }
  paux^.info := elem;
  paux^.next := NIL;   { il record sara` l'ultimo della lista }
  if lis = NIL then
    lis := paux
  else
  begin
    ultimo := lis;
    while ultimo^.next <> NIL do
      ultimo := ultimo^.next;
    { concatenazione del nuovo record in coda alla lista }
    ultimo^.next := paux       { 2 }
  end
end; { InserisciCodaLista }


procedure CopiaLista (lis: TipoLista; var copia: TipoLista);
{ Restituisce in copia una copia della lista lis.
  Versione che usa le operazioni elementari. }
var
  testa : TipoElemLista;
begin
  if TestListaVuota(lis) then
    InitLista(copia)
  else
  begin
    TestaLista(lis, testa);           { memorizzazione della testa }
    RestoLista(lis);                  { aggiornamento di lis al resto di lis }
    CopiaLista(lis, copia);           { copia del resto }
    InserisciTestaLista(copia, testa) { inserimento della testa nella copia }
  end
end; { CopiaLista }


procedure CancellaLista (var lis: TipoLista);
{ Pone lis uguale alla lista vuota e rende disponibile la memoria occupata.
  Versione che usa le operazioni elementari. }
begin
  if (not TestListaVuota(lis)) then
  begin
    CancellaPrimoLista(lis);
    CancellaLista(lis)
  end
end; { CancellaLista }


procedure InvertiLista (var lis: TipoLista);
{ Inverte la lista lis.  Versione iterativa. }
var
  prec,             { puntatore all'elemento precedente a quello corrente }
  suc  : TipoLista; { puntatore all'elemento successivo a quello corrente }
begin
  prec := NIL;
  while lis <> NIL do
  begin
    suc := lis;
    lis := lis^.next;
    suc^.next := prec;
    prec := suc
  end;
  lis:= prec
end; { InvertiLista }


{ Procedure che necessitano di effettuare il confronto di uguaglianza tra
  elementi. }


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 che usa altre operazioni. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
  primo   : TipoElemLista;
begin
  trovato := FALSE;
  while (not TestListaVuota(lis)) and (not trovato) do
  begin
    TestaLista(lis, primo); { memorizza in primo la testa }
    if UgualeElemento(primo, elem) then
      trovato := TRUE       { forza l'uscita dal ciclo }
    else
      RestoLista(lis)       { aggiorna lis al resto della lista }
  end;
  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 che usa altre operazioni. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
  primo   : TipoElemLista;
begin
  trovato := FALSE;
  while (not TestListaVuota(lis)) and (not trovato) do
  begin
    TestaLista(lis, primo);
    if UgualeElemento(primo, elem) then
      trovato := TRUE
    else
      RestoLista(lis)
  end
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 che usa le operazioni elementari. }
var
  testa : TipoElemLista;
begin
  if (not TestListaVuota(lis)) then
  begin
    TestaLista(lis, testa);   { memorizza la testa della lista }
    CancellaPrimoLista(lis);  { cancella la testa }
    if (not UgualeElemento(testa, elem)) then
    begin
      CancellaElementoLista(lis, elem); { cancella elem dal resto }
      InserisciTestaLista(lis, testa)   { reinserisce la testa }
    end
  end
end; { CancellaElementoLista }


procedure CancellaTuttiLista (var lis: TipoLista; elem: TipoElemLista);
{ Cancella tutte le  occorrenze dell'elemento elem dalla lista lis.
  Versione che usa altre operazioni. }
begin
  while EsisteInLista(lis, elem) do
    CancellaElementoLista(lis, elem)
end; { CancellaTuttiLista }


{ Procedure che operano su liste ordinate (versioni iterative o che usano le
  operazioni elementari). }


procedure InserisciInListaOrdinata (var lis: TipoLista; elem: TipoElemLista);
{ Inserisce l'elemento elem nella lista lis ordinata per elementi crescenti,
  mantenendo l'ordinamento.
  Chiama MinoreElemento per verificare l'ordinameto tra elementi.
  Versione che usa le operazioni elementari. }
var
  testa : TipoElemLista;
begin
  if TestListaVuota(lis) then
    InserisciTestaLista(lis, elem)
  else
  begin
    TestaLista(lis, testa);  { memorizzazione della testa }
    if (not MinoreElemento(testa, elem)) then
      InserisciTestaLista(lis, elem)
    else
    begin { inserimento di elem nel resto della lista }
      CancellaPrimoLista(lis);
      InserisciInListaOrdinata(lis, elem);
      InserisciTestaLista(lis, testa)
    end
  end
end; { InserisciInListaOrdinata }


function EsisteInListaOrdinata (lis: TipoLista; elem: TipoElemLista): boolean;
{ Restituisce TRUE se l'elemento elem compare nella lista ordinata lis,
  FALSE altrimenti.
  Chiama UgualeElemento per verificare l'uguaglianza tra elementi.
  Versione iterativa. }
var
  trovato,             { indica se elem e` stato trovato }
  continua : boolean;  { indica se la scansione deve contiuare }
begin
  trovato := FALSE;
  continua := TRUE;
  while (lis <> NIL) and continua do
    if UgualeElemento(lis^.info, elem) then
    begin
      trovato := TRUE;    { elem e` stato trovato }
      continua := FALSE   { la scansione puo` terminare }
    end
    else if MinoreElemento(elem, lis^.info) then
      continua := FALSE   { la scansione puo` terminare in quanto
                            elem non puo` piu` comparire }
    else
      lis := lis^.next;
  EsisteInListaOrdinata := trovato
end; { EsisteInListaOrdinata }


procedure TrovaElementoListaOrdinata (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;
begin
  trovato := FALSE;
  while (lis <> NIL) and (not trovato) do
    if UgualeElemento(lis^.info, elem) then
      trovato := TRUE
    else if MinoreElemento(lis^.info, elem) then
      lis := NIL
    else
      lis := lis^.next
end; { TrovaElementoListaOrdinata }


procedure CancellaElementoListaOrdinata (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 usato per la scansione }
  paux     : TipoLista;
  continua : boolean;   { booleano usato per terminare la scansione }
begin
  if lis <> NIL then
    if UgualeElemento(lis^.info, elem) then
    begin { cancellazione del primo elemento }
      paux := lis;
      lis := lis^.next;
      dispose(paux)
    end
    else
    begin { scansione della lista e cancellazione dell'elemento }
      prec := lis;
      continua := TRUE;
      while (prec^.next <> NIL) and continua do
        if UgualeElemento(prec^.next^.info, elem) then
        begin { cancella l'elemento }
          paux := prec^.next;
          prec^.next := paux^.next;
          dispose(paux);
          continua := FALSE
        end
        else if MinoreElemento(elem, prec^.next^.info) then
          continua := FALSE
        else
          prec := prec^.next
    end
end; { CancellaElementoListaOrdinata }