Sign in to follow this  
Followers 0
GrahamS

Associative Array

2 posts in this topic

#1 ·  Posted (edited)

An updated associative array (see New Datatype, VB=Dictionary, Ruby=Hash)

BTW watch out for the wrapped lines

#include-once
;------------------------------------------------------------------------------
;
; AutoIt Version: 3.0
;
; Script Function:
;  "Hash" - an associative container of key/value pairs
;
; Note that the name is taken from the Perl "Hash" and is not a "hash table"
;
; Author:         Graham Shanks
;
; Version 1.0   28/01/2004  Initial release
; Version 1.1   10/03/2004  Initial release
;------------------------------------------------------------------------------


;------------------------------------------------------------------------------
; Description:  Create a hash (associative array) from a string containing a 
;               series of key/value pairs
;
; Parameters:
;   $string     A string containing the data to be entered into the hash
;   $sep1       The delimeter between elements
;   $sep2       The delimeter between the key and the value within the element
;
; Returns:
;   Success:    The hash. 
;   Failure:    If any of the elements do not contain a key/value pair (i.e.
;               $sep2 is not contained in in the element) then @error is set 
;               to the index of the offending element. An empty hash is 
;               returned
;
; Example:
;
;   $dLanguages = HashCreate("0436:Afrikaans\041c:Albanian\0401:Arabic Saudi Arabia\0801:Arabic Iraq\0c01:Arabic Egypt\1001:Arabic Libya\0409:English", "\", ":")
;
;   MsgBox(4096 +64,"","Your PC speaks " & HashLookUp($dLanguages, @OSLANG))
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($dLanguages,"0436"))
;------------------------------------------------------------------------------
Func HashCreate($string, $sep1, $sep2)
  Local $Result[3]

  $temp = StringSplit($string, $sep1)

  Local $keys[$temp[0]]
  Local $data[$temp[0]]

  for $i = 1 to $temp[0]
    $split = StringSplit($temp[$i], $sep2)
    if @error == 1 then
      $Result[0] = 0
      $Result[1] = 0
      $Result[2] = 0
      SetError($i)
      return $Result
    endif
    $keys[$i-1] = $split[1]
    $data[$i-1] = $split[2]
  next

; sort on BOTH $keys AND $data
  HashQuickSort($keys, $data, 0, $temp[0]-1)

  $Result[0] = $temp[0]
  $Result[1] = $keys
  $Result[2] = $data
  return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Create an empty hash (associative array)
;
; Returns:      The hash. 
;
; Example:
;
;   $hash = HashCreateEmpty()
;
;------------------------------------------------------------------------------
Func HashCreateEmpty()
  Local $Result[3]
  $Result[0] = 0
  $Result[1] = 0
  $Result[2] = 0
  return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Insert a key/value pair into a hash (associative array)
;
; Parameters:
;   $hash       The hash
;   $key        The key
;   $value      The value associated with teh key
;
; Returns:      Nothing
;
; Example:
;
;   $hash = HashCreateEmpty()
;   HashInsert($hash, "0436", "Afrikans")
;
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($hash,"0436"))
;
;------------------------------------------------------------------------------
Func HashInsert(ByRef $hash, $key, $value)
  Local $keys[HashSize($hash)+1]
  Local $data[HashSize($hash)+1]

  for $i = 0 to HashSize($hash)-1
    $keys[$i] = HashKey($hash, $i)
    $data[$i] = HashData($hash, $i)
  next
  $keys[HashSize($hash)] = $key
  $data[HashSize($hash)] = $value
  HashQuickSort($keys, $data, 0, HashSize($hash))
  $hash[0] = HashSize($hash)+1
  $hash[1] = $keys
  $hash[2] = $data
EndFunc

;------------------------------------------------------------------------------
; Description:  Look up the value associated with the specified key in the 
;               specified hash
;
; Parameters:
;   $hash       The hash
;   $key        The key to look up
;
; Returns:
;   Success:    The value associated with the specified key
;   Failure:    If the key is not in the hash, then zero is returned and 
;               @Error is set to 1
;------------------------------------------------------------------------------
Func HashLookUp(ByRef $hash, $key)
  $l = 0
  $u = HashSize($hash) - 1
  while $l <= $u
    $m = int(($l+$u)/2)
    $t = HashKey($hash, $m)
    if $t < $key then
      $l = $m + 1
    else
      if $t > $key then
        $u = $m - 1
      else
        return HashData($hash, $m)
      endif
    endif
  wend

  SetError(1)
  return 0
