%% -*-prolog-*-
% Computational Intelligence: a logical approach. 
% Prolog Code. 
% An iterative deepening search, based on the generic search algorithm.
% Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press.

% idsearch(Ns,P) is true if path P is a path found from starting nodes Ns
% using iterative deepening search 
% Example query: idsearch([o103],P).
idsearch(Ns,P, DB) :-
   add_paths_db(Ns,[],0,[],Fr),
   initialiseCounter(nodesGenerated),
   initialiseCounter(nodesExpanded),
   dbsearch(Fr,DB,Fr,natural,P),
   counter(nodesGenerated, NodesGenerated),
   writelnn(['Number of nodes generated: ', NodesGenerated]),
   counter(nodesExpanded, NodesExpanded),
   writelnn(['Number of nodes expanded: ', NodesExpanded]).

% dbsearch(F,DB,Q,How1,P) is true if a depth bound search from frontier F
% can find a path P of length >= DB.
% where Q is the initial frontier to (re)start from,
% How specifies whether the previous bound failed naturally or unnaturally

% The frontier is a list of  node(Node,Path,PathLength)
%   where Node is a node, Path is the path found to Node,
%   PathLength is the number of arcs in the path.

/*dbsearch(F,_,_,_,_) :-
   writelnn(['Frontier: ',F]),
   fail.
*/
dbsearch([node(N,P,DB)|_],DB,_,_,[N|P]) :-
   is_goal(N),
   writelnn([solved]).
dbsearch([node(N,P,PL)|F1],DB,Q,H,S) :-
   PL<DB,
   incrementCounter(nodesExpanded),
   neighbours(N,NNs),
   length(NNs, NumberOfChildren),
   addToCounter(nodesGenerated, NumberOfChildren),
   PL1 is PL+1,
   add_paths_db(NNs,[N|P],PL1,F1,F2),
   dbsearch(F2,DB,Q,H,S).
dbsearch([node(_,_,PL)|F1],DB,Q,_,S) :-
   PL >= DB,
   dbsearch(F1,DB,Q,unnatural,S).
dbsearch([],DB,Q,unnatural,S) :-
   DB1 is DB+1,
   counter(nodesGenerated, NodesGenerated),
   writelnn(['Number of nodes generated: ', NodesGenerated]),
   counter(nodesExpanded, NodesExpanded),
   writelnn(['Number of nodes expanded: ', NodesExpanded]),
   retractall(lastNodesGenerated(_)),
   assert(lastNodesGenerated(NodesGenerated)),
   retractall(lastNodesExpanded(_)),
   assert(lastNodesExpanded(NodesExpanded)),
   initialiseCounter(nodesGenerated),
   initialiseCounter(nodesExpanded),
   writeln(['New Depth bound: ',DB1]),
   dbsearch(Q,DB1,Q,natural,S).

% add\_paths\_db(NNs,Path,PL,F_0,F_1) adds the
% neighbours NNs to the front of frontier F_0
% forming frontier F_1. The neighbors need to be
% converted to the form of elements of the frontier.
% Path is the path found to the neighbor, and PL
% is the path's length.
add_paths_db([],_,_,F,F).
add_paths_db([NN|R],Path,PL,F0,[node(NN,Path,PL)|F1]) :-
   add_paths_db(R,Path,PL,F0,F1).

% **************************************************
% writelnn(L) is true if L is a list of items to
% be written on a line, followed by a newline.
writelnn([]) :- nl.
writelnn([H|T]) :- write(H), writelnn(T).