#!/usr/bin/env swipl -s

/*
 * Rick van der Zwet
 * 0433373
 * Prolog programming assigment 2
 * Licence: BSD
 * $Id: assignment2.pro 299 2007-11-08 00:10:31Z rick $
 *
 * We shall consider binary trees whose nodes are (labelled with)
 * natural numbers, and use the term void to denote the empty tree, and
 * the term tree(x, left, right). to denote the tree with root x, left
 * subtree left and right subtree right. For example, the term tree(1,
 * tree(2, void, void), tree(3, void, void)) represents the tree with
 * root 1 and children 2 and 3
 *  We call a binary tree tree(x, left, right) nice if:
 * 1. if left is not empty then x is greater than all the elements in
 *    left
 * 2. if right is not empty then x is less than all the elements in
 *    right.
 *
 * A binary tree is called a search tree if every subtree of it is nice.
 * Write a program which tests whether a ground term is a search tree.
 *
 * Hint: Use the following predicate is_search_tree(T) in the definition
 * of search tree:
 * is_search_tree(void).
 * is_search_tree(T) :- is_search_tree(T, Min, Max).
 *  where Min and Max are the minimum and maximum element of the tree T.
 *  Then implement the predicate is_search_tree(T, Min, Max).
 */


/* Make a call to a void/2 fail to make the once(call( fail when calling
 * the void X X
 */
void(_, _) :-
    fail.

/* Calculate wether leaf is valid */
tree(X, void, void, Min, Max) :-
    X =< Max,
    X >= Min.

/* Only Left set, make the call */
tree(X, Left, void, Min, _) :-
    once(call(Left, Min, X)).

/* Only Right set, make the call */
tree(X, void, Right, _, Max) :-
    once(call(Right, X, Max)).

/* Both set, make the call */
tree(X, Left, Right, Min, Max) :-
    once(call(Left,  Min, X)),
    once(call(Right, X, Max)).

/* Initial values */
tree(X, Left, Right) :-
    tree(X, Left, Right, -32768, 32768).

/* Exception single tree node */
tree(_, void, void) :-
    true.

/* Exception no node */
is_search_tree(void).

is_search_tree(T) :-
    once(call(T)).