{ File: fusione.pas }

program FusioneListeOrdinate;
{ Costruisce due liste ordinate a partire da due file che contengono sequenze
  di interi non ordinate, poi fonde le due liste in un'unica lista ordinata.
  La lista risultante viene costruita creando nuovi record in memoria,
  cosi' le due liste di partenza continuano a esistere. }


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

var
  lista1, lista2, lista3 : TipoLista;
  nomef                  : string;
  memoria                : longint;

{ ----------------- }

  procedure InserisciInListaOrdinata (var lis:TipoLista; elem:TipoElemLista);
  var
    paux : TipoLista;
  begin
    if lis = NIL then
    begin
      new(lis);
      lis^.info := elem;
      lis^.next := NIL
    end
    else if lis^.info >= elem then
    begin
      new(paux);
      paux^.info := elem;
      paux^.next := lis;
      lis := paux
    end
    else InserisciInListaOrdinata(lis^.next, elem)
  end; {InserisciInListaOrdinata}

{ ----------------- }

  procedure LeggiListaOrdinata(var lis:TipoLista; nomefile:string);
  var
    filetesto : text;
    e         : TipoElemLista;

  begin
    assign(filetesto, nomefile);
    reset(filetesto);
    lis := NIL;
    while not eof(filetesto) do begin
      read(filetesto, e);
      InserisciInListaOrdinata(lis, e)
    end
  end; {LeggiListaOrdinata}

{ ----------------- }

  procedure StampaLista(lis:TipoLista);
  begin
    if lis = NIL then
      writeln('Lista vuota')
    else
    begin
      while lis <> NIL do
      begin
        write (lis^.info:4);
        lis:=lis^.next
      end;
    end;
    writeln
  end; {StampaLista}

{ ----------------- }

  procedure FondiListe (lis1, lis2: TipoLista; var lisf: TipoLista);
  { Fonde le liste lis1, lis2 nella lista lisf.

    In questa versione la nuova lista viene costruita replicando i
    record delle due liste di partenza, quindi dopo la fusione le due
    liste di partenza "sopravvivono" all'operazione. }

  var
    pgen, ultimo : TipoLista;
  begin
    new(pgen);     { creazione record generatore per lisf }
    ultimo := pgen;
    while (lis1 <> NIL) and (lis2 <> NIL) do
    begin
      new(ultimo^.next);
      { viene creato un nuovo nodo, appeso alla lista lisf dopo ultimo }
      ultimo := ultimo^.next;	 { ultimo viene aggiornato }
      if lis1^.info < lis2^.info then
      begin    { se il nodo della prima lista e' piu' piccolo, va aggiunto: }
        ultimo^.info := lis1^.info;
        lis1 := lis1^.next
        { lis1 viene aggiornato per indicare il prossimo elemento da
          controllare nella prima lista }
      end
      else     { se il nodo della seconda lista e' piu' piccolo, va aggiunto: }
      begin
        ultimo^.info := lis2^.info;
        lis2 := lis2^.next
        { lis2 viene aggiornato per indicare il prossimo elemento da
          controllare nella seconda lista }
      end
    end; { while }
    { A questo punto una delle due liste e' finita.  Quindi dobbiamo solo
      aggiungere alla lista puntata da lisf i daticontenuti nel resto della
      lista non vuota. }

    { NB: dei due while, uno solo viene eseguito }
    while lis1 <> NIL do
    begin
      new(ultimo^.next);
      ultimo := ultimo^.next;
      ultimo^.info := lis1^.info;
      lis1 := lis1^.next
    end;

    while lis2 <> NIL do
    begin
      new(ultimo^.next);
      ultimo := ultimo^.next;
      ultimo^.info := lis2^.info;
      lis2 := lis2^.next
    end;
    ultimo^.next := NIL;
    { l'ultimo nodo della lista deve puntare a nil }
    lisf := pgen^.next;
    { la terza lista e' completa; bisogna eliminare il record generatore per
      lisf, che inizia subito dopo pgen }
    dispose(pgen);
  end; { FondiListe }


{ ----------------- }

  procedure FondiListe2 (var lis1, lis2: TipoLista; var lisf: TipoLista);

  { Versione alternativa della procedura FondiListe in cui la lista lisf
    viene costruita usando direttamente i record delle due liste di partenza
    che quindi sopravvivono all'operazione di fusione.
    Le liste lis1 e lis2 devono diventare NIL dopo la fusione,
    dato che le liste cui puntavano sono state distrutte. }

  var
    pgen, ultimo : TipoLista;

  begin
    new(pgen);     { creazione record generatore per lisf }
    ultimo := pgen;
    while (lis1 <> NIL) and (lis2 <> NIL) do
    begin
      if lis1^.info < lis2^.info then
      begin { Se il nodo della prima lista e' piu' piccolo, deve essere
              inserito nella lista lisf: pertanto il nodo viene attaccato dopo
              quello puntato da ultimo, ultimo viene aggiornato all'elemento
              appena inserito e lis1 viene spostato per puntare all'elemento
              successivo della prima lista. }
        ultimo^.next := lis1;
        ultimo:=ultimo^.next;
        lis1 := lis1^.next;
      end
      else
      begin { Se il nodo della prima lista e' piu' grande, allora e' il nodo
              della seconda lista a dover essere inserito nella lista lisf:
              pertanto il nodo puntato da lis2 viene attaccato dopo quello
              puntato da ultimo, ultimo viene aggiornato all'elemento appena
              inserito e lis2 viene spostato per puntare al prossimo elemento
              della seconda lista. }
        ultimo^.next:= lis2;
        ultimo:=ultimo^.next;
        lis2 := lis2^.next
      end
    end; { while }

    { A questo punto una delle due liste e' vuota, quindi dobbiamo solo
      appendere gli elementi contenuti nella lista non vuota e assegnare
      a questa NIL. }

    if lis1 <> NIL then
    begin
      ultimo^.next := lis1;
      lis1 := NIL
    end
    else
    begin
      ultimo^.next := lis2;
      lis2 := NIL
    end;

    { La terza lista e' completa.  Bisogna eliminare il record generatore per
      lisf, che inizia subito dopo pgen. }
    lisf := pgen^.next;
    dispose(pgen)
  end; { FondiListe2 }


{ ----------------- }

  procedure CancellaLista (var lis:TipoLista);
  var
    paux : TipoLista;
  begin
    while lis <> nil do
    begin
      paux := lis;
      lis := lis^.next;
      dispose(paux)
    end
  end; {CancellaLista}

{ ----------------- }


begin

{ Il PASCAL permette di verificare la quantita' di memoria utilizzabile per
  l'allocazione dinamica (heap) mediante la funzione MEMAVAIL, che e' priva
  di parametri. La funzione MEMAVAIL viene chiamata semplicemente scrivendone
  il nome e restituisce un valore di tipo LONGINT. }

  writeln('-----------------Inizio programma-----------');
  writeln;
  memoria := memavail;
  writeln('Memoria disponibile all''inizio del programma: ', memavail);
  writeln;
  write ('Inserire il nome del file contenente la prima lista: ');
  readln (nomef);
  LeggiListaOrdinata(lista1, nomef);
  writeln('Stampa della prima lista');
  StampaLista(lista1);
  writeln('Memoria utilizzata dopo la lettura della prima lista: ',
          memoria-memavail);
  writeln;
  write('Inserire il nome del nome file contenente la seconda lista: ');
  readln(nomef);
  LeggiListaOrdinata(lista2, nomef);
  writeln('Stampa della seconda lista');
  StampaLista(lista2);
  writeln('Memoria utilizzata dopo la lettura della seconda lista: ',
          memoria-memavail);
  FondiListe(lista1, lista2, lista3);
  writeln;
  writeln('Stampa della fusione delle due liste');
  StampaLista(lista3);
  writeln('Memoria utilizzata dopo la creazione della terza lista: ',
          memoria-memavail);
  CancellaLista(lista1);
  CancellaLista(lista2);
  CancellaLista(lista3);
  writeln;
  writeln('Memoria disponibile alla fine del programma : ', memavail);
  writeln;

  writeln('--------Fine programma, premere return---------');
  readln
end. { FusioneListeOrdinate }