ff(X,[H|T],[H|R]):-ff(X,T,R),X<H,!.
ff(H,[H|T],T).



cmmdc1(X,Y,Z) :- X>Y, Diff is X-Y, cmmdc1(Diff,Y,Z).
cmmdc1(X,Y,Z) :- X<Y, Diff is Y-X, cmmdc1(X,Diff,Z).
cmmdc1(X,X,X).

%rec inainte
fact1(0,1).
fact1(N,F) :-N>0, N1 is N-1, fact1(N1,F1), F is N*F1.

%rec inapoi
fact2(0,Acc,F) :- F = Acc.
fact2(N,Acc,F) :- N > 0, N1 is N-1, Acc1 is Acc*N, fact2(N1,Acc1,F).
fact2(N,F) :- fact2(N,1,F). % acumulatorul este ini?ializat cu 1


length([H|T], L, Rez) :- Laux is L + 1,
			length(T,Laux,Rez).
length([], L,L).



%length2([H|T], L) :- Laux is L + 1,
			%length(T,Laux).
%length2([], L).

length2([H|T], L) :- length2(T,LI),
			L is LI + 1.
length2([], 0).



cmmmc(A,B,Res):- A>0, B>0,
		cmmdc1(A,B,Inter),
		Res is (A*B) / Inter.



putere(A,1,Res):- Res = A.
putere(A,B,Res) :- A>0,B>1, A1 is A*A,B1 is B - 1, putere(A1, B1, Res).



putere2(A,1,A).
putere2(A,B,Res):-A>0,B>1, B1 is B - 1, putere2(A,B1,X), Res is A*X.


fibo(0,1).
fibo(1,1).
fibo(A,Rez):- A>1,N1 is A-1, N2 is A-2, fibo(N1, Res1), fibo(N2, Res2), Rez is Res1 + Res2.


eq(A,B,C,R1,R2) :- Delta is (B*B)-(4*A*C), Delta >=0,
		  R1 is (-B + sqrt(Delta))/(2*A),
		  R2 is (-B - sqrt(Delta))/(2*A).



member1(X, [X|_]).
member1(X, [_|T]) :- member1(X, T).



append1([], L2, L2).
append1([H|T], L2, [H|CoadaR]) :- append1(T, L2, CoadaR).


delete1(X, [X|T], T). % sterge prima aparitie si se opreste
delete1(X, [H|T], [H|R]) :- delete1(X, T, R). % altfel itereaza peste elementele listei
delete1(_, [], []). % daca a ajuns la lista vida inseamna ca elementul nu a fost gasit si putem returna lista vida




delete_all(X, [X|T], R) :- delete_all(X, T, R). % daca s-a sters prima aparitie se va continua si pe restul elementelor
delete_all(X, [H|T], [H|R]) :- delete_all(X, T, R).
delete_all(_, [], []).




append3(L1,L2,L3,R):-append1(L2,L3,RI),
	    	     append1(L1,RI,R).


add_first(X,L,[X|L]).
add_first(X,L,R):-add_first(X,L,K), K is [X|R].

%add_first2(X,L,R):- append1([X|_],L,R).
%add_first(X,L,[X|L]).



sum2([H|T],Ac,S):- Ac1 is Ac+H, sum2(T,Ac1,S). %apelez cu 0
sum2([],Ac,S):- S=Ac.


sum([H|T],S):-sum(T,S1), S is H+S1.
sum([],0).


separate_parity([H|T],[H|L1],L2):- 0 is H mod 2, separate_parity(T,L1,L2).
separate_parity([H|T],L1,[H|L2]):- 1 is H mod 2, separate_parity(T,L1,L2).
separate_parity([],[],[]).




remove_duplicates([H|T],R) :- member(H,T), remove_duplicates(T,R).
remove_duplicates([H|T],[H|R]) :-remove_duplicates(T,R).
remove_duplicates([],[]).


 %inlocuieste toate aparitiile lui x in lista l cu y
replace_all(X,Y,[X|T],[Y|R]) :- replace_all(X,Y,T,R).
replace_all(X,Y,[H|T],[H|R]) :- replace_all(X,Y,T,R).%pune pe h in lista 2
replace_all(_,_,[],[]).

