% Collatz.pl
% April 2002, Michael H. Albert
%
% Illustrative predicates about search trees in Prolog using
% the Collatz function as an example. Also includes some basic
% output facilities (including file output).

% The Collatz function is N/2 on even N, and 3N+1 on odd N.
    
collatz(N, CN) :-
     0 is N mod 2,
     CN is (N/2).

 collatz(N, CN) :-
     1 is N mod 2,
     CN is (3*N + 1).


% The Collatz sequence of a number is the list of iterated
% values of the Collatz function starting from that number 
% until it reaches 1. 
%
% NB: No one knows whether this sequence is always finite.

collatzSeq(1, [1]) :- !.

collatzSeq(N, [N | L]) :-
    collatz(N, CN),
    collatzSeq(CN, L).
    
% Construct the Collatz tree up to input n. The vertices of
% the tree contain a pair (key, value), where key is an integer
% and value is the number of iterations of the Collatz functions
% required starting from key to reach 1. We guarantee that the
% key values include all numbers from 1 through n. We don't 
% want to have to evaluate the full sequence from every integer. 
%
% No attempt is made to ensure balance in the tree.

% Base case 
collatzTree(1, ct(1, 0, nilTree, nilTree)).
    
% General case:
% Construct the tree to N-1,
% Add the path from N to the tree (possibly a no brainer
% if N is already in the tree). The last parameter is the
% value -- we don't need it here but will when we need to
% compute the value for N, having added its collatz image
% to the tree.

collatzTree(N, Tree) :-
    N1 is N-1,
    N1 > 0,
    collatzTree(N1, Tree1),
    addPathFrom(N, Tree1, Tree, _).
    
% addPathFrom: If we find N in the tree, simply
% succeed and cut out so the other clause isn't
% tested. Notice that V will be the actual value
% found.

addPathFrom(N, TOld, TOld, V) :-
    lookup(N, TOld, V),
    !.
    
% addPathFrom: N is not in the tree, so apply
% the collatz function once, add the path from the
% result to the tree, compute the value for N, and
% insert it in the tree.

addPathFrom(N, TOld, TNew, V) :-
    collatz(N, N1),
    addPathFrom(N1, TOld, TInt, V1),
    V is V1+1,
    insert(N, V, TInt, TNew).

% lookup: if the top vertex matches the key, return
% its value.

lookup(K, ct(K, V, _, _), V).

% lookup: if the top vertex is larger than the key, look
% up in the left subtree.

lookup(K, ct(K1, _, L, _), V) :-
    K < K1,
    lookup(K, L, V).
    
% lookup: if the top vertex is larger than the key, look
% up in the right subtree.

lookup(K, ct(K1, _, _, R), V) :-
    K > K1,
    lookup(K, R, V).

% insert: insert a new key/value in the tree (fail if attempting
% to insert an existing value).

insert(N, V, nilTree, ct(N, V, nilTree, nilTree)).

insert(N, V, ct(K, VK, L, R), ct(K, VK, L1, R)) :-
    N < K,
    insert(N, V, L, L1).
    
insert(N, V, ct(K, VK, L, R), ct(K, VK, L, R1)) :-
    N > K,
    insert(N, V, R, R1).

% General utility predicates intended to take a Collatz tree
% and report various interesting things.

% The maximum key created in building the tree to N.

maxCKey(N, M) :-
    collatzTree(N, T),
    maxKey(T, M).

% maxKey is general for trees of this type.

maxKey(ct(K, _, _, nilTree), K) :- !.

maxKey(ct(_, _, _, R), K) :-
    maxKey(R, K).
    
% The maximum value found in creating the tree to N.
    
maxCValue(N, M) :-
    collatzTree(N, T),
    maxValue(T, M).

% maxValue is general for trees of this type.

maxValue(nilTree, 0).

maxValue(ct(_, V, L, R), M) :-
    maxValue(L, ML),
    maxValue(R, MR),
    M is max(max(ML, MR), V).
         
% A "safe" set of predicates for showing a tree:
% showTree(T) : show the tree T (in key order) on
%               the current stream (usually terminal)
% showTree(B,T) : show the tree T (in key order) up to
%               a maximum key of B.
% fshowTree(Fn, T): show the tree T (in key order) on
%               the file Fn
% fshowTree(Fn, B,T) : show the tree T (in key order) up to
%               a maximum key of B on the file Fn.

showTree(T) :- printTree(T), !, fail.
showTree(B, T) :- printTree(B, T), !, fail.

fShowTree(Fn, T) :-
   open(Fn, write, Fd),
   tell(Fd),
   printTree(T),
   close(Fd),
   !,
   fail.
    
fShowTree(Fn, B, T) :-
   open(Fn, write, Fd),
   tell(Fd),
   printTree(B, T),
   close(Fd),
   !,
   fail.

% Now the basic printTree facilities.

% Printing a nil tree with or without a bound simply
% succeeds.

printTree(nilTree).
printTree(_, nilTree).

% For a non empty tree, print its left subtree, print
% the top node, and then print the right subtree.

printTree(ct(K,V,L,R)) :-
    printTree(L),
    writef('%6l%6l\n', [K,V]),
    printTree(R).
    
% Given a bound, print the left subtree with the bound,
% check the bound against the key, and if the key is small
% enough, print it, and then print the right subtree with the
% bound.

printTree(B, ct(K,V,L,R)) :-
    printTree(B, L),
    K =< B,
    writef('%6l%6l\n', [K,V]),
    printTree(B, R).

