TITLE	"mp4.a by Douglas Jones, Quicksort"
;               This code is based on solution 2 to Homework 8 problem 1
;               as a result, it uses almost no array indexing and
;               does lots of pointer arithmetic instead.

	USE	"hawk.h"
	USE	"stdio.h"
	USE	"string.h"
	USE	"/mnt/nfs/clasnetappvm/fs3/dwjones/2630mp4.h"

; Quicksort routine activation record
RETAD	=	0;
R8SV	=	4;
R9SV	=	8;
R10SV	=	12;
R11SV	=	16;
R12SV	=	20;
ARSIZE	=	24;

QSORT:				; void qsort( char * *l, char * *h) {
	; expects l in R3 	    -- l points to the low array element
	;         h in R4 	    -- h points to the high array element
	;			    -- array elements are pointers to strings
	; returns nothing	    -- on return, the array is sorted
	CMP	R3,R4
	BGE	QSQUIT		;   if (l < h) { -- there is work to do

	STORES	R1,R2
	STORE	R8,R2,R8SV
	STORE	R9,R2,R9SV
	STORE	R10,R2,R10SV
	STORE	R11,R2,R11SV
	STORE	R12,R2,R12SV
	ADDI	R2,R2,ARSIZE	;     -- deferred receiving sequence

	ADDI	R8,R3,-4	;     char * *low = l - 1
	ADDI	R9,R4,4		;     char * *high = h + 1
	LOADS	R10,R3		;     char * pivot = *l
			        ;     -- pivot could be any array element
	MOVE	R11,R3
	MOVE	R12,R4		;     -- save l and h 

QSPLOOP:			;     for (;;) { -- Hoare partition algorithm

QSLOWLP:			;       do { -- low started one below base
	ADDSI	R8,4		;         low = low + 1

	LOADS	R3,R8		;         -- parameter *low
	MOVE	R4,R10		;         -- parameter pivot
	LIL	R1,STRCMP
	JSRS	R1,R1
	TESTR	R3
	BLT	QSLOWLP		;       } while (strcmp( *low, pivot ) < 0);

QSHILP:				;       do { -- high started one above range
	ADDSI	R9,-4		;         high = high - 1

	LOADS	R3,R9		;         -- parameter *high
	MOVE	R4,R10		;         -- parameter pivot
	LIL	R1,STRCMP
	JSRS	R1,R1
	TESTR	R3
	BGT	QSHILP		;       } while (strcmp( *high, pivot ) > 0)

	CMP	R8,R9
	BGE	QSPQUIT		;       if (low >= high) break

	LOADS	R3,R8		;	char * temp1 = *low
	LOADS	R4,R9		;	char * temp2 = *high
	STORES	R4,R8		; 	*low = temp2
	STORES	R3,R9		; 	*high = temp1  -- swap done

	BR	QSPLOOP
QSPQUIT:			;     }
				;     -- assert low >= high
				;     -- high is return value from partition

	MOVE	R3,R11		;     -- parameter l
	MOVE	R4,R9		;     -- parameter high
	JSR	R1,QSORT	;     qsort( l, high );

	ADDI	R3,R9,4		;     -- parameter high + 1
	MOVE	R4,R12		;     -- parameter h
 	JSR	R1,QSORT	;     qsort( high + 1, h );

	ADDI	R2,R2,-ARSIZE	;     -- early return sequence
	LOAD	R12,R2,R12SV
	LOAD	R11,R2,R11SV
	LOAD	R10,R2,R10SV
	LOAD	R9,R2,R9SV
	LOAD	R8,R2,R8SV
	LOADS	R1,R2
QSQUIT:				;   }
	JUMPS	R1		; }

; Main program activation record
RETAD	=	0
ARSIZE	=	4

	INT	MAIN
	S	MAIN
MAIN:	STORES	R1,R2		; void main() {
	ADDSI	R2,ARSIZE

	LIL	R3,MP4DATA	;   -- parameter
	ADDI	R4,R3,(MP4SIZE-1)<<2
	JSR	R1,QSORT	;   qsort( mp4data, mp4data + mp4size - 1 )

	LIL	R8,MP4DATA	;   char ** p = mp4data  -- addr of first item
	LIS	R9,MP4SIZE	;   int i = mp4size
MAINLP:				;   loop {
	ADDSI	R9,-1		;     i = i - 1
	BLT	MAINQT		;     if (i < 0) break

	LOADS	R3,R8		;     -- get item from array
	LIL	R1,PUTS
	JSRS	R1,R1		;     puts( *p )

	ADDSI	R8,4		;     p = p + 1   -- addr of next item

	BR	MAINLP
MAINQT:				;   }
	ADDSI	R2,-ARSIZE
	LOADS	R1,R2
	JUMPS	R1              ; }