MODULE stabla;
FROM FIO IMPORT File, Exists, Open, Create, Close,RdInt, RdChar,WrInt,WrStr,WrLn,WrChar;
FROM InOut IMPORT WriteInt, WriteString, WriteLn, ReadString, Write, ReadInt;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM Str IMPORT Length;

TYPE
        string = ARRAY [1..40] OF CHAR;
TYPE
        InfoTip = INTEGER;

CONST
        MAXINFOTIP = MAX(InfoTip);
        MININFOTIP = MIN(InfoTip);

PROCEDURE FRdInfo(f:File; VAR info:InfoTip);
BEGIN
                info := RdInt(f);
END FRdInfo;

PROCEDURE WrInfo(info:InfoTip);
BEGIN
                WriteInt(info,3);
END WrInfo;

PROCEDURE FWrInfo(f:File; info:InfoTip);
BEGIN
                WrInt(f,info,2);
END FWrInfo;

TYPE
        Stablo = POINTER TO cvor;
        cvor = RECORD
                id : INTEGER;
                info : InfoTip;
                levo : Stablo;
                desno : Stablo;
        END;

PROCEDURE Nadji(s:Stablo; id:INTEGER):Stablo;
VAR
        temp : Stablo;
BEGIN
        IF (s= NIL) THEN
                RETURN NIL;
        ELSIF (s^.id = id) THEN
                RETURN s;
        ELSE
                temp := Nadji(s^.levo,id);
                IF temp#NIL THEN
                        RETURN temp;
                ELSE
                        temp:= Nadji(s^.desno,id);
                        RETURN temp;
                END;
        END;
END Nadji;

PROCEDURE DodajCvor(VAR s:Stablo; id:INTEGER; info: InfoTip; levo, desno :INTEGER):BOOLEAN;
VAR
        cv, novi : Stablo;
        postoji : BOOLEAN;
BEGIN
        IF s=NIL THEN
                NEW(s);
                s^.id := id;
                cv := s;
                postoji := TRUE;
        ELSE
            cv := Nadji(s, id);
            postoji := cv#NIL;
        END;

        IF postoji THEN
                cv^.info := info;
                IF levo>0 THEN
                        NEW(novi);
                        cv^.levo:=novi;
                        novi^.id:=levo;
                        novi^.levo:=NIL;
                        novi^.desno:=NIL;
                END;
                IF desno>0 THEN
                        NEW(novi);
                        cv^.desno:=novi;
                        novi^.id:=desno;
                        novi^.levo:=NIL;
                        novi^.desno:=NIL;
                END;
        RETURN TRUE;

    ELSE
        RETURN FALSE;
    END;
END DodajCvor;

PROCEDURE Ucitaj(fn: string; VAR s: Stablo):BOOLEAN;
VAR
        i,n : INTEGER;
        info : InfoTip;
        id, levo, desno : INTEGER;
        f: File;
BEGIN
        IF Exists(fn) THEN
                f := Open(fn);
                n := RdInt(f);
                FOR i:= 1 TO n DO
                        id := RdInt(f); (*sve je integer osim info koji je infotip*)
                        FRdInfo(f,info);
                        levo := RdInt(f);
                        desno := RdInt(f);
                        IF NOT DodajCvor(s,id,info,levo,desno) THEN
                                WriteString("Greska: unos, definicija ");
                                WriteInt(i,2);
                                WriteLn;
                        END;
                END;
                Close(f);
                RETURN TRUE;
        ELSE
                RETURN FALSE;
        END;
END Ucitaj;

PROCEDURE Stampaj(s: Stablo);
BEGIN
        IF s#NIL THEN
                WriteInt(s^.id,0);
                WriteString(" ");
                WrInfo(s^.info);
                WriteString(" ");
                IF s^.levo#NIL THEN
                        WriteInt(s^.levo^.id,0);
                ELSE
                        WriteInt(0, 0);
                END;
                WriteString(" ");
                IF s^.desno#NIL THEN
                        WriteInt(s^.desno^.id,0);
                ELSE
                        WriteInt(0,0);
                END;
                WriteLn;
                Stampaj(s^.levo); (* stampa levo i desno rekurzivna*)
                Stampaj(s^.desno);
        END;
END Stampaj;

PROCEDURE StampajNivoe(s: Stablo; dubina:INTEGER; VAR brp:INTEGER);
VAR
        i:INTEGER;
