home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.barnyard.co.uk
/
2015.02.ftp.barnyard.co.uk.tar
/
ftp.barnyard.co.uk
/
cpm
/
walnut-creek-CDROM
/
CPM
/
LANGUAGS
/
MODULA2
/
MERGESOR.MOD
< prev
next >
Wrap
Text File
|
2000-06-30
|
4KB
|
159 lines
(* Natural merge sort with 3 files and 2 phases. *)
MODULE mergesort;
FROM InOut IMPORT Write,WriteCard,WriteString,WriteInt,
WriteLn,ReadInt,Read;
FROM FileNames IMPORT ReadFileName;
FROM FileSystem IMPORT File,Response,Close,Create,ReadWord,
WriteWord,SetPos,GetPos,Reset,SetRead,SetWrite;
FROM ByteBlockIO IMPORT WriteByteBlock,ReadByteBlock;
TYPE item = RECORD
key : INTEGER
END;
VAR f,a,b,c : File;
n,buf: item;
FileA,FileB,FileC : ARRAY [0..10] OF CHAR;
high1,low1,high2,low2 : CARDINAL;
ch : CHAR;
PROCEDURE list(VAR f: File);
VAR x: item;
BEGIN
Reset(f);
LOOP
ReadByteBlock(f,x);
IF f.eof THEN EXIT END;
WriteInt(x.key,4);
WriteString(' ');
END;
WriteLn
END list;
PROCEDURE naturalmerge;
VAR l: INTEGER; (*no. of runs merged*)
eor: BOOLEAN; (*end-of-run indicator*)
PROCEDURE copy(VAR x,y: File);
VAR buf,next: item;
high,low : CARDINAL;
BEGIN
ReadByteBlock(x, buf);
IF x.eof THEN
eor:= TRUE
ELSE
WriteByteBlock(y,buf);
GetPos(x,high,low);
ReadByteBlock(x,next);
SetPos(x,high,low);
eor:= buf.key > next.key;
END
END copy;
PROCEDURE copyrun(VAR x,y: File);
BEGIN (*copy one run from x to y*)
REPEAT copy(x,y) UNTIL eor
END copyrun;
PROCEDURE distribute;
BEGIN (*from c to a & b*)
REPEAT
copyrun (c,a);
IF NOT c.eof THEN copyrun(c,b) END;
UNTIL c.eof;
END distribute;
PROCEDURE mergerun;
VAR nexta,nextb : item;
BEGIN (*from a and b to c*)
REPEAT
GetPos(a,high1,low1);
ReadByteBlock(a,nexta);
SetPos(a,high1,low1);
GetPos(b,high2,low2);
ReadByteBlock(b,nextb);
SetPos(b,high2,low2);
IF nexta.key < nextb.key THEN
copy(a,c);
IF eor THEN copyrun(b,c) END
ELSE
copy(b,c);
IF eor THEN copyrun (a,c) END
END
UNTIL eor
END mergerun;
PROCEDURE merge;
VAR dummy: item;
high,low: CARDINAL;
teof: BOOLEAN;
BEGIN (*from a and b to c*)
REPEAT mergerun; INC(l)
UNTIL a.eof OR b.eof;
GetPos(a,high,low);
ReadByteBlock(a,dummy);
teof := a.eof;
SetPos(a,high,low);
WHILE NOT teof DO
copyrun(a,c);
INC(l);
teof := a.eof
END ;
GetPos(b,high,low);
ReadByteBlock(b,dummy);
teof := b.eof;
SetPos(b,high,low);
WHILE NOT teof DO
copyrun (b,c);
INC(l);
teof := b.eof
END;
list(c)
END merge;
BEGIN (*naturalmerge*)
REPEAT
WriteLn; WriteString('In Loop:');
Close(a);
Create(a,'DK.');
Close(b);
Create(b,'DK.');
Reset(c);
distribute;
Reset(a);
Reset(b);
Reset(c);
l := 0;
merge;
UNTIL l = 1
END naturalmerge;
BEGIN (*main program. read input sequence ending with 0*)
Create(a,'DK.');
IF a.res # done THEN WriteString('FileA not opened.') END;
Create(b,'DK.');
IF b.res # done THEN WriteString('FileB not opened.') END;
Create(c,'DK.');
IF c.res # done THEN WriteString('FileC not opened.') END;
WriteString('Type in an Integer, exit by typing a 0 -> ');
ReadInt(buf.key);
WriteLn;
REPEAT
WriteByteBlock(c,buf);
WriteString('Type in an Integer, exit by typing a 0 -> ');
ReadInt(buf.key);
WriteLn
UNTIL buf.key = 0;
list(c);
WriteString('Before naturalmerge'); WriteLn;
naturalmerge;
WriteString('After naturalmerge'); WriteLn;
list(c);
Close(a);
Close(b);
Close(c);
END mergesort .