%pour qu'il ne tronque pas les termes
:- prolog_flag(toplevel_print_options,_,[quoted(true),numbervars(true),portrayed(true),max_depth(30)]).
:- prolog_flag(debugger_print_options,_,[quoted(true),numbervars(true),portrayed(true),max_depth(30)]).

%PARTIE 1 : LES ENTIERS
%inferieur(A,B) vrai si A est inférieur strictement à B.
%inferieur(A,B) vrai si A < B.
inferieur(zero,s(_A)).
inferieur(s(A),s(B)):-inferieur(A,B).
%| ?- inferieur(A,B).
%A = zero,
%B = s(_A) ? ;
%A = s(zero),
%B = s(s(_A)) ? ;
%A = s(s(zero)),
%B = s(s(s(_A))) ? ;
%A = s(s(s(zero))),
%B = s(s(s(s(_A)))) ? 
%yes
%| ?- inferieur(s(s(s(zero))),s(zero)).
%no
%| ?- inferieur(s(zero),s(s(s(zero)))).
%yes
%| ?- inferieur(X,s(s(s(zero)))).
%X = zero ? ;
%X = s(zero) ? ;
%X = s(s(zero)) ? ;
%no

%max(A,B,M) vrai si M est le max de A et B.
max(A,A,A).
max(A,B,A):-inferieur(B,A).
max(A,B,B):-inferieur(A,B).

%somme(A,B,C) vrai si A+B=C. (Bornée)
somme(A,B,C):-somme1(A,B,C,zero).

somme1(s(A),B,s(C),Borne):-inferieur(Borne,s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(zero)))))))))))))))),somme1(A,B,C,s(Borne)).
somme1(zero,A,A,_Borne).
%test :
%| ?-somme(A,B,s(s(s(zero)))).
%A = zero,
%B = s(s(s(zero))) ? ;
%A = s(s(s(zero))),
%B = zero ? ;
%A = s(zero),
%B = s(s(zero)) ? ;
%A = s(s(zero)),
%B = s(zero) ? ;
%no
%| ?- somme(s(zero),s(s(zero)),C).
%C = s(s(s(zero))) ? ;

%produit(A,B,C) vrai si A*B=C (Borné)
produit(A,B,C):-produit1(A,B,C,zero).

produit1(zero,_A,zero,_Borne).
produit1(s(A),B,C,Borne):-inferieur(Borne,s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(zero)))))))))))))))),somme(B,D,C),produit1(A,B,D,s(Borne)).

%| ?- produit(X,Y,s(s(s(s(s(s(zero))))))).
%X = s(s(s(s(s(s(zero)))))),
%Y = s(zero) ? ;
%X = s(s(s(zero))),
%Y = s(s(zero)) ? ;
%X = s(s(zero)),
%Y = s(s(s(zero))) ? ;
%X = s(zero),
%Y = s(s(s(s(s(s(zero)))))) ? ;
%no
%| ?- produit(X,s(s(zero)),Y).
%X = zero,
%Y = zero ? ;
%X = s(zero),
%Y = s(s(zero)) ? ;
%X = s(s(zero)),
%Y = s(s(s(s(zero)))) ? ;
%X = s(s(s(zero))),
%Y = s(s(s(s(s(s(zero)))))) ? ;
%X = s(s(s(s(zero)))),
%Y = s(s(s(s(s(s(s(s(zero)))))))) ? 

%div(A,B,Q,R) vrai si le quotient de la division entière de A par B est Q
%  et son reste R.
div(A,B,Q,R):-inferieur(R,B),somme(P,R,A),produit(B,Q,P).

%test | ?- div(zero,s(s(zero)),Q,R).
%Q = zero,
%R = zero ? ;
%| ?- div(s(s(s(s(s(zero))))),s(s(zero)),Q,R).
%
%Q = s(s(zero)),
%R = s(zero) ? ;

%PARTIE II : Prédicats sur les listes
%concaténation de deux listes
conc([],L,L).
conc([X|L],L2,[X|L3]):-conc(L,L2,L3).

%longueur d'une liste
longueur([],zero).
longueur([_X|L],s(N)):-longueur(L,N).

%extrait d'une liste
%extrait(L,N,Milieu,Avant,Apres) vrai si Milieu est l'élément de L de
%rang N, Avant est la liste contenant les éléments de rang inférieur strict à N et
%Après est la liste des éléments de rang supérieur strict à N.
extrait([X|L],s(zero),X,[],L).
extrait([X|L],s(N),Y,[X|Lavant],Lapres):-extrait(L,N,Y,Lavant,Lapres).

