;Indexed Tries

;Ascii-Set except the first 32 codes (0-31)
;Although it is possible to change these for memory-optimization inte 26 for example, please do not to this!
;You will need to modify the position-calculation too and that was not my intention.
Const alphabet_size=96 

Global IT_root.router=New router

Type router
	Field trie_data.trie_data[alphabet_size]
	Field next_router.router[alphabet_size]
End Type

;You can modify this type to anything you need to
;(but please do not change the name)
Type trie_data
	Field txt$
	Field key$
End Type

;Insert a word. init with root=IT_root and i=0
;Insert the same word twice won't make sense!
Function IT_Insert(root.router,word$,i,trie_data.trie_data)
	Local char=0
	If i=Len(word$) Then
		char=Asc(Mid(word$,i,1))-32
		root\trie_data[char]=trie_data
	Else
		char=Asc(Mid(word$,i+1,1))-32
		If root\next_router[char]=Null Then
			root\next_router[char]=New router
			;all end_flags are automatcally false,
			;all next_router are automatically null
		EndIf
		IT_Insert(root\next_router[char],word$,i+1,trie_data)
	EndIf
End Function

;Search a word, init with root=IT_root and i=0
Function IT_Search.trie_data(root.router,word$,i)
	Local char=0
	If root=Null Then Return Null
	If i<Len(word$) Then
		char=Asc(Mid(word$,i+1,1))-32
		Return IT_Search(root\next_router[char],word$,i+1)
	Else
		char=Asc(Mid(word$,i,1))-32
		Return root\trie_data[char]
	EndIf
End Function

;Remove a word from the trie, init with root=IT_root and i=0
;use optional clean_mode to clean up empty nodes (may take longer but frees memory)
;please note that the trie_data of the removed word will NOT be deleted (because maybe you need it?)
Function IT_Delete(root.router,word$,i,clean_mode=False)
	Local char=0,ok=False
	If root=Null Then Return
	If i<Len(word$) Then
		char=Asc(Mid(word$,i+1,1))-32
		IT_Delete(root\next_router[char],word$,i+1,clean_mode)
	Else
		char=Asc(Mid(word$,i,1))-32
		root\trie_data[char]=Null
	EndIf
	If clean_mode Then
		ok=True
		For j=0 To alphabet_size
			If root\trie_data[j]<>Null Or root\next_router[j]<>Null Then
				ok=False
			EndIf
		Next
		If ok Then
			If root<>IT_root Then Delete root
		EndIf
	EndIf
End Function

;Calculates memory-usage in Bytes for the current trie
;does not consider the trie_data - this is up to you!
Function IT_GetMemory()
	Local router.router
	Local count=0
	For router=Each router
		count=count+1
	Next
	Return count*alphabet_size*2*4
End Function

;-------------- TESTING

;functional

Local trie_data.trie_data=New trie_data
trie_data\txt$="This is very informative text for 'Hello'"
trie_data\key$="Hello" ;This is JUST for testing, usually NOT required

DebugLog "Insert 'Hello'"
IT_Insert(IT_root,"Hello",0,trie_data)
IT_Insert(IT_root,"Hello",0,trie_data)

DebugLog "Memory-Usage: "+IT_GetMemory()

Local result.trie_data=IT_Search(IT_root,"Hello",0)
If result=Null Then
	DebugLog "No matches for 'Hello'"
Else
	DebugLog "We found the following for 'Hello':"
	DebugLog "   "+result\txt$
EndIf

DebugLog "Delete 'Hello'"
IT_Delete(IT_root,"Hello",0,True)

DebugLog "Memory-Usage: "+IT_GetMemory()

;performance

Local count
For i=0 To 10000
	trie_data.trie_data=New trie_data
	count=Rand(10,30)
	For j=0 To count
		trie_data\txt$=trie_data\txt$+Chr(Rand(65,91))
	Next
	count=Rand(5,10)
	For j=0 To count
		trie_data\key$=trie_data\key$+Chr(Rand(65,91))
	Next
Next

Local time=MilliSecs()
For trie_data=Each trie_data
	IT_Insert(IT_root,trie_data\key$,0,trie_data)
Next
DebugLog "10.000 Inserts in "+(MilliSecs()-time)+"ms"

DebugLog "Memory-Usage: "+IT_GetMemory()

time=MilliSecs()
For trie_data=Each trie_data
	result=IT_Search(IT_root,trie_data\key$,0)
	If result=Null Then
		DebugLog "There is a problem! "+trie_data\key$+" not found."
	EndIf
Next
DebugLog "10.000 Searches in "+(MilliSecs()-time)+"ms"

;mode=0 ; dirty delete, doesn't free the memory
mode=1 ; clean delete
time=MilliSecs()
For trie_data=Each trie_data
	IT_Delete(IT_root,trie_data\key$,0,mode)
Next
DebugLog "10.000 Deletes in "+(MilliSecs()-time)+"ms"

DebugLog "Memory-Usage: "+IT_GetMemory()

;comparison

DebugLog "Search for 10.000 words using the naive way"
;Shuffle the words to avoid linearity
Dim words$(10000)
For i=0 To 10000
	count=Rand(0,10000)
	trie_data=First trie_data
	For j=0 To count-1
		trie_data=After trie_data
	Next
	words$(i)=trie_data\key$
Next

time=MilliSecs()
For i=0 To 10000
	For trie_data=Each trie_data
		If trie_data\key$=words$(i) Then
			Exit
		EndIf
	Next
Next
DebugLog "10.000 'naively searches' in "+(MilliSecs()-time)+"ms"

DebugLog "done"
WaitKey()
End