Deeply nested arrays

[jvanegmond]

Edit: New problem in post #3:

Please someone tell me I am missing something obvious. That I'm either doing something completely retarded, or that this is a well documented limitation.

What exactly is happening here anyway? I have a lot of guesses but not able to fully confirm nor eliminate a single one.

expandcollapse popup

Local $a[2] = [1, 0]
Local $b[2] = ["$b", 0]
Local $c[2] = ["$c", 0]
Local $d[2] = ["$d", "End"]

$a[1] = $b
$b[1] = $c
$c[1] = $d

ConsoleWrite(s($a))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($b))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($c))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($d))
ConsoleWrite("=======================" & @CRLF)

Local $a[2] = [1, 0]
Local $b[2] = ["$b", 0]
Local $c[2] = ["$c", 0]
Local $d[2] = ["$d", "End"]

$a[1] = $b
$b[1] = $c
$c[1] = $d

ConsoleWrite(s($a))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($b))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($c))
ConsoleWrite("=======================" & @CRLF)
ConsoleWrite(s($d))
ConsoleWrite("=======================" & @CRLF)

Func s(ByRef $a, $indent = 0)
    $str_indent = ""
    For $i = 0 To $indent-1
        $str_indent &= "  "
    Next

    $ret = ""

    If IsArray($a) Then
        $ret &= @CRLF
        For $i = 0 To UBound($a)-1
            $ret &= $str_indent & "[" & $i & "]" & s($a[$i], $indent + 1) & @CRLF
        Next
    Else
        $ret &= $a
    EndIf

    Return $ret
EndFunc

Received output (just first variable):

[0]1
[1]
  [0]$b
  [1]0

=======================

Expected output:

[0]1
[1]
  [0]$b
  [1]
    [0]$c
    [1]
      [0]$d
      [1]End

=======================

Edit: Someone pointed me to this part:

$c[1] = $d
$b[1] = $c
$a[1] = $b

AutoIt is making copies of course. 8)

Typical. A few hours worth of debugging. When I post, someone finds the trivial problem in minutes.

Edited April 27, 2011 by Manadar

[jchd]

Hi Manadar,

Your assignments should be made the other way round to achieve what to expect:

$c[1] = $d

$b[1] = $c

$a[1] = $b

Too late!

Edited April 27, 2011 by jchd

[jvanegmond]

I might as well make use of this thread now that it is here.

I'm trying to implement a linked list by using 2 element arrays. First element has the value, the next element is the next array. The way it is going now, I think that every time that you assign an array to any variable (or element of variable array) AutoIt makes a (albeit recursive) copy. Going from this, I think my idea of using 2 element arrays will never work.

Anyone can confirm this from the code below?

expandcollapse popup

#include <Array.au3>

Local $a[2] = [3, 0]
Local $b[2] = ["$b", 0]
Local $c[2] = ["$c", 0]
Local $d[2] = ["$d", 0]

$c[1] = $d
$b[1] = $c
$a[1] = $b

_ListAddItem($a,"$new")

$arr = _ListGetArray($a)
_ArrayDisplay($arr)

Func _ListAddItem(ByRef $list, $item)
    Local $new[2] = [$item, 0]

    $list[0] += 1 ; increment list size
    If Not IsArray($list[1]) Then
        $list[1] = $new
    Else
        $next = $list[1]
        While 1
            ConsoleWrite(s($next))
            If Not IsArray($next[1]) Then
                $next[1] = $new
                ConsoleWrite("assigned" & @CRLF)
                ConsoleWrite(s($next))
                ExitLoop
            EndIf
            $next = $next[1]
        WEnd
    EndIf
EndFunc

Func _ListGetArray(ByRef $list)
    $count = $list[0]
    If $count = 0 Then Return 0

    Local $ret[$count]

    $next = $list[1]
    $i = 0

    While 1
        $ret[$i] = $next[0]
        $i += 1

        If Not IsArray($next[1]) Then
            ExitLoop
        EndIf

        $next = $next[1]
    WEnd

    Return $ret
EndFunc

Func s(ByRef $a, $indent = 0)
    $str_indent = ""
    For $i = 0 To $indent-1
        $str_indent &= "  "
    Next

    $ret = ""

    If IsArray($a) Then
        $ret &= @CRLF
        For $i = 0 To UBound($a)-1
            $ret &= $str_indent & "[" & $i & "]" & s($a[$i], $indent + 1) & @CRLF
        Next
    Else
        $ret &= $a
    EndIf

    Return $ret
EndFunc

Edited April 27, 2011 by Manadar

[jchd]

The problem with this

Func _ListAddItem(ByRef $list, $item)
    Local $new[2] = [$item, 0]

    $list[0] += 1 ; increment list size
    Local $next = $list[1]
    While IsArray($next[1])
        $next = $next[1]
    WEnd
    $next[1] = $new
EndFunc

is that you never change $List, only $next is assigned something ($new). You'd have to rebuild a new copy of the nested array from the bottom (the end) just like you built $a in the first place. This is going to take forever if you want to handle large lists. Why not make it the other way: add new item at [1], it would be much faster and you could make it work like you want.

