20060303a

1 files changed, 129 insertions, 0 deletions

diff --git a/appl/cmd/sort.b b/appl/cmd/sort.b
new file mode 100644
index 00000000..1accd583
--- /dev/null
+++ b/appl/cmd/sort.b
@@ -0,0 +1,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];
+	}
+}