:- include('avl.pl').       % predicats pour gerer des arbres bin. de recherche   
:- include('taquin.pl').    % predicats definissant le systeme a etudier

main :-
    % Calcul de H pour la situation de départ
    initial_state(U0),
    heuristique(U0, H0),

	% initialisations Pf, Pu et Q 
    insert([ [H0, H0, 0], U0 ], nil, Pf),
    insert([U0, [H0, H0, 0], nil, nil], nil, Pu),
    empty(Q),
	!,
	
	% lancement de Aetoile
    aetoile(Pf, Pu, Q).

%*******************************************************************************

afficher_solution(_, nil).

afficher_solution(Q, S) :-
    belongs([S, [_,_,G], Pere, Action], Q),
    !,
    write_state(S),
    print(Action),
    print(' ('),
    print(G),
    print(')'),
    nl, nl,
    afficher_solution(Q, Pere).

%*******************************************************************************

% Cas arbres vides -> plus d'état à développer -> pas de solution
aetoile(Pf, _, _) :-
    empty(Pf),
    !,
    print('Pas de solution : l\'état final n\'est pas atteignable !\n').

% Cas état final -> solution trouvée
aetoile(Pf, Pu, Q) :-
	suppress_min([[F, H, G], Sf], Pf, _),
    final_state(Sf),
    !,
	suppress([Sf, [F, H, G], Pere, A], Pu, _),
	insert([Sf, [F, H, G], Pere, A], Q, Q1),
    print('Solution trouvée :\n'),
    afficher_solution(Q1, Sf).

aetoile(Pf, Pu, Q) :-
	suppress_min([[F, H, G], S], Pf, Pf1),
	suppress([S, [F, H, G], Pere, A], Pu, Pu1),
    expand(S, G, Successors),
    loop_successors(Successors, S, Pf1, Pu1, Q, Pf2, Pu2),
    insert([S, [F, H, G], Pere, A], Q, Q1),
    aetoile(Pf2, Pu2, Q1).
    
%*******************************************************************************

expand(S, Gs, Successors) :-
    findall([Successor, [F, H, G], Action], (
        rule(Action, Cost, S, Successor),
        G is Gs + Cost,
        heuristique(Successor, H),
        F is G + H
    ), Successors).

%*******************************************************************************

% Cas pas de successseurs
loop_successors([], _,Pf, Pu, _, Pf, Pu) :- !.

% Cas successeur déjà traité : on ignore
loop_successors([[S,_,_] | Rest], Pere, Pf, Pu, Q, Pf_new, Pu_new) :-
    belongs([S,_,_,_], Q),
    %!,
    loop_successors(Rest, Pere, Pf, Pu, Q, Pf_new, Pu_new),
    !.

% Cas successeur déjà connu : on met à jour le coût
loop_successors([[S, [F, H, G], Action] | Rest], Pere, Pf, Pu, Q, Pf_new, Pu_new) :-
    belongs([S, [F_old,_,_], _, _], Pu),
    %!,
    update_trees(S, H, [F, G, Pere, Action], F_old, Pf, Pf1, Pu, Pu1),
    loop_successors(Rest, Pere, Pf1, Pu1, Q, Pf_new, Pu_new), 
    !.

% Cas successeur inconnu : on l'ajoute à P
loop_successors([[S, [F, H, G], Action] | Rest], Pere, Pf, Pu, Q, Pf_new, Pu_new) :-
    insert([S, [F, H, G], Pere, Action], Pu, Pu1),
    insert([[F, H, G], S], Pf, Pf1),
    loop_successors(Rest, Pere, Pf1, Pu1, Q, Pf_new, Pu_new).

%*******************************************************************************

% Mise à jour des coûts et des parents seulement si plus faible
update_trees(S, H, [F, G, Pere, Action], F_old, Pf, Pf2, Pu, Pu2) :-
    (F_old is min(F, F_old) -> 
		Pf = Pf2,
		Pu = Pu2
	;
		suppress([S,_,_,_], Pu, Pu1),
		insert([S, [F, H, G], Pere, Action], Pu1, Pu2),
		suppress([[F_old,_,_], S], Pf, Pf1),
		insert([[F, H, G], S], Pf1, Pf2)
	).