# Flaviu Andreescu
# CSE 220 Lab 6
#
#
# The Program asks for 10 values from the user
# Then it generates three 100 value arrays in ascending
# descending and random order. It sorts all four arrays
# using max heap sort and then displays its result.

.data 
	pbegin:		.asciiz	"\nPlease enter 10 integers for the array."
	pvalue:		.asciiz "\nEnter Value:"
	
	infodisplay:	.asciiz "\nDisplaying Array:\n"
	infoasc:	.asciiz "\n\nBuilding Ascending Array"
	infodesc:	.asciiz "\n\nBuilding Descending Array"
	inforand:	.asciiz "\n\nBuilding Random Array"
	infosort:	.asciiz "\n\nSorting using heap sort..."


	utilnl:		.asciiz "\n"
	utilsp:		.asciiz " "
	
	Array:		.word 	1		# our Array allocation in memory
.text


main:
	la 	$s0, Array			# Load our array into $s0
	li 	$s1, 10				# number of inputs
	li 	$s2, 1				# initialize index place holder, start at 1

	li 	$v0, 4 				# load string
	la 	$a0, pbegin			# instruct the user
	syscall


################################
#
# 	Data Aquisition
#
################################

dataloop:	
	li 	$v0, 4 		
	la 	$a0, pvalue			# ask user for input
	syscall

	li 	$v0, 5				# system code to receive integer
	syscall
	addi 	$t0, $v0, 0			# set t0 to user input

	add  	$t1, $s2, $s2			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is headed

	sw 	$t0, 0($t1)			# save user input

	
	addi 	$s1, $s1, -1			# decrement loop counter
	addi 	$s2, $s2, 1			# increment our index
	bne  	$s1, $zero, dataloop		# prompt for more input if we need to



################################
#
#	Display 10 Input Array 
#
################################

	move 	$a0, $s0			# array to print
	li 	$a1, 1				# initial index
	li 	$a2, 10				# how many numbers to print
	jal 	begindisplay			# jump to display procedure

################################
#
#	Sort & Print 10 Input Array 
#
################################

	li 	$v0, 4 		
	la 	$a0, infosort			# tell user what we're doing
	syscall

	li 	$s1, 10				# our last index value in the array 
						# elements since element 0 is empty

	jal 	heapify				# sort the array
	jal	printheap			# print heap


################################
#
#	Handle 100 Ascending 
#	       Array
#
################################

	li 	$v0, 4 		
	la 	$a0, infoasc			# tell user what we're doing
	syscall

	li 	$a2, 100			# create 100 numbers
	li	$a1,   1			# start at index 1

ascloop:	

	add  	$t1, $a1, $a1			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is headed
	sw 	$a1, 0($t1)			# save value
	
	addi 	$a2, $a2, -1			# decrement loop counter
	addi 	$a1, $a1, 1			# increment our index
	bne  	$a2, $zero, ascloop		# keep generating if necesary


	jal dsrarray				# Display Sort and Redisplay 


################################
#
#	Handle 100 Descending
#	       Array
#
################################

	li 	$v0, 4 		
	la 	$a0, infodesc			# tell user what we're doing
	syscall

	li 	$a2, 100			# create 100 numbers
	li	$a1,   1			# start at index 1

descloop:	

	add  	$t1, $a1, $a1			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is headed
	addi	$t3, $zero, 101			# t3 = 101
	sub 	$t3, $t3, $a1			# t3 = t3 - a1
	sw 	$t3, 0($t1)			# save value
	
	addi 	$a2, $a2, -1			# decrement loop counter
	addi 	$a1, $a1, 1			# increment our index
	bne  	$a2, $zero, descloop		# keep generating if necesary


	jal dsrarray				# Display Sort and Redisplay 


################################
#
#	Handle 100 Random
#	       Array
#
################################

	li 	$v0, 4 		
	la 	$a0, inforand			# tell user what we're doing
	syscall

	li 	$a2, 100			# create 100 numbers
	li	$a1,   1			# start at index 1

	li 	$t4, 31				# a = 31
	li 	$t5, 23				# b = 23
	li 	$t6, 1000			# c = 1000

randloop:	

	add  	$t1, $a1, $a1			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is headed

	mul 	$t0, $t4, $t0			# t0 = a * s
	add 	$t0, $t0, $t5			# t0 = a * s + b
	div 	$t0, $t6 			# hi = (a * s + b) mod c
	mfhi 	$t0				# t0 = (t0 = seed / remainder)

	sw 	$t0, 0($t1)			# save value
	
	addi 	$a2, $a2, -1			# decrement loop counter
	addi 	$a1, $a1, 1			# increment our index
	bne  	$a2, $zero, randloop		# keep generating if necesary

	jal dsrarray


################## END PROGRAM ##################################################

end:	li 	$v0, 10				# actually end the program
	syscall

################## END PROGRAM ##################################################


################################
#
# 	Procedure Space
#
################################
################################
#
#	Print Array Procedure
#
################################
# a2 = how many numbers to print
# a1 = which number to start with
# s0 = where the array is

begindisplay:
	li 	$v0, 4 		
	la 	$a0, infodisplay		# tell user what we're doing
	syscall

