(* Modul za rad sa polinomima preko listi
   verzija 2014; rev 1 *)
IMPLEMENTATION MODULE PolinomL;
FROM InOut IMPORT Write, WriteString, WriteLn,
           WriteCard, ReadCard, Done;
FROM RealInOut IMPORT WriteReal, ReadReal;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

PROCEDURE Anuliraj(VAR p: Polinom);
BEGIN
  p := NIL;
END Anuliraj;

PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
VAR
  pomocni: Polinom;
BEGIN
  IF p = NIL THEN
    kopija := NIL
  ELSE
    NEW(kopija);
    kopija^ := p^;
    p := p^.veza;
    pomocni := kopija;
    WHILE p <> NIL DO
      NEW(pomocni^.veza);
      pomocni := pomocni^.veza;
      pomocni^ := p^;
      p := p^.veza
    END
  END
END Kopiraj;

PROCEDURE Stampaj(p: Polinom; d: CARDINAL);

  PROCEDURE StampajMonom(m : Polinom);
  BEGIN
    WITH m^ DO
      IF st <> 0 THEN
        IF ABS(k) <> 1.0 THEN
          WriteReal(ABS(k), d)
        END;
        Write('x');
        IF st <> 1 THEN
          Write('^');
          WriteCard(st, 1)
        END
      ELSE
        WriteReal(ABS(k), d)
      END
    END
  END StampajMonom;

BEGIN
  IF p = NIL THEN
    WriteReal(0., d)
  ELSE
    IF p^.k < 0.0 THEN
      WriteString(' - ')
    END;
    StampajMonom(p);
    p := p^.veza;
    WHILE p <> NIL DO
      IF p^.k > 0.0 THEN
        WriteString(' + ')
      ELSE
        WriteString(' - ')
      END;
      StampajMonom(p);
      p := p^.veza
    END
  END
END Stampaj;

PROCEDURE PostaviClan(k:REAL; st:CARDINAL;
                      VAR p:Polinom);
VAR
  cilj, prethodni : Polinom;
