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

	EXT	MP5DATA		; the data we are to process

	SUBTITLE "Lexicographically ordered binary tree of strings"

; layout of tree nodes, one node per string
LEFT	=	0		; pointer to left subtree
RIGHT	=	4		; pointer to right subtree
STR	=	8		; pointer to string
NODESIZE=	12

	COMMON	TREE,4		; pointer to root of tree
LCSAVE	=	.
.	=	TREE
	W	NULL		; initially NULL
.	=	LCSAVE

; PUTTREE sorts the string s into the tree of strings
; activation record
;RETAD	=	0
R8SV	=	4
R9SV	=	8
R10SV	=	12
ARSIZE	=	16
PUTTREE:; expects R3  = s -- pointer to the new string
	; uses	  R8  = s
	;         R9  = n -- pointer to the new node
	;         R10 = t -- pointer used to traverse tree
	STORES	R1,R2
	STORE	R8,R2,R8SV
	STORE	R9,R2,R9SV
	STORE	R10,R2,R10SV
	ADDI	R2,R2,ARSIZE	; -- optimized AR fiddling
	MOVE	R8,R3

	LIS	R3,NODESIZE	; -- parameter
	LIL	R1,MALLOC
	JSRS	R1,R1		; n = malloc( nodesize )
				; initialize new tree node
	STORE	R0,R3,LEFT	; n->left = NULL
	STORE	R0,R3,RIGHT	; n->right = NULL
	STORE	R8,R3,STR	; n->str = s

	LIL	R5,TREE		; -- global variable reference
	LOADSCC	R10,R5		; t = tree
	BZR	PUTELS		; if (t == NULL) { -- create tree

	STORES	R3,R5		;   tree = n;
	BR	PUTEIF
PUTELS:				; } else { -- walk down tree looking for place
	MOVE	R9,R3		;   -- move where n is
PUTLP:				;   for (;;) { -- loop exit by break

	MOVE	R3,R8		;     -- parameter s
	LOAD	R4,R10,STR	;     -- parameter t->str
	LIL	R1,STRCMP
	JSRS	R1,R1		;     order = strcmp( s, t->str )
	
	TESTR	R3
	BLT	PUTELS2		;     if (order >= 0) { -- right subtree

	LOADCC	R3,R10,RIGHT	;       tright = t->right
	BZR	PUTEIF3		;       if (tright == NULL) { -- found place

	STORE	R9,R10,RIGHT	;         t->right = n;
	BR	PUTLPQ		;         break;

PUTEIF3:			;       }
	MOVE	R10,R3		;       t = tright -- walk down tree branch
	BR	PUTLP		;       -- optimized to avoid BR to PUTEIF2;

PUTELS2:			;     } else { -- left subtree
	LOADCC	R3,R10,LEFT	;       tleft = t->left
	BZR	PUTEIF4		;       if (tleft == NULL) { -- found place

	STORE	R9,R10,LEFT	;         t->left = n;
	BR	PUTLPQ		;         break;

PUTEIF4:			;       }
	MOVE	R10,R3		;       t = tleft -- walk down tree branch
;PUTEIF2:			;     }
	BR	PUTLP
PUTLPQ:				;   } -- end loop walking down tree
PUTEIF:                         ; } -- end outer if statement
	ADDI	R2,R2,-ARSIZE	; -- optimized AR fiddling
	LOAD	R10,R2,R10SV
	LOAD	R9,R2,R9SV
	LOAD	R8,R2,R8SV
	LOADS	PC,R2		; return nothing

; PRINTTREE traverses the tree recursively and prints the strings
; activation record
;RETAD	=	0
R8SV	=	4
ARSIZE	=	8
PRINTTREE:
	; expects R3  = t -- pointer to the new string
	; uses	  R8  = t
	STORES	R1,R2
	STORE	R8,R2,R8SV
	MOVE	R8,R3
	ADDSI	R2,ARSIZE	; -- optimized AR fiddling

	LOADCC	R3,R8,LEFT	; tleft = t->left
	BZS	PRTELS1		; if (tleft != NULL) {
				;   -- parameter already there
	JSR	R1,PRINTTREE	;   printtree( tleft );
PRTELS1:			; }

	LOAD	R3,R8,STR	; -- parameter t->str
	LIL	R1,PUTSTR
	JSRS	R1,R1		; putstr( t->str )

	LOADCC	R3,R8,RIGHT	; tright = t->right
	BZS	PRTELS2		; if (tright != NULL) {
				;   -- parameter already there
	JSR	R1,PRINTTREE	;   printtree( tright );
PRTELS2:			; }

	ADDSI	R2,-ARSIZE	; -- optimized AR fiddling
	LOAD	R8,R2,R8SV
	LOADS	PC,R2

	SUBTITLE "main program to sort and print MP5DATA"
	S	MAIN
	INT	MAIN

; activation record structure
;RETAD	=	0
ARSIZE	=	4

MAIN:	; uses    R8 = p    -- pointer into mp5data
	; 	  R9 = plen -- strlen( p )
	STORES	R1,R2
	ADDSI	R2,ARSIZE	; -- optimized AR fiddling

	LIL	R8,MP5DATA	; p = mp5data
MAINLP:				; for (;;) { -- loop exit by break

	MOVE	R3,R8		;   -- parameter
	LIL	R1,STRLEN
	JSRS	R1,R1		;   plen = strlen( p )
	MOVECC	R9,R3		;   -- set aside plen
        BZS	MAINLX		;   if (plen == 0) break

	MOVE	R3,R8		;   -- parameter
	JSR	R1,PUTTREE	;   puttree( p );

	ADD	R8,R8,R9	;   -- advance to next "word"
	ADDSI	R8,1		;   p = p + plen + 1;

	BR	MAINLP
MAINLX:				; }

	LIL	R3,TREE
	LOADS	R3,R3		; -- parameter tree
	JSR	R1,PRINTTREE	; printtree( tree )

	ADDSI	R2,-ARSIZE	; -- optimized AR fiddling
	LOADS	PC,R2		; return nothing

	END