intersect(A,B,C):- findall(X,(member(X,A),member(X,B)),C).

difference(A,B,C):- findall(X,(member(X,A),not(member(X,B))),C).

%----------------------- PRÁTICA DIFFERENCE LISTS --------------------------%

%tree2list(void,[]).
%tree2list(bt(X,E,D),L) :- tree2list(E,L1), tree2list(D,L2), append(L1,[X],L3), append(L3,L2,L).

tree2list(T,L) :- tree2listdl(T,L-[]).
tree2listdl(void,L-L).
tree2listdl(bt(X,E,D),L-R):- tree2listdl(E,L-[X|R1]), tree2listdl(D,R1-R).

preorder(T,L):- preordert(T,L-[]).
preordert(void,L-L).
preordert(bt(A,E,D),[A|L]-R):-preordert(E,L-R1), preordert(D,R1-R).

postorder(T,L):- postordert(T,L-[]).
postordert(void,L-L).
postordert(bt(A,E,D),L-R) :- postordert(E, L-R1), postordert(D,R1-[A|R]).

%separate([o,x,o,x,x,x,o,x],L).

separate(L,L2) :- separatedl(L,L2-[]).
separatedl([],L2-L2).
separatedl([o|L],L2-R2) :- separatedl(L, L2-[o|R2]).
separatedl([x|L],[x|L2]-R2):- separatedl(L, L2-R2).


%----------------------------- PRÁTICA DCG -------------------------------%


dec-->d,dec.
dec-->d.
d-->[0];[1];[2];[3];[4];[5];[6];[7];[8];[9].

even-->p.
even-->p,even.
p-->[0];[2];[4];[6];[8].

greet-->sn(_,_).
  sn(N,G)-->adj(N,G),n(N,G).
  sn(N,G)-->det(N,G),adj(N,G),n(N,G).
  adj(sing,femi)-->[boa].
  adj(sing,maxo)-->[bom].
  adj(plur,femi)-->[boas].
  adj(plur,maxo)-->[bons].
  det(sing,maxo)-->[muito].
  det(sing,femi)-->[muita].
  det(plur,maxo)-->[muitos].
  det(plur,femi)-->[muitas].
  n(sing,femi)-->[tarde];[noite].
  n(plur,femi)-->[tardes];[noites].
  n(sing,maxo)-->[dia].
  n(plur,maxo)-->[dias].

bet(N, M, K) :- N < M, K = N.
bet(N, M, K) :- N == M, !, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).

date-->seq.
    seq-->day,month(_).
	day-->[1];[2];[3];[4];[5];[6];[7];[8];[9];[10];[11];[12];[13];[14];[15];
    [16];[17];[18];[19];[20];[21];[22];[23];[24];[25];[26];[27];[28];[29];[30];[31].
	month(D)-->{D=<31},[jan];[mar];[may];[aug];[oct];[dec].
	month(D)-->{D=<30},[apr];[jun];[jul];[sep];[nov].
	month(D)-->{D=<28},[feb].

%--- b a* b* ---%
s-->b1,a,b.
b1-->[b].
a-->[a],a.
a-->[].
b-->[b],b.
b-->[].

btree(void).
btree(bt(R,_,_)):- number(R).
btree(bt(_,E,_)):- number(E), btree(E).
btree(bt(_,_,D)):- number(D), btree(D).

inbtree(bt(A,_,bt(S,_,_)),A,S):-!.
inbtree(bt(_,E,_),A,S):- inbtree(E,A,S),!.
inbtree(bt(_,_,D),A,S):- inbtree(D,A,S),!.


containAll([loc(X1,Y1),loc(X2,Y2)],H,V):-
	Hmin is min(X1,X2), Hmax is max(X1,X2),
    Vmin is min(Y1,Y2), Vmax is max(Y1,Y2),
	H is Hmax-Hmin, V is Vmax-Vmin.
%containAll([loc(X1,Y1),loc(X2,Y2)|XYs],H,V).

listLoc([loc(X1,Y1)|XYs],Hfin,Vfin):-
    listH([loc(X1,_)|XYs],H),
    listV([loc(_,Y1)|XYs],V),
    min_in_list(H,Hmin),
    max_in_list(H,Hmax),
    min_in_list(V,Vmin),
    max_in_list(V,Vmax),
    Hfin is Hmax-Hmin,
    Vfin is Vmax-Vmin.


listH([],[]).
listH([loc(X,_)|Xs],[X|H]):-
 	listH(Xs,H).

listV([],[]).
listV([loc(_,Y)|Ys],[Y|H]):-
 	listV(Ys,H).
%----Minimun in a list----%
min_in_list([Min],Min).

min_in_list([H,K|T],M) :-
    H =< K,
    min_in_list([H|T],M).

min_in_list([H,K|T],M) :-
    H > K,
    min_in_list([K|T],M).

%-----Maximum in list-----%
max_in_list([Min],Min).

max_in_list([H,K|T],M) :-
    H >= K,
    max_in_list([H|T],M).

max_in_list([H,K|T],M) :-
    H < K,
    max_in_list([K|T],M).


%--- example 1: [a] [a,b,c]
%--- example 2: [not,a]
%--- example 3: [a, not, b]
%--- example 4: [and, b, not ,c]
%--- example 5:  errado! [b, not] , [not]

frase--> seq1.
	seq1--> simbolo.						% frase([a,b,c],[]).
	seq1--> conj.							% frase([not],[]).
	seq1--> c.					 			% frase([not,a,or,b,and,f],[]).
	seq1--> c2.								% frase([a,or,b,and,c],[]).
simbolo--> ([a];[b];[c];[d];[e];[f]),simbolo.
simbolo--> [].
c--> conj,simbolo2,c.
c--> [].
c2--> simbolo2,c.
conj--> [not];[and];[or].
simbolo2--> [a];[b];[c];[d];[e];[f].

%------- input: T1= bt(....), T2= bt(....), intersect_trees()

intersect2(A,B,C):- setof(X, (member(X,A),member(X,B)), C).

list2tree2(void,[]).
list2tree2(bt(X,E,D), L):-
    list2tree2(E,L1),
    list2tree2(D,L2),
    append(L1,[X],L3),
    append(L3,L2,L).

intersect_trees(T1,T2,L):-
    list2tree2(T1,L),
    list2tree2(T2,L2),
    intersect2(L,L2,L).