MODULE liste2;
FROM InOut IMPORT WriteString, WriteLn,
           WriteCard, ReadCard;
FROM IO IMPORT RdKey;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
  skupZn = SET OF CHAR;
  brojevi = POINTER TO brojSlog;
  brojSlog = RECORD
      info:CARDINAL;
      veza:brojevi;
  END;
VAR
  lista : brojevi;
  menu,prazno:CHAR;

PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
(* dodaje broj pom na pocetak liste *)
VAR
  temp:brojevi;
BEGIN
  (* kreiramo novi element *)
  NEW(temp);
  temp^.info := br;
  (* treba da pokazuje na ostatak liste *)
  temp^.veza := lista;
  (* pocetak liste je novi element *)
  lista := temp;
END DodajPoc;

PROCEDURE Unos(VAR lista:brojevi);
(* dodaje n brojeva u listu *)
VAR
  n,i,br:CARDINAL;
BEGIN
  WriteString('unesite n (broj brojeva): ');
  ReadCard(n);
  FOR i:= 1 TO n DO
      WriteString("unesite broj ");
      WriteCard(i,0);
      WriteString(": ");
      ReadCard(br);
      DodajPoc(lista,br);
  END;
END Unos;

(* -- procedure za stampu -- *)

PROCEDURE Stampaj(lista:brojevi);
(* stampa sadrzaj liste na ekran *)
VAR
  temp:brojevi;
BEGIN
  WriteLn;
  WriteString("Sadrzaj liste:");
  WriteLn;
  temp:=lista;
  WHILE temp # NIL DO
      WriteCard(temp^.info,0);
      WriteLn;
      temp := temp^.veza;
  END;
END Stampaj;

PROCEDURE StampajK(VAR lista:brojevi);
(* stampa k-ti element (k unosi korisnik) *)
VAR
  temp:brojevi;
  k,brojac:CARDINAL;
