#include-once
; #INDEX# =======================================================================================================================
; Title .........: hash table in pure AutoIt
; Version .......: 0.8
; AutoIt Version : 3.3.16.1
; Language ......: English
; Description ...: An implementation of a hash table with dynamic resizing written in AutoIt.
;                  A productive use of this UDF is not intended due to the alternatives AutoIt-Map and Scripting.Dictionary object.
;                  The actual reason for this UDF is pedagogical and is intended to make the functionality of a hash table understandable using AutoIt code.
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; License .......: This work is free.
;                  You can redistribute it and/or modify it under the terms of the Do What The Fuck You Want To Public License, Version 2,
;                  as published by Sam Hocevar.
;                  See http://www.wtfpl.net/ for more details.
; ===============================================================================================================================

; #CURRENT# =====================================================================================================================
; _hashtable_create            - builds and returns a new empty hash-table
; _hashtable_add               - add elements or overwrite if key already exists
; _hashtable_get               - get value of an element by it's key
; _hashtable_Remove            - remove element froma a hash-table by it's key
; _hashtable_getKeys           - get array of all keys in a hash-table
; _hashtable_getValues         - get array of all values in a hash-table
; _hashtable_getKeyValues      - get 2D-Array of all key-value pairs
; _hashtable_getUsedIndexCount - count the number of used indices of the main array
; ===============================================================================================================================

; #INTERNAL_USE_ONLY# ===========================================================================================================
; __hashtable_Hash             - calculate a integer hash-value for a key
; __hashtable_getIndex         - calculate the Index of an hash for the main array out of the hash-value
; __hashtable_resize           - resize the main array of a hash-table to a new size
; ===============================================================================================================================


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_create
; Description ...: builds and returns a new empty hash-table
; Syntax ........: _hashtable_create()
; Parameters ....: None
; Return values .: a empty hash-table (a 1D array on low level)
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; Remarks .......: the element counter is written to $aHash[0]
; ===============================================================================================================================
Func _hashtable_create()
	; begin with size 256 like AutoIt Maps
	Local $aHash[257] = [0]

	; return Array
	Return $aHash
EndFunc   ;==>_hashtable_create


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_add
; Description ...: add elements or overwrite if key already exists
; Syntax ........: _hashtable_add(ByRef $aHash,  $sKey,  $vValue)
; Parameters ....: $aHash               - [in/out] the hash-table-variable where the element should be added
;                  $sKey                - the key under which the element to be added is indexed
;                  $vValue              - the value of the element to be added
; Return values .: True and set @extended to:
;                             0 - new element
;                             1 - element overwrite
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_add(ByRef $aHash, $sKey, $vValue)
	; collision handling used: chaining up to 4 subelements, if more then resizing array

	Local $iElements = $aHash[0], $iSize = UBound($aHash) - 1

	; check if resizing is necessary (parameters need optimization - here only a demonstration)
	If $iElements > ($iSize / 2) Then
		__hashtable_resize($aHash, $iElements * 3)
		$iSize = UBound($aHash) - 1
	EndIf

	; calculate the hash-value for $sKey
	Local $iHash = __hashtable_Hash($sKey)

	; calculate the index out of the hash (map the hash value to the index space)
	Local $iIndex = __hashtable_getIndex($iHash, $iSize)

	; check if index is already used (collision)
	Local $vTmp = $aHash[$iIndex]
	If IsArray($vTmp) Then    ; collision
		; check if key already exists and overwrite value
		For $i = 0 To UBound($vTmp) - 1
			If $vTmp[$i][0] = $sKey Then
				$vTmp[$i][1] = $vValue

				$aHash[$iIndex] = $vTmp
				Return SetExtended(1, True)
			EndIf
		Next

		; add new element
		ReDim $vTmp[UBound($vTmp) + 1][3]        ; also save hash-value to boost the resize (to avoid multiple hashing)
		$vTmp[UBound($vTmp) - 1][0] = $sKey
		$vTmp[UBound($vTmp) - 1][1] = $vValue
		$vTmp[UBound($vTmp) - 1][2] = $iHash

		; overwrite subarray
		$aHash[$iIndex] = $vTmp

		; too much collisions - so better resize
		If UBound($vTmp) > 4 Then __hashtable_resize($aHash, $iElements * 3)

	Else ; no collision
		Local $aTmp[][3] = [[$sKey, $vValue, $iHash]]
		$aHash[$iIndex] = $aTmp
	EndIf

	; increment element counter
	$aHash[0] += 1

	Return SetExtended(0, True)
