% Code from O'Keefe (1994), Chapter 1 
%
% Note: some modifications of predicates given in that chapter were made,
% mostly to allow all predicates to occur in one file at the same
% Where this was done is noted in a comment to the code.

% direction_adjective(Direction,Adjective)
% is true when Adjective is the Latinised adjective meaning
% ``pertaining to Direction'' 

direction_adjective(north, boreal).
direction_adjective(south, austral).
direction_adjective(east, oriental).
direction_adjective(west, occidental).


abs_diff(X, Y, Diff) :-
     compare(R, X, Y),
     abs_diff(R, X, Y, Diff).
abs_diff(<,X,Y,Diff) :- Diff is Y-X.
abs_diff(>,X,Y,Diff) :- Diff is X-Y.
abs_diff(=,_,_,0).


is_list([]).           % a) base/non-recursive case
is_list([_|Tail]) :-   % b) step/recursive/inductive case
     is_list(Tail).


% arithmetic_value(Expr,Value)
% is true when Expr represents an arithmetic expression and
% Value is its numeric value

arithmetic_value(c(N), N).            % base case
arithmetic_value(E+F, Value) :-       % recursive case 1
     arithmetic_value(E,Eval),
     arithmetic_value(F,Fval),
     Value is Eval + Fval.
arithmetic_value(-F, Value) :-        % recursive case 2
     arithmetic_value(F,Fval),
     Value is -Fval.
arithmetic_value(E-F, Value) :-       % recursive case 3
     arithmetic_value(E,Eval),
     arithmetic_value(F,Fval),
     Value is Eval - Fval.
arithmetic_value(E*F, Value) :-       % recursive case 4
     arithmetic_value(E,Eval),
     arithmetic_value(F,Fval),
     Value is Eval * Fval.
arithmetic_value(E/F, Value) :-       % recursive case 5
     arithmetic_value(E,Eval),
     arithmetic_value(F,Fval),
     Value is Eval / Fval.


member(X,[X|_]).
member(X,[_|L]) :-
     member(X,L).
  

birthday(byron,   date(feb,4)).
birthday(noelene, date(dec,25)).
birthday(richard, date(oct,11)).
birthday(clare,   date(sep,15)).


factorial(0,1).
factorial(N,N_Factorial) :-
     N > 0,
     M is N-1,
     factorial(M, M_Factorial),
     N_Factorial is M_Factorial*N.


min(X, Y, X) :- X < Y.
min(X, Y, Y) :- X >= Y.

min_and_max(X, Y, X, Y) :- X < Y.
min_and_max(X, Y, Y, X) :- X >= Y.


scale([], _, []).
scale([X|Xs], Multiplier, [Y|Ys]) :-
     Y is X*Multiplier,
     scale(Xs, Multiplier, Ys).


% big_elements(InputList,OutputList)
% True if OutputList is the list of those elements of
% InputList which are bigger than 10, preserving order.

big_elements(Input,Output) :-
     big_elements(Input, 10, Output).

big_elements([], _, []).
big_elements([Nbr|Nbrs], Bound, Bigs) :-
     Nbr < Bound,
     big_elements(Nbrs, Bound, Bigs).
big_elements([Nbr|Nbrs], Bound, [Nbr|Bigs]) :-
     Nbr >= Bound,
     big_elements(Nbrs, Bound, Bigs).


len(List,Length) :-
     len(List, 0, Length).

len([], N, N).
len([_|L], N0, N) :-
     N1 is N0+1,
     len(L, N1, N).

rev(List, Reverse) :-
     rev(List, [], Reverse).

rev([], Reverse, Reverse).
rev([Head|Tail], Reverse0, Reverse) :-
     rev(Tail, [Head|Reverse0], Reverse).


sum_pos_neg(List, Pos, Neg) :-
     sum_pos_neg(List, 0, Pos, 0, Neg).

sum_pos_neg([], Pos, Pos, Neg, Neg).
sum_pos_neg([X|Xs], Pos0, Pos, Neg0, Neg) :-
     X >= 0,
     Pos1 is Pos0+X,
     sum_pos_neg(Xs, Pos1, Pos, Neg0, Neg).
