% Algoritmi su liste, alberi binari e binary search tree

% suffix(Xs, Zs) :- Xs e' un suffisso (parte finale) di Zs)
suffix(Xs, Xs).
suffix(Xs, [Y|Ys]) :- suffix(Xs,Ys).

% prefix(Xs, Zs) :- Xs e' un prefisso (parte iniziale) di Zs)
prefix([], Xs).
prefix([X|Xs], [X|Ys]) :- prefix(Xs,Ys).
	
% append(Xs,Ys,Zs) :- Zs = Xs @ Ys)
append([],Xs,Xs).
append([X|Xs],Ys,[X|XsYs]):-append(Xs,Ys,XsYs).
	
% flatten(Xss, Zs) :- Zs e' la concatenazione delle liste elementi della
% 						lista di liste Xss
flatten([],[]).
flatten([Xs|Xss],Zs) :- flatten(Xss,Ys),append(Xs,Ys,Zs).

% isBST(T), insert(X,T,T') => isBST(T'),
% labels(T') = labels(T) U {a} dove:
%		labels(empty) = insieme vuoto,
%		labels(node(X,L,R)) = {a} U labels(L) U labels(R)

insert(X,empty,node(X,empty,empty)).
insert(X,node(Y,L,R),node(Y,L1,R)) :- X @< Y,insert(X,L,L1).
insert(X,node(Y,L,R),node(Y,L,R1)) :- X @> Y,insert(X,R,R1).
insert(X,node(X,L,R),node(X,L,R)).
	
% isBST(T), insert([a_1,...,a_n],T,T') => isBST(T')
% labels(T') = labels(T) U {a_1, ..., a_n} *)
insertlist([],T,T).
insertlist([X|L],T,T2) :- insert(X,T,T1), insertlist(L,T1,T2).
	
% consBST([a_1,...,a_n],T) => isBST(T),
% labels T = {a_1, ..., a_n}
consBST(L,T) :- insertlist(L,empty,T).
	
%visita inorder di alberi binari
inorder(empty,[]).
inorder(node(X,L,R),F):-inorder(L,Lf),inorder(R,Rf),append(Lf,[X|Rf],F).
	
% isBST(T) :- T e' un binary search tree

isBST(empty).
isBST(T) :- isBST(T,R).
isBST(node(X,empty,empty),result(X,X)).
isBST(node(X,empty,R),result(X,MaxR)) :-
	R \== empty, isBST(R,result(MinR,MaxR)), X @< MinR.
isBST(node(X,L,empty),result(MinL,X)) :-
	L \==empty, isBST(L,result(MinL,MaxL)), MaxL @< X.
isBST(node(X,L,R),result(MinL,MaxR)) :-
	R \== empty, L\== empty, isBST(L,result(MinL,MaxL)), MaxL @< X,
	isBST(R,result(MinR,MaxR)), X @< MinR.