gistfile1.aux

%% definice linearniho usporadani prvku, to jest a < b < c < d < e < f < g
lt(a,b). lt(a,c). lt(a,d). lt(a,e). lt(a,f). lt(a,g).
lt(b,c). lt(b,d). lt(b,e). lt(b,f). lt(b,g).
lt(c,d). lt(c,e). lt(c,f). lt(c,g).
lt(d,e). lt(d,f). lt(d,g).
lt(e,f). lt(e,g).
lt(f,g).

%% kazdy prvek je roven prave sobe
eq(X,X).

%% slevani usporadanych seznamu
slij([X|A],[Y|B],[X|C]) :- lt(X,Y), !, slij(A,[Y|B],C).
slij([X|A],[Y|B],[X,Y|C]) :- eq(X,Y), !, slij(A,B,C).
slij([X|A],[Y|B],[Y|C]) :- lt(Y,X), !, slij([X|A],B,C).
slij(A,[],A) :- !.
slij([],B,B) :- !.

zatrid(X,[],[X]) :- !.
zatrid(X,[Y|A],[X,Y|A]) :- lt(X,Y), !.
zatrid(X,[Y|A],[Y|A]) :- eq(X,Y), !.
zatrid(X,[Y|A],[Y|B]) :- lt(Y,X), zatrid(X,A,B).

% insert_sort(InputList, SortedList)
insert_sort([],[]) :- !.
insert_sort([X],[X]) :- !.
insert_sort([X|A],C) :- insert_sort(A,B), zatrid(X,B,C).

%?- insert_sort([d,b,f,c,g,a,e],R).
% R = [a, b, c, d, e, f].

% binarni vyhledavaci strom:
% node(d, 10, node(c, 2, node(b, 35, nil, nil), nil),
%             node(f, 5, node(e, 11, nil, nil),
%                        node(g, 13, nil, nil)))

% hledej(Key, Tree, Val)
hledej(Key, node(Key,Val,_,_), Val) :- !.
hledej(Key, node(Root,_,LeftSub,_), Val) :- lt(Key, Root), !, hledej(Key, LeftSub, Val).
hledej(Key, node(_,_,_,RightSub), Val) :- hledej(Key, RightSub, Val).
% pocita s binarnim vyhledavacim stromem - klic v levem podstromu je vzdy nizsi nez root
%	- klic v pravem vzdy vyssi, pochopitelne tedy klic nenajde, pokud tomu tak neni
%	- nebylo by tezke udelat to tak, aby jej nasel, ale pak by to ztratilo efektivitu
%	  binarniho vyhledavaciho stromu

%?- hledej(e, node(d, 10, node(c, 2, node(b, 35, nil, nil), nil),
%                         node(f, 5, node(e, 11, nil, nil), node(g, 13, nil, nil))),R).
% R = 11.

% hledej(Key, Value, Tree, NewTree) - prida do stromu Key s hodnotou Value
hledej(nil, _, Tree, Tree) :- !.
hledej(Key, _, node(Root, Val, LeftSub, RightSub),
               node(Root, Val, LeftSub, RightSub)) :- eq(Key, Root), !.
hledej(Key, Value, node(Root, Val, nil, RightSub),
                   node(Root, Val, node(Key, Value, nil, nil), RightSub)) :- lt(Key, Root), !.
hledej(Key, Value, node(Root, Val, LeftSub, RightSub),
                   node(Root, Val, NewLeft, RightSub)) :- lt(Key, Root), !, hledej(Key, Value, LeftSub, NewLeft).
hledej(Key, Value, node(Root, Val, LeftSub, nil),
                   node(Root, Val, LeftSub, node(Key, Value, nil, nil))) :- !.
hledej(Key, Value, node(Root, Val, LeftSub, RightSub),
                   node(Root, Val, LeftSub, NewRight)) :- hledej(Key, Value, RightSub, NewRight).

% ?- hledej(a,10, node(d, 10, node(c, 2, node(b, 35, nil, nil), nil),
%                             node(f, 5, node(e, 11, nil, nil),
%	                                 node(g, 13, nil, nil))),R).
% R = node(d, 10, node(c, 2, node(b, 35, node(a, 10, nil, nil), nil), nil),
%                 node(f, 5, node(e, 11, nil, nil), node(g, 13, nil, nil))).

%% CERVENE REZY:
%% odstran prvek X z daneho seznamu, vyuziti rezu 
odstran(_,[],[]).
odstran(X,[X|Y],Z) :- !, odstran(X,Y,Z).
odstran(X,[Q|Y],[Q|Z]) :- odstran(X,Y,Z).

unikatni([], []) :- !.     % zeleny rez
unikatni([X], [X]) :- !.   % cerveny rez - zamezi nekolika stejnym vysledkum pri volani unikatni([a], R).
unikatni([X|Rest], [X|NewRest]) :- odstran(X, Rest, RestWithoutX), unikatni(RestWithoutX, NewRest).

% ?- unikatni([a, a, b, c, b, d, b, a, d], R).
% R = [a, b, c, d]

mnozina(List) :- unikatni(List, List).

% ?- mnozina([a, a, b, c, b, d, b, a, d]).
% false.
% ?- mnozina([a,b,c,d]).
% true.

existuje_prvek(X, [X|_]) :- !.   % cerveny rez - zamezi nekolika stejnym vysledkum
existuje_prvek(X, [_|Rest]) :- existuje_prvek(X, Rest).

% ?- existuje_prvek(b, [a,b,c]).
% true.
% ?- existuje_prvek(d, [a,b,c]).
% false.

% replace(List, Nahrazenec, Nahraditel, NewList)
replace([], _, _, []) :- !.   % zeleny rez
replace([X|Rest], X, Y, [Y|NewRest]) :- !, replace(Rest, X, Y, NewRest).   % cerveny rez
replace([Z|Rest], X, Y, [Z|NewRest]) :- replace(Rest, X, Y, NewRest).

% ?- replace([a,b,c,a,d],a,x,R).
% R = [x, b, c, x, d].

replace_first([], _, _, []) :- !.   % zeleny rez
replace_first([X|Rest], X, Y, [Y|Rest]) :- !.   % cerveny rez
replace_first([Z|Rest], X, Y, [Z|NewRest]) :- replace_first(Rest, X, Y, NewRest).

% ?- replace_first([a,b,c,a,d],a,x,R).
% R = [x, b, c, a, d].

replace_last([], _, _, []) :- !.   % zeleny rez
replace_last([X|Rest], X, Y, [Y|Rest]) :- replace(Rest, X, Y, Rest), !.   % cerveny rez
replace_last([Z|Rest], X, Y, [Z|NewRest]) :- replace_last(Rest, X, Y, NewRest).
%% toto by pravdepodobne melo fungovat, ale protoze replace([a,b,c],a,x,[a,b,c]) vrati true prestoze
%% replace([a,b,c],a,x,R) vrati jako jedinou moznost [x,b,c], projde vzdy podminka druheho pravidla