Mercurial > hg > Applications > Tokio

comparison Examples/sorter/pipe_sort @ 0:cfb7c6b24319

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial revision
author kono
date Thu, 30 Aug 2007 14:57:44 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:cfb7c6b24319
1
2 test :- Strdata = [10,20,5,100,1,6,2,3],
3 datagen(Strdata,Data),
4 pipe(Data,Out),
5 length(18),
6 #write(Out).
7
8 % Data Generator
9
10 datagen([],[]).
11 datagen([H|T],Out) :-
12 Out = [H],
13 @T = T, @datagen(T,Out).
14
15 % Pipeline Merge Sorter
16
17 pipe(I0,Out) :-
18 I1 = [], I2 = [], Out = [],
19 proc_start(I0,I1, 2,1),
20 proc_start(I1,I2, 4,2),
21 proc_start(I2,Out,8,4).
22
23 % Processor Unit
24
25 proc_start(I,O,P,PP) :-
26 X = [], Y = [], Z = [], T = 1,
27 #proc(I,O,X,Y,Z,T,P,PP).
28
29 proc(I,O,X,Y,Z,T,P,PP) :- X=[],Y=[],I=[],!,
30 @X=X, @Y=Y, @Z=Z, @O=[], @T=1.
31 proc(I,O,X,Y,Z,T,P,PP) :-
32 load(I,O,X,Y,Yn,Z,Zn,T,P,PP),
33 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP).
34
35 load(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- T=<PP, !,
36 append(Z,I,Zn), @Z=Zn, Yn=Y,
37 @T=T+1.
38 load(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-
39 append(Y,I,Yn), @Z=[],
40 (if T<P then @T=T+1 else @T=1).
41
42 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[],Yn=[],!,
43 @O=[], @Y=Yn,
44 (if T=PP then @X=Zn else @X=X).
45 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- X=[A|L],Yn=[],!,
46 @O=[A], @Y=Yn,
47 (if T=PP then @X=Zn else @X=L).
48 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[],Yn=[B|N],!,
49 @O=[B], @Y=N,
50 (if T=PP then @X=Zn else @X=X).
51 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[A|L],Yn=[B|N],!,
52 (if A<B then
53 @O=[A], @X=L, @Y=Yn
54 else
55 @O=[B], @Y=N, @X=X).
56
57 append(Nil,L,L1) :- Nil=[],L=L1.
58 append(X,L,Y) :-[H|T]=X,[H1|M]=Y,
59 H=H1,append(T,L,M).
60