Try this:

expandcollapse popup

;~ #include <Array.au3>
Local $a[2] = [0, 0]

_ListAddItem($a, "abc")
ConsoleWrite(_VarDump($a) & @LF)
_ListAddItem($a, "def")
ConsoleWrite(_VarDump($a) & @LF)
_ListAddItem($a, "new")
ConsoleWrite(_VarDump($a) & @LF)
_ListAddItem($a, "last new")
ConsoleWrite(_VarDump($a) & @LF)

$arr = _ListGetArray($a)
_ArrayDisplay($arr)

Func _ListAddItem(ByRef $list, $item)
    Local $new[2] = [$list[0] + 1, 0]
    Local $next[2] = [$item, $list[1]]
    $new[1] = $next
    $list = $new
EndFunc

Func _ListGetArray(ByRef $list)
    Local $count = $list[0]
    If $count = 0 Then Return 0
    Local $ret[$count]
    $next = $list[1]
    $i = $count - 1
    Do
        $ret[$i] = $next[0]
        $i -= 1
        $next = $next[1]
    Until Not IsArray($next[1])
    $ret[0] = $next[0]
    Return $ret
EndFunc

Func s(ByRef $a, $indent = 0)
    $str_indent = ""
    For $i = 0 To $indent-1
        $str_indent &= "  "
    Next

    $ret = ""

    If IsArray($a) Then
        $ret &= @CRLF
        For $i = 0 To UBound($a)-1
            $ret &= $str_indent & "[" & $i & "]" & s($a[$i], $indent + 1) & @CRLF
        Next
    Else
        $ret &= $a
    EndIf

    Return $ret
EndFunc

Func _VarDump(ByRef $vVar, $sIndent = '')
    Select
        Case IsDllStruct($vVar)
            Return 'Struct(' & DllStructGetSize($vVar) & ') @:' & Hex(DllStructGetPtr($vVar)) & ' = '  & __ShortHexDump(DllStructGetPtr($vVar, 1), DllStructGetSize($vVar))
        Case IsArray($vVar)
            Local $iSubscripts = UBound($vVar, 0)
            Local $sDims = 'Array'
            $iSubscripts -= 1
            For $i = 0 To $iSubscripts
                $sDims &= '[' & UBound($vVar, $i + 1) & ']'
            Next
            Return $sDims & @CRLF & _VarDumpArray($vVar, $sIndent)
        Case IsBinary($vVar)
            Return 'Binary(' & BinaryLen($vVar) & ') = ' & __ShortHexDump(DllStructGetPtr($vVar, 1), DllStructGetSize($vVar))
        Case IsBool($vVar)
            Return 'Boolean(' & $vVar & ')'
        Case IsFloat($vVar)
            Return 'Float(' & $vVar & ')'
        Case IsHWnd($vVar)
            Return 'HWnd(' & $vVar & ')'
        Case IsInt($vVar)
            Return 'Integer(' & $vVar & ')'
        Case IsKeyword($vVar)
            Return 'Keyword(' & $vVar & ')'
        Case IsPtr($vVar)
            Return 'Pointer(' & $vVar & ')'
        Case IsObj($vVar)
            Return 'Object(' & ObjName($vVar) & ')'
        Case IsString($vVar)
            Return 'String(' & StringLen($vVar) & ") '" & $vVar & "'"
        Case Else
            Return 'Unknown(' & $vVar & ')'
    EndSelect
EndFunc

Func _VarDumpArray(ByRef $aArray, $sIndent = '')
    Local $sDump
    Local $sArrayFetch, $sArrayRead, $bDone
    Local $iSubscripts = UBound($aArray, 0)
    Local $aUBounds[$iSubscripts]
    Local $aCounts[$iSubscripts]
    $iSubscripts -= 1
    For $i = 0 To $iSubscripts
        $aUBounds[$i] = UBound($aArray, $i + 1) - 1
        $aCounts[$i] = 0
    Next
    $sIndent &= @TAB
    While 1
        $bDone = True
        $sArrayFetch = ''
        For $i = 0 To $iSubscripts
            $sArrayFetch &= '[' & $aCounts[$i] & ']'
            If $aCounts[$i] < $aUBounds[$i] Then $bDone = False
        Next

        $sArrayRead = Execute('$aArray' & $sArrayFetch)
        If @error Then
            ExitLoop
        Else
            $sDump &= $sIndent & $sArrayFetch & ' => ' & _VarDump($sArrayRead, $sIndent)
            If Not $bDone Then
                $sDump &= @CRLF
            Else
                Return $sDump
            EndIf
        EndIf

        For $i = $iSubscripts To 0 Step -1
            $aCounts[$i] += 1
            If $aCounts[$i] > $aUBounds[$i] Then
                $aCounts[$i] = 0
            Else
                ExitLoop
            EndIf
        Next
    WEnd
EndFunc