%test
%| ?- extrait([a,b,c,d,e,f],s(s(s(s(zero)))),X,A,P).
%A = [a,b,c],
%P = [e,f],
%X = d ? ;
%no
%| ?- extrait([a,b,c,d,e,f],S,X,A,P).
%A = [],
%P = [b,c,d,e,f],
%S = s(zero),
%X = a ? ;
%A = [a],
%P = [c,d,e,f],
%S = s(s(zero)),
%X = b ? ;
%A = [a,b],
%P = [d,e,f],
%S = s(s(s(zero))),
%X = c ? ;
%A = [a,b,c],
%P = [e,f],
%S = s(s(s(s(zero)))),
%X = d ? ;
%A = [a,b,c,d],
%P = [f],
%S = s(s(s(s(s(zero))))),
%X = e ? ;
%A = [a,b,c,d,e],
%P = [],
%S = s(s(s(s(s(s(zero)))))),
%X = f ? ;
%no

%%dichotomise(L1,L2) vrai si L2 est la liste construite à partir de L1
%%contenant en premier l'élément milieu de L1 si 
dichotomise([],[]).
dichotomise(L,[Milieu|L1]):-longueur(L,N), div(N,s(s(zero)),Q,_R),extrait(L,s(Q),Milieu,Lavant,Lapres),dichotomise(Lavant,L2),dichotomise(Lapres,L3),conc(L2,L3,L1).

%test
%| ?- dichotomise([a,b,c,d,e,f,g,h],L).
%L = [e,c,b,a,d,g,f,h] ? ;
%no

%PARTIE III : arbre binaire de recherche
% est_vide(A) vrai si A est vide
est_vide(vide).

% racine(A,R), gauche(A,G) et droit(A,G) qui permettent d'obtenir
%  respectivement la racine, le sous-arbre gauche et le sous-arbre droit de
%  l'arbre A.
racine(noeud(X,_G,_D),X).
gauche(noeud(_X,G,_D),G).
droit(noeud(_X,_G,D),D).

% ajout(X,A,Res) ajoute l'entier X au bon endroit dans l'arbre A pour donner
%testez en ins\'erant successivement 6,2,8,1 et 7 dans un
%arbre initialement vide. 
ajout(X,vide,noeud(X,vide,vide)).
ajout(X,noeud(X,G,D),noeud(X,G,D)).
ajout(X,noeud(Y,G,D),noeud(Y,G1,D)):- inferieur(X,Y), ajout(X,G,G1).
ajout(X,noeud(Y,G,D),noeud(Y,G,D1)):- inferieur(Y,X), ajout(X,D,D1).

ajoutliste([],A,A).
ajoutliste([X|L],A,B):-ajout(X,A,A1),ajoutliste(L,A1,B).

%test
%| ?-ajoutliste([s(s(s(s(s(s(zero)))))),s(s(zero)),s(s(s(s(s(s(s(s(zero)))))))),s(zero),s(s(s(s(s(s(s(zero)))))))],vide,R).
%R = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)) ? ;
%no

arbre(noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide))).

% appartient(X,A) vérifie si X appartient à l'arbre A
appartient(X,noeud(X,_G,_D)).
appartient(X,noeud(Y,G,_D)):-inferieur(X,Y), appartient(X,G).
appartient(X,noeud(Y,_G,D)):- inferieur(Y,X), appartient(X,D).

%test
%| ?- arbre(A),appartient(s(s(s(zero))),A).
%no
%| ?- arbre(A),appartient(s(s(zero)),A).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)) ? ;
%no

%nbnoeud(A,N) vrai si N est le nombre de noeuds de A
nbnoeud(vide,zero).
nbnoeud(noeud(_X,G,D),s(N)):-nbnoeud(G,NG),nbnoeud(D,ND),somme(NG,ND,N).

%test
%| ?- arbre(A),nbnoeud(A,N).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%N = s(s(s(s(s(zero))))) ? 
%yes

%hauteur(A,H)
hauteur(vide,zero).
hauteur(noeud(_X,G,D),s(M)):-hauteur(G,HG),hauteur(D,HD),max(HD,HG,M).
%| ?- arbre(A),hauteur(A,H).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%H = s(s(s(zero))) ? 
%yes

% hauteur(A,X,H)
hauteur(vide,_X,erreur).
hauteur(noeud(X,_G,_D),X,s(zero)).
hauteur(noeud(Y,G,_D),X,s(H)):-inferieur(X,Y), hauteur(G,X,H).
hauteur(noeud(Y,_G,D),X,s(H)):- inferieur(Y,X), hauteur(D,X,H).

