% nacteni:
/* ['2.8_17.pl']. */

% ve SWISH muze hlasit chybu "No permission to call sandboxed `tab(_4808)'"
% reseni viz https://github.com/SWI-Prolog/swish/issues/119

add(T,X,T1) :- addroot(T,X,T1).
add(t(L,Y,R),X,t(L1,Y,R)) :- gt(Y,X),add(L,X,L1).
add(t(L,Y,R),X,t(L,Y,R1)) :- gt(X,Y),add(R,X,R1).

addroot(nil ,X,t( nil ,X, nil )).
addroot(t(L,Y,R),X,t(L1,X,t(L2,Y,R))) :- gt(Y,X),addroot(L,X,t(L1,X,L2)).
addroot(t(L,Y,R),X,t( t(L,Y,R1),X,R2)) :- gt(X,Y),addroot(R,X,t(R1,X,R2)).
addroot(t(L,X,R),X,t(L,X,R)).

del(T,X,T1) :- add(T1,X,T).

gt(X, Y) :- X > Y.

show(T) :- show2(T,0).
show2(nil,_).
show2(t(L,X,R),Indent) :- Ind2 is Indent+2,show2(R,Ind2),tab(Indent),
                          write(X),nl,show2(L,Ind2).

%maketree(+LIST,-TREE)
%LIST - prvky kt. maji byt ve stromu ulozeny
%TREE - vytvoreny strom
%note: vypise vytvoreny strom!!!
maketree([],nil).
maketree([H|T],TREE) :- maketreeacc([H|T],nil,TREE), show(TREE).
%akumulatorova verze predikatu =>
%optimalizace pro "odstraneni" backtrackingu a zrychleni
maketreeacc([],TREE,TREE).
maketreeacc([H|T],PTREE,TREE) :- add(PTREE,H,RTREE), 
                                maketreeacc(T,RTREE,TREE).

%delitems(+TREE,+ITEMS,-NEWTREE).
%smaze ze stromu TREE uzly odpovidajici polozkam ITEMS, vrati NEWTREE
%(pokud takove neexistuji, pokracuje-pro zmenu chovani odebrat posledni kl.)
%note: vypise vytvoreny strom!!!
delitems(TREE,[],TREE) :- show(TREE).
delitems(TREE,[H|T],NEWTREE) :- del(TREE,H,PTREE), 
                                delitems(PTREE,T,NEWTREE).
%v pripade, ze dany prvek ve stromu neni, pokracuj...
delitems(TREE,[_H|T],NEWTREE) :- delitems(TREE,T,NEWTREE). 


% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       start/0.
       
start:- 
    write('Binarni stromy'),nl,
    write('--------------'),nl, nl,
    write('Vytvoreni stromu: '),nl,
    write('add(nil ,6,T),add(Tr,8,Tr1), add(Tr1,2,Tr2),'),nl, 
    write('add(Tr2,4,Tr3), add(Tr3,1,Tr4), show(Tr4) :'),nl,
    add(nil ,6,Tr),add(Tr,8,Tr1), add(Tr1,2,Tr2), add(Tr2,4,Tr3), add(Tr3,1,Tr4),
    show(Tr4),

    write('Smazani uzlu s hodnotou 8:'),nl,
    write('del(Tr4, 8, Tr5), show(Tr5) :'),nl,
    del(Tr4, 8, Tr5), show(Tr5),

    write('Smazani uzlu s hodnotou 2:'),nl,
    write('del(Tr5, 2, Tr6), show(Tr6) :'),nl,
    del(Tr5, 2, Tr6), show(Tr6).

?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).

Binarni stromy
--------------

Vytvoreni stromu: 
add(nil ,6,T),add(Tr,8,Tr1), add(Tr1,2,Tr2),
add(Tr2,4,Tr3), add(Tr3,1,Tr4), show(Tr4) :
    8
      6
  4
    2
1
Smazani uzlu s hodnotou 8:
del(Tr4, 8, Tr5), show(Tr5) :
    6
  4
    2
1
Smazani uzlu s hodnotou 2:
del(Tr5, 2, Tr6), show(Tr6) :
    6
  4
1