#
# Copyright (c) 1999
#      Ali Onur Cinar &060;cinar&064;zdo.com&062;
#
# License:
#
#   Permission  to  use,  copy, modify, and  distribute  this software and its
#   documentation   for  educational   purposes  and  without  fee  is  hereby
#   granted,  provided  that the  above  copyright notice appear in all copies
#   and  that both  the  copyright  notice  and  this  permission  notice  and
#   warranty  disclaimer appear in supporting documentation, and that the name
#   of Ali Onur Cinar not be  used  in  advertising or publicity pertaining to
#   distribution of the software without specific, written prior permission.
#

	.data
size:	.word	11		# size(array) - 1
array:	.word	0,11,10,9,8,7,6,5,4,3,2,1

	.text
	.globl main

#
# @function: main
#	@parameters:	n/a
# 	@used_reg: 	$s0,$s1
#
main:
	sub	$sp,$sp,4	# save return address
	sw	$ra,0($sp)
	
	lw	$s0,size	# size of the array
	li	$s1,0		# init cursor

	li	$a0,0		# index=0
	jal	recbuildheap	# recbuildheap
		
end00:
	lw	$ra,0($sp)	# restore return address
	add	$sp,$sp,4
	jr	$ra		# return to kernel

minchild:
	sub	$sp,$sp,36	# save $s and $ra 
	sw	$ra,0($sp)
	sw	$s0,4($sp)
	sw	$s1,8($sp)
	sw	$s2,12($sp)
	sw	$s3,16($sp)
	sw	$s4,20($sp)
	sw	$s5,24($sp)
	sw	$s6,28($sp)
	sw	$s7,32($sp)

	la	$s0,array	# s0 = @array
	lw	$s1,size	# s1 = size
	move	$s2,$a0		# s2 = index

	mul	$t0,$s2,2	# t0 = 2index
	li	$v0,0		# v0 = 0 (incase we return)
	bgt	$t0,$s1,end10	# if (t0>s1) return
	
	add	$t0,$t0,1	# t0 = 2index+1
	blt	$t0,$s1,twoch	# if (t0= t4 go els10
	li	$v0,-1		# v0 = -1
	blt	$t3,$t5,end10	# return
	li	$v0,0		# v0 = 0
	j	end10		# return
els10:
	li	$v0,1		# v0 = 1
	blt	$t4,$t5,end10	# return
	li	$v0,0		# v0 = 0
	
end10:
	lw	$ra,0($sp)	# restore registers
	lw	$s0,4($sp)
	lw	$s1,8($sp)
	lw	$s2,12($sp)
	lw	$s3,16($sp)
	lw	$s4,20($sp)
	lw	$s5,24($sp)
	lw	$s6,28($sp)
	lw	$s7,32($sp)
	add	$sp,$sp,36
	jr	$ra		# return back

recbuildheap:	
	sub	$sp,$sp,36	# save $s and $ra 
	sw	$ra,0($sp)
	sw	$s0,4($sp)
	sw	$s1,8($sp)
	sw	$s2,12($sp)
	sw	$s3,16($sp)
	sw	$s4,20($sp)
	sw	$s5,24($sp)
	sw	$s6,28($sp)
	sw	$s7,32($sp)

	la	$s0,array	# s0 = @array
	lw	$s1,size	# s1 = size
	move	$s2,$a0		# s2 = index

	mul	$s3,$s2,2	# s3 = 2index
	bgt	$s3,$s1,end20	# 2index>size go end20
	
	move	$a0,$s3		# a0 = 2index
	jal	recbuildheap	# recbuildheap
	
	add	$s3,$s3,1	# s3 = 2index+1
	bgt	$s3,$s1,els20	# 2index+1>size go els20
	move	$a0,$s3		# a0 = 2index+1
	jal	recbuildheap	# recbuildheap
	
els20:
	move	$s3,$s2		# s3 = index
lop20:
	move	$a0,$s3		# a0 = s3
	jal	minchild	# minchild
	move	$s4,$v0		# save result
	beq	$s4,0,end20	# return
	beq	$s4,-1,els21	# s4 = -1 go els21
	beq	$s4,1,els22	# s4 = 1 go els22
	j	lop20		# cont. loop
els21:
	mul	$t0,$s3,2	# t0 = 2index
	move	$t1,$t0		# t1 = t0
	mul	$s3,$s3,4	# s3 = s3 * 1word
	add	$s3,$s3,$s0	# s3 = @array[index]
	lw	$t2,($s3)	# t2 = array[index]
	
	mul	$t1,$t1,4	# t1 = t1 * 1word
	add	$t1,$t1,$s0	# t1 = @array[ip]
	lw	$t3,($t1)	# t3 = array[ip]
	
	sw	$t3,($s3)	# array[index]=array[ip]
	sw	$t2,($t1)	# array[ip]=array[index]
	
	move	$s3,$t0		# index = ip
	j	lop20
els22:
	mul	$t0,$s3,2	# t0 = 2index
	add	$t0,$t0,1	# t0 = 2index+1
	move	$t1,$t0		# t1 = t0
	mul	$s3,$s3,4	# s3 = s3 * 1word
	add	$s3,$s3,$s0	# s3 = @array[index]
	lw	$t2,($s3)	# t2 = array[index]
	
	mul	$t1,$t1,4	# t1 = t1 * 1word
	add	$t1,$t1,$s0	# t1 = @array[ip]
	lw	$t3,($t1)	# t3 = array[ip]
	
	sw	$t3,($s3)	# array[index]=array[ip]
	sw	$t2,($t1)	# array[ip]=array[index]
	
	move	$s3,$t0		# index = ip
	j	lop20
	
end20:
	lw	$ra,0($sp)	# restore registers
	lw	$s0,4($sp)
	lw	$s1,8($sp)
	lw	$s2,12($sp)
	lw	$s3,16($sp)
	lw	$s4,20($sp)
	lw	$s5,24($sp)
	lw	$s6,28($sp)
	lw	$s7,32($sp)
	add	$sp,$sp,36
	jr	$ra		# return back