Jump to content
Sign in to follow this  
Ejoc

Stack UDF

Recommended Posts

So I did a search on stack, pop, push... and came across only 1 set of Stack functions. I modifed the code and it runs faster now.

Version 1.3:

Added _NewStack()

Version 1.2:

Added _Pop() - uses internal stack

Added _Push() - uses internal stack

Added _Peek() - uses internal stack

Added _PeekStack()

Version 1.1:

Added a ReDim when the last item is pop'd off the stack

So this is the code:

#cs
vi:ts=4 sw=4:
Stack functions based on SumTingWong's Stack functions:
http://www.autoitscript.com/forum/index.php?showtopic=6899&hl=

By: Ejoc
Version 1.3

Major difference is that the intial stack doesnt need to be an array,
it just needs to be declared.  There is significantly less ReDim's which
should improve code execution times, on a test I ran my code executed more
then twice as fast.

UDFs included In this file:
    _NewStack($initalSize=0)
    _PopStack(ByRef $vaStack, ByRef $vValue)
    _PushStack(ByRef $vaStack, $vValue)
    _PeekStack(ByRef $vsStack, $ByRef $vValue)
    _Pop(ByRef $vValue)
    _Push($vValue)
    _Peek(ByRef $vValue)
#ce
#include-once

Global $_Ejocs_Internal_Stack

;======================================================================
;   _NewStack($InitalSize=0)
;   InitalSize      : default 0  Using a Larger number would improve
;                     _Push execution times, A number close to the max
;                     number of elements you'll have would be ideal
;   Return          : A new Array
;   Example $myStack = _NewStack()
;======================================================================
Func _NewStack($InitalSize=0)
    Local $array
    Dim $array[$InitalSize+1]
    $array[0]   = 0
    Return $array
EndFunc

;======================================================================
;   _PopStack
;   ByRef vaStack   : The stack
;   ByRef vValue    : The variable the stack element will be pop into
;   Return          : 1 if there was an element 0 if the stack is empty
;   Example If _PopStack($myStack,$item) Then MsgBox(0,"",$item)
;======================================================================
Func _PopStack(ByRef $vaStack, ByRef $vValue)
    Local $iStackIndex
  
    If Not IsArray($vaStack) Or Not $vaStack[0] Then return 0
    $iStackIndex    = $vaStack[0]
    $vaStack[0]     = $iStackIndex - 1
    $vValue         = $vaStack[$iStackIndex]
    If $iStackIndex = 1 Then
        ReDim $vaStack[1]
        $vaStack[0] = 0
    Endif
    Return 1
EndFunc

;======================================================================
;   _PushStack
;   ByRef vaStack   : The Stack
;   vValue          : The element to push onto the stack
;   Return          : none
;   Example _PushStack($myStack,"Example")
;======================================================================
Func _PushStack(ByRef $vaStack, $vValue)
    Local $iStackIndex,$iStackLen

    If Not IsArray($vaStack) Then
        Dim $vaStack[10]
        $vaStack[0] = 0
       Else
        $iStackLen  = UBound($vaStack)
        if ($vaStack[0] + 1) >= $iStackLen Then
            ReDim $vaStack[$iStackLen + 10]
        Endif
    EndIf

    $iStackIndex            = $vaStack[0] + 1
    $vaStack[$iStackIndex]  = $vValue
    $vaStack[0]             = $iStackIndex
EndFunc

;======================================================================
;   _PeekStack
;   ByRef vaStack   : The stack
;   ByRef vValue    : The variable the stack element will be placed into
;   Return          : 1 if there was an element 0 if the stack is empty
;   Example If _PeakStack($myStack,$item) Then MsgBox(0,"",$item)
;======================================================================
Func _PeekStack(ByRef $vaStack, ByRef $vValue)
    Local $iStackIndex
  
    If Not IsArray($vaStack) Or Not $vaStack[0] Then return 0
    $iStackIndex    = $vaStack[0]
    $vValue         = $vaStack[$iStackIndex]
    Return 1
EndFunc

;======================================================================
;   _Pop
;   ByRef vValue    : The variable the stack element will be pop into
;   Return          : 1 if there was an element 0 if the stack is empty
;   Example If _Pop($item) Then MsgBox(0,"",$item)
;======================================================================
Func _Pop(ByRef $vValue)
    Return _PopStack($_Ejocs_Internal_Stack,$vValue)
EndFunc

;======================================================================
;   _Push
;   vValue          : The element to push onto the stack
;   Return          : none
;   Example _Push("Example")
;======================================================================
Func _Push($vValue)
    _PushStack($_Ejocs_Internal_Stack,$vValue)
EndFunc

;======================================================================
;   _Peek
;   ByRef vValue    : The variable the stack element will be placed into
;   Return          : 1 if there was an element 0 if the stack is empty
;   Example If _Peak($item) Then MsgBox(0,"",$item)
;======================================================================
Func _Peek(ByRef $vValue)
    Return _PeekStack($_Ejocs_Internal_Stack,$vValue)
