{ File: liste.pas }

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

{ Richiede le seguenti definizioni preliminari:

  type
    TipoElemLista   = ...;
    TipoLista       = ^TipoRecordLista;
    TipoRecordLista = record
                        info : TipoElemLista;
                        next : TipoLista
                      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 CancellaLista (var lis: TipoLista);
{ Pone lis uguale alla lista vuota e rende disponibile la memoria occupata.
  Versione iterativa. }
var
  paux : TipoLista;
begin
  while lis <> NIL do
  begin
    paux := lis;
    lis := lis^.next;
    dispose(paux)
  end
end; { CancellaLista }


procedure CopiaLista (lis: TipoLista; var copia: TipoLista);
{ Restituisce in copia una copia della lista lis.
  Versione iterativa. Utilizza record generatore. }
var
  prec : TipoLista; { puntatore all'elemento precedente }
begin
  { creazione del record generatore }
  new(prec);
  { scansione e copia della lista }
  copia := prec;
  while lis <> NIL do
  begin { copia dell'elemento corrente di lis }
    new(prec^.next);
    prec := prec^.next;
    prec^.info := lis^.info;
    lis := lis^.next
  end;
  prec^.next := NIL;  { chiusura della lista }
  { eliminazione del record generatore }
  prec := copia;
  copia := copia^.next;
  dispose(prec)
end; { CopiaLista }


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 }