<* M2ADDTYPES + *>
IMPLEMENTATION MODULE zadatak;
(* Potrebno je raditi na 3 procedure, Hash, Ubaci i IzFajla.
   Test program se moze pokretati i bez modifikacija
   *)

IMPORT IO;
IMPORT FIO;

FROM Str IMPORT Length;
IMPORT Str;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
IMPORT HashT;

(* Potrebno je popraviti ovu funkciju da daje
    raznolike vrednosti radi efikasnijeg
    popunjavanja tabele.
*)
PROCEDURE Hash(elem: InfoTip) : CARDINAL;
VAR
  rez:CARDINAL;
  razlicitbroj,rezint, i, j, zbirreda, telem:INTEGER;
BEGIN
  rez:= 0;
  rezint:=0;
  zbirreda:=0;
  razlicitbroj:=4733;
  FOR i:=1 TO 3 DO
    FOR j:=1 TO 3 DO
      zbirreda:=zbirreda+(elem[i,j]*razlicitbroj) MOD 53;
      razlicitbroj:= (razlicitbroj * 7057) MOD 6073;
    END;
    razlicitbroj:= (razlicitbroj * 7883) MOD 6199;
    rezint:= rezint + ((zbirreda*zbirreda*razlicitbroj) MOD 6073);
    razlicitbroj:= (razlicitbroj * 5827) MOD 6569;
    zbirreda:=0;
  END;
  FOR j:=1 TO 3 DO
    FOR i:=1 TO 3 DO
      zbirreda:=zbirreda+(elem[i,j]*razlicitbroj) MOD 73;
      razlicitbroj:= (razlicitbroj * 5473) MOD 6073;
    END;
    razlicitbroj:= (razlicitbroj * 7096) MOD 6569;
    rezint:= rezint + ((zbirreda*zbirreda*razlicitbroj) MOD 5741);
    razlicitbroj:= (razlicitbroj * 4787) MOD 6199;
    zbirreda:=0;
  END;
  IF rezint < 0 THEN
    rez:= -17 * rezint;
  ELSE
    rez := rezint;
  END;
  rez := rez  MOD VelicinaTabele;
  RETURN rez;
END Hash;

(* Procedure vezane za InfoTip *)
(* =========================== *)

PROCEDURE Compare(e1: InfoTip; e2: InfoTip):INTEGER;
VAR
    i,j: CARDINAL;
    rez : INTEGER;
BEGIN
    rez := 0;
    i:=1;
    j:=1;
    WHILE (i<=Dim) AND (rez=0) DO
        IF (e1[i,j] > e2[i,j]) THEN
            rez := 1;
        ELSIF (e1[i,j] < e2[i,j]) THEN
            rez := -1;
        END;
        INC(j);
        IF j>Dim THEN
            j:=1;
            INC(i);
        END;
    END;
    RETURN rez;
END Compare;

PROCEDURE WrInfo(elem: InfoTip);
VAR
    i,j: CARDINAL;
BEGIN
    FOR i:=1 TO Dim DO
        FOR j:=1 TO Dim DO
            IO.WrInt(elem[i,j],0);
            IO.WrStr(" ");
        END;
        IO.WrLn;
    END;
END WrInfo;

PROCEDURE RdInfo(VAR elem: InfoTip);
VAR
    i,j : CARDINAL;
BEGIN
    FOR i:=1 TO Dim DO
      FOR j:=1 TO Dim DO
        IO.WrStr("unesite broj ");
        IO.WrCard(i,0);
        IO.WrStr(", ");
        IO.WrCard(j,0);
        IO.WrStr(":");
        IO.WrLn;
        elem[i,j] := IO.RdInt();
      END;
    END;
    IO.WrLn;
END RdInfo;

PROCEDURE FRdInfo(f: FIO.File; VAR elem: InfoTip);
VAR
    i,j : CARDINAL;
BEGIN
    FOR i:=1 TO Dim DO
      FOR j:=1 TO Dim DO
        elem[i,j] := FIO.RdInt(f);
      END;
    END;
    IF (FIO.Size(f)<FIO.GetPos(f)+2) THEN
        FIO.EOF := TRUE;
    END;
END FRdInfo;

PROCEDURE Inicijalizuj(VAR t:Tabela);
VAR
  i : CARDINAL;
BEGIN
  NEW(t);
  t^.ukupno := 0;
  FOR i := 0 TO VelicinaTabele - 1 DO
    t^.broj[i] := 0;
    NEW(t^.sadrzaj[i]);
    t^.sadrzaj[i]^.veza := t^.sadrzaj[i];
  END
END Inicijalizuj;

PROCEDURE Unisti(VAR t:Tabela);
VAR
  i : CARDINAL;
  pom : List;
BEGIN
  FOR i := 0 TO VelicinaTabele - 1 DO
    WHILE t^.sadrzaj[i]^.veza # t^.sadrzaj[i] DO
      pom := t^.sadrzaj[i]^.veza;
      t^.sadrzaj[i]^.veza := pom^.veza;
      DISPOSE(pom)
    END;
    DISPOSE(t^.sadrzaj[i])
  END;
  DISPOSE(t)
END Unisti;

(* Proceduru treba implementirati tako da element "elem" ubaci u
   tabelu "t". Ukoliko hash vrednost elementa nije adekvatna treba postaviti
   "ok" na FALSE, a inace na TRUE. Ako element vec postoji
   u tabeli postaviti "duplikat" na TRUE, a inace na FALSE.
*)
PROCEDURE Ubaci(elem: InfoTip; VAR t: Tabela;
        VAR duplikat: BOOLEAN; VAR ok: BOOLEAN);
VAR
  prethodni,novi:List;
  pozicija:CARDINAL;
