%
% CS 430 Module 6 Lab Solution (Dr. Mike Lam)
%

% determines the size of a list
size([], 0).
size([_|T],N) :- size(T,M), N is M+1.

% find the last value in a list (fails for empty list)
end([], _) :- fail.
end([X], X).
end([_|T], E) :- end(T,E).

% find the maximum value in a list (fails for empty list)
max([], _) :- fail.
max([X], X).
max([H|T], H)  :- max(T,MT), H >= MT.
max([H|T], MT) :- max(T,MT), H <  MT.

% extract all even numbers from a list
evens([], []).
evens([H|T], [H|TE]) :- 0 is H mod 2, evens(T,TE).
evens([H|T], TE)     :- 1 is H mod 2, evens(T,TE).

% append two lists together
concatenate([],B,B).
concatenate([A|T],B,[A|C]) :- concatenate(T,B,C).

% top-level: invoke recursive insertion on an empty tree
bst(L,T) :- build_bst(L, [empty], T), !.

% empty list: no tree modifications necessary
build_bst([], T, T).

% non-empty list: insert the head and recurse on the tail
build_bst([X|XS], T, TTT) :- insert_bst(X, T, TT), build_bst(XS, TT, TTT).

% empty tree: create new node
insert_bst(V, [empty], [node,V,[empty],[empty]]).

% binary node: insert into left or right subtree
insert_bst(V, [node,X,L,R], [node,X,LL,R]) :- V =< X, insert_bst(V,L,LL).
insert_bst(V, [node,X,L,R], [node,X,L,RR]) :- V  > X, insert_bst(V,R,RR).

% binary search
find(X,[node,X,_,_]).
find(X,[node,Y,L,_]) :- X =< Y, find(X,L).
find(X,[node,Y,_,R]) :- X  > Y, find(X,R).

% wrapper for binary search
find_bst(X,L) :- bst(L,T), find(X,T), !.

% flatten tree
sorted([empty],[]).
sorted([node,X,L,R],S) :- sorted(L,LS), sorted(R,RS),
                          append(LS,[X],X1), append(X1,RS,S).

% wrapper for flatten tree
sorted_bst(L,S) :- bst(L,T), sorted(T,S), !.

% count tree nodes
count_nodes([empty],     0).
count_nodes([node,_,L,R],N) :- count_nodes(L,LN), count_nodes(R,RN),
                               N is 1 + LN + RN.

% wrapper for count tree nodes
count_bst(L,N) :- bst(L,T), count_nodes(T,N), !.