replace(X,Y,[H|T],[Y|R]):-X=H,replace(X,Y,T,R).
replace(X,Y,[H|T],[H|R]):-X \=H,replace(X,Y,T,R).
replace(X,Y,[],[]).


%Scrieti un predicat care sterge tot al k-lea element din lista de intrare.
%drop_k([1, 2, 3, 4, 5, 6, 7, 8], 3,1, R).

drop_k([H|T], P, Ac, R):- Ac = P, drop_k(T,P,1,R).
drop_k([H|T], P, Ac, [H|R]):- Ac < P, Ac1 is Ac + 1, drop_k(T,P,Ac1,R).
drop_k([], P, Ac,[]).



member_c(X, [X|_]) :- !.
member_c(X, [_|T]) :- member(X, T).



delete_c(X, [X|T], T) :- !.
delete_c(X, [H|T], [H|R]) :- delete_c(X, T, R).
delete_c(_, [], []).



% Varianta 1 (recursivitate înapoi)
length1([], 0).
length1([H|T], Len) :- length1(T, Lcoada), Len is 1+Lcoada.


% Varianta 2 (recursivitate înainte)
length2([], Acc, Len) :- Len=Acc.
length2([H|T], Acc, Len) :- Acc1 is Acc + 1, length2(T, Acc1, Len).
length2_pretty(L, R) :- length2(L, 0, R).


--------------------------------------------taiere backtr---------------------

% Varianta 1 (recursivitate înapoi)
reverse1([], []).
reverse1([H|T], R) :- reverse1(T, Rcoada), append1(Rcoada, [H], R).


% Varianta 2 (recursivitate înainte)
reverse2([], Acc, R) :- Acc=R.
reverse2([H|T], Acc, R) :- Acc1=[H|Acc], reverse2(T, Acc1, R).
reverse2_pretty(L, R) :- reverse2(L, [], R).



% Varianta 1 (recursivitate înapoi)
min1([H|T], M) :- min1(T, M), M<H, !.
min1([H|_], H).


max1([H|T], M) :- max1(T, M), M>H, !.
max1([H|_], H).

% Varianta 2 (recursivitate înainte)
min2([], Mp, M) :- M=Mp.
min2([H|T], Mp, M) :- H<Mp, !, min2(T, H, M).
min2([H|T], Mp, M) :- min2(T, Mp, M).
min2_pretty([H|T], M) :- min2(T, H, M). % la inceput initialiam minimul cu primul element Urmareste



union_c([], L, L).
union_c([H|T], L2, R) :- member(H, L2), !, union_c(T, L2, R).
union_c([H|T], L2, [H|R]) :- union_c(T, L2, R).



inters_c([], _, []).
inters_c([H|T], L2, [H|R]) :- member1(H, L2), !, inters_c(T, L2, R).
inters_c([H|T], L2, R) :- inters_c(T, L2, R).



dif1([], _, []).
dif1([H|T], L2, R) :- member1(H, L2), !, dif1(T, L2, R).
dif1([H|T], L2, [H|R]) :- dif1(T, L2, R).



%sterge toate aparitiile minimului
del_min(L,R) :- min1(L,M),
	        delete_all(M,L,R).




del_max(L,R) :- max1(L,M),
                delete_all(M,L,R).



reverse_k([H|T], K, R):- K>0, K1 is K-1, reverse_k(T,K1,R1), R= [H|R1],!.
reverse_k( L, K, R) :-reverse1(L,R).

%recursivitate inainte
revk([H|T],K,Q,R) :-    K > 0,
			K1 is K - 1,
			append1(Q,[H],Q1),
			revk(T,K1,Q1,R).

revk(L,_,Q,Y) :-    reverse1(L,R1),
	            append1(Q,R1,Y).
revk(L,K,R) :-  revk(L,K,[],R).





%pt rle-----------------------------------------------------------------
count([H|T], H, R):- count(T,H,R1), R is R1 + 1, !.
count([H|T], X, R):- count(T,X,R).
count([],_,0).

