TITLE	"MP3 by Douglas Jones"
;	a function to traverse a binary tree concatenate the strings in it.
;	this version is based on the first posted solution to Homework 6.
;	this version makes no attempt to free unused space on the heap.
;	this version is minimally optimized.

	USE	"hawk.h"
	USE	"stdio.h"
	USE	"string.h"
	USE	"stdlib.h"

; activation record for TRAVERS
;RETAD	=	0
P	=	4	; points to a tree node
LSTR	=	8	; left_string of P
RSTR	=	12	; right_string of P
LEN	=	16	; total length of the strings
ARSIZE	=	20

TRAVERS:; expects R3 = p, pointer to the root
	; returns nothing	; void travers( node * p ) {
	STORES	R1,R2

	TESTR	R3
	BZS	TRAVEL		;   if (p != NULL) {

	STORE	R3,R2,P		;     -- move p

	LOAD	R3,R3,LEFT	;     -- param
	ADDI	R2,R2,ARSIZE
	JSR	R1,TRAVERS	;     left_string = travers( p->left )
	ADDI	R2,R2,-ARSIZE
	STORE	R3,R2,LSTR
				;     -- param already in R3
	LIL	R1,STRLEN
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE
	STORE	R3,R2,LEN	;     length = strlen( left_string )

	LOAD	R3,R2,P
	LOAD	R3,R3,RIGHT	;     -- param
	ADDI	R2,R2,ARSIZE
	JSR	R1,TRAVERS	;     right_string = travers( p->right )
	ADDI	R2,R2,-ARSIZE
	STORE	R3,R2,RSTR
				;     -- param already in R3
	LIL	R1,STRLEN
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE
	LOAD	R4,R2,LEN
	ADD	R4,R4,R3	;     length = length + strlen( right_string )
	STORE	R4,R2,LEN

	LOAD	R3,R2,P
	LOAD	R3,R3,DATA	;     -- param
	LIL	R1,STRLEN
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE
	LOAD	R4,R2,LEN
	ADD	R3,R4,R3	;     length = length + strlen( p->data )
	ADDSI	R3,1		;     length = length + 1 -- allow for '\0'
	
				;     -- param already in R3
	LIL	R1,MALLOC
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1		;     buf = malloc( length )
	ADDI	R2,R2,-ARSIZE

	LOAD	R4,R2,LSTR
	LIL	R1,STRCPY
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1		;     buf = strcpy( buf, left_string )
	ADDI	R2,R2,-ARSIZE

	LOAD	R4,R2,P
	LOAD	R4,R4,DATA	;     -- param
	LIL	R1,STRCAT
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1		;     buf = strcat( buf, p->data )
	ADDI	R2,R2,-ARSIZE
	
	LOAD	R4,R2,RSTR
	LIL	R1,STRCAT
	ADDI	R2,R2,ARSIZE
	JSRS	R1,R1		;     buf = strcat( buf, right_string )
	ADDI	R2,R2,-ARSIZE

	BR	TRAVQT
TRAVEL:				;   } else { -- empty tree

	LEA	R3,EMPTY	;     buf = ""

TRAVQT:				;   } -- end of if
	LOADS	R1,R2		;     -- early partial return sequence
	JUMPS	R1		;   return buf
				; } -- end of travers
EMPTY:	ASCII	"",0

; the assignment said to put the following at the very end
	USE	"/mnt/nfs/clasnetappvm/fs3/dwjones/2630mp3.h"

	END