TITLE	"mp4.a -- output an H-tree to the screen"

; This code is written by direct translation from the C solution mp4.c
; except that it plots directly on the screen instead of using an array.

; This program is not the simplest possible program to do this because the
; assignment explicitly said that the calling sequence was haich(x,y,n)
; where n is the order.  A simpler formulation would have haich(x,y,n,w,h)
; where w and h are the width and height of the tree, respectively.

	USE	"hawk.macs"
	USE	"monitor.h"
	EXT	UNUSED
	S	START

	SUBTITLE "The actual code for plotting H-trees"

; Activation record structure used by EVENH and ODDH
;RETAD	=	0
X	=	4	; x coord of tree center
Y	=	8	; y coord of tree center
O	=	12	; order of tree
W	=	16	; width of tree, in characters
H	=	20	; height of tree, in characters
OFFSET	=	24	; offset of half-tree from center
ARSIZE	=	28

; variable reuse in activation where previous value is no longer needed
NEWH	=	H	; new value of H for recursive calls
NEWW	=	W	; new value of W for recursive calls
I	=	O	; loop counter
ENDVAL	=	H	; loop counter terminal value

; ---------------------------------

EVENH:	; Plot an even order H

	; on entry
	; R3 = x
	; R4 = y
	; R5 = o
	; R6 = w
	; R7 = h

	TESTR	R5
	BLE	EVENHX		; if (o > 0) { /* side by side case */

	STORES	R1,R2		;   -- save parameters except W
	STORE	R3,R2,X
	STORE	R4,R2,Y
	STORE	R5,R2,O
	STORE	R7,R2,H

	ADDSI	R6,-3
	SR	R6,1
	STORE	R6,R2,NEWW	;   neww = (w - 3)/2

	MOVE	R1,R6
	ADDSI	R1,3
	SR	R1,1
	STORE	R1,R2,OFFSET	;   offset = (neww + 3)/2

	SUB	R3,R3,R1	;   -- fix x parameter
	ADDSI	R5,-1		;   -- fix o parameter
	ADDI	R2,R2,ARSIZE
	JSR	R1,ODDH		;   oddh( x - offset, y, o - 1, neww, h );
	ADDI	R2,R2,-ARSIZE

	LOAD	R3,R2,X
	LOAD	R4,R2,Y
	LOAD	R5,R2,O
	LOAD	R6,R2,NEWW
	LOAD	R7,R2,H
	LOAD	R1,R2,OFFSET

	ADD	R3,R3,R1	;   -- fix x parameter
	ADDSI	R5,-1		;   -- fix o parameter
	ADDI	R2,R2,ARSIZE
	JSR	R1,ODDH		;   oddh( x + offset, y, o - 1, neww, h );
	ADDI	R2,R2,-ARSIZE

	LOAD	R3,R2,X
	LOAD	R1,R2,OFFSET
	SUB	R3,R3,R1
	ADDSI	R3,1		;   -- compute (x - offset) + 1
	LOAD	R4,R2,Y
	ADDI	R2,R2,ARSIZE
	LIL	R1,DSPAT	;   dspat( (x - offset) + 1, y )
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE

	; original -- for (i = (x - offset) + 1; i < (x + offset); i++) {
	; new      -- for (i = 2*offset - 1; i > 0; i--) {

	LOAD	R1,R2,OFFSET
	SL	R1,1
	ADDSI	R1,-1		;   i = 2*offset - 1
EVENHL:				;   do {
	STORE	R1,R2,I
	LIS	R3,'_'
	ADDI	R2,R2,ARSIZE
	LIL	R1,DSPCH	;     dspch( '_' )
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE
	LOAD	R1,R2,I
	ADDSI	R1,-1		;     i--
	BGT	EVENHL		;   } while (i > 0)

	LOADS	R1,R2
EVENHX:				; }
	JUMPS	R1		; return

; ---------------------------------

ODDH:	; Plot an odd order H

	; on entry
	; R3 = X
	; R4 = Y
	; R5 = O
	; R6 = W
	; R7 = H

	TESTR	R5
	BLE	ODDHX		; if (o > 0) { /* top to bottom case */

	STORES	R1,R2		;   -- save parameters except H
	STORE	R3,R2,X
	STORE	R4,R2,Y
	STORE	R5,R2,O
	STORE	R6,R2,W

	ADDSI	R7,-2
	SR	R7,1
	STORE	R7,R2,NEWH	;   newh = (h - 2)/2

	MOVE	R1,R7
	ADDSI	R1,2
	SR	R1,1
	STORE	R1,R2,OFFSET	;   offset = (newh + 2)/2

	SUB	R4,R4,R1	;   -- fix y parameter
	ADDSI	R5,-1		;   -- fix o parameter
	ADDI	R2,R2,ARSIZE
	JSR	R1,EVENH	;   evenh( x , y - offset, o - 1, w, newh );
	ADDI	R2,R2,-ARSIZE

	LOAD	R3,R2,X
	LOAD	R4,R2,Y
	LOAD	R5,R2,O
	LOAD	R6,R2,W
	LOAD	R7,R2,NEWH
	LOAD	R1,R2,OFFSET

	ADD	R4,R4,R1	;   -- fix y parameter
	ADDSI	R5,-1		;   -- fix o parameter
	ADDI	R2,R2,ARSIZE
	JSR	R1,EVENH	;   evenh( x, y + offset, o - 1, w, newh );
	ADDI	R2,R2,-ARSIZE

	LOAD	R4,R2,Y
	LOAD	R1,R2,OFFSET
	ADD	R5,R4,R1
	ADDSI	R5,1
	STORE	R5,R2,ENDVAL	;   endval = y + offset + 1

	SUB	R4,R4,R1
	ADDSI	R4,1		;   i = (y - offset) + 1
ODDHL:				;   do {
	STORE	R4,R2,I
	LOAD	R3,R2,X
	ADDI	R2,R2,ARSIZE
	LIL	R1,DSPAT	;     dspat( x, i )
	JSRS	R1,R1
	LIS	R3,'|'
	LIL	R1,DSPCH	;     dspch( '|' )
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE

	LOAD	R4,R2,I
	ADDSI	R4,1		;     i++
	LOAD	R1,R2,ENDVAL
	CMP	R4,R1
	BLT	ODDHL		;   } while (i < endval)

	LOADS	R1,R2
ODDHX:				; }
	JUMPS	R1		; return

	SUBTITLE "The required interface"

;RETAD	=	0
ARSIZE	=	4

HAICH:	; Plot an order o H-tree at x,y

	; on entry
	; R3 = x -- carefully preserved until call to evenh or oddh
	; R4 = y -- ditto
	; R5 = o -- ditto

	TESTR	R5
	BLE	HAICHX		; if (o > 0) { /* nontrivial case */

	STORES	R1,R2		;   -- save return address
        			;   -- compute what size H-tree
	LIS	R6,1		;   w = 1;
	LIS	R7,0		;   h = 0;
	MOVE	R1,R5		;   i = o

HAICHL:				;   do {
	BITTST	R1,0
	BCR	HAICHE1		;     if (i & 1) { -- i is odd
	SL	R7,1
	ADDSI	R7,2		;        h = 2*h + 2
	BR	HAICHX1
HAICHE1:			;     } else { -- i is even
	SL	R6,1
	ADDSI	R6,3		;        w = 2*w + 3
HAICHX1:			;     }
	ADDSI	R1,-1		;     i--;
	BGT	HAICHL		;   } while (i > 0)

	BITTST	R5,0
	BCR	HAICHE2		;   if (o & 1) { -- o is odd
	ADDI	R2,R2,ARSIZE
	JSR	R1,ODDH		;     oddh( x, y, o, w, h );
	ADDI	R2,R2,-ARSIZE
	BR	HAICHX2
HAICHE2:			;   } else { -- o is even
	ADDI	R2,R2,ARSIZE
	JSR	R1,EVENH	;     evenh( x, y, o, w, h );
	ADDI	R2,R2,-ARSIZE
HAICHX2:			;   }
	
	LOADS	R1,R2
HAICHX:				; }
	JUMPS	R1		; return

	SUBTITLE "Main program"

START:	LIL	R2,UNUSED
	LIL	R1,DSPINI
	JSRS	R1,R1		; w,h = dspini()

				; figure size of h-tree to display
	LIS	R6,1		; x = 1;
	LIS	R7,0		; y = 0;
	LIS	R5,0		; o = 0;
FIGLP:				; for (;;) {
	BITTST	R5,0
	BCR	FIGEL		;   if (o & 1) { -- if o-1 is odd
	SL	R6,1
	ADDSI	R6,3		;     x = 2*x + 3;
	BR	FIGEI
FIGEL:				;   } else { -- if o-1 is even
	SL	R7,1
	ADDSI	R7,2		;     y = 2*y + 2;
FIGEI:				;   }
	CMP	R6,R3
	BGE	FIGQ		;   if (x >= w) break
	CMP	R7,R4
	BGE	FIGQ		;   if (y >= h) break
	ADDSI	R5,1		;   o = o + 1;
	BR	FIGLP
FIGQ:				; }

	SR	R3,1		; draw the h-tree centered on the screen
	SR	R4,1
	JSR	R1,HAICH	; haich( w/2, h/2, o )

	LIL	R1,EXIT
	JSRS	R1,R1		; exit()

	END