% APPLICATION 1: Binary search trees

menu(Tree) :- nl,
   writeln('1. Create empty tree'),
   writeln('2. Insert or modify node'),
   writeln('3. Delete node'),
   writeln('4. Find node'),
   writeln('5. Show tree'),
   writeln('6. Stop'),
   writeln('Type option number followed by dot: '),
   read(Q),
   Q \= 6,!,
   action(Q,Tree,NewTree),
   menu(NewTree).
menu(_) :- writeln('Stopped.').   

% tree creation
action(1,_,nil).
% node insertion or modification
action(2,Tree,NewTree) :-
   write('Enter key: '),read(K),
   write('Enter data: '),read(D),
   insert(K,D,Tree,NewTree).
% node deletion
action(3,Tree,NewTree) :-
  write('Enter key of node to delete: '),
  read(Key),
  elim(Key,Tree,NewTree).
% node finding
action(4,Tree,Tree) :-
   write('Enter key of node to find: '),
   read(Key),findNode(Key,Tree).
% display tree content
action(5,Tree,Tree) :- showTree(Tree).

insert(K,D,nil,bt(K,D,nil,nil)).
insert(K,D,bt(K,_,T1,T2),bt(K,D,T1,T2)) :- !.
insert(K,D,bt(K1,D1,T1,T2),bt(K1,D1,NewT1,T2)) :- 
   K<K1,!,insert(K,D,T1,NewT1).
insert(K,D,bt(K1,D1,T1,T2),bt(K1,D1,T1,NewT2)) :-
   insert(K,D,T2,NewT2).

elim(_,nil,nil).
elim(K,bt(K1,D,T1,T2),bt(K1,D,NewT1,T2)) :- 
  K<K1,!,elim(K,T1,NewT1).   
elim(K,bt(K1,D,T1,T2),bt(K1,D,T1,NewT2)) :- 
  K>K1,!,elim(K,T2,NewT2). 
elim(K,bt(K,_,nil,T2),T2):-!.
elim(K,bt(K,_,T1,nil),T1):-!.
elim(K,bt(K,_,T1,T2),NewTree):-
  insertTree(T1,T2,NewTree).

insertTree(bt(K,D,T1,nil),T,bt(K,D,T1,T)):-!.
insertTree(bt(K,D,T1,T2),T,bt(K,D,T1,NewT2)):-
  insertTree(T2,T,NewT2).

findNode(_,nil) :- writeln("Node not found").
findNode(K,bt(K,D,_,_)) :- !,
  writeln(D).
findNode(K,bt(K1,_,T1,_)) :- K<K1,!,
  findNode(K,T1).
findNode(K,bt(_,_,_,T2)) :- 
  findNode(K,T2).

showTree(nil).
showTree(bt(K,D,T1,T2)):-
   showTree(T1),
   write('Key: '),write(K),
   write(', data: '), writeln(D),
   showTree(T2).  

% APPLICATION 2: Hanoi Towers

hanoi(N):-move(N,1,2,3). 
move(0,_,_,_) :- !. 
move(N,A,B,C) :- 
  M is N-1,
  move(M,A,C,B),
  write('move from '),write(A), 
  write(' to '),writeln(B), 
  move(M,C,B,A).


% Application 3: Best-first search for weighted difraphs

% FACTS
arc(newcastle,carlisle,58). 
arc(carlisle,penrith,23). 
arc(smallville,metropolis,15). 
arc(penrith,darlington,52). 
arc(smallville,ambridge,10). 
arc(workington,carlisle,33). 
arc(workington,ambridge,5). 
arc(workington,penrith,39). 
arc(darlington,metropolis,25).

propagate_min([Rec],[Rec]):-!.
propagate_min([Rec|L],[A,B|T]):-
   propagate_min(L,[Rec1|T]),
   rearrange(Rec,Rec1,A,B).

rearrange(r(W1,Xs),r(W2,Ys),
          r(W2,Ys),r(W1,Xs)) :- W1>W2,!.   
rearrange(R1,R2,R1,R2).

extension_ok(Y,[X|Xs],W,NewW) :- 
  arc(X,Y,D), not(member(Y,[X|Xs])), NewW is W+D.

extend([r(W,[Y|Xs])|_],Y,r(W,[Y|Xs])) :- !. 
extend([r(W,Xs)|Rs],Y,WAPath) :-
 findall(r(NewW,[Z|Xs]), 
         extension_ok(Z,Xs,W,NewW),
         Rs1),
  append(Rs,Rs1,LsNew),
  propagate_min(LsNew,RsNew), 
  extend(RsNew,Y,WAPath).

best_path(X,Y,r(W,Path)) :- 
  extend([r(0,[X])],Y,r(W,T)), 
  reverse(T,Path).