compress([H|T], A, R):- member1(H,A), compress(T,A,R).
compress([H|T], A, R):- A1=[H|A],
                      count([H|T],H,C),
                      compress(T,A1,R1),
                      R=[[H|C]|R1].
compress([],A,[]).

rle_encode(L,R):-compress(L,[],R).
%---------------------------------------------------------------------------





%pt rotire k pozitii------------------------------------------------------------
rotate_k([H|T],K,LL,L1,R):- K<LL, K1 is K+1,
                             append(L1,[H],L11),
                             rotate_k(T,K1,LL,L11,R), !.
rotate_k(L,K,LL,L1,R):- append(L,L1,R).

rotate_right(L,K,R):- length1(L,LL), K1 is K mod LL,
                      rotate_k(L,K1,LL,[],R).
%-------------------------------------------------------------------------------




%pt random----------------------------------------------------------------------
select_p(0,[H|T],H).
select_p(X,[H|T],R):-X1 is X-1, select_p(X1,T,R).

rnd_sel(L,LL,0,[]).
rnd_sel([H|T],LL,K,R):-K1 is K-1,LL1 is LL-1,P is random(LL),
                      select_p(P,[H|T],R1),
                       rnd_sel([H|T],LL1,K1,R2), R=[R1|R2], !.

rnd_select(L,K,R):-length1(L,LL), rnd_sel(L,LL,K,R).

%-------------------------------------------------------------------------------

%----------------------------------SORTARI------------------------------------------------
perm_sort(L,R):-perm(L, R), is_ordered(R), !.



perm(L, [H|R]):-append(A, [H|T], L), append(A, T, L1), perm(L1, R).
perm([], []).


is_ordered([H1, H2|T]):-H1 =< H2, is_ordered([H2|T]).
is_ordered([_]). % daca ii doar un element ii deja ordonata

%------------------------------------------------------------------



sel_sort(L, [M|R]):- min1(L, M), delete1(M, L, L1), sel_sort(L1, R).
sel_sort([], []).
%----------------------------------------------------------------------


ins_sort([H|T], R):- ins_sort(T, R1), insert_ord(H, R1, R).
ins_sort([], []).

insert_ord(X, [H|T], [H|R]):-X>H, !, insert_ord(X, T, R).
insert_ord(X, T, [X|T]).



%------------------------------------------------------------------------------------------------
bubble_sort(L,R):-one_pass(L,R1,F), nonvar(F), !, bubble_sort(R1,R).
bubble_sort(L,L).


one_pass([H1,H2|T], [H2|R], F):-H1>H2, !, F=1, one_pass([H1|T],R,F).
one_pass([H1|T], [H1|R], F):-one_pass(T, R, F).
one_pass([], [] ,_).
%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

quick_sort([H|T], R):- % alegem pivot primul element
                         partition(H, T, Sm, Lg),
                         quick_sort(Sm, SmS), % sortam sublista cu elementele mai mici decat pivotul
                         quick_sort(Lg, LgS), % sortam sublista cu elementele mai mari decat pivotul
                         append(SmS, [H|LgS], R).
quick_sort([], []).

partition(H, [X|T], [X|Sm], Lg):-X<H, !, partition(H, T, Sm, Lg).
partition(H, [X|T], Sm, [X|Lg]):-partition(H, T, Sm, Lg).
partition(_, [], [], []).

%------------------------------------------------------------------------------------------


merge_sort(L, R):-split(L, L1, L2), % imparte L in doua subliste de lungimi egale
                 merge_sort(L1, R1),
                 merge_sort(L2, R2),
                 merge(R1, R2, R). % interclaseaza sublistele ordonate
merge_sort([H], [H]). % split returneaza fail daca lista ii vida sau are doar un singur element
merge_sort([], []).

split(L, L1, L2):-length(L, Len),
                  Len>1,
                  K is Len/2,
                  splitK(L, K, L1, L2).
splitK([H|T], K, [H|L1], L2):-K>0,!,K1 is K-1,splitK(T, K1, L1, L2).
splitK(T, _, [], T).

merge([H1|T1], [H2|T2], [H1|R]):-H1<H2, !, merge(T1, [H2|T2], R).
merge([H1|T1], [H2|T2], [H2|R]):-merge([H1|T1], T2, R).
merge([], L, L).
merge(L, [], L).


