% 7

% mobil
% zaves(DelkaLeva, DelkaPrava, ObjektLevy, ObjektPravy).
% zavazi(Hmotnost).

% priklad vyvazeneho mobilu
% zaves(2,3,zaves(4,1,zavazi(6),zaves(2,1,zavazi(8),zavazi(16))),zaves(1,3,zavazi(15),zavazi(5)))
% priklad bezpecneho mobilu (ale neni vyvazeny!)
% zaves(6,6,zaves(1,3,zaves(1,1,zavazi(1),zaves(1,1,zavazi(1),zavazi(1))),zavazi(1)),zaves(3,1,zavazi(1),zaves(1,1,zaves(1,1,zaves(1,1,zavazi(1),zavazi(1)),zavazi(1)),zavazi(1))))



vaha(zavazi(Hmotnost),Hmotnost).
vaha(zaves(_,_,L,P),Vaha):-vaha(L,VL),vaha(P,VP),Vaha is VL+VP.

vyvazeny(zavazi(_)):-!.
vyvazeny(zaves(DL,DP,L,P)):-vyvazeny(L),vyvazeny(P),vaha(L,VL),vaha(P,VP),ML is (DL*VL),MP is (DP*VP),ML is MP.

ekvivalentni(zavazi(H),zavazi(H)):-!.
ekvivalentni(zaves(DL,DP,L1,P1),zaves(DL,DP,L2,P2)):-ekvivalentni(L1,L2),ekvivalentni(P1,P2),!.
ekvivalentni(zaves(DL,DP,L1,P1),zaves(DP,DL,L2,P2)):-ekvivalentni(L1,P2),ekvivalentni(P1,L2),!.

bezpecny(zavazi(_)):-!.
bezpecny(zaves(DL,DP,L,P)):-bezpecny(L),bezpecny(P),sirky(L,SL),sirky(P,SP),bvk(DL,DP,SL,SP),!.

pridej(X,S,[X|S]).

sirky(zavazi(_),[0]).
%sirky(zaves(DL,DP,L,P),S):-sirky(L,SL),pridej(DL,SL,SL1).
sirky(zaves(DL,DP,L,P),Sirky):-sirky(L,SL),sirky(P,SP),pricti_vsude(SL,DL,SL1),pricti_vsude(SP,DP,SP1),pridej(DL,SL1,SL2),pridej(DP,SP1,SP2),maxima(SL2,SP2,Sirky),!.

bvk(_,_,_,[]):-!.
bvk(_,_,[],_):-!.
bvk(DL,DP,[SL|SLT],[SP|SPT]):- XL is SL-DL, XP is DP-SP,XL < XP,bvk(DL,DP,SLT,SPT),!.

pricti_vsude([],_,[]):-!.
pricti_vsude([X|Xt],N,[Y|Yt]):-pricti_vsude(Xt,N,Yt),Y is X+N,!.

maxima([],[],[]):-!.
maxima(A,[],A):-!.
maxima([],B,B):-!.
maxima([A|At],[B|Bt],[A|Mt]):-A >=B,maxima(At,Bt,Mt),!.
maxima([A|At],[B|Bt],[B|Mt]):-A < B,maxima(At,Bt,Mt),!.

% halda
% reprezentovana strukturou halda(Koren,PocetPrvku), kde koren je tvaru h(L,V,R), kde L je levy a P pravy podstrom a V je hodnota uzlu.

% extractMin(+Halda,-Minimum,-Halda1) - Halda1 vznikne odebráním Minima z Haldy. O(log n)
extractMin(halda(h(nil,X,nil),1),X,halda(nil,0)):-!.
extractMin(halda(HaldaKoren,HaldaPocetPrvku),Minimum,Halda1):-extractMin(HaldaKoren,HaldaPocetPrvku,NovaHalda,Minimum),PP1 is HaldaPocetPrvku-1,vytvor_haldu(NovaHalda,PP1,Halda1).
extractMin(Koren,PocetPrvku,NovaHalda,Min):-hodnota(Koren,Min),odstran_posledni(Koren,PocetPrvku,NH1,Posledni),vloz_do_korene(NH1,Posledni,NH2),vybublat(NH2,NovaHalda).

hodnota(h(_,V,_),V).

vytvor_haldu(h(L,V,R),PocetPrvku,halda(h(L,V,R),PocetPrvku)).

