%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Merging and Sorting in CHR
%
% Based on an implementation by Thom Fruehwirth.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- module(mergesort,[bench/0,main/0]).

:- use_module(library(chr)).

handler mergesort.

constraints arrow/2, merge/2.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

arrow(X,A) \ arrow(X,B) <=> A < B | arrow(A,B).

merge(N,A), merge(N,B) <=> A < B | M is N+1, merge(M,A), arrow(A,B).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


bench :- (main;main;main;main),fail.
bench.

main :- 
	main(500).

main(N) :-
        statistics(runtime,[T1|_]),
	loop(N),
        statistics(runtime,[T2|_]),
        Time is T2 - T1,
	write(bench(mergesort,N,Time,0,sicstus)), write('.'),nl.

loop(N) :-
	( N == 0 ->
		true
	;
		(work,fail;true),
		M is N - 1,
		loop(M)
	).

work :-
	Numbers = 
       	     [27,74,17,33,94,18,46,83,65, 2,
              32,53,28,85,99,47,28,82, 6,11,
              55,29,39,81,90,37,10, 0,66,51,
               7,21],
        process(Numbers).

process([]).
process([X|Xs]) :-
        merge(0,X),
        process(Xs).