%-----------------------------------------------------------------------------------------------------------

sel_sort_desc(L, [M|R]):- max1(L, M),
                         delete1(M, L, L1),
                         sel_sort_desc(L1, R).
sel_sort_desc([], []).


%-------------Sorteaza lista de caractere ascii--------------------------------------------------------------------------------



sort_chars(L, [M|R]):-  min_char(L, M),
                        delete(L, M, L1),

sort_chars(L1, R).
sort_chars([], []):- !.

min_char([H|T], M) :- min_char(T, M),
                      char_code(M, R1),
                      char_code(H, R2), R1<R2, !.
min_char([H|_], H).

%----------------------sorteaza lista de subliste in functie de lungimea sublistelor----------------------------
sort_len(L, [M|R]):- min_list(L, M),
                    delete(L, M, L1),
                    sort_len(L1, R).
sort_len([], []):- !.

min_list([H|T], M) :- min_list(T, M),
                   length(M, R1),
                   length(H, R2),
                    R1<R2, !.
min_list([H|_], H).





%------------------------------------------LISTE ADANCI-----------------------------------
%L1 = [1,2,3,[4]]    member1(1,L1).



max(A, B, B) :- A<B.
max(A, B, A) :- A>B.
max(A, A, A).

depth([H|T], D) :- atomic(H), !, depth(T, D).
depth([H|T], D) :- depth(H, D1), depth(T, D2), D3 is D1+1, max(D3, D2, D).
depth([], 1).

append([H|T], L2, [H|R]) :- append(T, L2, R).
append([], L2, L2).

flat([H|T], [H|R]):- atomic(H), !, flat(T, R).
flat([H|T], R) :- flat(H, R1), flat(T, R2), append(R1, R2, R).
flat([], []).


%extrage elementele atomice de la capul fiecarei liste
heads([],[],_).
%la recursiv setam flag=0
heads([H|T],[H|R],1):- atomic(H), !, heads(T,R,0).

heads([H|T],R,0):- atomic(H), !, heads(T,R,0).

heads([H|T],R,_):- heads(H,R1,1), heads(T,R2,0), append(R1,R2,R).
heads_pretty(L,R):- heads(L, R, 1).


member(H, [H|_]):-!.
member(X, [H|_]) :- member(X, H), !.
member(X, [_|T]) :- member(X, T).

count_atomic([H|T], Count):- atomic(H), !, count_atomic(T, Count1), Count is Count1 +1.
count_atomic([H|T], Count):- count_atomic(H, Count1), count_atomic(T, Count2), Count is Count1+Count2.
count_atomic([], 0).


%numarul de elemente atomice din lista
sum_atomic([H|T], Sum) :- atomic(H), not(is_list(H)), !, sum_atomic(T, Sum1), Sum is Sum1+H.
sum_atomic([H|T], Sum) :- sum_atomic(H, Sum1), sum_atomic(T, Sum2), Sum is Sum1+Sum2.
sum_atomic([], 0).



%Scrie?i predicatul lasts(L,R) care extrage elementele atomice de pe ultima
%pozi?ie din fiecare sublista din L.
lasts([], []).
lasts([H], [H]) :- atomic(H).
lasts([H|T], R):- atomic(H), !, lasts(T, R).
lasts([H|T], R):- lasts(H, L1), lasts(T, L2), append(L1, L2, R).


%Scrie?i predicatul replace(X,Y,L,R) care înlocuie?te pe X cu Y în lista adânca
%L (la orice nivel de imbricare) ?i pune rezultatul în R.
replace(H, Y, [H|T], [Y|R]):- !, replace(H, Y, T, R).
replace(X, Y, [H|T], [H|R]) :- atomic(H), !, replace(X, Y, T, R).
replace(X, Y, [H|T], R) :-  replace(X, Y, H, R1), replace(X, Y, T, R2), append([R1], R2, R).
replace(_, _, [], []).






%-------------------------------ARBORI------------------------------------------
%tree1(t(6, t(4,t(2,nil,nil),t(5,nil,nil)), t(9,t(7,nil,nil),nil))).  operatie_pe_arbore(T,…).