BEGIN
        IF s#NIL THEN (* Ovaj deo koda prebrojava parne cvorove *)
                IF (s^.info MOD 2 = 0 ) THEN
                        INC (brp);
                END;

                StampajNivoe(s^.desno,dubina+1,brp);
                FOR i:=1 TO dubina-1 DO
                        WriteString("   |    ");
                END;
                IF dubina>0 THEN
                        WriteString("   |--->");
                END;
                WriteString("(");
                WriteInt(s^.id,2);
                WriteString(":");
                WrInfo(s^.info);
                WriteString(")");WriteLn;
                StampajNivoe(s^.levo,dubina+1,brp);
        END;
END StampajNivoe;

PROCEDURE ObilazakStabla (s : Stablo);
VAR temp: stablo;
BEGIN
        temp:=s;
        IF s # NIL THEN
                IF (s^.levo # NIL) THEN
                        ObilazakStabla (s^.levo);
                END;
                IF (s^.desno # NIL) THEN
                        ObilazakStabla (s^.desno);
                END;
        END;

END ObilazakStabla;

PROCEDURE StampajUDubinu(s: Stablo; dubina:INTEGER);
VAR
        i:INTEGER;
BEGIN
        IF s#NIL THEN
                FOR i:=1 TO dubina-1 DO
                        WriteString("   |    ");
                END;
                IF dubina>0 THEN
                        WriteString("   |--->");
                END;
                WriteString("(");
                WriteInt(s^.id,2);
                WriteString(":");
                WrInfo(s^.info);
                WriteString(")");WriteLn;
                StampajUDubinu(s^.levo,dubina+1);
                StampajUDubinu(s^.desno,dubina+1);
        END;
END StampajUDubinu;

PROCEDURE Unisti(VAR s: Stablo);
BEGIN
        IF (s#NIL) THEN
                Unisti(s^.levo);
                Unisti(s^.desno);
                DISPOSE(s); (* postavlja i s na NIL *)
        END;
END Unisti;

PROCEDURE Prebroj(s:Stablo):INTEGER;
BEGIN
        IF s#NIL THEN
                RETURN 1 + Prebroj(s^.levo) + Prebroj(s^.desno);
        ELSE
                RETURN 0;
        END;
END Prebroj;

PROCEDURE Snimi(fn:string; s: Stablo);

        PROCEDURE SnimiCvor(f:File;s:Stablo);
        BEGIN
                IF s#NIL THEN
                        WrInt(f,s^.id,4);
                        WrStr(f," ");
                        FWrInfo(f,s^.info);
                        WrStr(f," ");
                        IF s^.levo#NIL THEN
                                WrInt(f,s^.levo^.id,4);
                        ELSE
                                WrInt(f, 0, 4);
                        END;
                        WrStr(f," ");
                        IF s^.desno#NIL THEN
                                WrInt(f,s^.desno^.id,4);
                        ELSE
                                WrInt(f, 0 ,4);
                        END;
                        WrLn(f);
                        SnimiCvor(f,s^.levo);
                        SnimiCvor(f,s^.desno);
                END;
        END SnimiCvor;
VAR
        f:File;
        i:INTEGER;
BEGIN
        f := Create(fn);
        (* treba proveriti koliko je veliko Stablo *)
        i := Prebroj(s);
        WrInt(f,i,0);
        WrLn(f);
        SnimiCvor(f,s);
        Close(f);
END Snimi;

PROCEDURE SnimiId(fn:string;s:Stablo;id:INTEGER);
BEGIN
        IF id>0 THEN
                Snimi(fn,Nadji(s,id));
        ELSE
                Snimi(fn,s);
        END;
END SnimiId;

PROCEDURE Visina(s : Stablo) : INTEGER;
VAR
        l, d : INTEGER;
BEGIN
        IF s # NIL THEN
                l := Visina( s^.levo );
                d := Visina( s^.desno );
                IF l > d THEN
                        RETURN l + 1;
                ELSE
                        RETURN d + 1;
                END;
        END;
        RETURN -1;
END Visina;

PROCEDURE Obilazak ( s : Stablo; VAR max:INTEGER);
BEGIN
        IF s # NIL THEN
                IF (s^.levo # NIL) THEN
                        IF (s^.levo^.info > max) THEN
                                max:=s^.levo^.info;
                        END;
                        Obilazak (s^.levo,max);
                END;
                IF (s^.desno # NIL) THEN
                        IF (s^.desno^.info > max) THEN
                                max:=s^.desno^.info;
                        END;
                        Obilazak(s^.desno,max);
                END;
        END;

END Obilazak;

PROCEDURE Obrni ( s : Stablo);
VAR
        temp:Stablo;
BEGIN
        IF s <> NIL THEN
                IF (s^.levo^.info = s^.info ) THEN
                        temp:=s^.levo;
                        s^.levo:=s^.desno;
                        s^.desno:=temp;
                        Obrni(s^.levo);
                END;
                IF  (s^.desno^.info = s^.info) THEN
                        temp:=s^.levo;
                        s^.levo:=s^.desno;
                        s^.desno:=temp;
                        Obrni(s^.desno);
                END;
        END;

END Obrni;

PROCEDURE VisljePodStablo ( s : Stablo);
VAR
        l,d:INTEGER;

BEGIN
        IF s # NIL THEN
                l:=Visina (s^.levo);
                d:=Visina (s^.desno);
                IF (l>d) THEN
                        WriteInt (s^.id,2);
                        WriteString ("  ");
                END;
                VisljePodStablo(s^.levo);
                VisljePodStablo(s^.desno);
        END;

END VisljePodStablo;

PROCEDURE Duplikatikorena ( s : Stablo; br: INTEGER; VAR d:INTEGER);

BEGIN
        IF s <> NIL THEN

                IF (s^.levo <> NIL) THEN
                        IF (s^.levo^.info = br) THEN
                                INC(d);
                        END;
                                Duplikatikorena(s^.levo,br,d);
                END;
                IF  (s^.desno <> NIL) THEN
                        IF (s^.desno^.info = br) THEN
                                INC(d)
                        END;
                                Duplikatikorena(s^.desno,br,d);
                END;
        END;

END Duplikatikorena;

PROCEDURE IspisBrCv(s : Stablo; k:INTEGER);
VAR

 pom : Stablo;
 brcv : INTEGER;
BEGIN
        pom := Nadji(s,k);
        IF pom <> NIL THEN
                brcv := (Prebroj(pom));
        END;
        WriteString("Broj cvorova u podstablu je:  ");
        WriteInt(brcv,1);

END IspisBrCv;

PROCEDURE VecePodStablo (s:Stablo; k:INTEGER);
VAR
        lev,des:INTEGER;
        pom:Stablo;
BEGIN
                pom := Nadji(s, k);
                lev := Visina(pom^.levo);
                des := Visina(pom^.desno);
                IF lev > des THEN
                        WriteString("Vece je levo podStablo.");
                ELSIF des>lev  THEN
                        WriteString("Vece je desno podStablo.");
                ELSE
                        WriteString ("Podstabla su jednake visine.");
                END;
                WriteLn; WriteLn;
END VecePodStablo;

PROCEDURE obrisi (s:Stablo; id:INTEGER);
VAR
        temp:Stablo;
BEGIN
        temp:=Nadji(s,id);
        Unisti(temp);
        WriteString ("PodStablo cvora sa id ");
        WriteInt (id,3);
        WriteString ("je obrisano.");
END obrisi;

PROCEDURE IspisNaDubini(s : Stablo; dubina : INTEGER );

        PROCEDURE uradi( sta : Stablo; d : INTEGER );
        BEGIN
                IF sta = NIL THEN
                        RETURN
                END;

                IF d < dubina THEN
                        uradi( sta^.levo , d + 1 );
                        uradi( sta^.desno , d + 1 );
                END;

                IF d = dubina THEN
                        WriteInt( sta^.info, 0 );
                        WriteString (",");
                END;
        END uradi;

BEGIN
        uradi( s, 0 );
END IspisNaDubini;

PROCEDURE Vrednost( s : Stablo ): INTEGER;
BEGIN
        IF s <> NIL THEN
                RETURN s^.info + Vrednost(s^.levo) + Vrednost(s^.desno);
        END;
        RETURN 0;
END Vrednost;

PROCEDURE VrP( s : Stablo);

BEGIN
        IF s <> NIL THEN

                IF (s^.levo <> NIL) THEN
                        WriteString ("Vrednost podstabla cvora sa id ")  ;
                        WriteInt (s^.levo^.id,2);
                        WriteString ("je: ");
                        WriteInt (Vrednost(s),2);
                        WriteLn;
                        VrP(s^.levo);
                END;
                IF  (s^.desno <> NIL) THEN
                        WriteString ("Vrednost podstabla cvora sa id ");
                        WriteInt (s^.desno^.id,2);
                        WriteString ("je: ");
                        WriteInt (Vrednost(s),2);
                        WriteLn;
                        VrP(s^.desno);
                END;
        END;

END VrP;

PROCEDURE VeciOdRoditelja( s : Stablo);

BEGIN
        IF s <> NIL THEN

                IF (s^.levo <> NIL) THEN
                        IF (s^.levo^.info > s^.info ) THEN
                                WriteInt (s^.levo^.id,2);
                        END;
                        VeciOdRoditelja (s^.levo);
                END;
                IF  (s^.desno <> NIL) THEN
                        IF (s^.desno^.info > s^.info ) THEN
                                WriteInt (s^.desno^.id,2);
                        END;
                        VeciOdRoditelja(s^.desno);
                END;
        END;

END VeciOdRoditelja;

VAR
        s: Stablo;
        fn: string;
        id,brp,k,d: INTEGER;
BEGIN
        (* init na prazno Stablo *)
        s := NIL;
        brp:=0;
        WriteString("ime fajla sa Stablom (podrazumevano s2.txt) ? ");
        WriteLn;
        ReadString(fn);
        (* podrazumevano ime za brze testiranje *)
        IF Length(fn)=0 THEN
                fn := "s2.txt";
        END;

        IF Ucitaj(fn, s) THEN
                WriteString ("---------OSNOVNE INFORMACIJE O STABLU---------");
                WriteLn; WriteLn;

                WriteString("Ukupan broj cvorova unetog stabla je :");
                WriteInt(Prebroj(s),0);
                WriteLn;
                WriteLn;

                WriteString("Visina stabla je : ");
                WriteInt(Visina(s), 3);
                WriteLn;WriteLn;

                WriteString("Vrednost stabla je : ");
                WriteInt(Vrednost(s),3);
                WriteLn;WriteLn;

                WriteString ("-----------STAMPANJE POGODNO ZA UCITAVANJE IZ FAJLA-------------" );
                WriteLn; WriteLn;
                Stampaj(s);
                WriteLn;


                WriteString ("------------STAMPANJE STABLA PO NIVOIMA-----------");
                WriteLn;
                WriteLn;
                StampajNivoe(s,0,brp);
                WriteLn;
                WriteLn;

                WriteString ("---------DODATNE INFORMACIJE O STABLU--------");
                WriteLn; WriteLn;

                WriteString ("Broj parnih cvorova je: ");
                WriteInt (brp,1);
                WriteLn; WriteLn;

                WriteString ("Maximalni element u stablu: ");
                Obilazak (s,brp);
                WriteInt (brp,2);
                WriteLn;
                WriteLn;

                WriteString ("Stampaj sve cvorove na dubini 3:");
                IspisNaDubini (s,3);
                WriteLn; WriteLn;

                WriteString  ("Sumiranje podstabala cvorova (odnosi se na podstabla koji imaju bar jedan cvor): ");
                WriteLn;
                VrP(s);
                WriteLn;
                WriteLn;

                WriteString (" Ispisujemo sve id cvorova kod kojih je vece levo podStablo: ");
                VisljePodStablo (s);
                WriteLn;
                WriteLn;

                WriteString ("Ispisujemo sve cvorove koji imaju vecu vrednost od roditelja: ");
                VeciOdRoditelja(s);
                WriteLn; WriteLn;

                WriteString ("Da vidimo da li ima duplikata korena u nasem stablu: ");
                Duplikatikorena(s,s^.info,d);
                WriteInt (d,2);
                WriteLn;
                WriteLn;

                WriteString("Unesite id cvora, za koji zelite da znate broj cvorova podstabla : ");
                ReadInt (k);
                WriteLn;
                IspisBrCv (s,k);
                WriteLn; WriteLn;


                WriteString ("Obrnucemo sva podstabla cvorova koji imaju isti info kao u korenu." );
                Obrni(s);
                WriteLn;
                StampajNivoe (s,d,brp);
                WriteLn; WriteLn;

                WriteString("Unesite id  cvora, za koji zelite da znate koje njegovo koje podStablo ima vecu visinu: ");
                ReadInt(k);
                VecePodStablo (s,k);

                WriteString ("Unesite id cvora cija podstabla zelite da obrisete: ");
                ReadInt (k);
                obrisi(s,k);
                WriteLn;
                StampajNivoe (s,d,brp);
                WriteLn; WriteLn;

                WriteString("Snimamo podStablo u fajl podStablo.txt - unesite id korena ili 0 za celo Stablo: ");
                ReadInt(id);
                SnimiId("podStablo.txt",s,id);
                Unisti(s);
                WriteLn;
                WriteString("oslobodjena memorija; kraj rada");
                WriteLn;
        ELSE
                WriteString("greska u ucitavanju");
                WriteLn;
        END;
END stabla.