TITLE	"mp5.a by Douglas Jones, using an array"
	USE	"hawk.h"
	USE	"stdio.h"
	USE	"stdlib.h"
	USE	"string.h"

	EXT	MP5DATA		; the data we are to process

; SORT sorts an array of strings into increasing alphabetical order
; uses the simplest known sort, see https://arxiv.org/pdf/2110.01111.pdf

; activation record structure
;RETAD	=	0
R8SV	=	4
R9SV	=	8
R10SV	=	12
R11SV	=	16
R12SV	=	20
R13SV	=	24
ARSIZE	=	28

SORT:	; expects R3  = array	-- address of the array
	;         R4  = elements-- size of the array
	; returns nothing
	; uses    R8  = i	-- array index
	;         R9  = j	-- array index
	;         R10 = array (copy)
	;         R11 = elements (copy)
	;         R12 = &array[i]
	;         R13 = &array[j]
	STORES	R1,R2
	STORE	R8,R2,R8SV
	STORE	R9,R2,R9SV
	STORE	R10,R2,R10SV
	STORE	R11,R2,R11SV
	STORE	R12,R2,R12SV
	STORE	R13,R2,R13SV	; -- saving done
	ADDI	R2,R2,ARSIZE
	MOVE	R10,R3		; -- move array
	MOVE	R11,R4		; -- move elements

	LIS	R8,0		; i = 0
SRTLP1:				; for (;;) {
	CMP	R8,R11
	BGE	SRTLQ1		;   if (i >= elements) break;

	LIS	R9,0		;   j = 0
SRTLP2:				;   for (;;) {
	CMP	R9,R11
	BGE	SRTLQ2		;     if (j >= elements) break;

	MOVESL	R12,R8,2
	ADD	R12,R12,R10	;     -- &array[i] precomputed
	MOVESL	R13,R9,2
	ADD	R13,R13,R10	;     -- &array[j] precomputed

	LOADS	R3,R12		;     -- parameter array[i]
	LOADS	R4,R13		;     -- parameter array[j]
	LIL	R1,STRCMP
	JSRS	R1,R1		;     -- strcmp( array[i], array[j] )
	TESTR	R3
	BGE	ENDIF		;     if (strcmp( array[i], array[j] ) < 0) {

	LOADS	R3,R12		;       t = array[i]
	LOADS	R4,R13
	STORES	R4,R12		;       array[i] = array[j]
	STORES	R3,R13		;       array[j] = t

ENDIF:				;     }

	ADDSI	R9,1		;     j = j + 1;
	BR	SRTLP2
SRTLQ2:				;   }

	ADDSI	R8,1		;   i = i + 1;
	BR	SRTLP1
SRTLQ1:				; }
	ADDI	R2,R2,-ARSIZE
	LOAD	R13,R2,R13SV	; -- start restoring
	LOAD	R12,R2,R12SV
	LOAD	R11,R2,R11SV
	LOAD	R10,R2,R10SV
	LOAD	R9,R2,R9SV
	LOAD	R8,R2,R8SV
	LOADS	PC,R2		; return

; MAIN program to read and print mp5data
	INT	MAIN
	S	MAIN

; activation record structure
;RETAD	=	0
ARSIZE	=	4
MAIN:	; expects nothing
	; returns nothing
	; uses	R8  = p    -- used to scan MP5DATA
	;     	R9  = a    -- points to the array of strings
	;     	R10 = size -- size of the array (counts strings)
	;     	R11 = i    -- index into a
	STORES	PC,R2
	ADDSI	R2,ARSIZE

	LIL	R8,MP5DATA	; p = MP5DATA
	LIS	R10,0		; size = 0
MANLP1:				; for (;;) {
	LOADS	R3,R8
	EXTB	R3,R3,R8	;   -- test *p
	BEQ	MANLQ1		;   if (*p == '\0') break

	ADDSI	R10,1		;   size = size + 1;

        MOVE	R3,R8		;   -- parameter p
	LIL	R1,STRLEN
	JSRS	R1,R1		;   -- call strlen( p )
	ADD	R8,R8,R3
	ADDSI	R8,1		;   p = p + strlen( p ) + 1

	BR	MANLP1
MANLQ1:				; }

	MOVESL	R3,R10,2	; -- parameter size * sizeof( pointer )
	LIL	R1,MALLOC
	JSRS	R1,R1
	MOVE	R9,R3		; a = malloc( size * sizeof( pointer ) )

	LIL	R8,MP5DATA	; p = MP5DATA
	LIS	R11,0		; i = 0
MANLP2:				; for (;;) {
	CMP	R11,R10
	BGE	MANLQ2		;   if (i >= size) break;

	MOVESL	R3,R11,2
	ADD	R3,R3,R9	;   -- &a[i]
	STORES	R8,R3		;   a[i] = p
	
        MOVE	R3,R8		;   -- parameter p
	LIL	R1,STRLEN
	JSRS	R1,R1		;   -- call strlen( p )
	ADD	R8,R8,R3
	ADDSI	R8,1		;   p = p + strlen( p ) + 1

	ADDSI	R11,1		;   i = i + 1;
	BR	MANLP2
MANLQ2:				; }

	MOVE	R3,R9		; -- parameter a
	MOVE	R4,R10		; -- parameter size
	JSR	R1,SORT		; sort( a, size )

	LIS	R11,0		; i = 0
MANLP3:				; for (;;) {
	CMP	R11,R10
	BGE	MANLQ3		;   if (i >= size) break;

	MOVESL	R3,R11,2
	ADD	R3,R3,R9	;   -- &a[i]
	LOADS	R3,R3		;   -- parameter a[i]
	LIL	R1,PUTSTR
	JSRS	R1,R1		;   putstr( a[i] )

	ADDSI	R11,1		;   i = i + 1;
	BR	MANLP3
MANLQ3:				; }

	ADDSI	R2,-ARSIZE
	LOADS	PC,R2		; return

	END