Stack Data Structure for AutoIT

[elektron]

Hello everyone,

I'm currently writing a set of data structures for AutoIt, and I've started with a stack, because stacks are the simplest (and can be so complex) data structure to write. I started writing a stack because I wanted to do a recursive (DFS) traversal without using recursion (because recursion blows up, and we already know from Computer Science 101 that any recursive algorithm can be turned into an iterative algorithm)

I've been really thinking hard about the most efficient ways to work with these data structures -- and since so many of them require dynamic memory, it's a bit difficult. The classical way of doing a Stack is by doing a linked list, but without the presence of pointers, structs, or anything of the like, I resorted to using an Array based implementation of a stack, which, looking back on it, is as poorly written as this post. (I'll post the code, even though I'm very embarrassed by it).

Lately, I've noticed that AutoIt has these functions, and I've never played with them before:

1) "Assign," which assigns values to a variable specified by a string

2) "Eval," which reads values to a variable specified by a string.

3) "IsDeclared," which checks to see if a value specified by a string is declared.

So, here's what I've been thinking -- perhaps it's possible for me to have my pie and eat it too.

Here's the code as it is:

expandcollapse popup

#cs ----------------------------------------------------------------------------

AutoIt Version: 3.3.8.1
Author: Alexander Alvonellos

Script Function:
A simple stack data structure for strings

#ce ----------------------------------------------------------------------------

#include 
#include 
#include 
#include-once

AutoItSetOption("MustDeclareVars", 1)
Global $__STACK__szDEALLOC_MAGIC_WORD = "0xDEADBEEF"
Global $__STACK__aszCurrentStackData[2]
Global $__STACK__iCurrentStackDataUsedCount = 0

; __STACK__TEST()
; __STACK__STRESSTEST()
; Pushes data onto the stack
; Returns 0 if successful, -1 if not.
Func __STACK__PUSH($szData)
; ConsoleWrite("---> PUSHED: " & $szData & @LF)
Local $iStackSize = (UBound($__STACK__aszCurrentStackData))
Local $iStackUtilization = $__STACK__iCurrentStackDataUsedCount
If($iStackUtilization < $iStackSize) Then
$__STACK__aszCurrentStackData[$__STACK__iCurrentStackDataUsedCount] = $szData
ElseIf ($iStackSize >= $iStackUtilization) Then
ReDim $__STACK__aszCurrentStackData[(2*UBound($__STACK__aszCurrentStackData))]
$__STACK__aszCurrentStackData[$__STACK__iCurrentStackDataUsedCount] = $szData
Else
Return -1
EndIf
$__STACK__iCurrentStackDataUsedCount = $__STACK__iCurrentStackDataUsedCount + 1
Return 0
EndFunc

Func __STACK__POP()
Local $szReturnValue = -1
Local $iStackSize = (UBound($__STACK__aszCurrentStackData) - 1)
Local $iStackUtilization = $__STACK__iCurrentStackDataUsedCount
If ($__STACK__iCurrentStackDataUsedCount > 0 ) Then
Local $szReturnValue = $__STACK__aszCurrentStackData[$__STACK__iCurrentStackDataUsedCount - 1]
$__STACK__aszCurrentStackData[$__STACK__iCurrentStackDataUsedCount - 1] = _
$__STACK__szDEALLOC_MAGIC_WORD
$__STACK__iCurrentStackDataUsedCount = $__STACK__iCurrentStackDataUsedCount - 1
Else
$szReturnValue = -1
EndIf
; ConsoleWrite("---> POPPED : " & $szReturnValue & @LF)
Return $szReturnValue
EndFunc

; Kinda...
Func __STACK__DEALLOC()
; If( $__STACK__iCurrentStackDataUsedCount > 0 ) Then
; Local $i = $__STACK__iCurrentStackDataUsedCount - 1
; For $i = $i To UBound($__STACK__aszCurrentStackData) Step 1
; ; _ArrayDelete($__STACK__aszCurrentStackData, $i)
; Next
; EndIf
$__STACK__aszCurrentStackData = ""
Dim $__STACK__aszCurrentStackData[2]
$__STACK__iCurrentStackDataUsedCount = 0
EndFunc

; If iMode = 0, then the stack is saved AS IS
; If iMode = 1, then the magic variables are
; trimmed from the array. The side effect of
; this is that after more variables are added
; to the stack and it resizes, it will resize
; in orders of magnitude other than powers of 2
Func __STACK__SAVE($szFilePath, $iMode = 0)
Local $copyArray = __STACK__ARRAY($iMode)
; _ArrayDisplay($copyArray, "PENIS")
Local $hFileHandle = FileOpen($szFilePath, 2) ; Overwrite
_FileWriteFromArray($hFileHandle, $copyArray)
FileFlush($hFileHandle)
FileClose($hFileHandle)
EndFunc

