Queue UDF - Based on the concept in .NET.

guinness · April 11, 2014

Mat gave me this idea from my >Stack UDF thread. It works like a stack, but instead of being LIFO (last in first out), it's FIFO (first in first out).

Enjoy.

Global Const $QUEUE_GUID = 'BB09E988-0DF3-11E4-846E-B46DECBA0006'
Global Enum $QUEUE_COUNT, $QUEUE_FIRSTINDEX, $QUEUE_LASTINDEX, $QUEUE_ID, $QUEUE_UBOUND, $QUEUE_MAX

#Region Example
#include <Array.au3>

Example()

Func Example()
    Local $hQueue = Queue() ; Create a queue object.

    For $i = 1 To 20
        If Queue_Enqueue($hQueue, 'Example_' & $i) Then ConsoleWrite('Enqueue: ' & 'Example_' & $i & @CRLF) ; Push random data to the queue.
    Next

    For $i = 1 To 15
        ConsoleWrite('Dequeue: ' & Queue_Dequeue($hQueue) & @CRLF) ; Pop from the queue.
        If Queue_Enqueue($hQueue, 'Example_' & $i * 10) Then ConsoleWrite('Enqueue: ' & 'Example_' & $i * 10 & @CRLF) ; Push random data to the queue.
    Next
    ConsoleWrite('Peek: ' & Queue_Peek($hQueue) & @CRLF)
    ConsoleWrite('Peek: ' & Queue_Peek($hQueue) & @CRLF)

    ConsoleWrite('Count: ' & Queue_Count($hQueue) & @CRLF)
    ConsoleWrite('Capacity: ' & Queue_Capacity($hQueue) & @CRLF)

    Queue_ForEach($hQueue, AppendUnderscore) ; Loop through the stack and pass each item to the custom function.

    ConsoleWrite('Contains Example_150: ' & (Queue_ForEach($hQueue, Contains_150) = False) & @CRLF) ; It will return False if found so as to exit the ForEach() loop, hence why False is compared
    ConsoleWrite('Contains Example_1000: ' & (Queue_ForEach($hQueue, Contains_1000) = False) & @CRLF) ; It will return False if found so as to exit the ForEach() loop, hence why False is compared

    Local $aQueue = Queue_ToArray($hQueue) ; Create an array from the queue.
    _ArrayDisplay($aQueue)

    Queue_Clear($hQueue) ; Clear the queue.
    Queue_TrimToSize($hQueue) ; Decrease the memory footprint.
EndFunc   ;==>Example

Func AppendUnderscore(ByRef $vItem)
    $vItem &= '_'
    Return (Random(0, 1, 1) ? True : False) ; Randomise when to return True Or False. The false was break from the ForEach() function.
EndFunc   ;==>AppendUnderscore

Func Contains_150(ByRef $vItem)
    Return ($vItem == 'Example_150' ? False : True) ; If found exit the loop by setting to False.
EndFunc   ;==>Contains_150

Func Contains_1000(ByRef $vItem)
    Return ($vItem == 'Example_1000' ? False : True) ; If found exit the loop by setting to False.
EndFunc   ;==>Contains_1000
#EndRegion Example

; Functions:
; Queue - Create a queue handle.
; Queue_ToArray - Create an array from the queue.
; Queue_Capacity - Retrieve the capacity of the internal queue elements.
; Queue_Clear - Remove all items/objects from the queue.
; Queue_Count - Retrieve the number of items/objects on the queue.
; Queue_Dequeue - Pop the first item/object from the queue.
; Queue_Enqueue - Push an item/object to the queue.
; Queue_ForEach - Loop through the queue and pass each item/object to a custom function for processing.
; Queue_Peek - Peek at the item/object in the queue.
; Queue_TrimToSize - Set the capacity to the number of items/objects in the queue.

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue
; Description ...: Create a queue handle.
; Syntax ........: Queue([$iInitialSize = Default])
; Parameters ....: $iInitialSize        - [optional] Initialise the queue with a certain size. Useful if you know how large the queue will grow. Default is zero
; Parameters ....: None
; Return values .: Handle that should be passed to all relevant queue functions.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue($iInitialSize = Default)
    Local $aQueue = 0
    __Queue($aQueue, $iInitialSize, False)
    Return $aQueue