BEGIN
  ok:=FALSE;
  duplikat:=FALSE;
  pozicija:=Hash(elem);
  IF pozicija < VelicinaTabele THEN
    ok:=TRUE;
    prethodni:=t^.sadrzaj[pozicija];
    prethodni^.el:=elem;
    WHILE (Compare(prethodni^.veza^.el,elem) # 0) DO
      prethodni:=prethodni^.veza;
    END;
    IF prethodni^.veza = t^.sadrzaj[pozicija] THEN
      NEW(novi);
      novi^.el:=elem;
      novi^.veza:=prethodni^.veza;
      prethodni^.veza:=novi;
      ok:=TRUE;
      INC(t^.ukupno);
      INC(t^.broj[pozicija]);
    ELSE
      duplikat:=TRUE;
    END;
  END;
END Ubaci;

(* Proceduru treba implementirati da iz fajla "ime"
   doda podatke u tabelu "t". U parametru "duplikata"
   treba vratiti koliko je bilo duplikata pri unosu,
   a u "losih" koliko je bilo pogresnih Hash vrednosti.
   Ukoliko fajl ne postoji treba postaviti parametar "ok" na FALSE.
*)
PROCEDURE IzFajla(ime: ARRAY OF CHAR; VAR t: Tabela; VAR ok: BOOLEAN;
        VAR duplikata: CARDINAL; VAR losih: CARDINAL);
VAR
  f : FIO.File;
  novi : InfoTip;
  duplikat, dobarhes : BOOLEAN;
BEGIN
  duplikata := 0;
  losih := 0;
  IF NOT FIO.Exists(ime) THEN
    ok:=FALSE
  ELSE
    ok := TRUE;
    f := FIO.Open(ime);
    FIO.EOF:=FALSE;
    WHILE (NOT FIO.EOF) DO
      FRdInfo(f, novi);
      Ubaci(novi, t, duplikat, dobarhes);
      IF NOT dobarhes THEN
        INC(losih);
      ELSIF duplikat THEN
        INC(duplikata);
      END;
    END;
    FIO.Close(f)
  END
END IzFajla;

PROCEDURE Izbaci(elem : InfoTip;
                 VAR t : Tabela;
         VAR ok : BOOLEAN);
BEGIN
    IO.WrStr("-- Procedura nije implementirana -- ");
    ok:=FALSE;
END Izbaci;

PROCEDURE Sadrzaj(VAR t: Tabela);
    VAR
      i: CARDINAL;
      tekuci: List;
BEGIN
    IO.WrStr('Sadrzaj:');
    IO.WrLn;
    FOR i:= 0 TO VelicinaTabele-1 DO
      tekuci:= t^.sadrzaj[i]^.veza;
      WHILE tekuci# t^.sadrzaj[i] DO
        WrInfo(tekuci^.el);
    IO.WrLn;
        tekuci:= tekuci^.veza;
      END;
    END;
END Sadrzaj;

PROCEDURE Nnad2(n: CARDINAL) : LONGCARD;
BEGIN
  IF n > 1 THEN
    RETURN (VAL(LONGCARD,n) * VAL(LONGCARD,n - 1)) DIV 2
  ELSE
    RETURN 0
  END
END Nnad2;

PROCEDURE IspisiNule(b: LONGCARD; duzina: CARDINAL);
VAR
  cifara, i: CARDINAL;
BEGIN
  IF b # 0 THEN
    cifara := 0;
    WHILE b # 0 DO
      INC(cifara);
      b := b DIV 10
    END
  ELSE
    cifara := 1
  END;
  FOR i := 1 TO duzina-cifara DO
    IO.WrChar('0')
  END
END IspisiNule;

PROCEDURE Kolizije(VAR t : Tabela);
VAR
  i, decimalni : CARDINAL;
  zbir, decimalniLong : LONGCARD;
  procenat, chi, prosek : REAL;
BEGIN
  WITH t^ DO
    IO.WrStr("Ukupno elemenata: "); IO.WrCard(ukupno, 0); IO.WrLn;

    IO.WrStr("Faktor popunjenosti: ");
    zbir := 0;
    FOR i := 0 TO VelicinaTabele - 1 DO
      IF broj[i] > 0 THEN
        INC(zbir);
      END
    END;
    procenat := FLOAT(zbir) * 100.0 / FLOAT(VelicinaTabele);
    IO.WrCard(TRUNC(procenat),0); IO.WrChar('.');
    decimalni := TRUNC((procenat - FLOAT(TRUNC(procenat)))*100.0);
    IspisiNule(VAL(LONGCARD,decimalni), 2);
    IO.WrCard(decimalni,0); IO.WrChar('%');
    IO.WrLn;

    IO.WrStr("Ukupno kolizija: ");
    zbir := 0;
    FOR i := 0 TO VelicinaTabele - 1 DO
      zbir := zbir + Nnad2(broj[i]);
    END;
    IO.WrLngCard(zbir, 0);
    IO.WrLn;

    IO.WrStr("Hi-kvadrat test: ");
    chi := 0.0;
    IF ukupno > 0 THEN
      prosek := FLOAT(ukupno)/FLOAT(VelicinaTabele);
      FOR i := 0 TO VelicinaTabele - 1 DO
        chi := chi + ((FLOAT(broj[i]) - prosek) * (FLOAT(broj[i]) - prosek) / prosek);
      END
    END;

    IO.WrLngCard(VAL(LONGCARD,chi),0); IO.WrChar('.');
    decimalniLong := VAL(LONGCARD,(chi - VAL(REAL,TRUNC(chi)))*1.0E+8);
    IspisiNule(decimalniLong, 8);
    IO.WrLngCard(decimalniLong,0);
    IO.WrLn
  END
END Kolizije;

END zadatak.