sum_pos_neg([X|Xs], Pos0, Pos, Neg0, Neg) :-
     X < 0,
     Neg1 is Neg0+X,
     sum_pos_neg(Xs, Pos0, Pos, Neg1, Neg).


sum_and_ssq(List, Sum, SSQ) :-
     sum_and_ssq(List, 0, Sum, 0, SSQ).

sum_and_ssq([], Sum, Sum, SSQ, SSQ).
sum_and_ssq([X|Xs], Sum0, Sum, SSQ0, SSQ) :-
     Sum1 is Sum0+X,
     SSQ1 is SSQ0+(X*X), 
     sum_and_ssq(Xs, Sum1, Sum, SSQ1, SSQ).


slow_len([],0).
slow_len([_|Tail],N) :-
     slow_len(Tail,M),
     N is M+1.

% Note: renamed non-tail-recursive version of len/2 to slow_len/2


is_proper_list(Term) :-
     classify_list(Term, proper, proper).

is_partial_list(Term) :-
     classify_list(Term, proper, partial).

is_a_list(Term) :-
     classify_list(Term, partial, partial).

classify_list(V, _, X) :-
     var(V),
     !,
     X=partial.
classify_list([],X,X).
classify_list([_|T],X0,X) :-
     classify_list(T, X0, X).


append([], L, L).
append([H|T], L, [H|R]) :-
     append(T,L,R).


map_p([],[]).
map_p([X|Xs],[Y|Ys]) :-
     p(X,Y),
     map_p(Xs,Ys).


% Data represented as: b(LeftDtr,RightDtr,Datum)

path_data([], Tree, Datum) :-
     b_access(d, Tree, Datum).
path_data([Arc|Arcs], Tree, Datum) :-
     b_access(Arc, Tree, Dtr),
     path_data(Arcs, Dtr, Datum).

b_access(1, b(Lson,_,_),  Lson).
b_access(2, b(_,Rson,_),  Rson).
b_access(d, b(_,_,Datum), Datum).

% Note: renamed access predicates from b/3 to b_access/3 to distinguish
% from access data structure as such.

dynamic_pattern(Path, Tree, Datum) :-
     path_data(Path, Pattern, Datum),
     Tree = Pattern.
 


% bup_ground(Term)
% is true when Term contains no variables.

