AutoComplete Library

Posted by on August 14, 2010

This nifty library will allow you to incorporate auto-completion in your latest game/software project without much hassle. It supports the use of a dictionary with both load and save routines, it keeps track of hits and allows to filter the suggestion using a “headroom” parameter.

The “algorithm” used to populate the suggestion list is down to the bare basics, reason being I wanted to keep the library small and simple. In fact some “methods” were not implemented for this very same reason. But please feel free to write a helper lib and I’ll happily add a link towards it.

The 4.50 source:

Structure AUTOCOMPLETE_ENTRY	; This represents each word in the dictionary
	word.s			; The word
	length.i		; The length of the word (cached for speed)
	hits.i			; Amount of hits this word received (see GetSuggestions for more information on this)
EndStructure

Structure AUTOCOMPLETE
	DictionaryFileName.s			; Filename for the dictionary, optional.
	last_input.s				; Handy last input helper
	last_suggestion.s			; Likewise but it holds the last "best" suggestion, in case you don't want to go through the list.
	List dictionary.AUTOCOMPLETE_ENTRY()	; Holds complete words or sentences, it is our database.
	List suggestion.AUTOCOMPLETE_ENTRY()	; This list will be populated with results once GetSuggestion is called.
EndStructure

Declare.i AutoComplete_LoadDictionary( *this.AUTOCOMPLETE, DictionaryFile.s )
Declare.i AutoComplete_SaveDictionary( *this.AUTOCOMPLETE, DictionaryFile.s = "" )

Procedure.i AutoComplete_Create( DictionaryFile.s = "" )
	; Creates an instance of the AutoComplete library.
	
	Define.AUTOCOMPLETE *this = AllocateMemory( SizeOf( AUTOCOMPLETE ) )
	If *this
		
		InitializeStructure( *this, AUTOCOMPLETE )
		
		If DictionaryFile
			AutoComplete_LoadDictionary( *this, DictionaryFile )
		EndIf
		
		ProcedureReturn *this	
	EndIf
	
EndProcedure