EndFunc   ;==>_hashtable_add


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_get
; Description ...: get value of an element by it's key
; Syntax ........: _hashtable_get(ByRef $aHash,  $sKey)
; Parameters ....: $aHash               - [in/out] the hash-table variable
;                  $sKey                - the key of the element
; Return values .: Success: the value of the element
;                  Failure: Null and set @error to:
;                           1 - element with that key not found
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_get(ByRef $aHash, $sKey)
	Local $iSize = UBound($aHash) - 1

	; calculate the hash-value for $sKey
	Local $iHash = __hashtable_Hash($sKey)

	; calculate the index out of the hash (map the hash value to the index space)
	Local $iIndex = __hashtable_getIndex($iHash, $iSize)

	; linear search for key because of possible element chaining
	Local $aTmp = $aHash[$iIndex]
	For $i = 0 To UBound($aTmp) - 1
		If $aTmp[$i][0] = $sKey Then Return $aTmp[$i][1] ; element found
	Next

	Return SetError(1, $iIndex, Null) ; element not found

EndFunc   ;==>_hashtable_get


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_Remove
; Description ...: remove element froma a hash-table by it's key
; Syntax ........: _hashtable_Remove(ByRef $aHash,  $sKey)
; Parameters ....: $aHash               - [in/out] the hash-table variable
;                  $sKey                - the key of the element
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_Remove(ByRef $aHash, $sKey)
	Local $iElements = $aHash[0], $iSize = UBound($aHash) - 1

	; calculate the hash-value for $sKey
	Local $iHash = __hashtable_Hash($sKey)

	; calculate the index out of the hash (map the hash value to the index space)
	Local $iIndex = __hashtable_getIndex($iHash, $iSize)

	; navigate to the element (if exists)
	Local $aTmp = $aHash[$iIndex]

	; iterate over the elements at this index (multiple elements are possible due to index collisions)
	For $i = 0 To UBound($aTmp) - 1

		If $aTmp[$i][0] = $sKey Then

			If UBound($aTmp) > 1 Then ; delete row
				For $j = $i + 1 To UBound($aTmp) - 1
					$aTmp[$j-1][0] = $aTmp[$j][0]
					$aTmp[$j-1][1] = $aTmp[$j][1]
					$aTmp[$j-1][2] = $aTmp[$j][2]
				Next
				ReDim $aTmp[UBound($aTmp) - 1][UBound($aTmp,2)]
				$aHash[$iIndex] = $aTmp

			Else ; only one entry - delete whole subarray
				$aHash[$iIndex] = ""
			EndIf

			; decrement element counter
			$aHash[0] -= 1

			; downsize if number of elements is now much smaller than array size
			;  If $iElements < ($iSize / 5) Then __hashtable_resize($aHash, $iElements / 3)

			Return SetExtended($iIndex, True)
		EndIf
	Next

	; element not found
	Return SetError(1, $iIndex, False)
EndFunc   ;==>_hashtable_Remove



; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_getKeys
; Description ...: get array of all keys in a hash-table
; Syntax ........: _hashtable_getKeys(ByRef $aHash)
; Parameters ....: $aHash               - [in/out] the hash-table variable
; Return values .: 1D-Array of with all keys inside the hash-table
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_getKeys(ByRef $aHash)
	Local $aRet[$aHash[0]] ; create return array
	Local $iCur = 0, $aTmp

	; iterate over all keys
	For $i = 1 To UBound($aHash) - 1
		$aTmp = $aHash[$i]
		If IsArray($aTmp) And UBound($aTmp, 0) = 2 And UBound($aTmp) > 0 Then
			For $j = 0 To UBound($aTmp) - 1
				$aRet[$iCur] = $aTmp[$j][0]
				$iCur += 1
			Next
		EndIf
	Next

	Return $aRet
EndFunc   ;==>_hashtable_getKeys


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_getValues
; Description ...: get array of all values in a hash-table
; Syntax ........: _hashtable_getValues(ByRef $aHash)
; Parameters ....: $aHash               - [in/out] the hash-table variable
; Return values .: 1D-Array with all values inside the hash-table
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_getValues(ByRef $aHash)
	Local $aRet[$aHash[0]] ; create return array
	Local $iCur = 0, $aTmp

	; iterate over all values
	For $i = 1 To UBound($aHash) - 1
		$aTmp = $aHash[$i]

		If IsArray($aTmp) And UBound($aTmp, 0) = 2 And UBound($aTmp) > 0 Then
			For $j = 0 To UBound($aTmp) - 1
				$aRet[$iCur] = $aTmp[$j][1]
				$iCur += 1
			Next
		EndIf
	Next

	Return $aRet
EndFunc   ;==>_hashtable_getValues


; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_getKeyValues
; Description ...: get 2D-Array of all key-value pairs
; Syntax ........: _hashtable_getKeyValues(ByRef $aHash)
; Parameters ....: $aHash               - [in/out] the hash-table variable
; Return values .: 2D-Array with all key-value-pairs inside the hash-table
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_getKeyValues(ByRef $aHash)
	Local $aRet[$aHash[0]][2] ; create return array
	Local $iCur = 0, $aTmp

	; iterate over all values
	For $i = 1 To UBound($aHash) - 1
		$aTmp = $aHash[$i]

		If IsArray($aTmp) And UBound($aTmp, 0) = 2 And UBound($aTmp) > 0 Then
			For $j = 0 To UBound($aTmp) - 1
				$aRet[$iCur][0] = $aTmp[$j][0]
				$aRet[$iCur][1] = $aTmp[$j][1]
				$iCur += 1
			Next
		EndIf
	Next

	Return $aRet
