0
|
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 run :- Strdata = [10,20,5,100,1,6,2,3],
|
|
9 datagen(Strdata,Data),
|
|
10 pipe(Data,Out),
|
|
11 length(18).
|
|
12
|
|
13 % Data Generator
|
|
14
|
|
15 datagen([],[]).
|
|
16 datagen([H|T],Out) :-
|
|
17 Out = [H], @T = T, @datagen(T,Out).
|
|
18
|
|
19 % Pipeline Merge Sorter
|
|
20
|
|
21 pipe(I0,Out) :-
|
|
22 I1 = [], I2 = [], Out = [],
|
|
23 proc_start(I0,I1, 2,1),
|
|
24 proc_start(I1,I2, 4,2),
|
|
25 proc_start(I2,Out,8,4).
|
|
26
|
|
27 % Processor Unit
|
|
28
|
|
29 proc_start(I,O,P,PP) :-
|
|
30 X = [], Y = [], Z = [], T = 1,
|
|
31 #proc(I,O,X,Y,Z,T,P,PP).
|
|
32
|
|
33 proc(I,O,X,Y,Z,T,P,PP) :- X=[],Y=[],I=[],
|
|
34 @X=X, @Y=Y, @Z=Z, @O=[], @T=1.
|
|
35 proc(I,O,X,Y,Z,T,P,PP) :-
|
|
36 load(I,O,X,Y,Yn,Z,Zn,T,P,PP),
|
|
37 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP).
|
|
38
|
|
39 load(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- PP>=T,
|
|
40 append(Z,I,Zn), @Z=Zn, Yn=Y, @T=T+1.
|
|
41 load(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- T>PP,T<P,
|
|
42 append(Y,I,Yn), @Z=[],@T=T+1.
|
|
43 load(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- T>PP,T>=P,
|
|
44 append(Y,I,Yn), @Z=[],@T=1.
|
|
45
|
|
46 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[],Yn=[],
|
|
47 @O=[], @Y=Yn,switch(T,PP,X,Zn,X).
|
|
48 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :- X=[A|L],Yn=[],
|
|
49 @O=[A], @Y=Yn,switch(T,PP,X,Zn,L).
|
|
50 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[],Yn=[B|N],
|
|
51 @O=[B], @Y=N,switch(T,PP,X,Zn,X).
|
|
52 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[A|L],Yn=[B|N],
|
|
53 A<B,
|
|
54 @O=[A], @X=L, @Y=Yn.
|
|
55 merge(I,O,X,Y,Yn,Z,Zn,T,P,PP) :-X=[A|L],Yn=[B|N],
|
|
56 A>=B,
|
|
57 @O=[B], @Y=N, @X=X.
|
|
58
|
|
59 switch(T,PP,X,Zn,L) :- T=PP, @X=Zn.
|
|
60 switch(T,PP,X,Zn,L) :- T\=PP, @X=L.
|
|
61
|
|
62
|
|
63 append(Nil,L,L1) :- Nil=[],L=L1.
|
|
64 append(X,L,Y) :-[H|T]=X,[H1|M]=Y,
|
|
65 H=H1,append(T,L,M).
|
|
66
|