// S C V S O R T -- SCAN CONVERTER (PREPRESS) // catalog number ??? // Copyright Xerox Corporation 1979 // Sort routine for scan conversion get "scv.dfs" // outgoing procedures external [ QuickSort ] // outgoing statics //external // [ // ] //static // [ // ] // incoming procedures //external // [ // ] // incoming statics //external // [ // ] // internal statics //static // [ // ] // File-wide structure and manifest declarations. // Procedures let //QuickSort: sort an array of double words. Knuth v.3 p. 116. // Comparison test is: first word first, then second word // (This is like a two-character key, not like a double-precision // number.) // b=> the array. // n=number of elements to sort (not counting guards). n<32000 // (i.e. first element is in b!2 and b!3, last in b!(2n) and b!(2n+1) //Comment about buffer layout internally. // 2 words - infinity // 2n words intersections // 2 words + infinity QuickSort(b,n) be [ let n2=n lshift 1 let b1=b+1 b!0=minusinfinity //Negative guard b!(n2+2)=plusinfinity //Positive guard let stack=vec 20; let stack1=vec 20 let stptr=0 //Quicksort stack. let l=2 //Q1 let r=n2 //set left,right let i,j,k,k1=nil,nil,nil,nil [ //Q2 test r-l gr 20 then [ i=l; j=r k=b!l; k1=b1!l [ //Q3 while k ls b!j % (k eq b!j & k1 ls b1!j) do j=j-2 if j le i then [ b!i=k; b1!i=k1; break ] //Q4 b!i=b!j; b1!i=b1!j; i=i+2 while b!i ls k % //Q5 (b!i eq k & b1!i ls k1) do i=i+2 if j le i then [ b!j=k; b1!j=k1; i=j; break ] //Q6 b!j=b!i; b1!j=b1!i; j=j-2 ] repeat test r-i ge i-l then //Q7 [ stack!stptr=i+2; stack1!stptr=r; r=i-2 ] or [ stack!stptr=l; stack1!stptr=i-2; l=i+2 ] stptr=stptr+1 ] or [ //Q8 for j=l+2 to r by 2 do [ k=b!j; k1=b1!j; i=j-2 while b!i gr k % (b!i eq k & b1!i gr k1) do [ let i2=i+2 b!i2=b!i b1!i2=b1!i i=i-2 ] let i2=i+2 b!i2=k; b1!i2=k1 ] if stptr eq 0 then break //Q9 stptr=stptr-1 l=stack!stptr; r=stack1!stptr ] ] repeat ]