EndFunc   ;==>_hashtable_getKeyValues

; #FUNCTION# ====================================================================================================================
; Name ..........: _hashtable_getUsedIndexCount
; Description ...: count the number of used indices of the main array (a quality parameter - especially in relation to the number of elements)
; Syntax ........: _hashtable_getUsedIndexCount($aHash)
; Parameters ....: $aHash               - the hash-table variable
; Return values .: number of used indices of the main array
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func _hashtable_getUsedIndexCount($aHash)
	Local $iC = 0

	For $i = 1 To UBound($aHash) - 1
		If IsArray($aHash[$i]) Then $iC += 1
	Next
	Return $iC
EndFunc


; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __hashtable_Hash
; Description ...: calculate a integer hash-value for a key
; Syntax ........: __hashtable_Hash(ByRef $sKey)
; Parameters ....: $sKey                - [in/out] the key for which the hash should calculated (should be a string)
; Return values .: the hash-value (a integer-value)
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; Remarks .......: The djb2-algorithm is used as hash-function.
;                  Due to the fact that there are already collision generators for this, this function is strictly speaking not ideal for a hash table.
;                  In AutoIt, however, it can be calculated quite performantly, which is why the choice fell on this function.
; ===============================================================================================================================
Func __hashtable_Hash(ByRef $sKey)
	Local $hash = 5381
	For $c In StringToASCIIArray($sKey)
		$hash = $hash * 33 + $c ; faster in AutoIt than this common form: $hash += BitShift($hash, -5) + $c
	Next
	Return $hash
EndFunc   ;==>__hashtable_Hash


; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __hashtable_getIndex
; Description ...: calculate the Index of an hash for the main array out of the hash-value (map the hash value to the index space)
; Syntax ........: __hashtable_getIndex($iHash,  $iSize)
; Parameters ....: $iHash               - the hash-value
;                  $iSize               - the size of the main array of the hash-table
; Return values .: the array index for the hash-value
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; ===============================================================================================================================
Func __hashtable_getIndex($iHash, $iSize)
	Return Abs(Mod($iHash, $iSize)) + 1  ; +1 because Index range = 1..$iSize
EndFunc   ;==>__hashtable_getIndex


; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __hashtable_resize
; Description ...: resize the main array of a hash-table to a new size
; Syntax ........: __hashtable_resize(ByRef $aHash,  $iNewSize)
; Parameters ....: $aHash               - [in/out] the hash-table variable
;                  $iNewSize            - The new size to which the hash table is to be resized
; Return values .: None
; Author ........: AspirinJunkie
; Modified ......: 2021-07-30
; Remarks .......: A resize is made because of a trade-off between performance and memory requirements.
;                  If a hash table is too small, a large number of index collisions occur and access is slower, 
;                  since subarrays for the individual indices must be searched linearly.
;                  On the other hand, if a hash table is too large, a lot of memory is wasted that is not actually needed. 
; ===============================================================================================================================
Func __hashtable_resize(ByRef $aHash, $iNewSize)
	Local $iElements = $aHash[0], $iSize = UBound($aHash) - 1, $aTmp

	; create a empty array with newSize
	Local $aRet[$iNewSize + 1] = [$iElements]

	; iterate over old elements and use _hashtable_add to new array
	For $i = 1 To $iSize
		$aTmp = $aHash[$i]
		If Not IsArray($aTmp) Then ContinueLoop ; no element at index

		For $j = 0 To UBound($aTmp) - 1

			; calculate the index
			Local $iIndex = __hashtable_getIndex($aTmp[$j][2], $iNewSize)

			; check if index is already used (collision)
			Local $vTmp = $aRet[$iIndex]
			If IsArray($vTmp) Then ; collision

				; add new element
				ReDim $vTmp[UBound($vTmp) + 1][3]
				$vTmp[UBound($vTmp) - 1][0] = $aTmp[$j][0]
				$vTmp[UBound($vTmp) - 1][1] = $aTmp[$j][1]
				$vTmp[UBound($vTmp) - 1][2] = $aTmp[$j][2]

				; overwrite subarray
				$aRet[$iIndex] = $vTmp

			Else ; no collision
				Local $aTemp[1][3] = [[$aTmp[$j][0], $aTmp[$j][1], $aTmp[$j][2]]]
				$aRet[$iIndex] = $aTemp
			EndIf
		Next
	Next

	; overwrite old array with new one
	$aHash = $aRet
EndFunc   ;==>__hashtable_resize