/* Généralisation de termes par l'algorithme de Plotkin
Ex1: generalisation(g(h, f(3, 5), k(i)), g(u, f(5, 5), k(8)), T, E1, E2).
Ex2: generalisation(g(h, f(3, 5), k(3)), g(u, f(5, 5), k(5)), T, E1, E2).
Ex3: generalisation([occur(blanc, gauche,p1), occur(noir, droite, p1)],
			[occur(blanc, gauche,p2), occur(noir, gauche, p2)], T, E1,E2).
Ex4: generalisation([occur(noir, droite, p1), occur(blanc, gauche,p1)],
			[occur(blanc, droite,p2), occur(noir, gauche, p2)], T, E1, E2). */

occ1([occur(blanc, gauche,p1), occur(noir, droite, p1)]).
occ2([occur(noir, gauche,p2), occur(noir, droite, p2)]).
occ3([occur(noir, droite, p1), occur(blanc, gauche,p1)]).

term1([pair(4), impair(3), impair(4 + 3)]).
term2([pair(8), impair(3), impair(8 + 3)]).
term3([pair(8), impair(5), impair(8 + 5)]).
term4([impair(5), pair(8), impair(8 + 5)]).
term5([impair(5), pair(8), impair(5 + 8)]).
term6([pair(8), impair(5), impair(5 + 8)]).

generalisation(V1,V2,V1,[],[]) :- V1==V2, !.
generalisation(V1,V2,T,[[L1,X]|Eps1],[[L2,X]|Eps2]) :-
            ss_termes_diff(V1,V2,L1,L2),
            remplacer([L1,L2],[V1,V2],X,[NV1,NV2]),!,
            generalisation(NV1,NV2,T,Eps1,Eps2).
            
/* Trouve la première différence entre deux termes */
ss_termes_diff(V1,V2,L1,L2) :- 
    not(var(V1)),not(var(V2)),
                V1=..[F,G1|A1], V2=..[F,G2|A2],G1==G2,
                longueur(A1,L), longueur(A2,L),!,
                W1=..[F|A1], W2=..[F|A2],
                ss_termes_diff(W1,W2,L1,L2).
ss_termes_diff(V1,V2,L1,L2) :- 
    not(var(V1)),not(var(V2)),
                V1=..[F,G1|A1], V2=..[F,G2|A2],
                longueur(A1,L), longueur(A2,L),!, 
                ss_termes_diff(G1,G2,L1,L2).
ss_termes_diff(V1,V2,V1,V2):-!.

/* Remplace toutes les occurrences différentes de L1 dans T1 et de L2 dans T2
par le terme X; le résultat est mis dans le quatrième argument
Ex: remplacer([3, 5], [g(h, f(3, o), l(3)),g(h, f(5, h(g, 5)), l(3))], k(X), [V1, V2])

 */
remplacer(_,[V1,V2],_,[V1,V2]) :- V1 == V2.
remplacer([L1,L2],[T1,T2],X,[[NV1|NQ1],[NV2|NQ2]]):-
            not(var(T1)), not(var(T2)),
            T1=[V1|Q1],T2=[V2|Q2],!,
            remplacer([L1,L2],[V1,V2],X,[NV1,NV2]),
            remplacer([L1,L2],[Q1,Q2],X,[NQ1,NQ2]).
remplacer([L1,L2],[V1,V2],X,[NV1,NV2]):-
            not(var(V1)), not(var(V2)),
            V1=..[F|Q1], V2=..[F|Q2],!,
            remplacer([L1,L2],[Q1,Q2],X,[NQ1,NQ2]),
            NV1=..[F|NQ1], NV2=..[F|NQ2].
remplacer([L1,L2],[V1,V2],X,[NV1,NV2]):-
            remplacer_t(L1,V1,X,NV1),
            remplacer_t(L2,V2,X,NV2).

/* remplace toutes les occurrences du sous-terme L dans le terme T, par le terme X;
le résultat est stocké dans la quatrième variable
Ex remplacer_t(3, g(h, f(3, o), l(3)), k(X), L).
 */
remplacer_t(L,T,X,X) :- T==L,!.
remplacer_t(_,T,_,T) :- var(T).
remplacer_t(L,T,X,NT) :- T=..[F|Q],
                      remplacer_l(L,Q,X,NQ),
                      NT=..[F|NQ]. 
/* Remplace tous les éléments d'une liste Q (deuxième arguments) égaux au
premier argument, L, par le troisième argument, X. Le résultat est mis dans le quatrième argument
Ex: remplacer_l(N, [2, 3, 9, N, f(5)], p, NL).
 */
remplacer_l(_,[],_,[]).
remplacer_l(L,[T|Q],X,[NT|NQ]) :-
                      remplacer_t(L,T,X,NT),
                      remplacer_l(L,Q,X,NQ).
longueur([],0):-!.
longueur([_|M],N) :- longueur(M,P), N is P+1.