inorder(t(K,L,R), List):-inorder(L,LL), inorder(R,LR),
append(LL, [K|LR], List).
inorder(nil, []).



% cheie, subarbore stâng ?i subarbore drept
preorder(t(K,L,R), List):-preorder(L,LL), preorder(R, LR),
append([K|LL], LR, List).
preorder(nil, []).


% subarbore stâng, subarbore drept ?i apoi cheia
postorder(t(K,L,R), List):-postorder(L,LL), postorder(R, LR),
append(LL, LR,R1), append(R1, [K], List).
postorder(nil, []).

search_key(Key, t(Key, _, _)):-!.
search_key(Key, t(K, L, _)):-Key<K, !, search_key(Key, L).
search_key(Key, t(_, _, R)):-search_key(Key, R).


insert_key(Key, nil, t(Key, nil, nil)). % insereaza cheia în arbore
insert_key(Key, t(Key, L, R), t(Key, L, R)):-!. % cheia exista deja
insert_key(Key, t(K,L,R), t(K,NL,R)):- Key<K,!,insert_key(Key,L,NL).
insert_key(Key, t(K,L,R), t(K,L,NR)):- insert_key(Key, R, NR).



delete_key(Key, t(Key, L, nil), L):-!.
delete_key(Key, t(Key, nil, R), R):-!.
delete_key(Key, t(Key, L, R), t(Pred,NL,R)):-!,get_pred(L,Pred,NL).
delete_key(Key, t(K,L,R), t(K,NL,R)):-Key<K,!,delete_key(Key,L,NL).
delete_key(Key, t(K,L,R), t(K,L,NR)):-delete_key(Key,R,NR).

% cauta nodul predecesor
get_pred(t(Pred, L, nil), Pred, L):-!.
get_pred(t(Key, L, R), Pred, t(Key, L, NR)):-get_pred(R, Pred, NR).




%Înal?ime unui arbore
height(nil, 0).
height(t(_, L, R), H):-height(L, H1),
			height(R, H2),
			max(H1, H2, H3),
			H is H3+1.

%Scrie?i un predicat care colecteaz? într-o list? toate cheile din frunzele
 %%arborelui binar.

collect(nil, []).
collect(t(Key, nil, nil), [Key]).
collect(t(_, L, R), List):- collect(L, R1),
	collect(R, R2),
	append(R1, R2, List).


%---------------------------------------------arbri ternari


append3([H|T], L2, L3, [H|R]) :- append3(T, L2, L3, R).
append3([], [H|T], L3, [H|R]) :- append3([], T, L3, R).
append3([], [], L3, L3).



inorder3(t(K,L,M,R), List):-inorder3(L,LL), inorder3(M, LM), inorder3(R,LR),
	append3(LL, [K|LM], LR, List).
inorder3(nil, []).
% cheie, subarbore stang si subarbore drept
preorder3(t(K,L,M,R), List):-preorder3(L,LL), preorder3(M, LM), preorder3(R, LR),
	append3([K|LL], LM, LR, List).
preorder3(nil, []).


% subarbore stang, subarbore drept si apoi cheia
postorder3(t(K,L,M,R), List):-postorder3(L,LL), postorder3(M, LM), postorder3(R, LR),
	append3(LL, LM, LR,R1), append(R1, [K], List).
postorder3(nil, []).


max3(X, Y, Z, M):- Max is max(X, Y), M is max(Max, Z).

height3(nil, 0).
height3(t(_, L, M, R), H):-height3(L, H1),
	height3(M, H2),
	height3(R, H3),
	max3(H1, H2, H3, H4),
	H is H4+1.


%-----------------STRUCTURI INCOMPLETE LISTE INCOMPLETE----------------------------------------------

 member_il(_, L):-var(L), !, fail.
member_il(X, [X|_]):-!.
member_il(X, [_|T]):-member_il(X, T).


insert_il(X, L):-var(L), !, L=[X|_].
insert_il(X, [X|_]):-!. % elementul exist? deja
insert_il(X, [_|T]):- insert_il(X, T).

