%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% rozdilove seznamy
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% append je pomala operace, v priapde, ze budeme mit hodne, tak je to zbytecne pomale.
% muzeme si vsimnout, ze v pripade, ze chceme spojit dva seznamy, muzeme pouzit fintu s unifikaci, ktera probehne rychleji, nez to same pres conc
% ?-List = [a,b,c|X], X = [d,e,f].
% 1  1  Call: _59=[a,b,c|_103] ?
% 1  1  Exit: [a,b,c|_103]=[a,b,c|_103] ?
% 2  1  Call: _103=[d,e,f] ?
% 2  1  Exit: [d,e,f]=[d,e,f] ?

% k tomuto ucelu mame v prologu rozdilove seznamy

conc_r(L1-R1,R1-L2,L1-L2). % tohle probehne v konstantnim case
% pouziti: ?- conc_r([a,b,c|T1]-T1,[d,e|T2]-T2,L).
% T1=[d,e|T2]
% S = [a, b, c, d, e|T2]-T2.

% da se prevadet mezi rozdilovym seznamem a normalnim
% preved(-S,-RS) - prevede seznam S na rozdilovy seznam RS

preved([],T-T):-var(T).
preved([X|S],[X|T1]-T):-var(T),preved(S,T1-T).

% jednosmerna varianta je jednodussi
preved2(R-[],R).

appendzac_r(X,A-B,[X|A]-B).

appendkon_r(X,A-[X|B],A-B).

posun1([H|T]-[H|A],T-A). % posune o jeden prvek

% obrat_r(S,RS) - obrati seznam S na rozdilovy seznam RS
obrat_r([],A-A).
obrat_r([X|L],A-B):-obrat_r(L,A-[X|B]).
% obrati seznam L1 na seznam L2 v linearnim case pomoci rozdiloveho seznamu
obrat(L1,L2):-obrat_r(L1,L2-[]).

% obrat2_r(A,B) obrati rozdilovy seznam A na rozdilovy seznam B
obrat2_r(A-A,B-B):-var(A),!.
obrat2_r([X|A1]-B1,A2-B2):-obrat2_r(A1-B1,A2-[X|B2]).

% pri praci s rozdilovymi seznamy je treba dat pozor na occur check
count(X-X, 0).
count([_|T]-T1, N) :- count(T-T1, M), N is M+1.

% tohle spadne pri count([1,2,3|T]-T,N), protoze prolog nedela occur check a bude nekonecne unifikovat [1,2,3|T] s T
% jde to vyresit pomoci unify_with_occurs_check/2, coz je predikat, ktery zunifikuje argumenty, ale pritom testuje occur check

% pouziti napr ve frontach, nebo obecne neuplnych strukturach

queue0(Is) :- q0(Is, []).
q0([enq(X)|Is], Q) :- append(Q, [X], Q2), q0(Is, Q2).
q0([deq(X)|Is], [X|Q]) :- q0(Is, Q).
q0([], []). % pro test, ze nam tam nic nezustalo

% pomoci roz. seznamu
queue(Is) :- q(Is, B-B).
q([enq(X)|Is], F-[X|B]) :- q(Is, F-B).
q([deq(X)|Is], [X|F]-B) :- q(Is, F-B).
q([], []-[]).

% qsort pomoci rozdilovych seznamu
qsort(A-A,B-B):-var(A),!.
qsort([X|Xs]-A,SL-Ah):-split(X,Xs-A,L,H),qsort(L,SL-[X|Al]),qsort(H,Al-Ah). % vyhoda je v appendu

split(_,A-A,B-B,C-C):-var(A),!.
split(X,[Y|Ys]-A,[Y|L]-Al,H-Ah):-X>Y,split(X,Ys-A,L-Al,H-Ah).
split(X,[Y|Ys]-A,L-Al,[Y|H]-Ah):-X=<Y,split(X,Ys-A,L-Al,H-Ah).



