1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
implement Sort;
include "sys.m";
sys: Sys;
include "bufio.m";
include "draw.m";
include "arg.m";
Sort: module
{
init: fn(nil: ref Draw->Context, args: list of string);
};
usage()
{
sys->fprint(sys->fildes(2), "usage: sort [-n] [file]\n");
raise "fail:usage";
}
Incr: con 2000; # growth quantum for record array
init(nil : ref Draw->Context, args : list of string)
{
bio : ref Bufio->Iobuf;
sys = load Sys Sys->PATH;
stderr := sys->fildes(2);
bufio := load Bufio Bufio->PATH;
if (bufio == nil) {
sys->fprint(stderr, "sort: cannot load %s: %r\n", Bufio->PATH);
raise "fail:bad module";
}
Iobuf: import bufio;
arg := load Arg Arg->PATH;
if (arg == nil) {
sys->fprint(stderr, "sort: cannot load %s: %r\n", Arg->PATH);
raise "fail:bad module";
}
nflag := 0;
rflag := 0;
arg->init(args);
while ((opt := arg->opt()) != 0) {
case opt {
'n' =>
nflag = 1;
'r' =>
rflag = 1;
* =>
usage();
}
}
args = arg->argv();
if (len args > 1)
usage();
if (args != nil) {
bio = bufio->open(hd args, Bufio->OREAD);
if (bio == nil) {
sys->fprint(stderr, "sort: cannot open %s: %r\n", hd args);
raise "fail:open file";
}
}
else
bio = bufio->fopen(sys->fildes(0), Bufio->OREAD);
a := array[Incr] of string;
n := 0;
while ((s := bio.gets('\n')) != nil) {
if (n >= len a) {
b := array[len a + Incr] of string;
b[0:] = a;
a = b;
}
a[n++] = s;
}
if (nflag)
mergesortnumeric(a, array[n] of string, n);
else
mergesort(a, array[n] of string, n);
stdout := bufio->fopen(sys->fildes(1), Bufio->OWRITE);
if (rflag) {
for (i := n-1; i >= 0; i--)
stdout.puts(a[i]);
} else {
for (i := 0; i < n; i++)
stdout.puts(a[i]);
}
stdout.close();
}
mergesort(a, b: array of string, r: int)
{
if (r > 1) {
m := (r-1)/2 + 1;
mergesort(a[0:m], b[0:m], m);
mergesort(a[m:r], b[m:r], r-m);
b[0:] = a[0:r];
for ((i, j, k) := (0, m, 0); i < m && j < r; k++) {
if (b[i] > b[j])
a[k] = b[j++];
else
a[k] = b[i++];
}
if (i < m)
a[k:] = b[i:m];
else if (j < r)
a[k:] = b[j:r];
}
}
mergesortnumeric(a, b: array of string, r: int)
{
if (r > 1) {
m := (r-1)/2 + 1;
mergesortnumeric(a[0:m], b[0:m], m);
mergesortnumeric(a[m:r], b[m:r], r-m);
b[0:] = a[0:r];
for ((i, j, k) := (0, m, 0); i < m && j < r; k++) {
if (int b[i] > int b[j])
a[k] = b[j++];
else
a[k] = b[i++];
}
if (i < m)
a[k:] = b[i:m];
else if (j < r)
a[k:] = b[j:r];
}
}
|
