/* Program to do parallel quicksort.  Ben Moszkowski
  Initial version written around 29 Apr 84.
  Subsequent changes made.
  Updated 7 Feb 85.

  translate to Tokio by S.Kono
				Sun Aug 31 21:29:10 JST 1986
				using list and explicit sync
  */

/* Support Routines */

'$function' (len(L) = Length :- list_length(L,Length)).

list_length(Nil, -1 ) :- Nil=[],!.
list_length(List,N) :- List=[H|L],list_length(L,NN),
    N = NN+1,!.

'$function' (slice(List,From,To) = Slice :- slice(0,List,From,To,Slice)).

slice(N,List,From,To,[]) :- N>To,!.
slice(N,[H|List],From,To,[H|Slice]) :- N>=From,!,
    NN = N+1,
    slice(NN,List,From,To,Slice).
slice(N,[H|List],From,To,Slice) :-
    NN = N+1,
    slice(NN,List,From,To,Slice).

'$function' (thof(I,L) = E :- thof(I,L,E)).

thof(0,[H|L],H) :- !.
thof(N,[H|L],H1) :- NN = N-1, thof(NN,L,H1).

fixed_list([],Length) :- Length = -1,!.
fixed_list([H|L],Length) :- Length1 = Length-1,
    fixed_list(L,Length1).

'$function' ( (if Cond then Yes else No) = Reply :-
    if Cond then Yes=Reply else No=Reply).


/* Support Routines end */

par_quicksort(L) :- 
    if len(L) < 1
    then empty
    else 
	stable(Pivot),
	(   quick_partition(L,Pivot) &
	    sort_parts(L,Pivot) ).

quick_partition(L,Pivot) :- 
	I = 1, Z=0, J = len(L), J1=J+1,skip, 
	P = thof(0,L),
	partition(I,J1,P,Z,J,L,Pivot).

partition(K,K,P,I,J,L,Pivot) :- !,@Pivot=I,@I=I,@thof(I,L)=P.
partition(K,E,P,I,J,L,Pivot) :- thof(K,L) < P,!, II=I+1,
	@I=I, @thof(I,L) = thof(K,L), KK=K+1,
	partition(KK,E,P,II,J,L,Pivot).
partition(K,E,P,I,J,L,Pivot) :- JJ=J-1,
	@J=J, @thof(J,L) = thof(K,L), KK=K+1,
	partition(KK,E,P,I,JJ,L,Pivot).

sort_parts(L,Pivot) :- 
	quicksort_process(Done,Ready1, slice(L,0,Pivot-1)),
	quicksort_process(Done,Ready2, slice(L,Pivot+1, len(L))),
	#((if 1 = Ready1, 1 = Ready2 then 1 = @Done else 0 = @Done)),
	stable(thof(Pivot,L)).

quicksort_process(Done,Ready,L) :-
	par_quicksort(L),
	#(Ready=0)
    &
	skip, @Ready=1, stable(L)
    &
	halt(Done=1),
	#(Ready=1),stable(L).

monitor(L) :- 
	fixed_list(Tag_list,len(L)),
	#tag(0,L,Tag_list),
    	#((write('''List='''),write(L),put(" "),
	   write('''Tag_list='''),write(Tag_list))).

tag(_,Nil,Nil) :- Nil=[],!.
tag(I,[H|L],[TH|TL]) :- TH = (if I=H then 1 else 0),
	J=I+1,tag(J,L,TL).

/*  test of quicksort */
sort_test(Init_vector) :- 
     %exists L : 
	stable(Init_vector),
        fixed_list(L,len(Init_vector)),
	L=Init_vector,
	par_quicksort(L),
        monitor(L).
%	#write(L).

sort_test1 :- [2,0,1]=List,sort_test(List).

sort_test2 :-  [2,4,9,1,0,10,6,8,7,5,3]=List,sort_test(List).

sort_test3 :- [13,7,5,3,1,9,8,6,2,0,12,11,4,10]=List,sort_test(List).