delete_il(_, L, L):-var(L), !. % am ajuns la finalul listei
delete_il(X, [X|T], T):-!. % ?tergem prima apari?ie ?i ne oprim
delete_il(X, [H|T], [H|R]):-delete_il(X, T, R).


%arbori

search_it(_, T):-var(T),!,fail.
search_it(Key, t(Key, _, _)):-!.
search_it(Key, t(K, L, _)):-Key<K, !, search_it(Key, L).
search_it(Key, t(_, _, R)):-search_it(Key, R).

insert_it(Key, t(Key, _, _)):-!.
insert_it(Key, t(K, L, R)):-Key<K, !, insert_it(Key, L).
insert_it(Key, t(_, _, R)):-insert_it(Key, R).




delete_it(Key, T, T):-var(T),!.
delete_it(Key, t(Key, L, R), L):-var(R),!.
delete_it(Key, t(Key, L, R), R):-var(L),!.
delete_it(Key, t(Key, L, R), t(Pred,NL,R)):-!,get_pred(L,Pred,NL).
delete_it(Key, t(K,L,R), t(K,NL,R)):-Key<K,!,delete_it(Key,L,NL).
delete_it(Key, t(K,L,R), t(K,L,NR)):-delete_it(Key,R,NR).
% caut? nodul predecesor

get_pred(t(Pred, L, R), Pred, L):-var(R),!.
get_pred(t(Key, L, R), Pred, t(Key, L, NR)):-get_pred(R, Pred, NR).







%Concateneaza 2 liste incomplete
append_i(L1, L2, L2):-var(L1), !.
append_i([H|T], L2, [H|R]):-append_i(T, L2, R).


%Inverseaza o lista incompleta
reverse_i(L, R):-rev_i(L, [], R).
rev_i(L, Pr, [Pr|_]):-var(L), ! .
rev_i([H|T], Pr, R):-rev_i(T, [H|Pr], R).


%Converteste o lista incompleta într-o lista completa
incomp_comp(L, []):-var(L), !.
incomp_comp([H|T], [H|R]):-incomp_comp(T, R).

comp_incomp([], [_]).
comp_incomp([H|T], [H|R]):-comp_incomp(T, R).




%arbori

tree1(t(6, t(4, t(2, _, _), t(5, _, _)), t(9, t(7, _, _), _))).

preorder(T, R1):-pre(T, R), comp_incomp(R, R1).

pre(T, []):-var(T), ! .
pre(t(K, L, R), List):-pre(L, LL), pre(R, RL), append([K|LL], RL, List).

max(A, B, A):-A > B, !.
max(_, B, B).

%inaltime arbore incomplet
height_i(T, 0):-var(T), !.
height_i(t(_, L, R), H):-height_i(L, H1), height_i(R, H2), max(H1, H2, MH), H is MH + 1.


in_tree_comp(t(K, L, R), t(K, nil, nil)):- var(L), !, var(R), !.
in_tree_comp(t(K, L, R), t(K, NL, nil)):- var(R), !, 										   in_tree_comp(L, NL).
in_tree_comp(t(K, L, R), t(K, nil, NR)):- var(L), !, 											in_tree_comp(R, NR).
in_tree_comp(t(K, L, R), t(K, NL, NR)):-in_tree_comp(L, NL), 									in_tree_comp(R, NR).


%convertirea unui arbore incomplet intr-un arbore complet si invers.
convert_it1(K,nil):-var(K),!.
convert_it1(t(K,L,R),t(K,LL,RR)):- convert_it1(L,LL),convert_it1(R,RR).
convert_il1(nil,_).



transform_arb(T, nil):-var(T),!.
transform_arb(t(Key, L, R), L):-var(R),!.
transform_arb(t(Key, L, R), R):-var(L),!.
transform_arb(t(K,L,R), t(K,NL,R)):-transform_arb(K,L,NL).
transform_arb(t(K,L,R), t(K,L,NR)):-transform_arb(K,R,NR).



%-------------------------------------LISTE DIFERENTA-----------------

%adaugare element in finalul listei
add2(X, LS, LE, RS, RE):- RS = LS, LE = [X|RE].


append_dl(LS1,LE1, LS2,LE2, RS,RE):- RS=LS1, LE1=LS2, RE=LE2.



