% File:   tree.pl
% Author: Dilian Gurov, KTH CSC

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Föreläsning 3a: Induktiva datatyper: Träd (inte inbyggd)
%
% - Prologtermer
% - Binära träd utan data
% - Strukturell induktion över binära träd utan data
% - Binära träd med data

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 2.1 Binära träd utan data
%
% Vi kan lägga till trädet som faktum och ställa frågor om den:

isTree(branch(leaf, branch(branch(leaf, leaf), leaf))).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: height(T, N)

max(X, Y, X) :- Y<X.
max(X, Y, Y).

height(leaf, 0).
height(branch(T1, T2), N) :-
  height(T1, N1),
  height(T2, N2),
  max(N1, N2, M),
  N is M+1.

% ?- isTree(T), height(T, N).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: complete(T)
%
% Ett träd är komplett om den har alla sina löv på samma höjd.

complete(leaf).
complete(branch(T1, T2)) :-
  complete(T1),
  complete(T2),
  height(T1, N),
  height(T2, N).

% ?- isTree(T), complete(T).
% ?- complete(branch(branch(leaf, leaf), branch(leaf, leaf))).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 2.2 Binära träd med data

isDTree(branch(-3,branch(4,leaf(8),leaf(-2)),leaf(7))).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: lookup(D, T)
%
% Som member, fast för träd med data.

lookup(D, leaf(D)).
lookup(D, branch(D, _, _)).
lookup(D, branch(_, LT, _)) :- lookup(D, LT).
lookup(D, branch(_, _, RT)) :- lookup(D, RT).

% ?- isDTree(T), lookup(4, T).
% ?- isDTree(T), lookup(5, T).

% ?- isDTree(T), lookup(X, T).

% ?- lookup(anna, T).
% ?- lookup(anna, T), lookup(4, T), lookup(bo, T).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: treesum(T)
%
% Obs: antar att allt data är tal!
% Beräknar summan av alla tal i trädet.

treesum(leaf(N), N).
treesum(branch(N, LT, RT), N1) :- 
  treesum(LT, LN),
  treesum(RT, RN),
  N1 is LN+RN+N.

% ?- isDTree(T), treesum(T, N).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%