BEGIN
  WriteString("unesite redni broj elementa:");
  ReadCard(k);
  temp:=lista;
  brojac := 1;
  WHILE (temp# NIL) AND (k>brojac) DO
    temp:=temp^.veza;
    INC(brojac);
  END;
  IF (temp#NIL) THEN
    WriteCard(temp^.info,2);
  ELSE
    WriteString("greska! - ne postoji element");
    WriteString(" u listi sa rednim brojem ");
    WriteCard(k,2);
  END;
  WriteLn();
END StampajK;

PROCEDURE StampajMinimum(VAR lista:brojevi);
(* nalazi i stampa minimalni element liste *)
VAR
  temp:brojevi;
  min:CARDINAL;
BEGIN
  IF (lista=NIL) THEN
    WriteString("prazna lista!");
  ELSE
    min:=lista^.info;
    temp:=lista^.veza;
    WHILE temp # NIL DO
      IF temp^.info < min THEN
        min := temp^.info;
      END;
      temp := temp^.veza;
    END;
    WriteString("Minimalni element liste je ");
    WriteCard(min,0);
  END;
  WriteLn;
END StampajMinimum;

(* -- pomocne procedure, bez ispisa  -- *)

PROCEDURE UListi(lista:brojevi; 
                 br: CARDINAL):BOOLEAN;
(* vraca da li se 'br' nalazi u listi 'lista' *)
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE (temp # NIL) AND (temp^.info # br) DO
    (* dok ne dodjemo do kraja liste 
       ili ne nadjemo broj *)
      temp := temp^.veza;
  END;
  IF temp#NIL THEN
    (* znaci da nismo na kraju liste, 
       tj da je nadjen broj *)
    RETURN TRUE;
  ELSE (* temp = NIL *)
    RETURN FALSE;
  END;
END UListi;

PROCEDURE IzbaciIzListe(VAR lista:brojevi; 
                        br: CARDINAL):BOOLEAN;
(* izbacuje broj 'br' iz liste, naravno ako 
   postoji i vraca da li je operacija uspesno 
   obavljena *)
VAR
  temp,prethodni:brojevi;
BEGIN
  (* proverimo da li je prvi element *)
  IF (lista # NIL) AND (lista^.info = br) THEN
    temp:=lista;
    lista :=lista^.veza;
    DISPOSE(temp);
    RETURN TRUE;
  ELSE
  (* trazimo u ostatku liste *)
    temp:=lista;
    prethodni:=NIL;
    WHILE (temp # NIL) AND (temp^.info # br) DO
        (* dok ne dodjemo do kraja liste 
           ili ne nadjemo broj *)
        prethodni:=temp;
        temp := temp^.veza;
    END;
    IF temp#NIL THEN
      (* znaci da nismo na kraju liste, 
         odnosno da smo nasli broj *)
      (* prevezemo listu oko elementa *)
      prethodni^.veza:=temp^.veza;
      DISPOSE(temp);
      RETURN TRUE;
    ELSE
      RETURN FALSE;
    END;
  END;
END IzbaciIzListe;

PROCEDURE IzbaciIzListeSve(VAR lista:brojevi; 
                        br: CARDINAL):CARDINAL;
(* izbacuje sve brojeve 'br' iz liste, naravno ako 
   postoje i vraca koliko ih je bilo *)
VAR
  temp,prethodni:brojevi;
  brojac : CARDINAL;
BEGIN
  brojac := 0;
  (* uklanjamo sa pocetka koliko je potrebno *)
  WHILE (lista # NIL) AND (lista^.info = br) DO
    temp:=lista;
    lista :=lista^.veza;
    DISPOSE(temp);
    INC(brojac);
  END;
  (* trazimo u ostatku liste *)
  IF (lista # NIL) THEN
    temp:=lista;
    WHILE (temp^.veza # NIL)  DO
        (* idemo do poslednjeg elementa liste *)
        prethodni:=temp;
        temp := temp^.veza;
        IF temp^.info = br THEN
          (* prevezemo listu oko elementa *)
          prethodni^.veza:=temp^.veza;
          DISPOSE(temp);
          INC(brojac);
          (* vracamo se jedan korak da bi 
          u novom krugu proverili i ovaj element *)
          temp := prethodni;
        END;
    END;
  END;
  RETURN brojac;
END IzbaciIzListeSve;

(* - procedure sa interakcijom sa korisnikom - *)

PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
(* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
VAR
  br:CARDINAL;
BEGIN
  WriteString("unesite broj za izbacivanje: ");
  ReadCard(br);
  IF IzbaciIzListe(lista,br) THEN
    WriteString("broj je izbacen iz liste");
  ELSE
    WriteString("greska! - broj ne postoji");
  END;
  WriteLn;
END IzbacivanjeEl;

PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
(* izbacuje sve primeke unetog broj iz liste 
   koristeci proceduru IzbaciIzListeSve *)
VAR
  br, ukupno:CARDINAL;
BEGIN
  WriteString("unesite broj za izbacivanje: ");
  ReadCard(br);
  ukupno := IzbaciIzListeSve(lista,br);
  WriteString("Iz liste je izbaceno ");
  WriteCard(ukupno,3);
  WriteString(" el.");
  WriteLn;
END IzbacivanjeElSvi;

PROCEDURE IzbacivanjeK(VAR lista:brojevi);
(* izbacuje k-ti element iz liste *)
VAR
  temp,tekuci:brojevi;
  k,brojac:CARDINAL;
BEGIN
  IF lista=NIL THEN
    WriteString("lista je prazna, nema ");
    WriteString("elemenata za izbacivanje");
  ELSE
    WriteString("unesite redni broj elementa");
    WriteString(" koji zelite izbaciti:");
    ReadCard(k);
    IF k=1 THEN (*izbacivanje prvog *)
      temp:=lista;
      lista := lista^.veza;
      DISPOSE(temp);
    ELSE
      tekuci := lista;
      brojac := 2; (*gledamo jedan unapred*)
      WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
        (* idemo kroz listu do k-tog el *)
        tekuci:=tekuci^.veza;
        INC(brojac);
      END;
      IF (tekuci^.veza#NIL) THEN
         (* pamtimo element za brisanje *)
         temp:=tekuci^.veza;
         (* prevezujemo listu oko njega*)
         tekuci^.veza:=tekuci^.veza^.veza;
         DISPOSE(temp);
      ELSE
        WriteString("greska! - ne postoji el ");
        WriteString("u listi sa rednim brojem ");
        WriteCard(k,2);
      END;
      WriteLn();
    END;
  END;
END IzbacivanjeK;

PROCEDURE Pretraga(lista:brojevi);
(* provera da li se uneti broj nalazi u listi *)
VAR
  br:CARDINAL;
BEGIN
  WriteString("unesite trazeni broj");
  ReadCard(br);
  IF UListi(lista,br) THEN
    WriteString("broj postoji u listi");
  ELSE
    WriteString("broj ne postoji u listi");
  END;
  WriteLn;
END Pretraga;

(* -- oslobadjanje memorije -- *)

PROCEDURE Unisti(VAR lista:brojevi);
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE temp # NIL DO
        lista:=lista^.veza;
        DISPOSE(temp);
        temp:=lista;
  END;
END Unisti;

BEGIN
  (* pocinjemo od prazne liste *)
  lista := NIL;
  REPEAT
     WriteLn;
     WriteString("Ilustracija rada sa");
     WriteString(" listama brojeva");
     WriteLn;
     WriteString("=============================");
     WriteLn;
     WriteString("s - Stampa");WriteLn;
     WriteString("u - Unos");WriteLn;
     WriteString("i - Izbacivanje br iz liste");
     WriteLn;
     WriteString("v - izbacivanje svih br iz liste");
     WriteLn;
     WriteString("e - izbacivanje k-tog El.");
     WriteLn;
     WriteString("k - stampanje k-tog elementa");
     WriteLn;
     WriteString("m - Minimalni broj u listi");
     WriteLn;
     WriteString("p - Pretraga el. u listi");
     WriteLn;
     WriteLn;
     WriteString("q - kraj rada (Quit)");WriteLn;
      REPEAT
        menu := CAP(RdKey());
      UNTIL menu IN skupZn{'S','U','E','I','V',
                           'M','K','P','Q'};
      IF menu#'Q' THEN
        CASE menu OF
         'S' : Stampaj(lista);|
         'U' : Unos(lista);|
         'I' : IzbacivanjeEl(lista);|
         'V' : IzbacivanjeElSvi(lista);|
         'E' : IzbacivanjeK(lista);|
         'K' : StampajK(lista); |
         'M' : StampajMinimum(lista); |
         'P' : Pretraga(lista);|
        END;
        WriteLn;
        WriteString("--- pritisnite bilo koji ");
        WriteString("taster za povratak u meni");
        prazno:=RdKey();
      ELSE
        WriteString("Kraj rada")
      END;
      WriteLn;
  UNTIL menu='Q';
  Unisti(lista);
END liste2.