1% ------------------------------------------------
    2% January 1999
    3% Author: Brian Ross
    4% Dept. of Computer Science, Brock University
    5%
    6% Misc prolog predicates.
    7%
    8% Sicstus: comment out member
    9%	- add routines for random numbers (seed, maybe, ...)
   10
   11?- dynamic been_here/0.   12
   13%append([], A, A).
   14%append([A|X], Y, [A|Z]) :- append(X, Y, Z).
   15
   16%member(A, [A|_]).
   17%member(A, [_|B]) :- member(A, B).
   18
   19memberd(A, L) :- once(member(A,L)).
   20
   21% my_random(R, N) finds a random integer N between 1 and R
   22% Note: N must be uninstantiated!
   23
   24my_random(R, N) :-
   25       % S is R + 1,
   26	random_between(1, R, N),
   27	!.
   28
   29% probability2(P, M) satisfied when random number between 0 and M
   30% is less or equal to probability P.
   31
   32probability2(P, M) :-
   33	random(X),
   34	Y is X*M,
   35	Y =< P,
   36	!.
   37
   38size_of([], 0).
   39size_of([_|R], K) :-
   40	size_of(R, L),
   41	K is L + 1,
   42	!.
   43
   44% once(P) :- P, !.
   45
   46writel([]) :- !, ttyflush.
   47writel([A|R]) :- var(A), !, write(A), write(' '), writel(R).
   48writel([nl|R]) :- !, nl, writel(R).
   49writel([A|R]) :- !, write(A), write(' '), writel(R).
   50writel(A) :- write(A), ttyflush, !.
   51
   52writel2([]) :- !, ttyflush.
   53writel2([A|R]) :- var(A), !, write(A), writel2(R).
   54writel2([nl|R]) :- !, nl, writel2(R).
   55writel2([A|R]) :- !, write(A), writel2(R).
   56writel2(A) :- write(A), ttyflush, !.
   57
   58/*
   59sum_list([], 0).
   60sum_list([A|L], N) :-
   61	sum_list(L, M),
   62	N is M + A,
   63	!.
   64
   65max_list([A|L], Max) :-
   66	once(max_list2(A, L, Max)).
   67
   68max_list2(A, [], A).
   69max_list2(A, [B|L], Max) :-
   70	B > A,
   71	max_list2(B, L, Max).
   72max_list2(A, [_|L], Max) :-
   73	max_list2(A, L, Max).
   74
   75min_list([A|L], Min) :-
   76	once(min_list2(A, L, Min)).
   77
   78min_list2(A, [], A).
   79min_list2(A, [B|L], Min) :-
   80	B < A,
   81	min_list2(B, L, Min).
   82min_list2(A, [_|L], Min) :-
   83	min_list2(A, L, Min).
   84*/
   85
   86copy_struct(S, T) :-
   87	assert(temp(S)),
   88	retract(temp(T)),
   89	!.
   90
   91count(_, [], 0).
   92count(X, [X|Y], C) :-
   93	!,
   94	count(X, Y, C2),
   95	C is C2 + 1.
   96count(X, [_|Y], C) :-
   97	count(X, Y, C).
   98
   99round(X, Y) :- Y is integer(X+0.5), !.
  100
  101set_random_number_gen :-
  102	been_here,
  103	!.
  104set_random_number_gen :-
  105	assert(been_here),
  106	!,
  107	seed_P(X,Y),
  108	set_seed(X,Y).
  109
  110set_seed(default, _) :- !.
  111set_seed(random, _) :-
  112	datime(datime(Year,Month,Day,Hour,Min,Sec)),
  113	% N is approx number of seconds since Jan 1 1970
  114	N is (((((Year-1970)*12+Month)*30+Day)*24+Hour)*60+Min)*60+Sec,
  115	R1 is mod(N, 30270) + 1,  % between 1 and 30000
  116	N2 is abs(N >> 2), 	  % shift right 2 bits
  117	R2 is mod(N2, 30308) + 1,
  118	N3 is abs(N >> 4),        % shift right 4 bits
  119	R3 is mod(N3, 30324) + 1,
  120	setrand(rand(R1,R2,R3)),
  121	retract(seed_P(_,_)),
  122	assert(seed_P(random, (R1,R2,R3))),
  123	!.
  124set_seed(manual, (X, Y, Z)) :-
  125	setrand(rand(X,Y,Z)).
  126	
  127
  128/*
  129set_seed(default, _) :- !.
  130set_seed(random, _) :-
  131	now(N),
  132	R1 is mod(N, 30000) + 1,  % between 1 and 30000
  133	N2 is abs(N >> 2), 	  % shift right 2 bits
  134	R2 is mod(N2, 30000) + 1,
  135	N3 is abs(N >> 4),        % shift right 4 bits
  136	R3 is mod(N3, 30000) + 1,
  137	getrand(random(_,_,_,B)),
  138	setrand(random(R1,R2,R3,B)),
  139	retract(seed_P(_,_)),
  140	assert(seed_P(random, (R1,R2,R3))),
  141	!.
  142set_seed(manual, (X, Y, Z)) :-
  143	getrand(random(_,_,_,B)), % use default bit string (could be changed)
  144	setrand(random(X,Y,Z,B)),
  145	!.
  146*/
  147
  148debug_echo(L) :- debug_set_P(yes), !, writel(L).
  149debug_echo(_).
  150
  151rem_dups([], []).
  152rem_dups([A|R], R2) :- 
  153	member(A, R),
  154	!,
  155	rem_dups(R, R2).
  156rem_dups([A|R], [A|R2]) :-
  157	rem_dups(R, R2),
  158	!.
  159
  160average(M, Avg) :-
  161	sum_list(M, Sum),
  162	size_of(M, N),
  163	Avg is Sum / N,
  164	!.
  165
  166% keep appending B to A until A is at least length K.
  167
  168extend_list(A, _, K, A) :-
  169	length(A, K2),
  170	K2 >= K,
  171	!.
  172extend_list(A, B, K, A2) :-
  173	append(A, B, A3),
  174	extend_list(A3, B, K, A2),
  175	!.
  176
  177num_list(0, []) :- !.
  178num_list(N, [N|R]) :-
  179	M is N - 1,
  180	num_list(M, R).
  181
  182remove(_, [], []).
  183remove(A, [A|B], B).
  184remove(A, [X|B], [X|C]) :- remove(A, B, C).
  185
  186remove_all(_, [], []).
  187remove_all(A, [A|B], C) :- !, remove_all(A, B, C).
  188remove_all(A, [X|B], [X|C]) :- remove_all(A, B, C).
  189
  190
  191intersect([], _,[]).
  192intersect([X|Y], R, [X|Z]) :-
  193	member(X, R),
  194	!,
  195	intersect(Y, R, Z).
  196intersect([_|Y], R, Z) :-
  197	intersect(Y, R, Z).
  198
  199set_diff([], T, T) :- !.
  200set_diff(T, [], T) :- !.
  201set_diff([A|B], T, Diff) :-
  202	member(A, T),
  203	!,
  204	remove_all(A, T, T2),
  205	set_diff(B, T2, Diff).
  206set_diff([A|B], T, [A|R]) :-
  207	set_diff(B, T, R).
  208
  209remove_list([], B, B) :- !.
  210remove_list([A|B], C, D) :-
  211	remove(A, C, E),
  212	!,
  213	remove_list(B, E, D).
  214
  215writelist([]) :- nl, !.
  216writelist([A|R]) :- write(A), nl, writelist(R), !.
  217
  218maybe :- maybe(0.5), !.
  219	
  220maybe(X) :-
  221	random(Y),
  222	Y < X,
  223	!.
  224
  225random_permutation(L, Perm) :-
  226	length(L, Len),
  227	random_permutation2(L, Len, Perm),
  228	!.
  229
  230random_permutation2([], _, []).
  231random_permutation2(L, Len, [X|Perm]) :-
  232	random(0, Len, R),
  233	remove_nth(R, L, X, L2),
  234	Len2 is Len-1,
  235	random_permutation2(L2, Len2, Perm),
  236	!.
  237
  238remove_nth(0, [X|Y], X, Y) :- !.
  239remove_nth(N, [X|Y], Z, [X|W]) :-
  240	N2 is N-1,
  241	remove_nth(N2, Y, Z, W),
  242	!.
  243
  244select_rand(L, R) :-
  245	length(L, Len),
  246	Len > 0,
  247	random(0, Len, Rand),
  248	remove_nth(Rand, L, R, _),
  249	!.
  250
  251
  252% first_K(M, N, List, Grabbed) counts from M to N, grabbing the first N
  253% entries of List, returning them in Grabbed.
  254
  255first_K(M, N, _, []) :- M >= N, !.
  256first_K(M, N, [A|R], [A|S]) :- 
  257	M2 is M + 1,
  258	first_K(M2, N, R, S),
  259	!