:- module(_,_,[doccomments]).
% :- use_package(sr/bfall).

%! \title   Binary tree example
%! \module  Defining the type binary tree and some operations.

%! binary_tree(T): `T` is a binary tree.
binary_tree(void).
binary_tree(tree(_Element,Left,Right)) :- 
    binary_tree(Left),
    binary_tree(Right).

%! Try:
% Seeing if a tree is indeed a tree (i.e., of the type):
% ?- tree_example(T), binary_tree(T).
% ?- tree_example(_T), binary_tree(_T).
% Checking something that is not in the type: 
% ?- binary_tree(tree(a, b, c)).
% ?- binary_tree(tree(a, [], [])).
% Generating binary trees: 
% ?- binary_tree(T).
% Try also uncommenting the :-use_package(sr/bfall). above!

% Same, using functional notation: 
:- use_package(functional).

%! binary_t(T): `T` is a binary tree.
binary_t := void | tree(_Element,~binary_t,~binary_t). 

%! tree_member(X,T): `X` is a node in binary tree `T`.
tree_member(X,tree(X,Left,Right)) :- 
    binary_tree(Left),
    binary_tree(Right).
tree_member(X,tree(_,Left,_Right)) :- 
    tree_member(X,Left). 
tree_member(X,tree(_,_Left,Right)) :- 
    tree_member(X,Right).

% Try:
% ?- tree_example(_T), tree_member(b, _T).
% ?- tree_example(_T), tree_member(X, _T).
% ?- tree_example(_T), tree_member(e, _T).
% ?- tree_member(e,T).
% ?- tree_member(e,T), tree_member(a,T).
% Try also uncommenting the :-use_package(sr/bfall). above!

% Same, using functional notation:
tree_mem_f(X) := tree(X,~binary_tree,~binary_tree)
               | tree(_Y,~tree_mem_f(X),_Right)
               | tree(_Y,_Left,~tree_mem_f(X)).

% Try:
% ?-tree_example(_T), tree_mem_f(b, _T).
% ?- tree_example(_T), tree_mem_f(X, _T).
% ?- tree_example(_T), tree_mem_f(e, _T).
% ?- tree_member(e,T).
% ?- tree_member(e,T), tree_mem_f(a,T).
% Try also uncommenting the :-use_package(sr/bfall). above!


% Auxiliary predicates: 

%! tree_example(T): `T` is a tree example.
tree_example(  tree( a,
                   tree( b,
                         void,
                         void
                       ),
                   tree( c,
                         tree( b,
                               void,
                               void
                               ),
                         void
                       )
                   )).