%test
%| ?- arbre(A),hauteur(A,s(zero),H).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%H = s(s(s(zero))) ? ;
%no

%parcours RGD
parcours_RGD(vide,[]).
parcours_RGD(noeud(X,G,D),[X|L]):-parcours_RGD(G,L1),parcours_RGD(D,L2),conc(L1,L2,L).

%test
%| ?- arbre(A),parcours_RGD(A,L).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%L = [s(s(s(s(s(s(zero)))))),s(s(zero)),s(zero),s(s(s(s(s(s(s(s(zero)))))))),s(s(s(s(s(s(s(zero)))))))] ? ;
%no

% parcours_croissant(A,L) L est la liste des entiers de l'arbre dans l'ordre croissant,
parcours_croissant(vide,[]).
parcours_croissant(noeud(X,G,D),L):-parcours_croissant(G,L1),parcours_croissant(D,L2),conc(L1,[X],L3),conc(L3,L2,L).

%test
%| ?- arbre(A),parcours_croissant(A,L).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%L = [s(zero),s(s(zero)),s(s(s(s(s(s(zero)))))),s(s(s(s(s(s(s(zero))))))),s(s(s(s(s(s(s(s(zero))))))))] ? ;
%no

% dernier(A,X) où X est le dernier entier de l'arbre,
dernier(noeud(X,_G,vide),X).
dernier(noeud(_X,_G,D),Y):-dernier(D,Y).

%test
%| ?- arbre(A),dernier(A,D).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%D = s(s(s(s(s(s(s(s(zero)))))))) ? ;
%no

% supprimer(A,X,Res) supprime X de A.
supprime(_X,vide,vide).
supprime(X,noeud(X,vide,D),D).
supprime(X,noeud(X,noeud(Y,G1,D1),D),noeud(Y,G1,D2)):-ajoutarbre1(D1,D,D2).
supprime(X,noeud(Y,G,D),noeud(Y,G1,D)):-inferieur(X,Y), supprime(X,G,G1).
supprime(X,noeud(Y,G,D),noeud(Y,G,D1)):- inferieur(Y,X), supprime(X,D,D1).
	
ajoutarbre(vide,A,A).
ajoutarbre(noeud(X,G,D),A,B):-ajout(X,A,A1),ajoutarbre(G,A1,A2),ajoutarbre(D,A2,B).

ajoutarbre1(vide,A,A).
ajoutarbre1(noeud(X,G,D),vide,noeud(X,G,D)).
ajoutarbre1(noeud(X,G,D),noeud(Y,G1,D1),noeud(Y,G2,D1)):-
	inferieur(X,Y),
	ajoutarbre1(noeud(X,G,D),G1,G2).
ajoutarbre1(noeud(X,G,D),noeud(Y,G1,D1),noeud(Y,G1,D2)):-
	inferieur(Y,X),
	ajoutarbre1(noeud(X,G,D),D1,D2).


%test
%| ?-supprime(s(s(s(s(s(s(s(s(zero)))))))),  noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),noeud(s(s(s(zero))),vide,noeud(s(s(s(s(zero)))),vide,noeud(s(s(s(s(s(zero))))),vide,vide)))),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),A).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),noeud(s(s(s(zero))),vide,noeud(s(s(s(s(zero)))),vide,noeud(s(s(s(s(s(zero))))),vide,vide)))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide)) ? ;

%| ?- arbre(A),ajoutliste([s(s(s(zero))),s(s(s(s(zero)))),s(s(s(s(s(zero)))))],A,A1),supprime(s(s(s(s(s(s(zero)))))),A1,A2).
%A2 = noeud(s(s(zero)),noeud(s(zero),vide,vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),noeud(s(s(s(zero))),vide,noeud(s(s(s(s(zero)))),vide,noeud(s(s(s(s(s(zero))))),vide,vide))),vide),vide)) ? ;
%no
% equilibre qui renvoie vrai si en tout noeud la différence, appelée déséquilibre, des hauteurs des sous-arbres gauche et droit est en valeur absolue inférieure ou égale à 1.

desequilibre(vide,zero,plus).
desequilibre(noeud(_X,G,D),zero,plus):-hauteur(G,HG),hauteur(D,HG).
desequilibre(noeud(_X,G,D),De,moins):-hauteur(G,HG),hauteur(D,HD),inferieur(HG,HD),somme(HG,De,HD).
desequilibre(noeud(_X,G,D),De,plus):-hauteur(G,HG),hauteur(D,HD),inferieur(HD,HG),somme(HD,De,HG).

