###############################################################################
# Turn-in file.
# Add the code for your function where indicated.
# Remember to create a readme file and indicate your full name and perm
# before e-mailing your files to the T.A.
###############################################################################
	.data
qfirst: .space 4				#Storage of pointer to first element in queue
troot:  .space 4				#Storage of pointer to root of tree
cspace: .space 512				#Compressed file
output: .space 2				#Create space for output
nline:	.asciiz "\n"				#Define new line string
	
	.text
	.globl main
main:						#main function
	addi $sp,$sp,-8				#make room in stack
	sw $ra,4($sp)				#store $ra into stack 
	sw $s0,0($sp)				#store $s0 into stack
	la, $s0,cspace				#create pointer to free space (for storing file)
	
loadloop:
	addi $a0, $s0, 0		#set the address to store input in
	li $v0, 8				#set system call to read char
	li $a1, 2				#read in 1 byte
	syscall					#syscall
	li $v0, 1				#set system call to print integer
	lbu $a0, 0($a0)			#get the value that was just read in
	beq $a0, $0, endloop	#check and see if it's 0, if it is,then exit the loop 
	syscall				#print value
	li $v0, 4				#set system call to print string
	la $a0, nline			#set newline to be printed
	syscall					#print newline
	addi $s0, $s0, 1		#incrm address
	j loadloop				#loop back
	
endloop:
	
	li $a0, 4
	li $v0, 1
	syscall
	
	la $a0,cspace				#Load pointer to compressed file
	jal mkqueue				#Jump to function mkqueue (makes queue)
	
	move $s0,$v0				#Copy pointer to compressed data into $s0
	jal tcreate					#Jump to function tcreate (create the tree)
	
	move $a0,$s0				#Set pointer to compressed data as first argument
	jal decompress				#Jump to function decompress (decompress data)
	
	lw $s0,0($sp)				#Restore value for $s0 from stack
	lw $ra,4($sp)				#Load address for $ra from stack
	addi $sp,$sp,8				#Return stack pointer to original location
	jr $ra						#Return to function that called


#################################################################
# mkqueue: This function is passed a pointer to the beginning
# of the compressed file. This function creates a priority queue
# and returns a pointer to the beginning of the compressed data.
#################################################################
mkqueue:
	addi $sp,$sp,-4				#Make room for $ra
	sw $ra,0($sp)				#Store $ra into stack

	lbu $t0,0($a0)				#Load the counter for the number of elements in the queue
	
	move $t1,$a0				#Copy contents of $a0 into $t1
	li $v0,9					#System call code for dynamically allocating memory
	li $a0,20					#Specification to allocate 20 bytes
	syscall						#Allocate 20 bytes
	move $a0,$t1				#Restore contents of $a0
	
	la $t1,qfirst				#Load address of qfirst into $t0
	sw $v0,0($t1)				#Store pointer to allocated memory into qfirst
	move $t1,$v0				#Copy pointer to allocated memory into $t1
	
	addi $a0,$a0,1				#Move $a0 to first character in queue
	li $t2,0					#Clear register $t2
	lbu $t2,0($a0)				#Load first character into $t2
	sb $t2,0($t1)				#Store character into qfirst
	
	addi $a0,$a0,1				#Move $a0 to priority for first character
	li $t2,0					#Clear register $t2
	lbu $t2,0($a0)				#Load first priority into $t2
	sb $t2,1($t1)				#Store priority into qfirst
	
	sw $zero,4($t1)				#Store null for pointer to previous in qfirst
	sw $zero,8($t1)				#Store null for pointer to next in qfirst
	sw $zero,12($t1)			#Store null for pointer to left child
	sw $zero,16($t1)			#Store null for pointer to right child
	
	addi $t0,$t0,-1				#Decrement counter for number of elements
	
qloop:							#Loop that creates queue
	move $t2,$a0				#Copy contents of $a0 into $t2
	li $v0,9					#System call code for dynamically allocating memory
	li $a0,20					#Specification to allocate 20 bytes
	syscall						#Allocate 20 bytes
	move $a0,$t2				#Restore contents of $a0
	
	move $t2,$v0				#Copy pointer to allocated memory into $t2
	
	addi $a0,$a0,1				#Move $a0 to character in queue
	li $t3,0					#Clear register $t3
	lbu $t3,0($a0)				#Load character into $t3
	sb $t3,0($t2)				#store character
	
	addi $a0,$a0,1				#move $a0 to priority
	li $t3,0					#Clear register $t3
	lbu $t3,0($a0)				#Load priority into $t3
	sb $t3,1($t2)				#Store priority
	
	sw $t2,8($t1)				#Store previous node's pointer to next
	sw $t1,4($t2)				#Store pointer to previous node
	sw $zero,8($t2)				#Store null for pointer to next node
	sw $zero,12($t2)			#Store null for pointer to left child
	sw $zero,16($t2)			#Store null for pointer to right child

	move $t1,$t2				#Copy pointer to previous node to $t1
	addi $t0,$t0,-1				#Decrement counter
	bgtz $t0,qloop				#Continue until all elements put into queue
	
	addi $a0,$a0,1				#Move $a0 to first location of compressed data
	move $v0,$a0				#Copy contents $a0 into $v0

	lw $ra,0($sp)				#Load address for $ra from stack
	addi $sp,$sp,4				#Return stack pointer to original location
	jr $ra						#Return to function that called
	