EndFunc

;------------------------------------------------------------------------------
; Description:  Gets the size of the specified hash container
;
; Parameters:
;   $hash       The hash
;
; Returns:      The number of key/value pairs in the hash
;------------------------------------------------------------------------------
Func HashSize(ByRef $hash)
  return $hash[0]
EndFunc

;------------------------------------------------------------------------------
; The following functions are for internal use and are not intended for use by 
; users. Ignore this and on your own head be it :-)
;------------------------------------------------------------------------------

; Gets the key at the specified position
Func HashKey(ByRef $hash, $index)
  return HashKeyHelper($hash[1],$index)
EndFunc

; Gets the data at the specified position
Func HashData(ByRef $hash, $index)
  return HashDataHelper($hash[2],$index)
EndFunc

; Helper function for HashKey
Func HashKeyHelper(ByRef $keys, $index)
  return $keys[$index]
EndFunc

; Helper function for HashData
Func HashDataHelper(ByRef $data, $index)
  return $data[$index]
EndFunc

Func HashIndexFind(ByRef $hash, $key)
  $l = 0
  $u = HashSize($hash) - 1
  while $l <= $u
    $m = int(($l+$u)/2)
    $t = HashKey($hash, $m)
    if $t < $key then
      $l = $m + 1
    else
      if $t > $key then
        $u = $m - 1
      else
        return $m
      endif
    endif
  wend

  SetError(1)
  return 0
EndFunc

; Debug aid - gathers the contents into a string
Func HashDisplay(ByRef $hash)
  $dummy = ""
  for $i = 0 to HashSize($hash)-1
    $dummy = $dummy & " " & $i & " <" & HashKey($hash, $i) & "> <" & HashIndexFind($hash, $i) & "> <" & HashData($hash,$i) & ">" & @CRLF
  next
  return $dummy
EndFunc

; Get a random value in the range $l to $u
Func HashRandInt($l, $u)
  return $l + int(($u - $l + 1) * Random(0, 1))
EndFunc

; Swap two element
Func HashSwap(ByRef $a, ByRef $b)
  $temp = $a
  $a = $b
  $b = $temp
EndFunc

; Quick sort routine - uses insertion sort on small subfiles
Func HashQuickSort(ByRef $keys, ByRef $data, $l, $u)
  while 1
    if $u - $l < 9 then
    ; Insertion sort
      for $step = $l to $u
        $dummy1 = $keys[$step]
        $dummy2 = $data[$step]
        for $j = $step-1 to $l step -1
          if $keys[$j] > $dummy1 then
            $keys[$j+1] = $keys[$j]
            $data[$j+1] = $data[$j]
          else
            exitloop
          endif
        next
        $keys[$j+1] = $dummy1
        $data[$j+1] = $dummy2
      next
      return
    else
    ; The actual quick sort
      $x = HashRandInt($l, $u)
      HashSwap($keys[$l], $keys[$x])
      HashSwap($data[$l], $data[$x])
      $t = $keys[$l]
      $m = $l
      for $i = $l + 1 to $u
        if $keys[$i] < $t then
          $m = $m + 1
          HashSwap($keys[$m], $keys[$i])
          HashSwap($data[$m], $data[$i])
        endif
      next
      HashSwap($keys[$l], $keys[$m])
      HashSwap($data[$l], $data[$m])
      HashQuickSort($keys, $data, $l, $m - 1)
      $l = $m + 1
    endif
  wend
EndFunc
Edited by GrahamS

GrahamS

Share this post


Link to post
Share on other sites



Update to add function to change the value associated with a key already in the associative array

#include-once
;------------------------------------------------------------------------------
;
; AutoIt Version: 3.0
;
; Script Function:
;  "Hash" - an associative container of key/value pairs
;
; Note that the name is taken from the Perl "Hash" and is not a "hash table"
;
; Author:         Graham Shanks
;
; Version 1.0   28/01/2004  Initial release
; Version 1.1   10/03/2004  Added HashCreateEmpty and HashInsert
; Version 1.2   04/04/2004  Added HashUpdate (plus declare all local variables as Local)
;------------------------------------------------------------------------------


