Sign in to follow this  
Followers 0
jvanegmond

Deeply nested arrays

7 posts in this topic

#1 ·  Posted (edited)

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.

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 by Manadar

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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?

#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 by Manadar

Share this post


Link to post
Share on other sites

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:

;~ #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).


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

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 by Manadar

Share this post


Link to post
Share on other sites

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).


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

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

#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 by Manadar

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