Func __STACK__LOAD($szFilePath)
_FileReadToArray($szFilePath, $__STACK__aszCurrentStackData)
; _ArrayDisplay($__STACK__aszCurrentStackData, "LOADED")
; We delete element zero because when _FileReadToArray reads
; the information from the file into the array, it stores the
; number of items in $__STACK__aszCurrentStackData[0] and that
; isn't what we want for this library.
_ArrayDelete($__STACK__aszCurrentStackData, 0)
; _ArrayDisplay($__STACK__aszCurrentStackData, "LOADED")
$__STACK__iCurrentStackDataUsedCount = UBound($__STACK__aszCurrentStackData)
; If we have less than or equal to three elements in the array,
; then we should return to prevent a subscript error.
If( $__STACK__iCurrentStackDataUsedCount <= 3 ) Then
Return
Else
While($__STACK__aszCurrentStackData[$__STACK__iCurrentStackDataUsedCount-1] = "")
$__STACK__iCurrentStackDataUsedCount = $__STACK__iCurrentStackDataUsedCount - 1
WEnd
EndIf
; ConsoleWrite($__STACK__iCurrentStackDataUsedCount)
EndFunc

; Returns the stack as an array
; and trims the extra space from
; the array.
; If iMode = 0, then the stack is saved AS IS
; If iMode = 1, then the magic variables are
; trimmed from the array. The side effect of
; this is that after more variables are added
; to the stack and it resizes, it will resize
; in orders of magnitude other than powers of 2
Func __STACK__ARRAY($iMode = 0)
Local $copy = ""
Local $i = 0
If( $iMode = 0 ) Then
Return $__STACK__aszCurrentStackData
Else
For $i = 0 To ($__STACK__iCurrentStackDataUsedCount - 1) Step 1
If( $__STACK__aszCurrentStackData[$i] <> $__STACK__szDEALLOC_MAGIC_WORD ) Then ; We can copy it
$copy &= $__STACK__aszCurrentStackData[$i]
If( ($i+1) < ($__STACK__iCurrentStackDataUsedCount) ) Then ; We're not at the last element
$copy &= Chr(0)
EndIf ; Otherwise, we don't want to add that last delim character.
Else
; ConsoleWrite("--> Debug on line 73")
EndIf
Next
Return StringSplit($copy, Chr(0), 3) ; Each character in string is req for delim.
; And returns the array as a 0 indexed array, so you have to use ubound to get the dim.
EndIf
EndFunc

; Return the size of the stack.
Func __STACK__SIZE()
Return $__STACK__iCurrentStackDataUsedCount
EndFunc
Func __STACK__STRESSTEST()
__STACK__DEALLOC()
Local $i = 0
For $i = 0 To 1000000 Step 1
__STACK__PUSH($i)
;ConsoleWrite($i & " : " & __STACK__PUSH($i) & " ::: " & UBound($__STACK__aszCurrentStackData) & " :- " & _
; $__STACK__iCurrentStackDataUsedCount & @LF)
Next
__STACK__SAVE(@ScriptDir & "\" & "STACK.dat")
MsgBox(0, "", "")
__STACK__DEALLOC()
MsgBox(0, "", "")
EndFunc

; Debugging...
FUNC __STACK__TEST()
_ArrayDisplay($__STACK__aszCurrentStackData)
Local $i = 0
For $i = 0 To 10 Step 1
ConsoleWrite($i & " : " & __STACK__PUSH($i) & " ::: " & UBound($__STACK__aszCurrentStackData) & " :- " & _
$__STACK__iCurrentStackDataUsedCount & @LF)
Next
_ArrayDisplay($__STACK__aszCurrentStackData, "Directly from stack data")
Local $arrCopy = __STACK__ARRAY()
_ArrayDisplay($arrCopy, "From __STACK__ARRAY()")
__STACK__SAVE(@ScriptDir & "\" & "STACK.dat")

For $i = 0 To 10 Step 1
__STACK__POP()
Next
_ArrayDisplay($__STACK__aszCurrentStackData, "Directly from stack data after deletion")
$arrCopy = __STACK__ARRAY()
_ArrayDisplay($arrCopy, "From __STACK__ARRAY() after deletion")
__STACK__DEALLOC()

__STACK__LOAD(@ScriptDir & "\" & "STACK.dat")
_ArrayDisplay($__STACK__aszCurrentStackData, "Data loaded from saved file")
For $i = 0 To 10 Step 1
ConsoleWrite($i & " : " & __STACK__PUSH($i) & " ::: " & UBound($__STACK__aszCurrentStackData) & " :- " & _
$__STACK__iCurrentStackDataUsedCount & @LF)
Next
_ArrayDisplay($__STACK__aszCurrentStackData, "After adding ten elements to data loaded from saved file")
__STACK__DEALLOC()

MsgBox(0, "", "")
EndFunc

There are a couple of very serious problems with this data structure, the way that it is designed:

1). You can only have ONE stack active at any given time.

2). Insertions are very fast, this is because of the doubling of the array size by a factor of 2 for when

the array gets to UBound($aArray) - 1

3). It's not smart with memory. If you perform 10 million insertions and then 10 million deletions, you've used 16 777 216 blocks of memory, and it doesn't deallocate it.

--> What I could do is deallocate the memory if the record pointer goes below a factor of 2.

Some advantages:

1) It uses ReDim as LITTLE as possible

2) It's very easy to use

3) It's fast. Pushing is almost always in constant time, unless the array needs to resize, and then (I'm guessing) it turns into a linear-time insertion. Popping is always in constant time.

4) it's easy to work with.

What do you guys think about any of this? Some peer-review would be very helpful.

What I was thinking about doing was using those functions I talked about above and using some variables to keep track of where I'm at and using some kind of an indexing mechanism to keep the constant insertion and deletion time and declare variables in an amortized fashion in order to gain better memory efficiency. (Linear memory)

Is it worth the trouble? I just want to get this right & make it easy.