###############################################################
#dequeue: This function obtains the first node in the priority
#queue. It removes this node from the queue and returns it
#via register $v0.
###############################################################
dequeue:
	addi $sp,$sp,-4				#Make room for $ra
	sw $ra,0($sp)				#Store $ra into stack
	
	la $t0,qfirst				#Load address of pointer to first element in queue
	lw $t1,0($t0)				#Load pointer to first element into $t1 
	move $v0,$t1				#Copy pointer to first element to return register
	beqz $v0,dqnull				#Null encountered in dequeue

	lw $t1,8($t1)				#Load address of next element in queue into $t0
	sw $t1,0($t0)				#Store address of the element into qfirst
	beqz $t1,dqnull				#Null encountered in dequeue
	
	sw $zero,4($t1)				#Make the element's previous pointer null
	sw $zero,8($v0)				#Make now disconnected node's pointer to next null
	
dqnull:		
	lw $ra,0($sp)				#Load address for $ra from stack
	addi $sp,$sp,4				#Return stack pointer to original location
	jr $ra						#Return to function that called

############################################################
#enqueue: This function is passed the pointer to a node.
#It places this node in the appropriate place in the 
#priority queue. 
############################################################
enqueue:
	addi $sp,$sp,-4				#Make room for $ra
	sw $ra,0($sp)				#Store $ra into stack
	
	la $t0,qfirst				#Load address to pointer to first element of queue
	lw $t0,0($t0)				#Load pointer to the first element of queue
	
	lbu $t1,1($a0)				#Load priority of node to be enqueue
	lbu $t2,1($t0)				#Load priority of element in queue
	ble $t1,$t2,prtydone		#Skip loop if first elem. in queue has greater priority
	
prtyloop:						#Loop to find proper location based upon priority
	lw $t1,8($t0)				#Load pointer to next element into $t1
	beqz $t1,prtydone			#Branch to prtyone if next element is null
	move $t0,$t1				#Move $t0 to next element
	li $t1,0					#Clear register $t2
	li $t2,0					#Clear register $t3
	lbu $t1,1($a0)				#Load priority of node to be enqueue
	lbu $t2,1($t0)				#Load priority of element in queue
	bgtu $t1,$t2,prtyloop		#Continue looping while priority of node is greater

prtydone:
	lbu $t1,1($a0)				#Re-load priority of node to be enqueue
	bgeu $t2,$t1,locfound		#Branch to location has been found (locfound)
								#If no location found, append to end of queue	
	sw $a0,8($t0)				#Link previous end of queue to node			
	sw $t0,4($a0)				#Link node's pointer to previous element
	sw $zero,8($a0)				#Make node's pointer to next element null
	b enqdone					#Branch to enqdone (finished adding node to queue)

locfound:
	lw $t3,4($t0)				#Load previous element of queue (from the current one)
	sw $t3,4($a0)				#Store it as previous element of node
	sw $t0,8($a0)				#Store current element in queue as next one after node
	sw $a0,4($t0)				#Store node as current element's previous pointer
	beqz $t3,enqnull			#Branch to enqnull (current element in queue is first)
	sw $a0,8($t3)				#Store node as the next element of the previous one
	b enqdone					#Branch to enqdone
enqnull:
	la $t4,qfirst				#Load address of pointer to first element in queue
	sw $a0,0($t4)				#Store pointer to node as qfirst
		
enqdone:	
	lw $ra,0($sp)				#Load address for $ra from stack
	addi $sp,$sp,4				#Return stack pointer to original location
	jr $ra						#Return to function that called

#######################################################
#tcreate: This function uses the priority queue to
#create a Huffman binary tree. It then stores the root
#of this tree into troot.
#######################################################
tcreate:
	jr $ra

###############################################################
#decompress: This function has one argument; a pointer to the
#compressed data. This function uses troot (the root of the
#tree) to decode the file to the screen.
##############################################################
decompress:
	jr $ra