EndFunc   ;==>Queue

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_ToArray
; Description ...: Create an array from the queue.
; Syntax ........: Queue_ToArray(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: A zero based array.
;                  Failure: Sets @error to non-zero and returns Null.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_ToArray(ByRef $aQueue)
    If __Queue_IsAPI($aQueue) And $aQueue[$QUEUE_COUNT] > 0 Then
        Local $aArray[$aQueue[$QUEUE_COUNT]]
        Local $j = 0
        For $i = $aQueue[$QUEUE_FIRSTINDEX] To $aQueue[$QUEUE_LASTINDEX]
            $aArray[$j] = $aQueue[$i]
            $j += 1
        Next
        Return $aArray
    EndIf
    Return SetError(1, 0, Null)
EndFunc   ;==>Queue_ToArray

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Capacity
; Description ...: Retrieve the capacity of the internal queue elements.
; Syntax ........: Queue_Capacity(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: Capacity of the internal queue
;                  Failure: None.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Capacity(ByRef $aQueue)
    Return (__Queue_IsAPI($aQueue) ? $aQueue[$QUEUE_UBOUND] - (($aQueue[$QUEUE_FIRSTINDEX] >= $QUEUE_MAX) ? $aQueue[$QUEUE_FIRSTINDEX] - 1 : $QUEUE_MAX) : 0)
EndFunc   ;==>Queue_Capacity

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Clear
; Description ...: Remove all items/objects from the queue.
; Syntax ........: QueueClear(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: True.
;                  Failure: None.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Clear(ByRef $aQueue)
    Return __Queue($aQueue, Null, False)
EndFunc   ;==>Queue_Clear

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Count
; Description ...: Retrieve the number of items/objects on the queue.
; Syntax ........: Queue_Count(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: Count of the items/objects on the queue.
;                  Failure: None.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Count(ByRef $aQueue)
    Return (__Queue_IsAPI($aQueue) And $aQueue[$QUEUE_COUNT] >= 0 ? $aQueue[$QUEUE_COUNT] : 0)
EndFunc   ;==>Queue_Count

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_ForEach
; Description ...: Loop through the queue and pass each item/object to a custom function for processing.
; Syntax ........: Queue_ForEach(ByRef $aQueue, $hFunc)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
;                  $hFunc               - A delegate to a function that has a single ByRef input and a return value of either True (continue looping) or False (exit looping).
; Return values .: Success: Return value of either True or False from the delegate function.
;                  Failure: Null
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_ForEach(ByRef $aQueue, $hFunc)
    Local $bReturn = Null
    If __Queue_IsAPI($aQueue) And IsFunc($hFunc) Then
        For $i = $aQueue[$QUEUE_FIRSTINDEX] To $aQueue[$QUEUE_LASTINDEX]
            $bReturn = $hFunc($aQueue[$i])
            If Not $bReturn Then
                ExitLoop
            EndIf
        Next
    EndIf
    Return $bReturn
EndFunc   ;==>Queue_ForEach

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Peek
; Description ...: Peek at the item/object in the queue.
; Syntax ........: Queue_Peek(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: Item/object in the queue.
;                  Failure: Sets @error to non-zero and returns Null.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Peek(ByRef $aQueue)
    Return (__Queue_IsAPI($aQueue) And $aQueue[$QUEUE_FIRSTINDEX] >= $QUEUE_MAX ? $aQueue[$aQueue[$QUEUE_FIRSTINDEX]] : SetError(1, 0, Null))
EndFunc   ;==>Queue_Peek

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Dequeue
; Description ...: Pop the first item/object from the queue.
; Syntax ........: Queue_Dequeue(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: Item/object popped from the queue.
;                  Failure: Sets @error to non-zero and returns Null.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Dequeue(ByRef $aQueue)
    If __Queue_IsAPI($aQueue) And $aQueue[$QUEUE_LASTINDEX] >= $QUEUE_MAX Then
        $aQueue[$QUEUE_COUNT] -= 1 ; Decrease the count.
        Local $vData = $aQueue[$aQueue[$QUEUE_FIRSTINDEX]] ; Save the queue item/object.
        $aQueue[$aQueue[$QUEUE_FIRSTINDEX]] = Null ; Set to null.
        $aQueue[$QUEUE_FIRSTINDEX] += 1
        ; If ($aQueue[$QUEUE_FIRSTINDEX] - $QUEUE_MAX) > 15 Then ; If there are too many blank rows then re-size the queue.
        ; __Queue($aQueue, Null, True)
        ; EndIf
        Return $vData
    EndIf
    Return SetError(1, 0, Null)
EndFunc   ;==>Queue_Dequeue

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_Enqueue
; Description ...: Push an item/object to the queue.
; Syntax ........: Queue_Enqueue(ByRef $aQueue, $vData)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
;                  $vData               - Item/object.
; Return values .: Success: True.
;                  Failure: Sets @error to non-zero and returns Null.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_Enqueue(ByRef $aQueue, $vData)
    If __Queue_IsAPI($aQueue) Then
        $aQueue[$QUEUE_LASTINDEX] += 1 ; Increase the queue by 1.
        $aQueue[$QUEUE_COUNT] += 1 ; Increase the count.
        If $aQueue[$QUEUE_LASTINDEX] >= $aQueue[$QUEUE_UBOUND] Then ; ReDim the internal queue array if required.
            $aQueue[$QUEUE_UBOUND] = Ceiling(($aQueue[$QUEUE_UBOUND] - $QUEUE_MAX) * 2) + $QUEUE_MAX
            ReDim $aQueue[$aQueue[$QUEUE_UBOUND]]
        EndIf
        $aQueue[$aQueue[$QUEUE_LASTINDEX]] = $vData ; Set the queue element.
        Return True
    EndIf
    Return SetError(1, 0, Null)
EndFunc   ;==>Queue_Enqueue

; #FUNCTION# ====================================================================================================================
; Name ..........: Queue_TrimToSize
; Description ...: Set the capacity to the number of items/objects in the queue.
; Syntax ........: Queue_TrimToSize(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: True.
;                  Failure: None.
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func Queue_TrimToSize(ByRef $aQueue)
    Return __Queue($aQueue, Null, True)
EndFunc   ;==>Queue_TrimToSize

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __Queue
; Description ...:Create a new queue object or re-size a current queue object.
; Syntax ........: __Queue(Byref $aQueue, $iInitialSize, $bIsCopyObjects)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
;                  $iInitialSize        - Initial size value.
;                  $bIsCopyObjects      - Copy the previous queue items/objects.
; Return values .: True
; Author ........: guinness
; ===============================================================================================================================
Func __Queue(ByRef $aQueue, $iInitialSize, $bIsCopyObjects)
    Local $iCount = (__Queue_IsAPI($aQueue) ? $aQueue[$QUEUE_COUNT] : ((IsInt($iInitialSize) And $iInitialSize > 0) ? $iInitialSize : 0))

    Local $iUBound = $QUEUE_MAX + (($iCount > 0) ? $iCount : 4) ; QUEUE_INITIAL_SIZE
    Local $aQueue_New[$iUBound]
    $aQueue_New[$QUEUE_FIRSTINDEX] = $QUEUE_MAX
    $aQueue_New[$QUEUE_LASTINDEX] = $QUEUE_MAX - 1
    $aQueue_New[$QUEUE_COUNT] = 0
    $aQueue_New[$QUEUE_ID] = $QUEUE_GUID
    $aQueue_New[$QUEUE_UBOUND] = $iUBound

    If $bIsCopyObjects And $iCount > 0 Then ; If copy the previous objects is true and the count is greater than zero then copy.
        $aQueue_New[$QUEUE_LASTINDEX] = $QUEUE_MAX - 1 + $iCount
        $aQueue_New[$QUEUE_COUNT] = $iCount

        Local $j = $aQueue[$QUEUE_FIRSTINDEX] + 1
        For $i = $QUEUE_MAX To $aQueue_New[$QUEUE_COUNT] + $QUEUE_MAX - 1
            $aQueue_New[$i] = $aQueue[$j]
            $j += 1
        Next
    EndIf
    $aQueue = $aQueue_New
    $aQueue_New = 0
    Return True
EndFunc   ;==>__Queue

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __Queue_IsAPI
; Description ...: Determine if the variable is a valid queue handle.
; Syntax ........: __Queue_IsAPI(ByRef $aQueue)
; Parameters ....: $aQueue              - [in/out] Handle returned by Queue().
; Return values .: Success: True.
;                  Failure: False.
; Author ........: guinness
; ===============================================================================================================================
Func __Queue_IsAPI(ByRef $aQueue)
    Return UBound($aQueue) >= $QUEUE_MAX And $aQueue[$QUEUE_ID] = $QUEUE_GUID
EndFunc   ;==>__Queue_IsAPI

Edited July 30, 2014 by guinness

guinness · April 11, 2014

Added Queue_ToArray().

FaridAgl · April 12, 2014

Well, works like a charm.

Using _ArrayDisplay() on the Queue handle ($hQueue in your example) shows the following:

[0]|7
[1]|27
[2]|20
[3]|33
[4]|
[5]|
[6]|
[7]|
[8]|Example_16
[9]|Example_17
[10]|Example_18
[11]|Example_19
[12]|Example_20
[13]|Example_10
[14]|Example_20
[15]|Example_30
[16]|Example_40
[17]|Example_50
[18]|Example_60
[19]|Example_70
[20]|Example_80
[21]|Example_90
[22]|Example_100
[23]|Example_110
[24]|Example_120
[25]|Example_130
[26]|Example_140
[27]|Example_150
[28]|
[29]|
[30]|
[31]|
[32]|

I believe this kind of stuff could cause serious memory leak.

Also I suggest Queue_IsEmpty() function to be added.

Thanks for this, it was really missing.

guinness · April 12, 2014

Thanks for testing.

I don't see a memory leak issue as every once in a while I remove blank lines at the beginning in Queue_Dequeue(). Basically 10 or more blank lines equals a reset of the queue. Otherwise I would have to keep shifting the elements down by one if I added to element 4 all the time. With this approach it's a little quicker.

Also similar answer to your Queue_IsEmpty() request as with Stack_IsEmpty().

Edited April 12, 2014 by guinness

guinness · April 12, 2014

Added Queue_TrimToSize() and now Queue_Clear() works the same as the .NET class version, in that all items/objects are cleared, but the capacity remains the same.

guinness · April 20, 2014

Changed example and variable renaming. There was a small bug, though it would have never caused an issue for those using the UDF.

The bug, which wasn't really causing an issue was I was setting the UBOUND to 3 instead of 4 e.g. $aQueue[$QUEUE_UBOUND] = $QUEUE_UBOUND + $iCount instead of $aQueue[$QUEUE_UBOUND] = $QUEUE_MAX + $iCount. It didn't cause an issue because when the array was re-sized Ceiling(3 * 1.5) = 5, a new element was added to the 4 length array. But in the Stack UDF the problem occurred because Ceiling(2 * 1.5) = 3, so an additional element wasn't added to the array which was already a length of 3. Hence why I should have set this to MAX in the first place!

Edited April 20, 2014 by guinness

guinness · April 21, 2014

Added: Queue_ForEach(). See example for usage of this amazing function.

Removed: Re-sizing the internal array. Now it's up to the developer when to re-size by calling Queue_TrimToSize().

Mat · April 21, 2014

For the Foreach function, I quite like to have callbacks that use Byref to modify the parameter, and then return either True or False to continue or break from the loop.

guinness · April 21, 2014

For the Foreach function, I quite like to have callbacks that use Byref to modify the parameter, and then return either True or False to continue or break from the loop.

I was actually thinking about that last night when going to bed, as I was about to write a Contains() example using ForEach().

So you were thinking along these lines?

Func AppendUnderscore(ByRef $vItem)
    $vItem &= '_'
    Return Random(0, 1, 1) ? True : False ; Randomise when to return True Or False
EndFunc   ;==>AppendUnderscore

Func Queue_ForEach(ByRef $aQueue, $hFunc)
    If UBound($aQueue) >= $QUEUE_MAX And IsFunc($hFunc) Then
        For $i = $aQueue[$QUEUE_FIRSTINDEX] + 1 To $aQueue[$QUEUE_LASTINDEX]
            If Not $hFunc($aQueue[$i]) Then
                ExitLoop
            EndIf
        Next
    EndIf
    Return True
EndFunc   ;==>Queue_ForEach

I also found a bug!? (jchd found a bug #2612) with Au3Check as this throws an error of "error: AppendUnderscore() previously called with Const or expression on ByRef param(s)." which of course is wrong.

Edited April 21, 2014 by guinness

guinness · April 21, 2014

Or...

Func Queue_ForEach(ByRef $aQueue, $hFunc)
    Local $fReturn = Null
    If UBound($aQueue) >= $QUEUE_MAX And IsFunc($hFunc) Then
        For $i = $aQueue[$QUEUE_FIRSTINDEX] + 1 To $aQueue[$QUEUE_LASTINDEX]
            $fReturn = $hFunc($aQueue[$i])
            If Not $fReturn Then
                ExitLoop
            EndIf
        Next
    EndIf
    Return $fReturn
EndFunc   ;==>Queue_ForEach

; And then this can be done...

ConsoleWrite('Contains: ' & (Stack_ForEach($hStack, Contains) = False) & @CRLF) ; It will return False if found so as to exit the ForEach() loop, hence why False is compared.

Func Contains(ByRef $vItem)
    Return $vItem == 'Example_150' ? False : True ; If found exit the loop by setting to False.
EndFunc   ;==>Contains

Edited April 21, 2014 by guinness

guinness · April 21, 2014

Added: Capacity() function.

Added: Contains() example.

Changed: ForEach() now expects the delegate function to return True or False to exit the ForEach() loop, instead of the value. This is passed by reference using ByRef.

Changed: Internal re-sizing by multiplying the capacity by 2 and initialising with 4 if no initial size is set. This mimics List<> in .NET

Changed: Return value of ForEach() which is either the return value of the delegate function or Null on failure.

guinness · May 11, 2014

Updated the example.

FaridAgl · May 11, 2014

guinness

Do you have any interest in writing an AssocArray UDF?

Scripting.Dictionary seems to be a good place to start.

#cs
    [Methods]
    Add = Adds a key and item pair to a Dictionary object.
    object.Add (key, item)

    Exists = Returns true if a specified key exists in the Dictionary object, false if it does not.
    object.Exists(key)

    Items = Returns an array containing all the items in a Dictionary object.
    object.Items()

    Keys = Returns an array containing all existing keys in a Dictionary object.
    object.Keys()

    Remove = Removes a key, item pair from a Dictionary object.
    object.Remove(key)

    RemoveAll = The RemoveAll method removes all key, item pairs from a Dictionary object.
    object.RemoveAll()


    [Properties]
    Add = Returns the number of items in a collection or Dictionary object. Read-only.
    object.Count

    Item = Sets or returns an item for a specified key in a Dictionary object. For collections, returns an item based on the specified key. Read/write.
    object.Item(key)[ = newitem]

    Key = Sets a key in a Dictionary object.
    object.Key(key) = newkey

    CompareMode = Sets and returns the comparison mode for comparing string keys in a Dictionary object.
    object.CompareMode[ = compare]
#ce

Func AssociativeArray()
    Return ObjCreate("Scripting.Dictionary")
EndFunc

guinness · May 11, 2014

Not really, because the Dictionary object doesn't really warrant a UDF in my opinion.

Edit: I do have some other UDFs I have been sitting on, but am torn whether to release or not.

Edited May 11, 2014 by guinness

Melba23 · May 11, 2014

D4RKON3,

In case you are unaware, there is already a very good associative array UDF here. I have used it a lot with no problems at all.

M23

FaridAgl · May 11, 2014

Yeah, actually I'm agree about the Dictionary object, having everything AutoIt oriented and playing with arrays and variables to write an AssocArray wrapper feels really better.

What kinds of UDFs? can I give em a try?

Melba23

Thanks mate, going to give it a try right now.

Edited May 11, 2014 by D4RKON3

guinness · May 12, 2014

What kinds of UDFs? can I give em a try?

One is a TrueCrypt UDF which uses the same approach as passing a handle to certain functions. I have had it for something like 4 years but just never published it. Lets see how I feel.

guinness · May 18, 2014

Added unique ID so it's guaranteed that the Queue is created with my UDF.

FaridAgl · May 18, 2014

guinness

Queue.au3"(255,75) : warning: $aQueue: possibly used before declaration.

guinness · May 18, 2014

Fixed incorrect variable being referenced.

Sign In

Queue UDF - Based on the concept in .NET.

Recommended Posts

guinness

guinness

FaridAgl

guinness

guinness

guinness

guinness

Mat

guinness

guinness

guinness

guinness

FaridAgl

guinness

Melba23

FaridAgl

guinness

guinness

FaridAgl

guinness

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Browse

AutoIt Resources

Release

Beta