Func __ShortHexDump($ptr, $blen)
    Local $tmpbin = DllStructCreate("byte[" & $blen & "]", $ptr)
    If $blen <= 64 Then
        Return('0x' & Hex(DllStructGetData($tmpbin, 1)))
    Else
        Return('0x' & Hex(BinaryMid(DllStructGetData($tmpbin, 1), 1, 32)) & ' ... ' & Hex(BinaryMid(DllStructGetData($tmpbin, 1), $blen - 31, 32)))
    EndIf
EndFunc

Other potential issue: the depth limit of AutoIt code when dealing with nested arrays is unknown (by me at least).

[jvanegmond]

Nicely done, jhcd, it works and gives a good insight into the problem at hand. Even when you add a new item at [1] you are still copying the remainder of the array into that new element. Then you have the first element and you copy that again into the final result. Summed up: In order to make this work you need to copy at least twice.

I'm going to abandon this approach entirely. The entire array needs to be copied recursively (even multiple times) no matter from which angle you look at it.

Edited April 27, 2011 by Manadar

[jchd]

I believe this is correct. I don't see any way to avoid two copies, unless terrible messing with pointers in the guts of AutoIt memory, with utter risks.

Other possible routes: Scripting Dictionnary, AutoIt Object, SQLite (RAM or disk).

[jvanegmond]

I believe this is correct. I don't see any way to avoid two copies, unless terrible messing with pointers in the guts of AutoIt memory, with utter risks.

Other possible routes: Scripting Dictionnary, AutoIt Object, SQLite (RAM or disk).

It's mostly an exercise, which can lead to some new insights in AutoIt and hopefully maybe even a linked list UDF. Right now I'm using this approach. So therefore I wouldn't like to use the scripting dictionary. Go under the assumption that a native solution is always better. For all you know, AutoIt v4 might be released tomorrow and it features a real compiler which is super fast.

I am using a 2 dimensional list and trying to avoid resizing it as much as possible. The first dimension contains the value, the second dimension contains the index to the next item in the list. The list can contain garbage values (so you can insert or delete list items in a cheap way). The [0][0] element contains the size of the list, so if you ever wanted to get an array containing the values the size would be known up front.

Inserting would just add the new value at the end of the array, and then set the indexes appropriate. For example my $list would be:

[0] = 3, 1

[1] = a, 2

[2] = b, 3

[3] = c, 0

_ListInsertItem($list, "a2", 1)

The new list would look like:

[0] = 4, 1

[1] = a, 4

[2] = b, 3

[3] = c, 0

[4] = a2,2

expandcollapse popup

#include <Array.au3>

$list = _ListCreate()
;_ArrayDisplay($list)

For $c = 65 To 90
    _ListAddItem($list, Chr($c))
    ;_ArrayDisplay($list)
Next

$arr = _ListGetArray($list)
_ArrayDisplay($arr)

; Creates a list
Func _ListCreate($initialCount = 10)
    Local $list[$initialCount][2] ; create a list array by initial size
    $list[0][0] = 0 ; set the list size
    $list[0][1] = 1 ; set the location of the first item
    Return $list
EndFunc

; Adds an item to a list
Func _ListAddItem(ByRef $list, $item)
    $size = $list[0][0]
    $nextIndex = $list[0][1]

    $list[0][0] += 1

    If $size = 0 Then
        $list[$nextIndex][0] = $item
        $list[$nextIndex][1] = $nextIndex + 1
        Return
    EndIf

    ; Loop through the array finding indices
    $i = 0
    $previousIndex = 0
    While $i < $size
        $previousIndex = $nextIndex
        $nextIndex = $list[$nextIndex][1]
        $i += 1
    WEnd

    $list[$previousIndex][1] = $nextIndex

    ; Check if we need to grow the list array, if so: grow with 50%
    $arrSize = UBound($list)-1
    If $nextIndex > $arrSize Then
        $newSize = Round($arrSize * 1.5)
        ReDim $list[$newSize][2]
    EndIf

    ; Assign the item and update the next index
    $list[$nextIndex][0] = $item
    $list[$nextIndex][1] = $nextIndex + 1
EndFunc

; Gets an array from the list
Func _ListGetArray($list)
    $size = $list[0][0]
    $nextIndex = $list[0][1]

    ; Can't declare arrays of size 0
    If $size = 0 Then Return 0

    Local $ret[$size]
    $i = 0

    ; Loop through the array and store the values
    While $i < $size
        $itemValue = $list[$nextIndex][0]
        $nextIndex = $list[$nextIndex][1]

        $ret[$i] = $itemValue

        $i += 1
    WEnd

    Return $ret
EndFunc

Edited April 27, 2011 by Manadar

[AutoXenon]

A little bit late to the party, but I wonder if perhaps you could use the function call stack in a way so that it is only copied/traversed only once when attaching it to the destination, as opposed to doing it twice?

local $a=pack(1898) ; recursion limit reached at 1899
msgbox(0,'',unpack($a))

func unpack($arr)
     return IsArray($arr[0]) ? $arr[1] & ' , ' & unpack($arr[0]) : $arr[0]
endfunc

func pack($n)
     if $n<1 then 
        local $a = [ $n ]
     else
        local $a = [ pack($n-1) , $n ]
     endif
     return $a
endfunc