Procedure.i AutoComplete_Destroy( *this.AUTOCOMPLETE, AutoSave.i = #False )
	; Destroys an instance of the AutoComplete library.
	
	If *this
		
		If AutoSave
			AutoComplete_SaveDictionary( *this )	
		EndIf
		
		ClearStructure( *this, AUTOCOMPLETE )
		FreeMemory( *this )
	EndIf
	
EndProcedure

Procedure.s AutoComplete_GetSuggestion( *this.AUTOCOMPLETE, PartialInput.s, Headroom.i = 4 )
	; Generates a suggestion list based on input string.
	; The Headroom variable limits how bigger a suggestion can be, compared to the input length.
	
	If *this
		
		Define.i PartialFindLength	= 99999
		Define.i PartialInputLength 	= Len( PartialInput )
		
		If PartialInputLength > 0
			
			ClearList( *this\suggestion() )
			
			ForEach *this\dictionary()
				
				If Left( *this\dictionary()\word, PartialInputLength ) = PartialInput
					
					If *this\dictionary()\word = PartialInput
						*this\dictionary()\hits + 1
					EndIf
					
					If *this\dictionary()\length < PartialFindLength + Headroom
						
						PartialFindLength = *this\dictionary()\length
						
						If AddElement(*this\suggestion())
							*this\suggestion() 	= *this\dictionary()
							*this\last_suggestion 	= *this\suggestion()\word
						EndIf
						
					EndIf
				EndIf
				
			Next
			
			SortStructuredList( *this\suggestion(),  #PB_Sort_Integer, OffsetOf( AUTOCOMPLETE_ENTRY\hits ), #PB_Sort_Descending )
			ProcedureReturn *this\last_suggestion
			
		EndIf
	EndIf
	
EndProcedure

Procedure.i AutoComplete_AddWord( *this.AUTOCOMPLETE, Word.s, Hits.i = 0 )
	; Adds a word to the dictionary.
	
	If *this
		
		If AddElement( *this\dictionary() )
			*this\dictionary()\word 	= Word
			*this\dictionary()\length 	= Len(Word)
			*this\dictionary()\hits 	= Hits
		EndIf
		
		ProcedureReturn #True
	EndIf
	
EndProcedure

Procedure.i AutoComplete_ClearHits( *this.AUTOCOMPLETE )
	; Clears all word hits from the dictionary.
	
	If *this
		
		ForEach *this\dictionary()
			*this\dictionary()\hits = 0
		Next
		
		ProcedureReturn #True
	EndIf
	
EndProcedure

Procedure.i AutoComplete_LoadDictionary( *this.AUTOCOMPLETE, DictionaryFile.s )
	; Loads a dictionary from a file.
	
	If *this
		If DictionaryFile
			
			Define.s sInput, sOutput
			Define.i Hits = 0
			Define.i fp = ReadFile( #PB_Any, DictionaryFile )
			
			If IsFile( fp )
				
				*this\DictionaryFileName = DictionaryFile
				
				While Not Eof( fp )
					
					sInput = ReadString( fp )
					
					If FindString( sInput, ",", 1 ) ; If there's a comma in the line, then it means we have to load the hits.
						
						sOutput = StringField( sInput, 1, "," )
						Hits 	= Val( StringField( sInput, 2, "," ) )
						
					Else ; Otherwise no hits are present in the dictionary file, assume 0.
						
						sOutput = sInput
						Hits	= 0
						
					EndIf
					
					AutoComplete_AddWord( *this, sOutput, Hits )
				Wend
				
				CloseFile( fp )	
			EndIf
			
		EndIf
	EndIf
	
EndProcedure

Procedure.i AutoComplete_SaveDictionary( *this.AUTOCOMPLETE, DictionaryFile.s = "" )
	; Saves the dictionary to a file.
	
	If *this
		
		If DictionaryFile = ""
			DictionaryFile = *this\DictionaryFileName	
		EndIf
		
		If DictionaryFile
			
			Define.s sInput, sOutput
			Define.i fp = CreateFile( #PB_Any, DictionaryFile )
			
			If IsFile( fp )
				
				ForEach *this\dictionary()
					
					sOutput = *this\dictionary()\word
					sOutput + "," + Str( *this\dictionary()\hits )
					WriteStringN( fp, sOutput )
					
				Next
				
				CloseFile(fp)	
			EndIf
			
		EndIf
	EndIf

EndProcedure

And a quick example:

Notice: The example requires a dictionary, you may download a sample one based on english words by clicking here.

Define.AUTOCOMPLETE *auto = AutoComplete_Create( "english.txt" ) ; load this dictionary for future auto completion assistance.
If *auto
	If OpenConsole()
		PrintN(" Type part of a word and press enter to view the suggestions" )
		Repeat
			
			Define.s in = Input()
			If in
				
				If AutoComplete_GetSuggestion( *auto, in, 2 )
					ForEach *auto\suggestion()
						PrintN( *auto\suggestion()\word + " - " + Str( *auto\suggestion()\hits ) )
					Next
					PrintN("")
				EndIf
				
			EndIf
			
			Delay(100)
		Until Inkey() = Chr(27) Or in = "exit"
		
		CloseConsole()
	EndIf
	
	AutoComplete_Destroy( *auto, #True ) ; Because we loaded a dictionary, if we pass True as the second parameter, the dictionary will be saved before the instance is destroyed.
EndIf

Another good point about this library is that it’s 100% cross-platform, so you’re not depending on the OS to auto-complete your fields and like I said before, you could easily implement it in your game, etc. A bad point is that it includes no error handling at the moment.

That’s it for now, you can download the entire source here. And a sample dictionary here.

Cheers!

0 Comments on AutoComplete Library

Closed