;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;

; Course:     COMP 2280, Section A01

; Instructor: Randy Cooper

; Assignment: 4, Question 5

; Author:     Mickeal Nevakshonoff
 7712495
; Version:    
1
;

; Purpose:    Traverse a tree, printing the elements in prefix, infix, and postfix order
;

; Register Dictionary
; -------------------

; R2-Current Node
; R1-Zero testing
; R6-Stack Pointer
; R5-Frame Pointer
; R0- I/O work

 .orig   x3000         ; standard starting address for an LC3 program
           


	ld r6,stackbase
	ld r2,root
	lea r0,prefixMsg
	puts
	jsr prefix

	ld r6,stackbase
	ld r2,root
	lea r0,infixMsg
	puts
	jsr infix

	ld r6,stackbase
	ld r2,root
	lea r0,postfixMsg
	puts
	jsr postfix

	lea R0,eopMsg
	puts
	halt


prefix

;---Activation Record---
;R5+0 = R5 Backup
;R5+1 = R7 Backup

	add	r6,r6,#-1	;Save the callers registers
	str	r5,r6,#0	;Save R5
	add	r6,r6,#-1
	str	r7,r6,#0	;Back up R7
	add	r5,r6,#1	;Establish frame pointer


	ldr 	r0,r2,#1	;Load nodes value to print
	trap	x21


;PROCESS LEFT TREE
	ldr	r1,r2,#0
	brz	preFixExit
	add	r6,r6,#-1	;Backing up current node to stack, and processing left tree
	str	r2,r6,#0
	ldr	r2,r2,#0	;Get the left tree loaded into R2
	jsr	prefix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1

;PROCESS RIGHT TREE
	ldr 	r1,r2,#2	;Access right tree to check if zero
	brz	preFixExit
	add	r6,r6,#-1	;Backing up
	str	r2,r6,#0	;Pushing to stack
	ldr	r2,r2,#2	;Get the right tree loaded into R2
	jsr	prefix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1



preFixExit
	ldr	r7,r6,#0	;Restore register 7
	add	r6,r6,#1
	ldr	r5,r6,#0	;Restore register 5 (old frame pointer)
	add	r6,r6,#1	;R6 should now point to the previous node, which is at the top of the stack
	ret

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


infix
	add	r6,r6,#-1	;Save the callers registers
	str	r5,r6,#0	;Save R5
	add	r6,r6,#-1
	str	r7,r6,#0	;Back up R7
	add	r5,r6,#1	;Establish frame pointer





;PROCESS LEFT TREE
	ldr	r1,r2,#0
	brz	inFixPrint
	add	r6,r6,#-1	;Backing up current node to stack, and processing left tree
	str	r2,r6,#0
	ldr	r2,r2,#0	;Get the left tree loaded into R2
	jsr	infix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1

;PRINT VALUE
inFixPrint
	ldr 	r0,r2,#1	;Load nodes value to print
	trap	x21


;PROCESS RIGHT TREE
	ldr 	r1,r2,#2	;Access right tree to check if zero
	brz	inFixExit
	add	r6,r6,#-1	;Backing up
	str	r2,r6,#0	;Pushing to stack
	ldr	r2,r2,#2	;Get the right tree loaded into R2
	jsr	infix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1


inFixExit
	ldr	r7,r6,#0	;Restore register 7
	add	r6,r6,#1
	ldr	r5,r6,#0	;Restore register 5 (old frame pointer)
	add	r6,r6,#1	;R6 should now point to the previous node, which is at the top of the stack
	ret



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


postfix
	add	r6,r6,#-1	;Save the callers registers
	str	r5,r6,#0	;Save R5
	add	r6,r6,#-1
	str	r7,r6,#0	;Back up R7
	add	r5,r6,#1	;Establish frame pointer





;PROCESS LEFT TREE
	ldr	r1,r2,#0
	brz	postFixSkip
	add	r6,r6,#-1	;Backing up current node to stack, and processing left tree
	str	r2,r6,#0
	ldr	r2,r2,#0	;Get the left tree loaded into R2
	jsr	postfix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1

;PRINT VALUE
postFixSkip



;PROCESS RIGHT TREE
	ldr 	r1,r2,#2	;Access right tree to check if zero
	brz	postFixPrint
	add	r6,r6,#-1	;Backing up
	str	r2,r6,#0	;Pushing to stack
	ldr	r2,r2,#2	;Get the right tree loaded into R2
	jsr	postfix
	ldr	r2,r6,#0	;Restore Node from stack
	add	r6,r6,#1

postFixPrint
	ldr 	r0,r2,#1	;Load nodes value to print
	trap	x21



postFixExit
	ldr	r7,r6,#0	;Restore register 7
	add	r6,r6,#1
	ldr	r5,r6,#0	;Restore register 5 (old frame pointer)
	add	r6,r6,#1	;R6 should now point to the previous node, which is at the top of the stack
	ret
















eopMsg	.stringz "\n\nProgramed by Mickeal Nevakshonoff.\nEnd of Processing.\n"
prefixMsg	.stringz "\n\nPrefix order:\n"
infixMsg	.stringz "\n\nInfix order:\n"
postfixMsg	.stringz "\n\nPostfix order:\n"

stackbase 	.fill	xFD00

root       .fill   n1

n1         .fill   n2

           .fill   x2A

           .fill   n3

n2         .fill   n4

           .fill   x2B

           .fill   n5
n3         .fill   n6

           .fill   x2D

           .fill   n7

n4         .fill   n8

           .fill   x2F

           .fill   n9

n5         .fill   0

           .fill   x37

           .fill   0

n6         .fill   0

           .fill   x35

           .fill   0

n7         .fill   0

           .fill   x32

           .fill   0

n8         .fill   0

           .fill   x39

           .fill   0

n9         .fill   0

           .fill   x33

           .fill   0

           .end