odstran_posledni(Halda,PocetPrvku,NovaHalda,Posledni):-binarne(PocetPrvku,BinPocet),poprav(BinPocet,_,NBP),odstran(Halda,NBP,NovaHalda,Posledni).

odstran(h(nil,U,nil),[],nil,U).
odstran(h(L,U,nil),[_],h(nil,U,nil),HU):-hodnota(L,HU).
odstran(h(L,U,R),[_],h(L,U,nil),HU):-hodnota(R,HU).
odstran(h(L,U,R),[HL|T],h(L,U,NR),X):-HL=:=1,odstran(R,T,NR,X).
odstran(h(L,U,R),[HL|T],h(NL,U,R),X):-HL=:=0,odstran(L,T,NL,X).

poprav([H|T],H,T).

binarne(X,T):-binarne1(X,T1),reverse(T1,T).

binarne1(0,[]):-!.
binarne1(X,[H|T]):-number(X),H is X mod 2,P is X // 2,binarne1(P,T).

vloz_do_korene(nil,X,h(nil,X,nil)).
vloz_do_korene(h(L,_,R),X,h(L,X,R)).

vybublat(nil,nil).
vybublat(h(nil,X,nil),h(nil,X,nil)):-!.
vybublat(h(L,H,nil),h(NL,NU,nil)):-hodnota(L,HL),H>HL,vymen_s_levym(h(L,H,nil),h(NL,NU,nil)),!.
vybublat(h(L,H,nil),h(L,H,nil)):-hodnota(L,HL),H<HL,!.
vybublat(h(L,H,R),h(NL,NU,R)):-hodnota(L,HL),hodnota(R,HR),HL<HR,H>HL,vymen_s_levym(h(L,H,R),h(NL1,NU,R)),vybublat(NL1,NL).
vybublat(h(L,H,R),h(L,NU,NR)):-hodnota(L,HL),hodnota(R,HR),HR<HL,H>HR,vymen_s_pravym(h(L,H,R),h(L,NU,NR1)),vybublat(NR1,NR).
vybublat(h(L,H,R),h(L,H,R)):-hodnota(L,HL),hodnota(R,HR),H<HL,H<HR.

vymen_s_levym(h(h(L1,U1,R1),U,R),h(h(L1,U,R1),U1,R)).
vymen_s_pravym(h(L,U,h(L1,U1,R1)),h(L,U1,h(L1,U,R1))).

%insert(+Halda,+Prvek,-Halda1) - Halda1 vznikne přidáním Prvku do Haldy. O(log n)
insert(halda(nil,0),X,halda(h(nil,X,nil),1)):-!.
insert(halda(Koren,PocetPrvku),X,Halda1):-PP1 is PocetPrvku + 1,binarne(PP1,B),poprav(B,_,NB),zarad(Koren,NB,X,NS),vytvor_haldu(NS,PP1,Halda1),!.

zarad(nil,[],X,h(nil,X,nil)).
zarad(h(L,V,R),[0|T],X,h(NL,V,R)):-X>=V,zarad(L,T,X,NL).
zarad(h(L,V,R),[1|T],X,h(L,V,NR)):-X>=V,zarad(R,T,X,NR).
zarad(h(L,V,R),[0|T],X,h(NL,X,R)):-X<V,zarad(L,T,V,NL).
zarad(h(L,V,R),[1|T],X,h(L,X,NR)):-X<V,zarad(R,T,V,NR).

%postav(+Pole,-Halda) - Z Pole přirozených čísel postaví haldu. Lze řešit postupným vkládáním prvků. O(n log n)
postav(Pole,Halda):-postav(Pole,halda(nil,0),Halda).
postav([],Halda,Halda).
postav([H|T],Halda,NovaHalda):-insert(Halda,H,Halda1),postav(T,Halda1,NovaHalda).

% heapsort(+Pole,-SetridenePole) - Z pole postaví haldu a vytvoří
% setříděné pole postupným odebíráním minima z haldy. O (n log n)
heapsort(Pole,SetridenePole):-postav(Pole,Halda),rozeber(Halda,SetridenePole).

rozeber(halda(nil,0),[]):-!.
rozeber(Halda,[Minimum|T]):-extractMin(Halda,Minimum,NovaHalda),rozeber(NovaHalda,T),!.