{ File: listeric.pas }

{ Scopo: operazioni su liste collegate semplici:
         - versione ricorsiva delle operazioni non 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 ricorsiva. }
begin
  if lis = NIL then
  begin { restituzione della lista contenente solo elem }
    new(lis);
    lis^.info := elem;
    lis^.next := NIL
  end
  else
    InserisciCodaLista(lis^.next, elem)
end; { InserisciCodaLista }


procedure CopiaLista (lis: TipoLista; var copia: TipoLista);
{ Restituisce in copia una copia della lista lis.
  Versione ricorsiva. }
begin
  if lis = NIL then
    copia := NIL
  else
  begin
    new(copia);
    copia^.info := lis^.info;            { copia del primo elemento }
    CopiaLista(lis^.next, copia^.next)   { copia del resto }
  end
end; { CopiaLista }


procedure CancellaLista (var lis: TipoLista);
{ Pone lis uguale alla lista vuota e rende disponibile la memoria occupata.
  Versione ricorsiva.  Dealloca gli elementi dall'ultimo al primo. }
begin
  if lis <> NIL then
  begin
    CancellaLista(lis^.next);     { cancella il resto della lista }
    dispose(lis);                 { dealloca il primo elemento }
    lis := NIL
  end
end; { CancellaLista }


procedure InvertiLista (var lis: TipoLista);
{ Inverte la lista lis.
  Versione ricorsiva. }
var
  paux : TipoLista;
begin
  if lis <> NIL then
    if lis^.next <> NIL then
    begin
      paux := lis;
      lis := lis^.next;
      InvertiLista(lis);
      paux^.next^.next := paux;
      paux^.next := NIL
    end
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 ricorsiva. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
begin
  if lis = NIL then
    EsisteInLista := FALSE
  else if UgualeElemento(lis^.info, elem) then
    EsisteInLista := TRUE
  else
    EsisteInLista := EsisteInLista(lis^.next, elem)
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 ricorsiva. }
var
  trovato : boolean; { indica se l'elemento e` stato trovato }
begin
  if lis <> NIL then
    if (not UgualeElemento(lis^.info, elem)) then
    begin
      lis := lis^.next;
      TrovaElementoLista(lis, elem)
    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 ricorsiva. }
var
  paux : TipoLista;
begin
  if lis <> NIL then
    if UgualeElemento(lis^.info, elem) then
    begin { cancella il primo elemento }
      paux := lis;
      lis := lis^.next;
      dispose(paux)
    end
    else  { cancella elem dal resto }
      CancellaElementoLista(lis^.next, elem)
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 ricorsiva. }
var
  paux : TipoLista;
begin
  if lis <> NIL then
    if UgualeElemento(lis^.info, elem) then
    begin
      { cancellazione del primo elemento }
      paux := lis;
      lis := lis^.next;
      dispose(paux);
      { cancellazione di elem dal resto della lista }
      CancellaTuttiLista(lis, elem)
    end
    else
      CancellaTuttiLista(lis^.next, elem)
end; { CancellaTuttiLista }


{ Procedure che operano su liste ordinate (versioni ricorsive o iterative). }


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'ordinamento tra elementi.
  Versione ricorsiva. }
var
  paux : TipoLista;
begin
  if lis = NIL then
  begin
    new(paux);
    paux^.info := elem;
    paux^.next := NIL;
    lis := paux
  end
  else if (not MinoreElemento(lis^.info, elem)) then
  begin { l'elemento in testa e` maggiore o uguale a elem }
    new(paux);
    paux^.info := elem;
    paux^.next := lis;
    lis := paux
  end
  else { l'elemento in testa e` minore di elem }
    InserisciInListaOrdinata(lis^.next, elem)
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 }