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

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

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

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

% extract all even numbers from a list
evens([], []).
evens([X|Xs], [X|XsEvens]) :- 0 is X mod 2, evens(Xs, XsEvens).
evens([X|Xs], XsEvens)     :- 1 is X mod 2, evens(Xs, XsEvens).

% append two lists together
concatenate([], L2, L2).
concatenate([X|Xs], L2, [X|Tmp]) :- concatenate(Xs, L2, Tmp).

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

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

% non-empty list: insert the head and recurse on the tail
build_bst([X|Xs], CurrentTree, NewTree) :-
    insert_bst(X, CurrentTree, TmpTree),
    build_bst(Xs, TmpTree, NewTree).

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

% binary node: insert value into left or right subtree (ignore if equal)
insert_bst(V, [node,V,L,R], [node,V,L,R]).
insert_bst(V, [node,X,L,R], [node,X,NewL,R]) :- V < X, insert_bst(V, L, NewL).
insert_bst(V, [node,X,L,R], [node,X,L,NewR]) :- V > X, insert_bst(V, R, NewR).

% binary search
find(_,   [empty]) :- fail.
find(Val, [node,Val,_,_]).
find(Val, [node,X  ,L,_]) :- Val < X, find(Val, L).
find(Val, [node,X  ,_,R]) :- Val > X, find(Val, R).

% wrapper for binary search
find_bst(Val, List) :- bst(List, Tree), find(Val, Tree), !.

% flatten tree
sorted([empty],[]).
sorted([node,X,L,R], List) :-
    sorted(L, SortedL), sorted(R, SortedR),
    append(SortedL, [X], Tmp), append(Tmp, SortedR, List).

% wrapper for flatten tree
sorted_bst(List, SortedList) :- bst(List, Tree), sorted(Tree, SortedList), !.

% count tree nodes
count_nodes([empty],      0).
count_nodes([node,_,L,R], Count) :-
    count_nodes(L, LCount), count_nodes(R, RCount),
    Count is 1 + LCount + RCount.

% wrapper for count tree nodes
count_bst(List, Count) :- bst(List, Tree), count_nodes(Tree, Count), !.

