##########################
# Programmrahmen fuer die 2. Praktikumsaufgabe
#
# Name: Matr.:
# Name: Matr.:
# Name: Matr.:
#
##########################

.text

main:		
		la		$t0, tree	
		sw		$zero, 0($t0)
	
		li		$v0, 13							#open the file
		la		$a0, filename
		li		$a1, 0
		li		$a2, 0
		syscall

		addi	$t9, $a0, 0						#save the file resource
		
		li		$v0, 14							#read the data
		la		$a1, newdata
		li		$a2, 1024000
		syscall

		li		$v0, 16							#close the file
		addi	$a0, $t9, 0
		syscall

		la		$t9, newdata	
	readout_first_line:							#find the end of the first line
		lb		$t0, 0($t9)
		addi	$t9, $t9, 1		
		bne		$t0, 13, readout_first_line

		addi	$t9, $t9, -1		
		sb		$zero, 0($t9)					#make a string out of the first line
		la		$a0, newdata					#parse an integer out of it
		jal 	atoi
	
		addi	$s2, $v0, 0						#save the number of rows	
		li		$t0, 13					
		sb		$t0, 0($t9)						#set the new line char back 
	
		la		$s3, tree						#set the end of the tree
	readout_loop:
		
		lb		$t0, 0($t9)						#repeat until the new row is found
		addi	$t9, $t9, 1
		bne		$t0, 13, readout_loop

		addi	$a0, $t9, 0		
		la		$a1, tree		
		addi	$a2, $s3, 0
		jal 	insert							#call the insert function
		addi	$s3, $v0, 0						#save the new end of the tree		

		addi	$s2, $s2, -1					#decrease the number of rows left
		bgtz	$s2, readout_loop				#repeat if there are rows left


		la		$a0, tree						#printout the results
		jal		print_inorder

		j 		end






	
#####################################################################
## atoi: Konvertiert einen String in eine Ganzzahl
##
## Parameter:		$a0 - address of the string
##
## Rückgabewert:	$v0 - parsed number
##
## Used:	$s0, $t0, $t1, $t2


atoi:
		add 	$s0, $ra, $zero					#save return address

		li		$v0, 0							#init the result
		li		$t2, 10							#init the step
		addi 	$t0, $a0, 0						#start the counter

	atoi_loop:									#iterate over the chars in the string
		lb		$t1, 0($t0)						#get the char
		addi 	$t0, $t0, 1
		
		beqz	$t1, end_atoi					#exit if end of string
		blt		$t1, 48, error_not_number		#throw and error if NaN
		bgt		$t1, 57, error_not_number
		
		mul		$v0, $v0, $t2					#shift the result in decimal
		add		$t1, $t1, -48					#make the char a number
		add		$v0, $v0, $t1					#add it to the temporary result		
		
		j 		atoi_loop	

	error_not_number:
		li 		$v0, 4							#print error message
		la		$a0, error_msg1					#   because non-numerical char was found
		syscall
		li		$v0, 10							#   and exit
		syscall

	end_atoi:
		add		$ra, $s0, $zero					#restore return address
		jr 		$ra


#####################################################################
## strcmp: Vergleicht zwei Stings miteinander
##
## Parameter:		$a0 - address of the first string
##					$a1 - address of the second string
##
## Rückgabewert:	$v0 - -1:a1<a0 1:a1>a0
##
## Used:	$s1, $t4, $t5, $t6, $t8

strcmp:
		add 	$s1, $ra, $zero					#save return address
		
		addi	$t4, $a0, 0
		addi	$t5, $a1, 0

	strcmp_loop:
		lb		$t6, 0($t4)						#load the current chars from both
		lb		$t7, 0($t5)						#   data locations
		addi	$t4, $t4, 1
		addi	$t5, $t5, 1
		
		bne		$t6, $t7, found_difference		#check if there is a difference
		bne		$t6, 58, strcmp_loop			#check if the end of the data

		li 		$v0, 4							#print error message
		la		$a0, error_msg					#   because the same names were found
		syscall
		li		$v0, 10							#   and exit
		syscall
		
	found_difference:							#if there is difference
		bgt		$t6, $t7, is_greater_than		#if a0<a1
		li		$v0, 1							#   set 1
		j		end_strcmp						#   and exit
	is_greater_than:							#else
		li		$v0, -1							#   set -1

	end_strcmp:
		add		$ra, $s1, $zero					#restore return address
		jr 		$ra


