// 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
]