/*  A collection of breadth-first search utilities  */


/*
    Provides a simple 'shell' environment, which will return a list
    of ALL the solutions to any given goal (at once), or inform the
    user that the goal has no solutions.  It follows a breadth-first
    search strategy.

    It is called by entering 'shell.', or shellq to get a query for
    more answers after each answer is given.

    Another breadth-first utility provided is one for solving conjuctions
    and/or disjunctions of goals - 'breadth_first/1', or 'breadth/1'.
*/




/*  shell: Breadth first shell without queries for more answers  */

shell :-
  shell_header,
  shell_do_shell.




/*  shellq : Breadth first shell with queries for more answers  */

shellq :-
  assert(queries_enabled),
  shell_header,
  shell_do_shell,
  retract(queries_enabled).




/*  breadth_first(Goal)  if there are solutions to 'Goal'
                         with a breadth-first search strategy.  */
breadth_first(X) :-
  bfs(X,[]).




/*  breadth(Goal)        if there are solutions to 'Goal'
                         with a breadth-first search strategy.  */
breadth(X) :-
  bfs(X,[]).





shell_do_shell :-
  shell_prompt,
  read(G),
  nl,
  shell_do(G).


shell_header :-
  nl, nl,
  writeln('Interactive Prolog Shell with breadth-first search, version 0.40'),
  writeln('Cuts and built-in predicates are not supported!'),
  writeln('  Enter ''exit'' to leave.').


shell_prompt :-
  nl,
  write('Enter query: ').



shell_do(exit) :- !.

shell_do(G) :-
  ground(G),!,
  shell_answer_ground(G),
  shell_do_shell.

shell_do(G) :-
  shell_answer(G),
  abolish(shell_output_done,0),
  shell_do_shell.



shell_answer_ground(G) :- bfs(G),!,
  writeln('  Yes').

shell_answer_ground(G) :-
  writeln('  No').



shell_answer(G) :-
  bfs(G),
  tab(2),write(G),nl,
  assert(shell_output_done),
  queryTheUser(Response),
  \+(actOn(Response)).


actOn(89).
actOn(121).

skip_to_EndOfLine :-
  skip(10).


queryTheUser(Response) :-
  queries_enabled,!,
  nl,write('More (y/n)? '),
  get(Response),
  skip_to_EndOfLine.


queryTheUser(89).



shell_answer(G) :-
  shell_output_done,!,
  nl,
  writeln('  No more solutions').

shell_answer(G) :-
  writeln('  No solutions').



/*  writeln(Message)  writes 'Message', followed by a newline  */

writeln(Message) :-
  write(Message),
  nl.



/*  append(List1, List2, List3)  if 'List3' is the concatenation
                                 of 'List1' and 'List2'  */


append([], List, List).
append([Head1 | Tail1], List2, [Head1 | List3]) :-
  append(Tail1,List2,List3).







/*  breadth-first solve!  (Finally works !!!!)  */

bfs(X) :-
  bfs(X,[]).


bfs(true,[]).



bfs(true,[H|T]) :-
  bfs(H,T).
  

bfs(A,[]) :-
  makelist(A, [H|Out]),
  bfs(H,Out).


bfs(A,In) :-
  makelist(A,X),
  append(In,X,[H|Out]),
  bfs(H,Out).


makelist((J,K),[L1|L2]) :-
  clause(J,B),
  listify(B,[L1]),
  makelist(K,L2).


makelist(C,L) :-
  clause(C,B),
  listify(B,L).


makelist((J;K),L) :-
  makelist(J,L).


makelist((J;K),L) :-
  makelist(K,L).




listify((B,C), [E|F]) :-
  listify(B,[E]),
  listify(C,F).



listify((B;C), E) :-
  listify(B,E).



listify((B;C), F) :-
  listify(C,F).


listify(B, [E|NewOut]) :-
  functor(B,_,0),
  B=..[_,E,Rest],
  listify(Rest,NewOut).



listify(B,[B]) :-
  functor(B,_,0),
  [B]=..[.,B,[]].
  


listify(B,[B]) :-
  functor(B,_,N),
  N > 0.






/*  various test routines which test the breadth-first routines!  */


a0 :- z9,b1,c1,z9.
a1 :- b1,c1,z9.
b1 :- b2,b3.
c1 :- c2,c3.
b2 :- b4,b5.
b3.
c2.
c3.
b4.
b5.
z9.



begat(te,av).
begat(te,ha).
begat(av,ish).
begat(av,isa).
begat(isa,esau).
begat(isa,yakov).



/*  an1(te,isa) works with breadth-first and depth-first searches  */

an1(X,Z) :-
  begat(X,Z).
an1(X,Z) :-
  begat(X,Y),an1(Y,Z).



/*  an4(te,isa) only works with breadth-first search!  */

an4(X,Z) :-
  an4(X,Y),begat(Y,Z).
an4(X,Z) :-
  begat(X,Z).