% al K lea element din lista L in X
% ( 1 )
extract_k([_|T],K,X) :- K > 0 , CONT is K - 1 , ! , extract_k(T,CONT,X).
extract_k([H|_],K,X) :- K = 0 , X is H.

%usage: extract_k([69,12,3,55,23],5,X).

% ?- diagonal([[1,2,3],[4,5,6],[7,8,9]], D).
% D = [1, 5, 9].
% ( 2 )
%diagonal_fun([],[],0).
diagonal([H|T],D,K) :- extract_k(H,K,X) ,
                        atomic(X),
                        %writeln(X),
                    append(D,[X],D1),
                    writeln(D1),
                    CONT is K + 1 ,
                    diagonal(T,D1,CONT).

%( 1 )
cmmdc(B,B,B).
cmmdc(A,B,C) :- A>B , A1 is A-B , cmmdc(A1,B,C).
cmmdc(A,B,C) :- B>A , B1 is B-A , cmmdc(A,B1,C).

%( 2 )
cmmmc(A,B,C) :- cmmdc(A,B,D) , C is A*B/D.

%( 3 ) suma
suma([H|T],R) :- suma(T,ACC) , R is ACC + H.
suma([],0).

%– suma([1,2,3,4,5], R).

% ( 4 )
%? – separate_parity([1,2,3,4,5,6], E, O).
%E = [2,4,6], O=[1,3,5]

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

% ( 5 ) Înlocui?i toate apari?iile lui X cu Y.
%Ex: ? – replace_all(1, a, [1,2,3,1,2], R).

replace_all(X,Y,[X|T],[Y|R]) :- replace_all(X,Y,T,R),!.
replace_all(X,Y,[H|T],[H|R]) :- not(H is X),  replace_all(X,Y,T,R).
replace_all(_,_,[],[]).

% ( 6 ) ?terge?i elementele de pe pozi?ii divizibile cu K.
%Ex: ? – sterge_k([6,5,4,3,2,1], 3, R).
%R = [6,5,3,2]

sterge( [H|T] , K , CONT , [H|R] ) :- CONT < K ,
                                     CONT1 is CONT + 1,
                                     sterge(T,K,CONT1,R) , !.
sterge( [_|T] , K , CONT , R ) :- 0 is CONT mod K , sterge(T,K,1,R).
sterge( [], _ , _ , [] ).

sterge_k(L,K,R) :- sterge(L,K,1,R).

% ( 7 ) Inverseaza o lista completa/incompleta.
%? – reverse([1, 2, 3, 4, 5], R).
%R = [5, 4, 3, 2, 1].

%reverse lista normala cu REC inainte
reverse1([],[]).
reverse1([H|T],R) :- reverse1(T,ACC) , append(ACC,[H],R).

reverse_il( L , R , R ) :- var(L),  !.
reverse_il( [H|T] , R , ACC ) :- reverse_il(T,R,[H|ACC]).
% reverse2([1, 2, 3, 4, 5|_], R ).
reverse2( L , R ) :- reverse_il(L,R,_).

% ( 8 ) Calcula?i adâncimea maxima a unei liste imbricate.
%Ex: ? – adancime([1, [2, [3]], [4]], R1), adancime([], R2).
%R1 = 3, R2 = 1.
%adancime([1, [2, [3]], [4]], R1), adancime([], R2).

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

adancime([],1).
adancime([H|T],R) :- atomic(H) ,!, adancime(T,R).
adancime([H|T],R) :- adancime(H,R1), adancime(T,R2),
                    R3 is R1 + 1,
                    max(R2,R3,R).

% ( 9 ) Aplatiza?i o lista imbricata cu liste complete/incomplete.
%Ex: ? - flat([1, [2, [3]], [4]], R).
%R = [1,2,3,4].

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( [],[] ).

%flat_il([[1|_], 2, [3, [4, 5|_]|_]|_], R).