;------------------------------------------------------------------------------
; Description:  Create a hash (associative array) from a string containing a 
;               series of key/value pairs
;
; Parameters:
;   $string     A string containing the data to be entered into the hash
;   $sep1       The delimeter between elements
;   $sep2       The delimeter between the key and the value within the element
;
; Returns:
;   Success:    The hash. 
;   Failure:    If any of the elements do not contain a key/value pair (i.e.
;               $sep2 is not contained in in the element) then @error is set 
;               to the index of the offending element. An empty hash is 
;               returned
;
; Example:
;
;   $dLanguages = HashCreate("0436:Afrikaans\041c:Albanian\0401:Arabic Saudi Arabia\0801:Arabic Iraq\0c01:Arabic Egypt\1001:Arabic Libya\0409:English", "\", ":")
;
;   MsgBox(4096 +64,"","Your PC speaks " & HashLookUp($dLanguages, @OSLANG))
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($dLanguages,"0436"))
;------------------------------------------------------------------------------
Func HashCreate($string, $sep1, $sep2)
  Local $Result[3]
  Local $temp, $i, $split

  $temp = StringSplit($string, $sep1)

  Local $keys[$temp[0]]
  Local $data[$temp[0]]

  for $i = 1 to $temp[0]
    $split = StringSplit($temp[$i], $sep2)
    if @error == 1 then
      $Result[0] = 0
      $Result[1] = 0
      $Result[2] = 0
      SetError($i)
      return $Result
    endif
    $keys[$i-1] = $split[1]
    $data[$i-1] = $split[2]
  next

 ; sort on BOTH $keys AND $data
  HashQuickSort($keys, $data, 0, $temp[0]-1)

  $Result[0] = $temp[0]
  $Result[1] = $keys
  $Result[2] = $data
  return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Create an empty hash (associative array)
;
; Returns:      The hash. 
;
; Example:
;
;   $hash = HashCreateEmpty()
;
;------------------------------------------------------------------------------
Func HashCreateEmpty()
  Local $Result[3]
  $Result[0] = 0
  $Result[1] = 0
  $Result[2] = 0
  return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Insert a key/value pair into a hash (associative array)
;
; Parameters:
;   $hash       The hash
;   $key        The key
;   $value      The value associated with the key
;
; Returns:      Nothing
;
; Example:
;
;   $hash = HashCreateEmpty()
;   HashInsert($hash, "0436", "Afrikans")
;
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($hash,"0436"))
;
;------------------------------------------------------------------------------
Func HashInsert(ByRef $hash, $key, $value)
  Local $keys[HashSize($hash)+1]
  Local $data[HashSize($hash)+1]
  Local $i

  for $i = 0 to HashSize($hash)-1
    $keys[$i] = HashKey($hash, $i)
    $data[$i] = HashData($hash, $i)
  next
  $keys[HashSize($hash)] = $key
  $data[HashSize($hash)] = $value
  HashQuickSort($keys, $data, 0, HashSize($hash))
  $hash[0] = HashSize($hash)+1
  $hash[1] = $keys
  $hash[2] = $data
EndFunc

;------------------------------------------------------------------------------
; Description:  Look up the value associated with the specified key in the 
;               specified hash
;
; Parameters:
;   $hash       The hash
;   $key        The key to look up
;
; Returns:
;   Success:    The value associated with the specified key
;   Failure:    If the key is not in the hash, then zero is returned and 
;               @Error is set to 1
;------------------------------------------------------------------------------
Func HashLookUp(ByRef $hash, $key)
  Local $l, $u, $m, $t
  $l = 0
  $u = HashSize($hash) - 1
  while $l <= $u
    $m = int(($l+$u)/2)
    $t = HashKey($hash, $m)
    if $t < $key then
      $l = $m + 1
    else
      if $t > $key then
        $u = $m - 1
      else
        return HashData($hash, $m)
      endif
    endif
  wend

  SetError(1)
  return 0
EndFunc

;------------------------------------------------------------------------------
; Description:  Gets the size of the specified hash container
;
; Parameters:
;   $hash       The hash
;
; Returns:      The number of key/value pairs in the hash
;------------------------------------------------------------------------------
Func HashSize(ByRef $hash)
  return $hash[0]
EndFunc

;------------------------------------------------------------------------------
; Description:  Update the value associated with a specified key. If the key is
;               not found in the asspciative array then it is added. If the
;               key is found in the array then the current associated value is
;               replaced with the new value
;
; Parameters:
;   $hash       The hash
;   $key        The key
;   $value      The value associated with the key
;
; Returns:      The number of key/value pairs in the hash
;------------------------------------------------------------------------------
Func HashUpdate(ByRef $hash, $key, $value)
  Local $i

  $i = HashKeyIndex($hash, $key)
  if @error = 1 then
   ; Not in hash, insert it
    HashInsert($hash, $key, $value)
  else
    HashSetDataHelper($hash[2], $i, $value)
  endif
  return $hash[0]
