COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	a program to sort the ONHAND.DSK file, in lexicographic order
C00011 ENDMK
C⊗;
comment a program to sort the ONHAND.DSK file, in lexicographic order
	according to report number;
comment the program uses a simple implementation of the QUICKSORT algorithm
	(Knuth, vol III, pp 116-125);
begin "quicksort"

   require "⊂⊃" delimiters;
   define crlf=⊂'15&'12⊃, til=⊂step 1 until⊃, ff=⊂('14)⊃, bsize=⊂1000⊃, lf=⊂('12)⊃, M=⊂16⊃;

   integer i,j,L,R,K,P,stack_ptr, inchan, outchan, brchar, eof, flag, n;
   comment i and j are temporary vars, L and R are the bounds of the subset that
      we are currently sorting, P is the `middle value', which corresponds to
      the permutation value of the division between the two sets;
   integer tempint, type;
   integer bfflf, babs;
   integer array key, permute[0:bsize+1];
   comment key is the number of the report (used for sorting), permute is used
      to record eventual changes in the order of the file;

   string infile, outfile, st, temp;

   label new_step, high, low, insert_sort, finish;

   string array title[1:bsize];
   integer array stack[1:20];

   procedure push (value integer val);
	if stack_ptr>20 then print("stack overflow",crlf)
	else begin stack[stack_ptr]←val; stack_ptr←stack_ptr+1; end;

   procedure pop (reference integer val);
   begin "pop"
	stack_ptr←stack_ptr-1;
	if stack_ptr < 1 then print("stack underflow",crlf)
	else val←stack[stack_ptr]; end "pop";
	
   setbreak(bfflf←getbreak,ff&lf,null,"IA");
   setbreak(babs←getbreak,"|",null,"IS");

   comment first, read in the file of titles, and initialize the appte arrays;
   open(inchan←getchan,"DSK",0,2,0,450,brchar,eof);
   open(outchan←getchan,"DSK",0,0,2,0,0,eof);
   stack_ptr←1;

   for i←1 til bsize do permute[i]←i;
   do begin 
	print("input file?"); infile←inchwl; lookup(inchan,infile,flag)
   end until ¬flag;
   do begin
	print("output file?"); outfile←inchwl; enter(outchan,outfile,flag)
   end until ¬flag;

   i←1;
   while true do begin
	do temp ← st←input(inchan,bfflf) until lop(st)="*" or eof;
	if eof then done;
	comment type is used to group the reports according to project;
 	type ← if st="A" then 0 else if st="C" then 2000 else 4000;
	key[i] ← intscan(st,brchar) + type;
	if equ(st[2 to 5],"SAME") then title[i-1]←title[i-1]&temp
	else begin title[i]←temp; i←i+1; end;
   end;
   n ← i-1;
   print("number of reports=",n,crlf);

   comment use dummy keys K[0]=-∞, K[n+1]←+∞;
   key[0]←-1;  key[n+1]←10000;
  
   L←1; R←N;
   
   comment when we have decided which subset to sort, and set L and R, we start here;
new_step: if R-L < M then goto insert_sort;

   i←L;  j←R;  K←key[permute[L]];  P←permute[L];
   comment P will be the record at the division between the sets;
   
high: while key[permute[j]]>K do j←j-1;

   if j ≤ i then begin
      permute[i]←P; goto finish; end;
   comment exchange the two records, and continue, coming up from the low end;
   permute[i] ← permute[j];
   i←i+1;

low: while key[permute[i]]<K do i←i+1;

   if j ≤ i then begin permute[j]←P; i←j; end
   else begin permute[j]←permute[i]; j←j-1; goto high; end;
   comment exchange, and come from the high end;

finish:
   comment we've partitioned the subfile from L to R into three parts.
   	Push the largest onto the stack, for later sorting, and sort the
	smaller one;
   if R=i then R←i-1 else if L=i then L←i+1 else
   if R-i > i-L then begin
      push(i+1); push(R); R←i-1;
   end else begin
      push(L); push (i-1); L←i+1; 
   end;

goto new_step;

insert_sort:
comment when the subset we're sorting gets small enough (arbitrarily set at 16),
	we come here, and finish with a simple insertion sort;
   for j←L+1 til R do begin
      K←key[permute[j]]; P←permute[j]; i←j-1;
      while key[permute[i]]>K ∧ i≥L do begin
	 permute[i+1]←permute[i]; i←i-1; end;
      permute[i+1]←P;
   end;

comment now pop the stack, to get one of the pairs that we have previously stored;
if stack_ptr > 1 then begin
   pop(R); pop(L); goto new_step;
end;

comment the keys and permutations are now sorted. Now print out the list,
	in sorted order;
for i←1 til n do begin
	out(outchan,title[permute[i]]);
	if i mod 55 = 54 then out(outchan,ff);
end;

close(outchan);
end "quicksort";