#include-once
; a hash-table implementation in pure AutoIt for training purposes (by AspirinJunkie)

; builds a new empty hash-table
Func _hashtable_Create()
	; begin with size 256 like AutoIt Maps
	Local $aHash[257] = [0]

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

; add elements or overwrite if key already exists (@extended = 0: new element; @extended = 1: element overwrite)
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
	Local $iHash = __hashtable_Hash($sKey)

	; calculate the index
	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


; get value by key
Func _hashtable_Get(ByRef $aHash, $sKey)
	Local $iSize = UBound($aHash) - 1

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

	; calculate the index
	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


; remove element by key
Func _hashtable_Remove(ByRef $aHash, $sKey)
	Local $iElements = $aHash[0], $iSize = UBound($aHash) - 1

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

	; calculate the index
	Local $iIndex = __hashtable_getIndex($iHash, $iSize)

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

	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

; get array of all keys
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

; get array of all values
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

; get 2D-Array of all key-value pairs
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

; count the number of used index (a quality parameter)
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

; calculate the Index of an hash in a range of size $iSize
Func __hashtable_getIndex($iHash, $iSize)
	Return Abs(Mod($iHash, $iSize)) + 1  ; +1 because Index range = 1..$iSize
EndFunc   ;==>__hashtable_getIndex

; calculate a Integer-hash value for a key
Func __hashtable_Hash($sKey)
	; djb
	Local $hash = 5381
	For $c In StringToASCIIArray($sKey)
		$hash += BitShift($hash, -5) + $c
	Next
	Return $hash
EndFunc   ;==>__hashtable_Hash

; resize a hashtable
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