; A program to sort (ASCII order) and then print a sequence of strings
; stored in memory at STRINGS (a label), written mostly in the ECE120
; class on 21 April 2017.

; Let's write a program!

	.ORIG	x3000

; R0 = string pointer
; R1 = pointer to current block
; R6 = temporary
	LEA	R0,STRINGS	; initialize R0 and R1
	LD	R1,BLOCKS

MAINLOOP			; check for remaining string
	LDR	R6,R0,#0	
	BRz	STRINGSDONE

; copy current string pointer (R0) into next block (at R1)
	STR	R0,R1,#0

; find end of string in R2
	ADD	R2,R0,#0	; copy R0 into R2
FINDEND	LDR	R6,R2,#0	; next char in string
	BRz	FOUNDEND
	ADD	R2,R2,#1
	BRnzp	FINDEND

FOUNDEND
	ADD	R0,R2,#1

; time to insert the new block into the list
; R3 = pointer to block pointer to change
	LEA	R3,LIST

; need to find the right insertion point for the block

; check first whether we have reached the end of the list
CHECKABLOCK
	LDR	R6,R3,#0
	BRz	INSERTBLOCK

; otherwise, compare the strings
; R4 = new block's string
; R5 = existing block's string
	LDR	R4,R1,#0
	LDR	R5,R6,#0
; R6 = character from new block's string
; R7 = character from existing block's string
COMPARESTRINGS
	LDR	R6,R4,#0
	BRz	INSERTBLOCK
	LDR	R7,R5,#0
	NOT	R7,R7
	ADD	R7,R7,#1
	ADD	R6,R6,R7
	BRp	LOOKATNEXT
	BRn	INSERTBLOCK
	ADD	R4,R4,#1
	ADD	R5,R5,#1
	BRnzp	COMPARESTRINGS

LOOKATNEXT
	LDR	R3,R3,#0
	ADD	R3,R3,#1
	BRnzp	CHECKABLOCK

INSERTBLOCK

; FIRST BLOCK OF CODE WRITTEN AFTER CLASS STARTS HERE

; now insert the new block into the list: first, change the new block's 
; next pointer to point to the block to which R3 points
	LDR	R6,R3,#0
	STR	R6,R1,#1	; the 'next pointer' is offset 1 from the 
				; start of the block
; now we write the new block pointer into the location pointed to by R3
	STR	R1,R3,#0
; the new block is now in the list, so we can advance R1 to an unused block;
; each requires 2 memory locations, so we add 2
	ADD	R1,R1,#2

; and now it's time for a new string
	BRnzp	MAINLOOP

; FIRST BLOCK OF CODE WRITTEN AFTER CLASS ENDS HERE

STRINGSDONE	; have processed all strings

; SECOND BLOCK OF CODE WRITTEN AFTER CLASS STARTS HERE

; we now walk through the linked list and print all strings
; R1 = block pointer

	LD	R1,LIST		; point R1 to the first block in the list
	BRz	PRINTINGDONE	; if NULL, we're done
PRINTONE
	LDR	R0,R1,#0	; read the block's string pointer into R0
	PUTS			; print the string (LC-3 TRAP)
	AND	R0,R0,#0	; print a newline
	ADD	R0,R0,x0A
	OUT
	LDR	R1,R1,#1	; point R1 to the next block in the list
	BRnp	PRINTONE	; if not NULL, print it
PRINTINGDONE

; SECOND BLOCK OF CODE WRITTEN AFTER CLASS ENDS HERE

	HALT

; some data
LIST	.FILL	x0000	; list starts empty
BLOCKS	.FILL	x4000
STRINGS
	.STRINGZ "here"
	.STRINGZ "is"
	.STRINGZ "a"
	.STRINGZ "set"
	.STRINGZ "of"
	.STRINGZ "strings"
	.STRINGZ ""

	.END

