% Tom Schrijvers
% 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		@ make(A) <=> root(A,0).

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

findNode	@ find(A,X), A ~> B <=> find(B,X), A ~> X.  
findRoot	@ root(A,_) \  find(A,X) <=> X=A.

linkEq		@ link(A,A) <=> true.  
linkLeft	@ link(A,B), root(A,SA), root(B,SB) <=> SA>=SB | 
                            B ~> A, SA1 is SA+1, root(A,SA1).
linkRight	@ link(B,A), root(A,SA), root(B,SB) <=> SA>=SB |
                            B ~> A, SA1 is SA+1, root(A,SA1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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).