#####################################################################
## insert: Fuegt einen Eintrag in den Suchbaum ein
##
## Parameter: 		$a0 - address of the new data 
##					$a1 - address of the tree
##					$a2 - address of the end of the tree
##
## Rückgabewert:	$v0 - the new end of the tree
##
## Used:	$s0, $s9, $t0, $t1, $t2, $t3
##

insert:
		add 	$s0, $ra, $zero					#save return address

		sw		$zero, 0($a2)					#save empty pointers before the data
		sw		$zero, 4($a2)
		
		add		$t0, $a0, $zero					#iterate to find the first semicolomn
	find_first_semicolomn:						#   and the beginning of the family name
		addi	$t0, $t0, 1	
		lb		$t1, 0($t0)	
		bne		$t1, 59, find_first_semicolomn
		
		addi	$t2, $a2, 7
	copy_family_name:							#copy the family name after the pointers
		addi	$t0, $t0, 1	
		lb		$t1, 0($t0)
		beq		$t1, 59, finished_family_name	#check if reached ;
		addi	$t2, $t2, 1	
		sb		$t1, 0($t2)
		j copy_family_name
	
	finished_family_name:
		addi	$t2, $t2, 1						#put a space after family name
		li 		$t1, 32
		sb		$t1, 0($t2)

		addi	$t3, $a0, 0						#copy the first name after the family name
	copy_first_name:					
		addi	$t3, $t3, 1	
		lb		$t1, 0($t3)
		beq		$t1, 59, finished_first_name	#check if reached ;
		addi	$t2, $t2, 1
		sb		$t1, 0($t2)
		j 		copy_first_name

	finished_first_name:
		addi	$t2, $t2, 1						#put a : after first name
		li 		$t1, 58
		sb		$t1, 0($t2)

		li		$t3, 0
	copy_number:								#copy the number after the first name
		addi	$t3, $t3, 1				
		addi	$t0, $t0, 1	
		lb		$t1, 0($t0)
		addi	$t2, $t2, 1
		sb		$t1, 0($t2)
		blt		$t3, 9, copy_number

		addi 	$s7, $t2, 1						#return the new end of the tree

		beq		$a1, $a2, end_insert			#check if this is the first node and exit

		add		$t0, $a1, $zero 				#save the address of the tree/root node
		add		$t1, $a2, $zero					#save the address of the new node
		
	insert_node:								#iterate over the nodes in the tree to find
												#   the place for the new node

		addi 	$a0, $t0, 8						#compare the data in the current node with that
		addi 	$a1, $t1, 8						# 	of the new node
		jal		strcmp

		bgt		$v0, 0, place_on_right			#if new node < current node
		addi	$t3, $t0, 0				
		lw		$t2, 0($t3)						#   place on the left
		j 		end_place
	place_on_right:								#else
		addi	$t3, $t0, 4				
		lw		$t2, 0($t3)						#   place on the right
	end_place:

		bnez	$t2, follow_pointer				#if the pointer is empty
		sw		$t1, 0($t3)						#   place as a child
		j		end_insert						#	and exit
	follow_pointer:								#else
		addi 	$t0, $t2, 0						#   set as current node
		j		insert_node						#   and repeat the loop

	
	end_insert:

		andi	$v0, $s7, 3						#make sure the new address is aligned to the word border
		sub		$v0, $s7, $v0
		addi	$v0, $v0, 4				
		add		$ra, $s0, $zero					#restore return address
		jr 		$ra
		