displayloop:	
	li 	$v0, 4 		
	la 	$a0, utilsp			# print a new line
	syscall

	add  	$t1, $a1, $a1			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is headed
	lw 	$t0, 0($t1)			# load user input

	li 	$v0, 1
	move 	$a0, $t0			# print array value at index
	syscall
	
	addi 	$a2, $a2, -1			# decrement loop counter
	addi 	$a1, $a1, 1			# increment our index
	bne  	$a2, $zero, displayloop		# display for more input if we need to
	j 	$ra				# return


################################
#
#	Print-Pop Heap
#
################################
# s1 = array's last index
# s0 = where the array is

printheap:
	li 	$v0, 4 		
	la 	$a0, infodisplay		# tell user what we're doing
	syscall

	sub 	$sp, $sp, 4			# push onto stack
	sw	$ra, 0($sp)			# save our return address

printheaploop:
	li 	$v0, 4 		
	la 	$a0, utilsp			# print a new line
	syscall

	lw 	$t0, 4($s0)			# load user input
	li 	$v0, 1
	move 	$a0, $t0			# print array value at index
	syscall

	add  	$t1, $s1, $s1			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location of last indexed value
	lw 	$t0, 0($t1)			# load user input
	sw	$t0, 4($s0)			# save last value on top of heap
	li	$a0, 1				# set index to be considered to 1
	jal 	heapifyloop			# bubble down
	

	addi 	$s1, $s1, -1			# decrement loop counter
	beq  	$s1, $zero, endheapprint	# display more if needed
	jal 	printheaploop			# loop

endheapprint:
	lw	$ra, 0($sp)			# obtain our return address
	add 	$sp, $sp, 4			# pop from stack
	j 	$ra
	


################################
#
#	Heapify Procedure
#
################################
# refers to $s1 as array's last index

heapify:
	sub 	$sp, $sp, 4			# push onto stack
	sw	$ra, 0($sp)			# save our return address

	li 	$t3, 2				# t3=2
	div	$s1, $t3
	mflo	$a2				# a2 = last index / 2
						# a2 is now largest index for a parent node

heapifyrepeat:
	add 	$a0, $a2, $zero			# set heapify loop parameter
	jal	heapifyloop			# heapify this node
	
	addi 	$a2, $a2, -1			# decrement loop counter
	beq  	$a2, $zero, endheapify		# display for more input if we need to
	jal 	heapifyrepeat

endheapify:
	lw	$ra, 0($sp)			# obtain our return address
	add 	$sp, $sp, 4			# pop from stack
	j 	$ra				# return




################################
#
#	Heapify Procedure Loop
#
################################
# takes in $a0 as index being considered
# refers to $s0 as array location
# refers to $s1 as array's last index

heapifyloop:
	sub 	$sp, $sp, 4			# push onto stack
	sw	$ra, 0($sp)			# save our return address
	sub 	$sp, $sp, 4			# push onto stack
	sw	$a0, 0($sp)			# save our index	


	add	$t0, $a0, $a0			# get indexes left child 
	bgt	$t0, $s1, skipleftchild		# if there is no left child, continue

	add  	$t1, $a0, $a0			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location of parent value
	lw 	$t3, 0($t1)			# t3 = parent value

	add  	$t2, $t0, $t0			# t2 = index times two
	add     $t2, $t2, $t2			# t2 = index times four
	add  	$t2, $t2, $s0			# t2 = location of left child value
	lw 	$t4, 0($t2)			# t4 = left child value

	bgt 	$t3, $t4, skipleftchild		# if parent is greater, do nothing

	sw      $t4, 0($t1)			# save child in place of parent
	sw	$t3, 0($t2)			# save parent in place of child
	move	$a0, $t0			# set argument to left child index
	jal heapifyloop				# heapify child
skipleftchild:

	lw 	$a0, 0($sp)			# recover parameter
	add	$t0, $a0, $a0			# get indexes left child 
	addi 	$t0, $t0, 1			# get index of right child 
	bgt	$t0, $s1, skiprightchild	# if there is no right child, continue

	add  	$t1, $a0, $a0			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location of parent value
	lw 	$t3, 0($t1)			# t3 = parent value

	add  	$t2, $t0, $t0			# t2 = index times two
	add     $t2, $t2, $t2			# t2 = index times four
	add  	$t2, $t2, $s0			# t2 = location of right child value
	lw 	$t4, 0($t2)			# t4 = right child value

	bgt 	$t3, $t4, skiprightchild	# if parent is greater, do nothing

	sw      $t4, 0($t1)			# save child in place of parent
	sw	$t3, 0($t2)			# save parent in place of child
	move	$a0, $t0			# set argument to right child index
	jal heapifyloop				# heapify child
skiprightchild:

	lw	$ra, 4($sp)			# recover jump linker
	add	$sp, $sp, 8			# return stack pointer to normal
	
	j $ra					# return

################################
#
#  Display, Sort and, Redisplay 
#        100 Input Array 
#
################################

dsrarray:
	sub 	$sp, $sp, 4			# push onto stack
	sw	$ra, 0($sp)			# save our return address

	move 	$a0, $s0			# array to print
	li 	$a1, 1				# initial index
	li 	$a2, 100				# how many numbers to print
	jal 	begindisplay			# jump to display procedure

	li 	$v0, 4 		
	la 	$a0, infosort			# tell user what we're doing
	syscall

	li 	$s1, 100			# our last index value in the array 
						# elements since element 0 is empty

	jal 	heapify				# sort the array
	jal	printheap			# print heap

	lw	$ra, 0($sp)			# obtain our return address
	add 	$sp, $sp, 4			# pop from stack
	j 	$ra