%arbore

inorder_dl(nil,L,L). % lista vida este reprezentata de 2 variabile egale
inorder_dl(t(K,L,R),LS,LE):-inorder_dl(L,LSL,LEL), % apel pe subarbore stâng
                            inorder_dl(R,LSR,LER), % apel pe subarbore drept
                            LS=LSL,
                            LEL=[K|LSR], % K este adaugat în fa?a la LSR
                            LE=LER.



quicksort_dl([H|T], S, E):- % s-a adaugat un parametru nou
                           partition(H, T, Sm, Lg), % predicatul partition a ramas la fel
                           quicksort_dl(Sm, S, [H|L]),
                           quicksort_dl(Lg, L, E).
quicksort_dl([], L, L). % condi?ia de terminare s-a modificat


%----------------efecte laterale

:-dynamic memo_fib/2.
fib(N,F):- memo_fib(N,F), !.
fib(N,F):- N>1,
           N1 is N-1,
           N2 is N-2,
           fib(N1,F1),
           fib(N2,F2),
           F is F1+F2,
           assertz(memo_fib(N,F)).
fib(0,1).
fib(1,1).
print_all:-memo_fib(N,F),
           write(N),
           write(' – '),
           write(F),
           nl,
           fail.
print_all.



%colecteaza toate permutarile unei liste
all_perm(L,_):- perm(L,L1), % predicatul de generare a unei permutari (vezi lucrare de laborator cu sortari)
                assertz(p(L1)),
                fail.
all_perm(_,R):- collect_perms(R).

collect_perms([L1|R]):- retract(p(L1)), !, collect_perms(R).
collect_perms([]).

%convertire lista incompleta in diferenta
convertID(L,E,E) :- var(L), !.
convertID([H|T], S, E) :- S=[H|T1], convertID(T,T1,E).

%convertire diferenta in incompleta
convertDI(E,E,_) :- var(E), !.
convertDI(SL, EL, [H|T]) :- SL=[H|SLint], convertDI(SLint,EL,T).

%comvertire din comlpeta in diferenta
convertCD([H|[]],[H|EL],EL).
convertCD([H|T],[H|R],EL):-convertCD(T,R,EL).

%convertire din diferenta in completa
convertDC(L,[]):-var(L),!.
convertDC([H|T],[H|R]):-convertDC(T,R).

%apaltizare lista diferenta
flat_dl([H|T],[H|RS],RE):- atomic(H),!,flat_dl(T,RS,RE).
flat_dl([H|T],RS,RE):- flat_dl(H,RS,RX),flat_dl(T,RX,RE).
flat_dl([H|[]],[H|RE],RE).

%flat_dl([[1], 2, [3, [4, 5]]], RS, RE).
%RS = [1, 2, 3, 4, 5|RE] ;
%false



collecteven(nil,L,L).
collecteven(t(K,L,R),LS,LE):- 0 is K mod 2,
			collecteven(L,LS,[K|LT]),
			collecteven(R,LT,LE).
collecteven(t(_,L,R),LS,LE):-
			collecteven(L,LS,LT),
			collecteven(R,LT,LE).

%colecteaza noduri chei pare arbore binar folosind liste diferenta
colect_pare(nil,L,L).
colect_pare(t(K,L,R),LS,LE):-
		0 is mod(K,2), !,
		colect_pare(L,LSL,LEL),
		colect_pare(R,LSR,LER),
		LS=LSL,
		LEL=[K|LSR],
		LE=LER.
colect_pare(t(K,L,R),LS,LE):-
		colect_pare(L,LSL,LEL),
		colect_pare(R,LSR,LER),
		LS=LSL,
		LEL=[K|LSR],
		LE=LER.



collectIncompletTree(T,L,L,_,_):-var(T), !.
collectIncompletTree(t(K,L,R),LS,LE,K1,K2):-
			K >= K1, K =< K2,
			collectIncompletTree(L,LS,[K|LT],K1,K2),
			collectIncompletTree(R,LT,LE,K1,K2).