append_il(L,L2,L2):- var(L),!.
append_il([H|T],L2,[H|R]) :- append_il(T,L2,R).

flat_il(L,_) :- var(L), !.
flat_il( [H|T] ,[H|R] ) :- atomic(H) , ! , flat_il(T,R).
flat_il( [H|T] , R ) :- flat_il(H,R1),flat_il(T,R2),  append_il(R1,R2,R).
%flat_il( [],[] ).
%flat_il([[1|_], 2, [3, [4, 5|_]|_]|_], R).


%( 11 ). Colecta?i toate nodurile unui arbore binar complet/incomplet în inordine folosind liste complete/diferen?a.
%tree1(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
%? – tree(T), inordine(T, R).
%R = [2,4,5,6,7,9].

%tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
inorder( t(K,L,R) , LIST ) :- inorder(L,LL) ,
                             inorder(R,LR) ,
                            append(LL,[K|LR],LIST).
inorder( nil , [] ).

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

postorder( t(K,L,R) , LIST ) :- postorder(L,LL) ,
                             postorder(R,LR) ,
                            append(LL,LR,R1) ,
                            append(R1,[K],LIST).
postorder( nil , [] ).


%12. Colectați toate frunzele dintr-un arbore binar.
tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
%? – tree(T), collect_k(T, R).
%R = [2,5,7].
height3(nil, 0).
height3(t(_, L,Mid, R), H):-
    height3(L, H1),
    height3(Mid, H2),
    height3(R, H3),
    max(H1, H2, H4),
    max(H4, H3 ,H5),
    H is H5+1.

collect( t(K,nil,nil) , [K] ) :- !.
collect( t(_,L,R) , LIST  ) :-
    collect( L , LL ),
    collect( R , RR ),
    append(LL,RR,LIST).
collect( nil , [] ).

count_leaves( t(_,_,_) , 1 ).
count_leaves( t(_,L,R) , CONT ) :-
        count_leaves( L , CONT1 ),
        count_leaves( R , CONT2 ),
        CONT is CONT1 + CONT2.


height( nil , 0 ).
height( t(_,L,R) , H ) :-
        height(L, H1 ),
        height(R, H2 ),
        max(H1,H2,H3),
        H is H3+1.

% Toate ele pare dintr-un arbore binar incomplet/complet
tree2(t(6, t(4, t(2, _, _), t(5, _, _)), t(9, t(7, _, _), _))).

%extract_even(T, []):- var(T), !.
extract_even(nil,[]).
extract_even(t(K, L, R),Rez):-
    1 is K mod 2, !,
    extract_even(L,Rez1),
    extract_even(R,Rez2),
    append(Rez1,[K],RezP),
    append(RezP,Rez2,Rez).
extract_even(t(_, L, R),Rez):-
    extract_even(L,Rez1),
    extract_even(R,Rez2),
    append(Rez1,Rez2,Rez).


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

adancime([],1).
adancime([H|T],R):-atomic(H),adancime(T,R).
adancime([H|T],R):-adancime(H,R1),adancime(T,R2),
                    R3 is R1+1,max(R2,R3,R).

adan( L,R,MAX ) :- adancime(L,MAX).

tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).

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

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



%encode
max_encode([H1,H1|T],R,C):-!, C1 is C+1, max_encode([H1|T],R,C1).
max_encode([_, H2|T],[C|TR],C):- max_encode([H2|T],TR,1).
max_encode([_],[C],C).
max_encode([],[],_).
max_encode([H1,H2|T],R):- max_encode([H1,H2|T],R1,1), max(R1,R).

max_from_list([H|T],R,MAX) :- H>MAX , max_from_list(T,R,H).
max_from_list([_|T],R,MAX) :- max_from_list(T,R,MAX).
max_from_list([],_,_).

max_enc(L,R,X) :- max_encode(L,R,1),max_from_list(R,X).

%max_enc([a,a,b,b,b,d,a,a,a,a,d],R,X).
%