EndFunc

I will also include the scripts I used to test the speed of the different Stack Operations.

Stack.au3

StackTests.zip

Edited by Ejoc

Start -> Programs -> AutoIt v3 -> AutoIt Help File -> Index -> (The Function you are asking about)----- Links -----DllStruct UDFsRSA Crypto UDFs

Share this post


Link to post
Share on other sites

The first element of the array this function references _has_ to be the # of elements?


"I thoroughly disapprove of duels. If a man should challenge me, I would take him kindly and forgivingly by the hand and lead him to a quiet place and kill him." - Mark TwainPatient: "It hurts when I do $var_"Doctor: "Don't do $var_" - Lar.

Share this post


Link to post
Share on other sites

The first element of the array this function references _has_ to be the # of elements?

<{POST_SNAPBACK}>

Yes, otherwise you have to ReDim constantly, which is what I was avoiding since it's faster not to ReDim. Edited by Ejoc

Start -> Programs -> AutoIt v3 -> AutoIt Help File -> Index -> (The Function you are asking about)----- Links -----DllStruct UDFsRSA Crypto UDFs

Share this post


Link to post
Share on other sites

added Peek and stack functions that use an internal stack so you dont have to bother with a variable if you dont want to


Start -> Programs -> AutoIt v3 -> AutoIt Help File -> Index -> (The Function you are asking about)----- Links -----DllStruct UDFsRSA Crypto UDFs

Share this post


Link to post
Share on other sites

I don't like the internal stack idea. Suggestion:

since your _PushStack and _PopStack functions already verify that an array has been passed, maybe just overload the _Push and _Pop functions to accept two parameters with the second being optional.

If the first parameter is an array, call _xxxStack directly, Else call _xxxStack ($_Ejocs_LastStack_Reference, $whatever)

the last stack reference could be set by _xxxStack

also add _NewStack() ... not necessary but would be nice for clarity.

So, someone coult write

$stStack1 = _NewStack ()

_Push ("foo")

_Push ("bar")

$stStack2 = _NewStack ()

_Push (_Pop ($stStack1)) ; Last ref would still be Stack2, because the _Push completed last... be careful with those Globals!

_Push ("baz")

_Push ($stStack1, "barf") ; Last ref is now Stack1

end result being that Stack1 contains "foo", "barf"

and Stack2 contains "bar", "baz"


601DisengageEnd Program

Share this post


Link to post
Share on other sites

I don't like the internal stack idea. Suggestion:

since your _PushStack and _PopStack functions already verify that an array has been passed, maybe just overload the _Push and _Pop functions to accept two parameters with the second being optional.

If the first parameter is an array, call _xxxStack directly, Else call _xxxStack ($_Ejocs_LastStack_Reference, $whatever)

the last stack reference could be set by _xxxStack

also add _NewStack()  ... not necessary but would be nice for clarity.

So, someone coult write

$stStack1 = _NewStack ()

_Push ("foo")

_Push ("bar")

$stStack2 = _NewStack ()

_Push (_Pop ($stStack1))  ; Last ref would still be Stack2, because the _Push completed last... be careful with those Globals!

_Push ("baz")

_Push ($stStack1, "barf") ; Last ref is now Stack1

end result being that Stack1 contains "foo", "barf"

and Stack2 contains "bar", "baz"

<{POST_SNAPBACK}>

The _NewStack() is easy, I can add that. It's the changing _Push() and _Pop() thats making the hamster run in its hamsterwheel in my head, if you listen carefuly that squeeking is comming from my head.

I am looking into. :)


Start -> Programs -> AutoIt v3 -> AutoIt Help File -> Index -> (The Function you are asking about)----- Links -----DllStruct UDFsRSA Crypto UDFs

Share this post


Link to post
Share on other sites

Feed your hamsters this, and see if they get any bright ideas:

Dim $Array[3]
$var = 1

_Function ($var); Produces "Array not... " msg
_Function ($Array); Produces "Array spec'd but..." msg
_Function ($Array, $var); Produces "Both..." msg

Func _Function ($p1, $p2 = "GGGGGGGGGGG"); Can't use a variable to specify default value

  If Not IsArray ($p1) Then 
    MsgBox (0, "_Function", "Array not specified, use value")
  Else
    If $p2 == "GGGGGGGGGGG" Then
      MsgBox (0, "_Function", "Array specified but value is not valid")
    Else
      MsgBox (0, "_Function", "Both Array and Value have been specified")
    EndIf
  EndIf
EndFunc

601DisengageEnd Program

Share this post


Link to post
Share on other sites

Ejoc, nice work. I do find your stack functions to be a bit quicker and a little faster routines are better.. BTW, stack functions are great. More people should use them..

Cheers... :)

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  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...