(* Ohjelmointi (Pascal)
 * Tehtävät 12.1 & 12.2 & 12.3
 *
 * © 1996 by allan@iki.fi *)

program h12t123(input, output);

type
   joukko = ^arvo;
   arvo   = record
               luku : integer;
               next : joukko;
            end;    

var
   A, B, C, apu : joukko;
   i            : integer;


procedure Poista(var J : joukko);
var next : joukko;
begin
   next := J;
   while (next <> nil) do begin
      J := next;
      next := next^.next;
      dispose(J);
   end;
end;

procedure Lisaa(var p : joukko; i : integer);
begin
   new(p^.next);
   p := p^.next;
   p^.luku := i;
   p^.next := nil;
end;


(* 12.1 Joukko esitetään järjestämättömänä listana, jossa luku voi
 *      esiintyä moneen kertaan. Toteuta operaatiot Yhdiste ja Kuuluu. *)

function Yhdiste(X, Y : joukko) : joukko;
var uusi, apu : joukko;
begin
   uusi := nil;
   apu := nil;

   if (X <> nil) then begin
      new(uusi);
      uusi^.luku := X^.luku;
      uusi^.next := nil;
      X := X^.next;
      apu := uusi;
      while (X <> nil) do begin
         Lisaa(apu, X^.luku);
         X := X^.next;
      end;
   end;

   if (Y <> nil) then begin
      if (apu = nil) then begin
         new(uusi);
         uusi^.luku := Y^.luku;
         uusi^.next := nil;
         Y := Y^.next;
         apu := uusi;
      end;
      while (Y <> nil) do begin
         Lisaa(apu, Y^.luku);
         Y := Y^.next;
      end;
   end;

   Yhdiste := uusi;
end; { Yhdiste }

function Kuuluu(e : integer; X : joukko) : boolean;
var loytyi, eioo : boolean;
begin
   loytyi := false;
   eioo := false;
   while not loytyi and not eioo and (X <> nil) do begin
      if X^.luku = e then
         loytyi := true
      else if X^.luku > e then
         eioo := true
      else
         X := X^.next;
   end;
   Kuuluu := loytyi;
end; { Kuuluu }

(* 12.2 Joukko esitetään nousevasti järjestettynä listana, jossa luku voi
 *      esiintyä vain kerran. Toteuta operaatiot Leikkaus ja Kuuluu. *)

function Kuuluu2(e : integer; X : joukko) : Boolean;
begin
   { Sama kuin 12.1 }
   Kuuluu2 := Kuuluu(e, X);
end; { Kuuluu2 }

function Leikkaus(X, Y : joukko) : joukko;

var uusi, apu : joukko;

   procedure Jarjesta(J : joukko);
   var p, q : joukko;
      procedure VaihdaTiedot(a, b : joukko);
      var x : integer;
      begin
         x := a^.luku;
         a^.luku := b^.luku;
         b^.luku := x;
      end;
   begin
      p := J;
      while (p <> nil) do begin
         q := p^.next;
         while (q <> nil) do begin
            if q^.luku < p^.luku then
               VaihdaTiedot(p, q);
            q := q^.next;
         end;
         p := p^.next;
      end;
   end;

begin
   uusi := nil;
   apu := nil;
   if (X <> nil) and (Y <> nil) then begin
      while (X <> nil) and (uusi = nil) do
         if not Kuuluu(X^.luku, Y) then
            X := X^.next
         else begin
            new(uusi);
            uusi^.luku := X^.luku;
            uusi^.next := nil;
            X := X^.next;
            apu := uusi;
         end;
      while (X <> nil) do begin
         if Kuuluu(X^.luku, Y) then
            Lisaa(apu, X^.luku);
         X := X^.next;
      end;
   end;
   if (uusi <> nil) then
      Jarjesta(uusi);
   Leikkaus := uusi;
end; { Leikkaus }

(* 12.3 Pohdi ja selitä piirroksin, millaisia operaatiot ovat eri tieto-
 *      rakenneratkaisuissa: lista on järjestetty tai järjestämätön, luku 
 *      voi esiintyä vain kerran tai monta kertaa, Miten asiaan vaikuttaa, 
 *      jos todelliset parametrit saavat muuttua?
 *
 * Ei järjestäytyneisyys juuri vaikuta sen kummemmin ... käytössä oleva
 * linkitetty lista on luonteeltaan melko tehoton. Etsinnöissä pitää aina
 * selata listaa läpi alkaen alusta. Binäärihakua ei voida hyödyntää,
 * sillä listaa ei voida 'indeksoida' suoraan kuten taulukkoa, ja
 * tällaisen 'indeksoinnin' toteutus (binäärihakua varten) tekisi hausta
 * *todella* epätehokkaan.
 *
 * Luvun esiintymiskertojen rajoittaminen yhteen on hyvä jos joukkoihin
 * lisätään alkioita paljon (kuten esim. tehtävässä 11.3 Tyylianalyysi-
 * ohjelma), sillä se alkaisi viedä muistia jo aika paljon. Jos
 * analysoitavana tiedostona olisi esimerkiksi juuri tehtävän 11.3
 * lähdekoodi (minun ratkaisun pituus oli 2001 tavua), niin muistitarve
 * olisi
 *         2001 * sizeof(arvo) =
 *         2001 * (sizeof(integer)+sizeof(^arvo)) =
 *         2001 * (32+32) =
 *         128064b =
 *         16008 tavua =
 *         15.6k
 *         !
 *)

{ TESTIPÄÄOHJELMA }

procedure out(p : joukko);
begin
   while (p <> nil) do begin
      write(p^.luku:1, ' ');
      p := p^.next;
   end;
end;

begin
   writeln('TEHTÄVÄT 12.1 & 12.2 & 12.3');
   writeln('===========================');
   writeln('Anna kaksi numerosarjaa.');
   
   write('1> ');
   read(i);
   new(A);
   A^.luku := i;
   A^.next := nil;
   apu := A;
   while not eoln do begin
      read(i);
      Lisaa(apu, i);
   end;
   
   write('2> ');
   read(i);
   new(B);
   B^.luku := i;
   B^.next := nil;
   apu := B;
   while not eoln do begin
      read(i);
      Lisaa(apu, i);
   end;
   
   C := Yhdiste(A, B);
   write('Yhdiste: ');
   out(C);
   writeln;
   
   Poista(C);
   
   C := Leikkaus(A, B);
   write('Leikkaus: ');
   out(C);
   writeln;
end.