EndFunc

;------------------------------------------------------------------------------
; Description:  Gets the key at the specified position. This can be used to
;               iterate over the elements in the associative array
;
; Parameters:
;   $hash       The hash
;   $index      The index, must be in range 0 to HashSize() - 1
;
; Returns:      The key at the specified position
;
; Example:
;
; For $i = 0 To HashSize($hash) - 1
;   $string = $string & $i & " " & HashKey($hash, $i) & ": " & HashData($hash, $i) & @LF
; Next
;------------------------------------------------------------------------------
Func HashKey(ByRef $hash, $index)
  return HashKeyHelper($hash[1],$index)
EndFunc

;------------------------------------------------------------------------------
; Description:  Gets the data value at the specified position. This can be used
;               to iterate over the elements in the associative array
;
; Parameters:
;   $hash       The hash
;   $index      The index, must be in range 0 to HashSize() - 1
;
; Returns:      The data value at the specified position
;------------------------------------------------------------------------------
Func HashData(ByRef $hash, $index)
  return HashDataHelper($hash[2],$index)
EndFunc

;------------------------------------------------------------------------------
; The following functions are for internal use and are not intended for use by 
; users. Ignore this and on your own head be it :-)
;------------------------------------------------------------------------------

; Helper function for HashKey
Func HashKeyHelper(ByRef $keys, $index)
  return $keys[$index]
EndFunc

; Helper function for HashData
Func HashDataHelper(ByRef $data, $index)
  return $data[$index]
EndFunc

; Helper function to set data
Func HashSetDataHelper(ByRef $data, $index, $value)
  $data[$index] = $value
EndFunc

; Debug aid - gathers the contents into a string
Func HashDisplay(ByRef $hash)
  Local $dummy, $i

  $dummy = ""
  for $i = 0 to HashSize($hash)-1
    $dummy = $dummy & " " & $i & " <" & HashKey($hash, $i) & "> <" & HashData($hash,$i) & ">" & @CRLF
  next
  return $dummy
EndFunc

; Gets the index associate with a specified key (@error = 1 if key not in hash)
Func HashKeyIndex(ByRef $hash, $key)
  Local $l, $u, $m, $t
  $l = 0
  $u = HashSize($hash) - 1
  while $l <= $u
    $m = int(($l+$u)/2)
    $t = HashKey($hash, $m)
    if $t < $key then
      $l = $m + 1
    else
      if $t > $key then
        $u = $m - 1
      else
        return $m
      endif
    endif
  wend

  SetError(1)
  return 0
EndFunc

; Get a random value in the range $l to $u
Func HashRandInt($l, $u)
  return $l + int(($u - $l + 1) * Random(0, 1))
EndFunc

; Swap two element
Func HashSwap(ByRef $a, ByRef $b)
  Local $temp

  $temp = $a
  $a = $b
  $b = $temp
EndFunc

; Quick sort routine - uses insertion sort on small subfiles
Func HashQuickSort(ByRef $keys, ByRef $data, $l, $u)
  Local $step, $dummy1, $dummy2, $x, $t, $m, $i

  while 1
    if $u - $l < 9 then
     ; Insertion sort
      for $step = $l to $u
        $dummy1 = $keys[$step]
        $dummy2 = $data[$step]
        for $j = $step-1 to $l step -1
          if $keys[$j] > $dummy1 then
            $keys[$j+1] = $keys[$j]
            $data[$j+1] = $data[$j]
          else
            exitloop
          endif
        next
        $keys[$j+1] = $dummy1
        $data[$j+1] = $dummy2
      next
      return
    else
     ; The actual quick sort
      $x = HashRandInt($l, $u)
      HashSwap($keys[$l], $keys[$x])
      HashSwap($data[$l], $data[$x])
      $t = $keys[$l]
      $m = $l
      for $i = $l + 1 to $u
        if $keys[$i] < $t then
          $m = $m + 1
          HashSwap($keys[$m], $keys[$i])
          HashSwap($data[$m], $data[$i])
        endif
      next
      HashSwap($keys[$l], $keys[$m])
      HashSwap($data[$l], $data[$m])
      HashQuickSort($keys, $data, $l, $m - 1)
      $l = $m + 1
    endif
  wend
EndFunc

GrahamS

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0