TITLE	"tree.a"
;		binary tree traversal"
	USE	"hawk.h"
	USE	"monitor.h"
	INT	MAIN
	S	MAIN

; errors discovered after the lecture
; 1) no null terminators on strings
; 2) a missing ALIGN 4 directive before the tree structure

; note:  this code could use lots of optimization!

NULL	=	0		; null pointer

; fields of one tree record
LEFT	=	0		; pointer to tree record
DATA	=	4		; pointer to a string
RIGHT	=	8		; pointer to tree record
RECSIZE	=	12		; size of a tree record

	SUBTITLE "main program"
; activation record
RETAD	=	0
ARSIZE	=	4

; code
MAIN:	STORE	R1,R2,RETAD	; -- boilerplate

	LEA	R3,ROOT		; -- parameter
	ADDI	R2,R2,ARSIZE
	JSR	R1,TRAVERSE	; traverse( root )
	ADDI	R2,R2,-ARSIZE

	LOAD	R1,R2,RETAD	; -- boilerplate
	JUMPS	R1		; return

	ALIGN	4
ROOT:	W	LEFTSON,ROOTDAT,RIGHTSON
LEFTSON:W	NULL,LEFTSONDAT,LEFTGRANDSON
LEFTGRANDSON:
	W	NULL,LEFTGRANDSONDAT,NULL
RIGHTSON:
	W	RIGHTGRANDSON,RIGHTSONDAT,NULL
RIGHTGRANDSON:
	W	NULL,RIGHTGRANDSONDAT,NULL

ROOTDAT:ASCII	"a ",0
LEFTSONDAT:
	ASCII	"This ",0
LEFTGRANDSONDAT:
	ASCII	"is ",0
RIGHTSONDAT:
	ASCII	"sentence.",0
RIGHTGRANDSONDAT:
	ASCII	"short ",0

	SUBTITLE "traverser"
	ALIGN	2
; activation record for traverser
RETAD	=	0
P	=	4	; pointer to a tree node
ARSIZE	=	8

; code for traverser
TRAVERSE:;	expects R3 = p, pointer to tree node
	STORE	R1,R2,RETAD	; -- boilerplate
	STORE	R3,R2,P		; -- save the parameter

	LOAD	R3,R2,P
	CMPI 	R3,NULL
	BEQ	TREND		; if (p != NULL) {

	LOAD	R3,R2,P
	LOAD	R3,R3,LEFT	;   -- parameter p->left
	ADDI	R2,R2,ARSIZE
	JSR	R1,TRAVERSE
	ADDI	R2,R2,-ARSIZE	;   traverse( p->left )

	LOAD	R3,R2,P
	LOAD	R3,R3,DATA	;   -- parameter p->data
	ADDI	R2,R2,ARSIZE
	LIL	R1,PUTS
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE	;   puts( p->data )

	LOAD	R3,R2,P
	LOAD	R3,R3,RIGHT	;   -- parameter p->right
	ADDI	R2,R2,ARSIZE
	JSR	R1,TRAVERSE
	ADDI	R2,R2,-ARSIZE	;   traverse( p->right )

TREND:				; }

	LOAD	R1,R2,RETAD	; -- boilerplate
	JUMPS	R1