%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                      %
% An implementation of the depth-first AND/OR search . %
%                                                      %
% (Infinite cycling is not avoided !!!)                %
%                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- module(andor, [solve/2, show/1]).



% Define infix operators '-->' and ':'
:- op(500, xfx, user:(:)).
:- op(600, xfx, user:(--->)).



% solve(+Node, -SolutionTree)
% Find a solution tree for Node in an AND/OR graph
solve(Node, Node) :-              % Solution tree of goal node is Node itself
    goal(Node).

solve(Node, Node ---> Tree) :-
    Node ---> or:Nodes,           % Node is an OR-node
    member(Node1, Nodes),         % Select a successor Node1 of Node
    solve(Node1, Tree).

solve(Node, Node ---> and:Trees) :-
    Node ---> and:Nodes,          % Node is an AND-node
    solveall(Nodes, Trees).       % Solve all Node's successors



% solveall([Node1,Node2, ...], [SolutionTree1,SolutionTree2, ...])
solveall([], []).

solveall([Node|Nodes], [Tree|Trees]) :-
    solve(Node, Tree),
    solveall(Nodes, Trees).



% Displaying a solution tree
show(Tree) :-                     % Display solution tree
    show(Tree, 0).                % Indented by 0



% show(Tree, H): display solution tree indented by H
show(Node ---> Tree, H) :- !,
    write(Node), write(' ---> '),
    H1 is H + 7,
    show(Tree, H1).

show(and:[T], H) :- !,            % Display single AND tree
    show(T, H).

show(and:[T|Ts], H) :- !,         % Display AND-list of solution trees
    show(T, H),
    tab(H),
    show(and:Ts, H).

show(Node, _) :-
    write(Node), nl.