#################################################################
# Test-case 2
# This is the second test-case file. This requires two functions 
# in order to work properly. The first one is called tcreate, 
# which creates the binary tree and the second is called 
# decompress, which uses the tree to decompress the file.
# Add these two functions to the designated locations. If they
# work properly, you should obtain the following output during 
# run-time:
# "Stop checking it already! It works!!!"
################################################################
	.data
qfirst: .space 4				#Storage of pointer to first element in queue
troot: .space 4					#Storage of pointer to root of tree
cdata: .byte 0x16,0xFF,0x01,0x73,0x01,0x77,0x01,0x49,0x01,0x79,0x01
	   .byte 0x64,0x01,0x6C,0x01,0x67,0x01,0x6E,0x01,0x68,0x01,0x70
	   .byte 0x01,0x53,0x01,0x6B,0x02,0x72,0x02,0x6F,0x02,0x61,0x02
	   .byte 0x65,0x02,0x69,0x02,0x63,0x02,0x74,0x03,0x21,0x04,0x20
	   .byte 0x05,0xF6,0xDB,0xCD,0x5F,0xA5,0x02,0xFD,0xCE,0x5B,0xCF
	   .byte 0xC0,0xA3,0xF7,0xD4,0xC5,0xBC,0x46,0x10,0x3C,0x90,0xC0
								#"Compressed file"
output: .space 2				#Create space for output
	
	.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 $a0,cdata				#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
	
#########################################
#Add your tree creation function here!!!
########################################


###############################################################
#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