Mercurial > hg > Applications > Tokio
diff Examples/sorter/sort2 @ 0:cfb7c6b24319
Initial revision
author | kono |
---|---|
date | Thu, 30 Aug 2007 14:57:44 +0900 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Examples/sorter/sort2 Thu Aug 30 14:57:44 2007 +0900 @@ -0,0 +1,105 @@ +/* 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). +