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