collectIncompletTree(t(_,L,R),LS,LE,K1,K2):-
			collectIncompletTree(L,LS,LT,K1,K2),
			collectIncompletTree(R,LT,LE,K1,K2).



%-------------------------GRAFURI------------------------
node(a). node(b). %etc
edge(a,b). edge(b,a).
edge(b,c). edge(c,b).

%----------------------

:-dynamic neighbor/2.
neighbor(a, [b, d]).
neighbor(b, [a, c, d]).
neighbor(c, [b, d]).
neighbor(h, []).
%---------------------

%conversie neighbor to edge
neighb_to_edge:-retract(neighbor(Node,List)),!, %extrage un predicat neighbor ?i apoi îl proceseaza
                 process(Node,List),
                 neighb_to_edge.
neighb_to_edge. % daca nu mai sunt predicate neighbor înseamna ca amterminat
% procesarea presupune adaugare de predicate edge ?i node pentru un predicat neighbor
process(Node, [H|T]):- assertz(edge(Node, H)), process(Node, T).
process(Node, []):- assertz(node(Node)).


%cauta path intre noduri path(a,c,R).
path(X,Y,Path):-path(X,Y,[X],Path).
path(X,Y,PPath, FPath):- edge(X,Z),
			not(member(Z, PPath)),
			append(PPath, [Z], R),
			path(Z, Y, R, FPath).
path(X,X,PPath, PPath).


%trecerea printr un anumit set de noduri  restricted_path(a, c, [a,c,d], R).

restricted_path(X,Y,LR,P):- path(X,Y,P), check_restrictions(LR, P).
check_restrictions([],_):- !.
check_restrictions([H|T], [H|R]):- !, check_restrictions(T,R).
check_restrictions(T, [_|L]):-check_restrictions(T,L).

%drumul cu lungime minima
optimal_path(X,Y,Path):-asserta(sol_part([],100)),
			path(X,Y,[X],Path,1).
optimal_path(_,_,Path):-retract(sol_part(Path,_)).
path(X,X,Path,Path,LPath):- retract(sol_part(_,_)),!,asserta(sol_part(Path,LPath)),fail.
path(X,Y,PPath,FPath,LPath):-   edge(X,Z),
			        not(member(Z,PPath)),
				LPath1 is LPath+1,
				sol_part(_,Lopt),
				LPath1<Lopt,
				append(PPath,[Z],R),
				path(Z,Y,R,FPath,LPath1).
%conversie edge to neighbor
edge_to_neighbor:-retract(node(Node)),!,
		process1(Node),
		 edge_to_neighbor.
edge_to_neighbor:- retract(edge(Node, Elem)),!,
		process2(Node, Elem),
		 edge_to_neighbor.
edge_to_neighbor.
process1(Node):- assertz(neighbor(Node, [])).
process2(Node, Elem):-retract(neighbor(Node,T)),
			assertz(neighbor(Node, [Elem|T])).


%verifica daca un graf are ccluri cycle(a, R).

cycle(X, [X|R]):-edge(X,Z),edge(Z,X), path(Z, X, R).




%------------------------DFS---------------------
:- dynamic nod_vizitat/1.
% d_search(Source, Path)
d_search(X,_):-df_search(X,_). % parcurgerea nodurilor
d_search(_,L):-!, collect_reverse([],L). % colectarea rezultatelor
df_search(X,L):- asserta(nod_vizitat(X)),
		edge(X,Y),
		not(nod_vizitat(Y)),
		df_search(Y,L).
% colectarea se face în ordine inversa
collect_reverse(L,P):- retract(nod_vizitat(X)), !,
			collect_reverse([X|L],P).
			collect_reverse(L,L).

%------------------------BFS----------------------
 % parcurgerea nodurilor
b_search(X,_):- assertz(nod_vizitat(X)),
		assertz(nod_de_expandat(X)),
		bf_search.
b_search(_,R):-!, collect_reverse([],R). % colectarea rezultatelor
bf_search:- retract(nod_de_expandat(X)),
		expand(X),!,
		bf_search.
expand(X):-edge(X,Y),
		not(nod_vizitat(Y)),
		asserta(nod_vizitat(Y)),
		assertz(nod_de_expandat(Y)),
		fail.
		expand(_).