% Thom Fruehwirth, conceived 2004-03-09, typed in 2004-06-14, corrected 06-15
% version with argument passing using '=' in a very restricted way ro return result

:- use_module(library(chr)).

% FUNCTION RETURN VERSION

operator(700, xfx, '~>').
:- op(700,xfx,'~>').

constraints 
	(~>)/2, 
	union/2, 
	find/2,
	link/2,
	root/2,
	make/1
	.

option(debug,off).

option(mode,make(+)).	
option(mode,root(+,+)).		
option(mode,union(+,+)).	
option(mode,find(+,?)).		
option(mode,link(+,+)).		
option(mode,'~>'(+,+)).		

make(A) <=> root(A,0).

union(A,B) <=> find(A,X), find(B,Y), link(X,Y).

% path compression with immediate update thanks to logical variable
find(A,X), A ~> B <=> find(B,X), A ~> X.  
% return function result in first argument
root(B,_) \  find(B,X) <=> X=B.      % found

% root treatment
link(A,A) <=> true.  
link(A,B), root(A,NA), root(B,NB) <=> NA>=NB | 
                            B ~> A, NA1 is max(NA,NB+1), root(A,NA1).
link(B,A), root(A,NA), root(B,NB) <=> NA>=NB |
                            B ~> A, NA1 is max(NA,NB+1), root(A,NA1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Benchmark
% Generates random unions and finds.

main :-
	bench_range(100,10000,100).	
	
bench(N,M) :-
	make_atoms(N,Atoms),
	AtomsTerm =.. [t|Atoms],
	generate_unions(N,N,AtomsTerm,Unions),
	generate_finds(M,N,AtomsTerm,Finds),
	statistics(runtime,[T1|_]),
	exists_list(Atoms),
	union_list(Unions),
	find_list(Finds),
	statistics(runtime,[T2|_]),
	T is T2 - T1,
	format('~w\t~w\n',[N,T]).

bench_range(From,To,Step) :-
	( From > To ->
		true
	;
		( bench(From,From), fail ; true),
		Next is From + Step,
		bench_range(Next,To,Step)
	).

exists_list([]).
exists_list([X|Xs]) :-
	make(X),
	exists_list(Xs).

union_list([]).
union_list([X-Y|Xs]) :-
	union(X, Y),
	union_list(Xs).

find_list([]).
find_list([X|Xs]) :-
	find(X,_),
	find_list(Xs).

generate_unions(I,N,Atoms,Unions) :-
	( I > 0 ->
		random_element(Atoms,N,X),	
		random_element(Atoms,N,Y),	
		Unions = [X-Y|Tail],
		J is I - 1,
		generate_unions(J,N,Atoms,Tail)
	;
		Unions = []
	).	

generate_finds(I,N,Atoms,Finds) :-
	( I > 0 ->
		random_element(Atoms,N,X),	
		Finds = [X|Tail],
		J is I - 1,
		generate_finds(J,N,Atoms,Tail)
	;
		Finds = []
	).	

make_atoms(N,L) :-
	( N > 0 ->
		make_atom(N,Atom),
		L = [Atom|T],
		M is N - 1,
		make_atoms(M,T)
	;
		L = []
	).

make_atom(N,Atom) :-
	atom_concat(atom,N,Atom).

random_element(Term,N,Element) :-
	Index is random(N) + 1,
	arg(Index,Term,Element).