bup_ground(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     bup_ground(Arity, Term).

% bup_ground(N, Term)
% is true when Term (known to be a non-variable has no
% variables in its first N arguments

bup_ground(0,_) :-!. % no more elements to process
bup_ground(N, Term) :-
     arg(N, Term, Arg), % process N
     bup_ground(Arg),
     M is N-1,
     bup_ground(M, Term).


% bup_ground2(Term), if-the-else version
% is true when Term contains no variables.

bup_ground2(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     bup_ground2(Arity, Term).

% bup_ground2(N, Term), if-then-else version
% is true when Term (known to be a non-variable has no
% variables in its first N arguments

bup_ground2(N, Term) :-
     (N = 0 ->  % no more elements to process
         true
     ;
         arg(N, Term, Arg),     % process N
         bup_ground2(Arg),
         M is N-1,
         bup_ground2(M, Term)).


% td_ground(Term)
% is true when Term contains no variables

td_ground(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     td_ground(0, Arity, Term).

td_ground(N,N,_) :-!. % no more elements to process
td_ground(I, N, Term) :-
     J is I+1,
     arg(J, Term, Arg),
     td_ground(Arg), % process element J
     td_ground(J,N,Term).

% td_ground2(Term), if-then-else version 
% is true when Term contains no variables

td_ground2(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     td_ground2(0, Arity, Term).

td_ground2(I,N,Term) :-
     (I < N ->
         J is I+1,
         arg(J, Term, Arg),
         td_ground2(Arg),       % process element J
         td_ground2(J,N,Term)
     ;   true % I = N, no more items to process
     ).


% bi_ground(Term)
% is true when Term contains no variables

bi_ground(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     bi_ground(1, Arity, Term).

% bi_ground(L, U, Term)
% is true when argument L..U of Term are all ground

bi_ground(L, U, Term) :-
     L<U, !,
     M is (L+U)//2,
     N is M+1,
     bi_ground(L, M, Term),
     bi_ground(N, U, Term).
bi_ground(L, L, Term) :- !,
     arg(L, Term, Arg),
     bi_ground(Arg).
bi_ground(_, _, _). % L>U: no elements to process


% bi_ground2(Term), if-then-else version
% is true when Term contains no variables

bi_ground2(Term) :-
     nonvar(Term),
     functor(Term, _, Arity),
     bi_ground2(1, Arity, Term).

% bi_ground2(L, U, Term), if-then-else version
% is true when argument L..U of Term are all ground

bi_ground2(L, U, Term) :-
     ( L<U ->
         M is (L+U)//2,
         N is M+1,
         bi_ground2(L, M, Term),
         bi_ground2(N, U, Term)
     ;   (L>U -> true
         ;   arg(L, Term, Arg), % L=U
             bi_ground2(Arg)
         )
     ).


% note: renamed number based twice_as_long to num_twice_as_long

num_twice_as_long(L1,L2) :-
     length(L1,N1),
     N2 is N1*2,
     length(L2,N2).


twice_as_long([],[]).
twice_as_long([_|L1],[_,_|L2]) :-
     twice_as_long(L1,L2).


% Note: name changed to  wrong_count_atom_arguments/2 and /4
wrong_count_atom_arguments(Term, Count) :-
     nonvar(Term),
     functor(Term, _, Arity),
     wrong_count_atom_arguments(Arity, Term, 0, Count).

wrong_count_atom_arguments(0, _, Count, Count).
wrong_count_atom_arguments(N, Term, Count0, Count) :-
     arg(N, Term, Arg),
     atom(Arg),
     Count1 is Count0+1,
     M is N-1,
     wrong_count_atom_arguments(M, Term, Count1, Count).
wrong_count_atom_arguments(N, Term, Count0, Count) :- % contains logical error!
     M is N-1,
     wrong_count_atom_arguments(M, Term, Count0, Count).


count_atom_arguments(Term, Count) :-
     nonvar(Term),
     functor(Term, _, Arity),
     count_atom_arguments(Arity, Term, 0, Count).

count_atom_arguments(0, _, Count, Count).
count_atom_arguments(N, Term, Count0, Count) :-
     arg(N, Term, Arg),
     ( atom(Arg) ->  Increment = 1  % Arg is atom
     ;               Increment = 0  % Arg is non-atom
     ),
     Count1 is Count0+Increment,
     M is N-1,
     count_atom_arguments(M, Term, Count1, Count).


% Note: renamed  third version to have all three in parallel

fast_count_atom_arguments(Term, Count) :-
     nonvar(Term),
     functor(Term, _, Arity),
     fast_count_atom_arguments(Arity, Term, 0, Count).

fast_count_atom_arguments(N, Term, Count0, Count) :-
     ( N=:=0 -> Count is Count0 % no more arguments
     ;          arg(N, Term, Arg),
                ( atom(Arg) ->  Increment = 1  % Arg is atom
                ;               Increment = 0  % Arg is non-atom
                ),
                Count1 is Count0+Increment,
                M is N-1,
                fast_count_atom_arguments(M, Term, Count1, Count)
     ).

% --- from chapter 3.4

cpu_time(Time) :-
     statistics(runtime, [T|_]),
     Time is T*0.001.

cpu_time(Goal,Duration) :-
   statistics(runtime, [Start|_]),
   ( call(Goal) -> true ; true ),
   statistics(runtime, [Finish|_]),
   Duration is (Finish-Start)*0.001.

cputime(N, Goal, Duration) :-
   statistics(runtime, [T0|_]),
   ( call(( repeat(N), (Goal -> fail) )) ; true ),
   statistics(runtime, [T1|_]),
   ( call(( repeat(N), (true -> fail) )) ; true ),
   statistics(runtime, [T2|_]),
   Duration is ((T1-T0) - (T2-T1))*0.001.