equilibre(vide).
equilibre(noeud(X,G,D)):-desequilibre(noeud(X,G,D),De,Signe),valabsbonne(De,Signe),equilibre(G),equilibre(D).

valabsbonne(zero,plus).
valabsbonne(s(zero),_Signe).

%| ?- arbre(A), equilibre(A).
%A = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)) ? ;
%no
%| ?- arbre(A),ajout(zero,A,A1),equilibre(A1).
%no

% inseretrie(L,A) où L est une liste d'entiers déjà triée, A est
%  l'arbre obtenu en insérant cette liste de nombre de fa\c{c}on \`a obtenir un arbre binaire de recherche \'equilibr\'e.
inseretrie(L,A):-dichotomise(L,L1),ajoutliste(L1,vide,A).

%ex : inseretrie([1,2,3,4,5,8],A).
%| ?- inseretrie([s(zero),s(s(zero)),s(s(s(zero))),s(s(s(s(zero)))),s(s(s(s(s(zero))))),s(s(s(s(s(s(s(s(zero))))))))],A).
%A = noeud(s(s(s(s(zero)))),noeud(s(s(zero)),noeud(s(zero),vide,vide),noeud(s(s(s(zero))),vide,vide)),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(zero))))),vide,vide),vide)) ? ;
%no


%définir les prédicats permettant d'effectuer des rotations d'arbre
% simples et doubles (rd,rg,rdg,rgd) comme dessiné ci-dessous.
rd(vide,vide).
rd(noeud(Q,vide,W),noeud(Q,vide,W)).
rd(noeud(Q,noeud(P,U,V),W),noeud(P,U,noeud(Q,V,W))).

rg(vide,vide).
rg(noeud(P,U,vide),noeud(P,U,vide)).
rg(noeud(P,U,noeud(Q,V,W)),noeud(Q,noeud(P,U,V),W)).

rgd(vide,vide).
rgd(noeud(R,vide,W),noeud(R,vide,W)).
rgd(noeud(R,noeud(P,T,vide),W),noeud(R,noeud(P,T,vide),W)).
rgd(noeud(R,noeud(P,T,noeud(Q,U,V)),W),noeud(Q,noeud(P,T,U),noeud(R,V,W))).

rdg(A,B):-rd(A,A1),rg(A1,B).

% Définir un autre prédicat insereq qui ajoute un élément dans un arbre équilibré sans perturber l'équilibre. Pour cela, on insère l'élément aux feuilles comme précédemment, puis on rééquilibre l'arbre par une rotation simple ou double.
insereq(X,A,B):-ajout(X,A,A1),reeq(A1,B).

reeq(A,A):-equilibre(A).
reeq(A,B):-desequilibre(A,s(s(zero)),plus),gauche(A,SAG),desequilibre(SAG,s(zero),plus),rd(A,B).
reeq(A,B):-desequilibre(A,s(s(zero)),moins),droit(A,SAD),desequilibre(SAD,s(zero),moins),rg(A,B).
reeq(A,B):-desequilibre(A,s(s(zero)),plus),gauche(A,SAG),desequilibre(SAG,s(zero),moins),rgd(A,B).
reeq(A,B):-desequilibre(A,s(s(zero)),moins),droit(A,SAD),desequilibre(SAD,s(zero),plus),rdg(A,B).
reeq(noeud(X,G,D),noeud(X,G1,D1)):-desequilibre(noeud(X,G,D),De,Si),valabsbonne(De,Si),reeq(G,G1),reeq(D,D1).% si la racine est équilibrée mais pas l'arbre tout entier, il faut relancer sur les sag et sad, pour qu'il ne sorte qu'une fois les solutions on peut ajouter \+equilibre(noeud(X,G,D) à cette ligne
%test en ajoutant 0 à l'arbre de tout à l'heure
%| ?-arbre(R), insereq(zero,R,R1).
%R = noeud(s(s(s(s(s(s(zero)))))),noeud(s(s(zero)),noeud(s(zero),vide,vide),vide),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)),
%R1 = noeud(s(s(s(s(s(s(zero)))))),noeud(s(zero),noeud(zero,vide,vide),noeud(s(s(zero)),vide,vide)),noeud(s(s(s(s(s(s(s(s(zero)))))))),noeud(s(s(s(s(s(s(s(zero))))))),vide,vide),vide)) ? ;





