# Flaviu Andreescu
# CSE 220 Lab 5
#
#
# This stores 10 values in an array and prints it
# Then it uses the stack to invert the array and prints
# Finally uses bucket sort to invert the array and prints
#
# Note: Program dynamically changes the size of the array based on input for the
#	sorting part.  As a result, this can take input range that goes beyond 1-10
#       as long as it doesn't go beyond memory bounds.  It also supports negative values
# 	and avoids negative index values by using the min as an offset bias.
#

.data 
	pbegin:		.asciiz	"\nPlease enter 10 integers for the array."
	pvalue:		.asciiz "\nEnter Value:"
	
	infodisplay:	.asciiz "\nDisplaying Array:"
	inforeverse:	.asciiz "\nInverting using the stack..."
	infosort:	.asciiz "\nSorting using bucket sort..."
	infomax:	.asciiz "\nMaximum value is:"
	infomin:	.asciiz "\nMinimum value is:"

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


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

	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

	subu    $sp, $sp, 4    			# Move stack pointer
	sw      $t0, ($sp)     			# also save user input in stack
	subu	$t3, $sp, 40			# save to the stack twice for later use
	sw      $t0, ($t3)     			# also save user input in stack
	
	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

	subu    $sp, $sp, 40    		# make sure stack pointer is correct


################################
#
#	Display Regular Array 
#
################################

	jal 	begindisplay			# jump to display procedure


################################
#
#	Construct Reverse Array 
#       & find min max
#
################################

	li 	$s1, 10				# number of outputs
	li 	$s2, 0				# initialize index place holder

	li 	$v0, 4 		
	la 	$a0, inforeverse		# print status
	syscall

	lw 	$t0, ($sp)      		# get data at top of the stack
	addi 	$s6, $t0, 0			# set some data element as min
	addi 	$s7, $t0, 0			# set some data element as max


reverseloop:

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

	lw 	$t0, ($sp)      		# pop a char off the stack
	addu 	$sp, $sp, 4 			# Move stack pointer

	sw 	$t0, 0($t1)			# save stack value

	blt	$t0, $s7, skipmax		# if not larger than max, skip
	addi 	$s7, $t0, 0			# else set max to data
skipmax:

	bgt	$t0, $s6, skipmin		# if not smaller than min, skip
	addi 	$s6, $t0, 0 			# else set min to data
skipmin:
	
	addi 	$s1, $s1, -1			# decrement loop counter
	addi 	$s2, $s2, 1			# increment our index
	bne  	$s1, $zero, reverseloop		# continue looping if needed
	jal 	begindisplay			# redisplay reversed array


################################
#
#	Initialize Buckets 
#
################################

	sub 	$s3, $s7, $s6			# array size = max - min + 1
	addi    $s3, $s3, 1			# array size = max - min + 1
	addi 	$s1, $s3, 0			# number of outputs
	li 	$s2, 0				# initialize index place holder

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

ibucketsloop:	

	add  	$t1, $s2, $s2			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is coming from
	sw 	$zero, 0($t1)			# initialize bucket data to 0

	addi 	$s1, $s1, -1			# decrement loop counter
	addi 	$s2, $s2, 1			# increment our index
	bne  	$s1, $zero, ibucketsloop	# zero more buckets if needed




################################
#
#	Drop Input Into Buckets
#
################################


	li 	$s1, 10				# number of outputs

fillbuckets:	
	lw 	$t0, ($sp)      		# pop a char off the stack
	addu 	$sp, $sp, 4 			# Move stack pointer

	sub 	$t0, $t0, $s6			# offset to acquire minimap positive index
	add  	$t1, $t0, $t0			# 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 bucket data
	addi	$t0, $t0, 1			# increment bucket data by 1
	sw 	$t0, 0($t1)			# save bucket data	
	
	addi 	$s1, $s1, -1			# decrement loop counter
	bne  	$s1, $zero, fillbuckets		# fill more buckets if needed



################################
#
#	Load and Print 
#        from Buckets
#
################################

	li 	$s2, 0				# initialize index place holder

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

readbuckets:	
	add  	$t1, $s2, $s2			# t1 = index times two
	add     $t1, $t1, $t1			# t1 = index times four
	add  	$t1, $t1, $s0			# t1 = location data is coming from
	lw 	$t0, 0($t1)			# load bucket data

	
	addi 	$s1, $t0, 0			# initialise loop counter
	add     $s4, $s2, $s6			# unbias index to obtain value
	beq	$s1, $zero, continue		# if nothing in bucket, continue

printbucket:

	li 	$v0, 4 		
	la 	$a0, utilnl			# print a new line
	syscall

	li 	$v0, 1 		
	addi 	$a0, $s4, 0			# load value to be printed
	syscall	

	addi 	$s1, $s1, -1			# decrement loop counter
	bne  	$s1, $zero, printbucket		# print more data if needed


	
continue:	

	addi 	$s3, $s3, -1			# decrement loop counter
	addi 	$s2, $s2, 1			# increment our index
	bne  	$s3, $zero, readbuckets		# read more buckets if needed


################################
#
#	Display Min/ Max
#
################################

	li 	$v0, 4 		
	la 	$a0, infomin			# display min message
	syscall
	li 	$v0, 1 		
	move 	$a0, $s6			# load min
	syscall


	li 	$v0, 4 		
	la 	$a0, infomax			# display max message
	syscall
	li 	$v0, 1 		
	move 	$a0, $s7			# load max
	syscall


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

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

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



################################
#
# 	Procedure Space
#
################################
################################
#
#	Print Array Procedure
#
################################

begindisplay:
	li 	$s1, 10				# number of outputs
	li 	$s2, 0				# initialize index place holder

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

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

	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
	lw 	$t0, 0($t1)			# load user input

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