%----------------------------------------------------------------------
% Test toplevel
%
% test(
%	N,           % test size (number of constraints)
%
%	AB,          % AB = 0  -> Non-strict inequalities X>=Y
%                    % AB = 1  -> Strict inequalities X>Y
%
%       Batch,	     % posting strategy: inc, batch
%
%       Order	     % posting order: up, down, odd_even, binchop, etc
%     )
%----------------------------------------------------------------------

:- use_module(library(lists)).


test(AB, Batch, Order) :-
	member(N, [100,200,500,1000,2000,5000,10000,20000]),
%	member(N, [100,200,500,1000,2000]),
%	between(1,600,N),
%	between(10,24,Exp), N is fix(1.5^Exp),
%	between(10,24,Exp), N is integer(1.5**Exp),
	test(N, AB, Batch, Order),
	fail.
test(_AB, _Batch, _Order) :-
	write(done), nl.


test(N, AB, Batch, Order) :-
%	write(test(N, AB, Batch, Order)), nl,

	% create N+1 variables in N pairs
	make_var_pairs(N, Pairs, Vars),
	% permute variable pairs into constraint posting order
	create_order(Order, Pairs, OrderedPairs),

%	monitor_vars(Vars),
%	make_display_matrix(Vars/8, vars),

	cputime(T),
	once(setup_and_solve(Batch, AB, N, Vars, OrderedPairs)),
	cputime(T2),

	Vars = [X|_], once(append(_, [Z], Vars)),
	write((min=X,max=Z)), nl,
	Time is T2-T,
	LNPerCons is Time/N,
%	LNPerCons is ln(Time/N)/ln(10),
	write(usercputimepercons(LNPerCons)), nl,
%	Stars is fix(Time*100),
%	Stars is fix(LNPerCons*10000),
%	printf("%w%t%*c%n", [N, Stars, 0'*]),

	fail.				% fail to clean up
test(_, _, _, _).


% repeat test R times for more accurate results
rtest(R, N, AB, Batch, Order) :-
	make_var_pairs(N, Pairs, Vars),
	create_order(Order, Pairs, OrderedPairs),
	cputime(T),
	do_rtest(R, Batch, AB, N, Vars, OrderedPairs),
	cputime(T2),

	Vars = [X|_], once(append(_, [Z], Vars)),
	write((min=X,max=Z)), nl,
	Time is T2-T,
	LNPerCons is Time/(N*R),
	write(usercputimepercons(LNPerCons)), nl,

	fail.				% fail to clean up
rtest(_,_, _, _, _).

   do_rtest(R, Batch, AB, N, Vars, OrderedPairs) :-
	(R > 1 ->
	   \+ \+ once(setup_and_solve(Batch, AB, N, Vars, OrderedPairs)),
	   R1 is R - 1,
	   do_rtest(R1, Batch, AB, N, Vars, OrderedPairs)
	;
	   once(setup_and_solve(Batch, AB, N, Vars, OrderedPairs))
	).

%----------------------------------------------------------------------
% Auxiliaries
%----------------------------------------------------------------------

between(L, H, X) :-
	L =< H,
	( X = L ; L1 is L+1, between(L1, H, X) ).


make_var_pairs(N, Pairs, [X0|Vars]) :-
	make_var_pairs(N, X0, Pairs, Vars).

    make_var_pairs(N, Xi, [Xi-Xj|Pairs], [Xj|Vars]) :-
    	( N > 1 ->
	    N1 is N-1,
	    make_var_pairs(N1, Xj, Pairs, Vars)
	;
	    Pairs = [],
	    Vars = []
	).


create_order(up, Is, Is).
create_order(down, Is, OrderedIs) :-
	reverse(Is, OrderedIs).
create_order(random, Is, OrderedIs) :-
	shuffle(Is, OrderedIs).
create_order(random(Seed), Is, OrderedIs) :-
    	seed(Seed), shuffle(Is, OrderedIs).
create_order(odd_even, Is, OrderedIs) :-
	distribute(Is, Odds, Evens), append(Odds, Evens, OrderedIs).
create_order(even_odd, Is, OrderedIs) :-
	distribute(Is, Odds, Evens), append(Evens, Odds, OrderedIs).
create_order(out_in, Is, OrderedIs) :-
	halve_r(Is, IsLeft, IsRight), reverse(IsRight, IsRightR), splice(IsRightR, IsLeft, OrderedIs).
create_order(in_out, Is, OrderedIs) :-
	halve_r(Is, IsLeft, IsRight), reverse(IsLeft, IsLeftR), splice(IsRight, IsLeftR, OrderedIs).
create_order(binchop, Is, OrderedIs) :-
	breadth_first_binary_chop(Is, OrderedIs).


distribute([], [], []).
distribute([X|Xs], [X|Odds], Evens) :-
	distribute(Xs, Evens, Odds).


breadth_first_binary_chop(List, Out) :-
	breadth_first_binary_chop([List|T], T, Out).

    breadth_first_binary_chop([], [], []) :- !.
    breadth_first_binary_chop([List|Next], Tail, [M|Out0]) :-
	halve_r(List, L, [M|R]),
	( L = [] -> Tail  = Tail1 ; Tail  = [L|Tail1] ),
	( R = [] -> Tail1 = Tail2 ; Tail1 = [R|Tail2] ),
	breadth_first_binary_chop(Next, Tail2, Out0).


% like halve/3, but balanced towards the right list
halve_r(List, Front, Back) :-
	halve_r(List, List, Front, Back).

    halve_r([], Back0, Front, Back) :- !, Front=[], Back=Back0.
    halve_r([_], Back0, Front, Back) :- !, Front=[], Back=Back0.
    halve_r([_,_|Es], [X|Rs], [X|Fs], Back) :-
	halve_r(Es, Rs, Fs, Back).


/*
% ECLiPSe specific
monitor_vars(Vars) :-
	( foreach(X,Vars) do
	    X #>= 0,
	    suspend(monitor(I), 1, X->any)
	).

:- demon monitor/1.
monitor(I) :-
	printf("%*c*%n", [I,0' ]).
*/
