// --------------------------------- //
// Project: ddd
// Start: Tuesday, October 05, 2010
// IDE Version: 8.120

//! TMap allows the mapping of a string to a value.  It uses a fast binary search on sorted key values to quick find the associated value for a key

TYPE tKeyValue
	key$
	value$
	used%
ENDTYPE

TYPE TMap
	list[] AS tKeyValue
	INVALID%	=	-1

	//! Initialise type
	//\param None
	//\return TRUE
	FUNCTION Initialise%:
		RETURN self.Destroy()
	ENDFUNCTION

	//! Destroy type
	//\param None
	//\return TRUE
	FUNCTION Destroy%:
		DIM self.list[0]
		RETURN TRUE
	ENDFUNCTION

	//! Add a key and value to the internal array, and sort array afterwards.  There can only be one unique key
	//\param key$ - Key to add
	//\param value$ - Value of key
	//\return TRUE if the key and value has been added, FALSE otherwise
	FUNCTION Add%:key$,value$
	LOCAL temp AS tKeyValue

		IF self.search(key$)=self.INVALID%
			// Found
			temp.key$=key$
			temp.value$=value$
			temp.used%=FALSE
			DIMPUSH self.list[],temp
			SORTARRAY self.list[],0
			RETURN TRUE
		ELSE
			DEBUG "Duplicate found : "+key$+ "Value : "+value$+"\n"
		ENDIF

		RETURN FALSE
	ENDFUNCTION

	//! Internal use only - DO NOT USE.  Used to search for a key string as quickly as possibly
	//\param key$ - Key to search for
	//\return self.INVALID% if key not found, <>self.INVALID% is the index that the key was found
	FUNCTION search%:key$
	LOCAL up%,down%,mid%

		up%=0
		down%=BOUNDS(self.list[],0)
		WHILE up%<down%
			mid%=up%+(down%-up%)/2
			IF self.list[mid%].key$>key$
				down%=mid% // MAX(mid%-1,up%)
			ELSEIF self.list[mid%].key$<key$
				up%=mid%+1 // MIN(down%,mid%+1)
			ELSE
				self.list[mid%].used%=TRUE
				RETURN mid% // Found
			ENDIF
		WEND

		RETURN self.INVALID%
	ENDFUNCTION

	//! Generates debug information, which outputs all key and associated values to the GLBasic output window
	//\param None
	//\return NONE
	FUNCTION StatusReport%:
	LOCAL loop AS tKeyValue

		FOREACH loop IN self.list[]
			DEBUG "Key : "+loop.key$+" Value : "+loop.value$+" Used : "+loop.used%+"\n"
		NEXT
		DEBUG "Number of keys and values : "+BOUNDS(self.list[],0)+"\n"
	ENDFUNCTION

	//! Returns the value of a key (if present)
	//\param key$ - Key to search
	//\param notFound$ - Default text to return of key has not been found
	//\return Value of key, or the contents of notFound$ if key has not been found
	FUNCTION GetValue$:key$,notFound$="NOT_FOUND"
	LOCAL index%

		index%=self.search(key$)
		IF index%=self.INVALID%
			RETURN notFound$
		ELSE
			RETURN self.list[index%].value$
		ENDIF
	ENDFUNCTION

	//! Delete a key and value pair
	//\param key$ - Key to delete
	//\return TRUE if the key has been found, FALSE otherwise
	FUNCTION DeleteKey%:key$
	LOCAL index%

		index%=self.search(key$)
		IF index%=self.INVALID%
			RETURN FALSE
		ELSE
			DIMDEL self.list[],index%
			RETURN TRUE
		ENDIF
	ENDFUNCTION

	//! Return the number of keys
	//\param none
	//\return The number of keys in the local array
	FUNCTION Count%:
		RETURN BOUNDS(self.list[],0)
	ENDFUNCTION
ENDTYPE