BEGIN
  cilj := p;
  prethodni := NIL;
  WHILE (cilj # NIL) AND (cilj^.st>st) DO
    prethodni := cilj;
    cilj := cilj^.veza;
  END;
  (* da li upisujemo vrednost ili sklanjamo clan *)
  IF k#0.0 THEN
    (* da li menjamo clan ili pravimo novi *)
    IF (cilj # NIL) AND (cilj^.st = st) THEN
      cilj^.k:=k;
    ELSE
      NEW(cilj);
      cilj^.k := k;
      cilj^.st := st;
      cilj^.veza := NIL;
      IF prethodni = NIL THEN
	(* ili je prazan polinom, ili dodajemo na pocetak *)
	cilj^.veza := p;
	p := cilj;
      ELSE
	cilj^.veza := prethodni^.veza;
	prethodni^.veza := cilj;
      END;
    END;
  ELSE
    (* da li postoji ovakav clan *)
    IF (cilj # NIL) AND (cilj^.st = st) THEN
      IF p = cilj THEN
	p := p^.veza;
      ELSE
	prethodni^.veza:= prethodni^.veza^.veza;
      END;
      DISPOSE(cilj);      
    END;
  END;
END PostaviClan;

PROCEDURE KoeficijentUz(p:Polinom; st:CARDINAL):REAL;
VAR
  tekuci : Polinom;
BEGIN
  tekuci := p;
  WHILE (tekuci#NIL) AND (tekuci^.st > st) DO
    tekuci := tekuci^.veza;
  END;
  IF (tekuci # NIL) AND (tekuci^.st = st) THEN
    RETURN tekuci^.k;
  ELSE
    RETURN 0.0;
  END;
END KoeficijentUz;

PROCEDURE MaksimalniStepen(p:Polinom):CARDINAL;
BEGIN
  IF p#NIL THEN
    RETURN p^.st;
  ELSE
    RETURN 0;
  END;
END MaksimalniStepen;

PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
VAR
  stari, tekuci, kopija: Polinom;
BEGIN
  IF mon # NIL THEN
    NEW(kopija);
    kopija^ := mon^;
    tekuci := p;
	stari := NIL;
    WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
      stari := tekuci;
      tekuci := tekuci^.veza
    END;
    kopija^.veza := tekuci;
    IF tekuci = p THEN
      p := kopija
    ELSE
      stari^.veza := kopija
    END;
    IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
      kopija^.k := kopija^.k + tekuci^.k;
      kopija^.veza := tekuci^.veza;
      DISPOSE(tekuci);
      IF kopija^.k = 0.0 THEN
        IF p = kopija THEN
          p := kopija^.veza
        ELSE
          stari^.veza := kopija^.veza
        END;
        DISPOSE(kopija)
      END
    END
  END
END UbaciMonom;

PROCEDURE Unos(VAR p : Polinom);
VAR
  i, n: CARDINAL;
  novi: Polinom;
BEGIN
  Anuliraj(p);
  REPEAT
    WriteLn;
    WriteString('Unesite broj monoma n (n>=0) ');
    ReadCard(n);
  UNTIL Done;
  WriteLn;
  FOR i := 1 TO n DO
    NEW(novi);
    WITH novi^ DO
      REPEAT
        WriteString('Unesite koeficijent monoma br.');
        WriteCard(i, 1);
        WriteString(' (<> 0) ');
        ReadReal(k);
        WriteLn
      UNTIL k <> 0.0;
      REPEAT
        WriteLn;
        WriteString('Unesite eksponent monoma br.');
        WriteCard(i, 1);
        WriteString(' (>=0) ');
        ReadCard(st);
      UNTIL Done;
      WriteLn;
    END;
    UbaciMonom(novi, p);
    DISPOSE(novi);
  END
END Unos;

PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
BEGIN
  Kopiraj(p1, zbir);
  WHILE p2 <> NIL DO
    UbaciMonom(p2, zbir);
    p2 := p2^.veza
  END
END Saberi;

PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
BEGIN
  WHILE p <> NIL DO
    UbaciMonom(p,rez);
    p := p^.veza;
  END;
END SaberiNa;

PROCEDURE PromeniZnak(VAR p: Polinom);
VAR
  t: Polinom;
BEGIN
  t := p;
  WHILE t <> NIL DO
    t^.k := - t^.k;
    t := t^.veza
  END
END PromeniZnak;

PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
BEGIN
  Kopiraj(p2, razlika);
  PromeniZnak(razlika);
  WHILE p1 <> NIL DO
    UbaciMonom(p1, razlika);
    p1 := p1^.veza
  END
END Oduzmi;

PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
VAR
  tekuci: Polinom;
BEGIN
  Anuliraj(mp);
  IF (mon <> NIL) AND (p <> NIL) THEN
    NEW(mp);
    mp^.k := p^.k * mon^.k;
    mp^.st := p^.st + mon^.st;
    p := p^.veza;
    tekuci := mp;
    WHILE p <> NIL DO
      NEW(tekuci^.veza);
      tekuci := tekuci^.veza;
      tekuci^.k := p^.k * mon^.k;
      tekuci^.st := p^.st + mon^.st;
      p := p^.veza
    END;
    tekuci^.veza := NIL
  END
END MonomPuta;

PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
VAR
  pomocni, brisi: Polinom;
BEGIN
  Anuliraj(pr);
  IF (p1 <> NIL) AND (p2 <> NIL) THEN
    MonomPuta(p1, p2, pr);
    p2 := p2^.veza;
    WHILE p2 <> NIL DO
      MonomPuta(p1, p2, pomocni);
      REPEAT
        UbaciMonom(pomocni, pr);
        brisi := pomocni;
        pomocni := pomocni^.veza;
        DISPOSE(brisi);
      UNTIL pomocni = NIL;
      p2 := p2^.veza
    END
  END
END Puta;

PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);

  PROCEDURE Deli(VAR kol, ost: Polinom);
  VAR
    novi, pomocni: Polinom;
  BEGIN
    IF ost <> NIL THEN
      IF ost^.st >= p2^.st THEN
        NEW(novi);
        novi^.k := - ost^.k / p2^.k;
        novi^.st := ost^.st - p2^.st;
        MonomPuta(p2, novi, pomocni);
        SaberiNa(pomocni, ost);
        DisposePolinom(pomocni);
        novi^.k := - novi^.k;
        UbaciMonom(novi, kol);
        DISPOSE(novi);
        Deli(kol, ost)
      END
    END
  END Deli;

BEGIN (* Kolicnik *)
  ok := TRUE;
  Anuliraj(kol);
  IF p2 = NIL THEN
    ok := FALSE
  ELSE
    Kopiraj(p1, ost);
    Deli(kol, ost)
  END
END Kolicnik;

PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
                     VAR rez: Polinom);
VAR
  i: CARDINAL;
  pret : Polinom;
BEGIN
  IF n = 0 THEN
    NEW(rez);
    rez^.k := 1.0;
    rez^.st := 0;
    rez^.veza := NIL;
  ELSE
    Kopiraj( p, rez );
    FOR i := 2 TO n DO
      pret := rez;
      Puta(pret, p, rez);
      DisposePolinom(pret);
    END
  END;
END PolinomNaN;

PROCEDURE DisposePolinom(VAR p: Polinom);
VAR
  pomocni: Polinom;
BEGIN
  pomocni := p;
  WHILE pomocni # NIL DO
    p := p^.veza;
    DISPOSE(pomocni);
    pomocni := p
  END
END DisposePolinom;

END PolinomL.