% Binary Search Trees in Prolog
% Author: Steve Wolfman
% Based on ideas by David Poole.
% Released into the public domain.


% A BST will be one of:
% + empty
% + node(Key, Value, LeftSubtree, RightSubtree), where 
%     all keys in LeftSubtree are less than Key, and
%     all keys in RightSubtree are greater than Key.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sample BSTs
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

example_bst("empty", empty).
example_bst("1 -> a", node(1, a, empty, empty)).
example_bst("1 -> a, 0 -> b, 2 -> c", 
    node(1, a,
        node(0, b, empty, empty),
        node(2, c, empty, empty))).
% Same contents as the previous one, but "rotated"
% to put 0 at the root:
example_bst("0 -> b, 1 -> a, 2 -> c", 
    node(0, b, empty,
        node(1, a, empty, 
            node(2, c, empty, empty)))).
% Again, same contents but "rotated" to put 2 at the root.
example_bst("2 -> c, 1 -> a, 0 -> b", 
    node(2, c,
        node(1, a, 
            node(0, b, empty, empty),
            empty),
        empty)).

% The example from our lecture:
example_bst("lecture",
    node(8, a, 
        node(3, b,
          node(1, d, empty, empty),
          node(6, e, 
            node(4, g, empty, empty),
            node(7, h, empty, empty))),
        node(10, c,
          empty,
          node(14, f,
            node(13, i, empty, empty),
            empty)))).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Look-up Predicate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% lookup(Tree, Key, Val) is true if Key is present
% in Tree with value Val.
%
% Because we'll use arithmetic comparison on the Key
% and the keys within the Tree, those keys all need
% to be ground numbers. Wouldn't it be great to use
% constraints that allowed more flexibility?
lookup(Tree, Key, Val).  % TODO!!!






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Insert Predicate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% insert(Tree, Key, Val, NewTree) is true if NewTree is
% the natural result of adding Key/Val to Tree. That means:
%
% + if Key is already in Tree, NewTree is the same as Tree
%   except Key's new value is Val. 
% + otherwise, NewTree is the same as Tree except that the
%   empty tree where Key would fit in Tree is replaced by 
%   a node with empty subtrees containing Key and Val.
%
% Because we'll use arithmetic comparison on the Key
% and the keys within the Tree, those keys all need
% to be ground numbers. Wouldn't it be great to use
% constraints that allowed more flexibility?
insert(Tree, Key, Val, NewTree).  % TODO!!!








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Tests
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


:- begin_tests('lookup').

% Base case:
test('fails on an empty tree, regardless of key/val', [fail]) :- 
    lookup(empty, _, _).

test('succeeds on a tree with just the key sought', [nondet]) :- 
    example_bst("1 -> a", Tree),
    lookup(Tree, 1, a).

test('fails on a tree with just the key sought, wrong value', [fail]) :- 
    example_bst("1 -> a", Tree),
    lookup(Tree, 1, b).

% Recursive cases:
test('fails on a small tree without the key sought', [fail]) :- 
    example_bst("1 -> a", Tree),
    lookup(Tree, 2, _).

test('fails on a small tree without the key sought, v2', [fail]) :- 
    example_bst("1 -> a", Tree),
    lookup(Tree, 0, _).


test('three-node successful cases', [nondet]) :- 
    example_bst("1 -> a, 0 -> b, 2 -> c", Tree),
    lookup(Tree, 1, V1), assertion(V1 == a),
    lookup(Tree, 2, V2), assertion(V2 == c),
    lookup(Tree, 0, V0), assertion(V0 == b).

test('complex successful cases', [nondet]) :- 
    example_bst("lecture", Tree),
    lookup(Tree, 4, V4), assertion(V4 == g),
    lookup(Tree, 14, V14), assertion(V14 == f).

test('complex failed cases', [fail]) :- 
    example_bst("lecture", Tree),
    % ; is disjunction (or):
    ( lookup(Tree, 2, _) ;  % not there
      lookup(Tree, 4, f) ;  % there but not with that key
      lookup(Tree, 15, _) ).% not there

:- end_tests('lookup').




:- begin_tests('insert').

% Base case #1:
test('just inserts the new Key/Val', [nondet]) :- 
    insert(empty, Key, Val, NewTree), 
    assertion(NewTree == node(Key, Val, empty, empty)).

% Base case #2:
test('replaces the root value with the new value when the root key matches the given one', [nondet]) :- 
    example_bst("1 -> a", Tree),
    insert(Tree, 1, Val, NewTree), 
    assertion(NewTree == node(1, Val, empty, empty)).
test('replaces the root value with the new value when the root key matches the given one, complex example', [nondet]) :- 
    example_bst("lecture", Tree),
    insert(Tree, 8, Val, NewTree),
    Tree = node(_, _, LST, RST),   % The subtrees, which stay the same.
    assertion(NewTree == node(8, Val, LST, RST)).

% Recursive cases.
test('simple insert to the left', [nondet]) :- 
    example_bst("1 -> a", Tree),
    insert(Tree, 0, Val, NewTree), 
    assertion(NewTree == node(1, a, node(0, Val, empty, empty), empty)).
test('simple insert to the right', [nondet]) :- 
    example_bst("1 -> a", Tree),
    insert(Tree, 2, Val, NewTree), 
    assertion(NewTree == node(1, a, empty, node(2, Val, empty, empty))).
test('complex insertion', [nondet]) :- 
    example_bst("lecture", Tree),
    insert(Tree, 9, Val, NewTree),
    Tree = node(RK, RV, LST, node(RSK, RSV, _, RST)), 
    assertion(NewTree == node(RK, RV, LST, node(RSK, RSV, node(9, Val, empty, empty), RST))).
test('complex replacement', [nondet]) :- 
    example_bst("lecture", Tree),
    insert(Tree, 6, Val, NewTree),
    Tree = node(RK, RV, node(LSK, LSV, LLST, node(LRSK, _, LRLST, LRRST)), RST), 
    assertion(NewTree == node(RK, RV, node(LSK, LSV, LLST, node(LRSK, Val, LRLST, LRRST)), RST)).

:- end_tests('insert').

