{ File: listeord.pas }

{ Scopo: operazioni su liste collegate semplici:
         - versione iterativa delle operazioni che richiedono confronti di
           ordinamento 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 MinoreElemento (elem1, elem2: TipoElemLista): boolean;
  begin
    ...
  end;

}


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 iterativa. Utilizza record generatore. }
var
  corr,                { usato per la scansione della lista }
  paux    : TipoLista;
  trovato : boolean;   { indica se la posizione corretta e` stata trovata }
begin
  { creazione del record generatore }
  new(paux);
  paux^.next := lis;
  lis := paux;

  { ricerca della posizione in cui inserire il nuovo elemento }
  corr := lis;
  trovato := FALSE;
  while (corr^.next <> NIL) and (not trovato) do
    if MinoreElemento(corr^.next^.info, elem) then
      corr := corr^.next
    else   { l'elemento in testa e` maggiore o uguale a elem }
      trovato := TRUE;      { forza il termine della scansione }

  { concatenazione del nuovo elemento }
  new(paux);                { 1 }  { alloca un record per il nuovo elemento }
  paux^.info := elem;       { 2 }
  paux^.next := corr^.next; { 3 }
  corr^.next := paux;       { 4 }

  { eliminazione del record generatore }
  paux := lis;
  lis := paux^.next;
  dispose(paux)
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 }