#####################################################################
## print_inorder: Konvertiert einen String in eine Ganzzahl
##
## Parameter:	$a0 - address of the tree
##
## Rückgabewert:
##
## Uses:	$s0, $t0, $t1, $t2, $t3, $t4, $t5

print_inorder:
		add 	$s0, $ra, $zero					#save return address

		li		$v0, 4							#init for the string syscalls
		la		$t4, pheap						#get the address of the pointer heap
		addi	$t5, $a0, 0						#save the address of the tree
		
		jal		print_loop						#start the parsing with the root node
		
		j		end_print_inorder				#after finish - exit




	print_loop:
		sw		$t5, 0($t4)						#store the current node address in the heap
		sw		$ra, 4($t4)						#store the current return address in the heap
		addi	$t4, $t4, 8						#advance the heap tracker

		lw		$t1, 0($t5)						#get the left child
		beqz	$t1, done_left_child			#if there is a left child
		addi	$t5, $t1, 0						#  set the left child as current
		jal		print_loop						#  work the left child
	done_left_child:
		
		lw		$t5, -8($t4)					#resore the address of the current node		

##
##	BEGIN: Print the data in the current node
##
		
		addi	$t0, $t5, 8						#get the beginning of the data
		addi	$t3, $t0, 0						#save the beginning of the data
		la		$t2, newdata					#get the buffer

	pfind_first_name:							#search for the first blank space
		lb		$t1, 0($t0)	
		addi	$t0, $t0, 1	
		bne		$t1, 32, pfind_first_name
		
	pcopy_first_name:							#copy the family name after the pointers
		lb		$t1, 0($t0)
		addi	$t0, $t0, 1	
		beq		$t1, 58, pfinished_first_name	#check if reached :
		sb		$t1, 0($t2)
		addi	$t2, $t2, 1	
		j pcopy_first_name
	
	pfinished_first_name:
		li 		$t1, 32							#put a space after first name
		sb		$t1, 0($t2)
		addi	$t2, $t2, 1				

	pcopy_family_name:					
		lb		$t1, 0($t3)
		addi	$t3, $t3, 1	
		beq		$t1, 32, pfinished_family_name	#check if reached a blank space
		sb		$t1, 0($t2)
		addi	$t2, $t2, 1
		j 		pcopy_family_name

	pfinished_family_name:
		li 		$t1, 58							#put a ": " after family name
		sb		$t1, 0($t2)
		li 		$t1, 32				
		sb		$t1, 1($t2)
		addi	$t2, $t2, 2				

		li		$t3, 0
	pcopy_number:								#copy the number after the first name
		addi	$t3, $t3, 1				
		lb		$t1, 0($t0)
		addi	$t0, $t0, 1	
		sb		$t1, 0($t2)
		addi	$t2, $t2, 1
		blt		$t3, 9, pcopy_number

		sb		$zero, 0($t2)					#and an end to the string
	
		la		$a0, newdata					#set the print string address
		syscall

		la		$a0, new_line					#write a new line
		syscall

##
##	END: Print the data in the current node
##

		lw		$t1, 4($t5)						#get the right child
		beqz	$t1, done_right_child			#if there is a right child
		addi	$t5, $t1, 0						#   set the right child as current
		jal		print_loop						#   work the right child
	done_right_child:

		lw		$t1, -4($t4)					#resore the return address for this node
		addi	$t4, $t4, -8					#decrease the heap tracker
		jr		$t1								#return to the code that started the parsing of this node

	
	

	end_print_inorder:

		add		$ra, $s0, $zero					#restore return address
		jr 		$ra




	end:

.data
tree:		.space		102400					# for the tree
newdata:	.space		102400					# for the newly read data
pheap:		.space		8000					# for the recursion on print

filename:   .asciiz     "prak2_500.txt"     		# Name der Eingabedatei
error_msg:	.asciiz		"Error: same names found"
error_msg1: .asciiz		"Error: the string does not contain a number"
new_line:	.asciiz		"\n"