Abstract data types in QTP: The linked list

Normally the need for abstract datatypes in Test Automation is not very high. But you will see, just if you don’t have direct access to them, you’ll need them most. Today I had to store some data and it would be nice if I could pop and push it on some stacks. The basis for stacks (and queues) is a linked list. This was a nice Monday morning starter. Linked lists are simple, if you have the right toolset. Unfortunately, QTP and VBScript do not support pointers, so I had to be a little creative. First of all, I created a node class. Each node has a unique index number and a reference to the index numbers of its left and right neighbours. The data is conserved in a public available data element that can contain objects or variants.

' This is a setup for a linked list. This linked list is the basis for
' queues and stacks. With a little adaptation this can be transformed to
' a binary three or more complex abstract data types.

Option explicit

' Initializer for a new listnode. If you keep it private, you don't need this
' caller function
Private function listNode()
    Set listNode = new clsListNode
End Function

' class for a node. The nodeIndex functions as pointerreference
Class clsListNode

    Public data              'Data, can be a variable or an object (not an array)
    Public prevNode
    Public nextNode
    Private nodeIndex        'Index reference

    ' I use a property get to make a defaulter
    Public default property get index()    
        index = nodeIndex    
    End Property

    ' and a property let to set a new indexer
    Public property let index(inr)
        nodeIndex = inr
    End Property
End class

To keep track of the nodes, I created an array called collection containing node elements. Collection() is a list of references, but is never referred directly except when we add a new node. If a new node is added, the subscript of collection is incremented to create a new unique reference. Because elements can be added or deleted randomly, do not use collection() and its subscript as a continuous or a chronological list!

With add(), we can add an element to the end of the linked list. With getlast() and getfirst() the last and first data elements on the linked list are returned and with deletelast() and deletefirst() the last and first nodes are deleted.

Count() is a helper function, returning the amount of nodes in the list.

' Make the linked list caller
Public function linkedList()
    set linkedList = new clsLinkedList
End Function

' The linked list call
Class clsLinkedList

    private    collection()       ' a single dimensional array of listNodes
    Private lastItemIndex         ' index of the last item
    Private firstItemIndex        ' index of the first item
    Private indexNumber           ' counter for nodes in the list. Only increment, never decrement!
    Private nodeCount             ' amount of nodes. Ugly but fast.
  
    Private Sub Class_Initialize  ' Setup Initialize event.
        lastItemIndex = null   
        firstItemIndex = null
        indexNumber = 0
        nodeCount = 0
    End Sub

    Public sub add(data)

        ' add new listNode element to the array
        ReDim preserve collection(indexNumber)
        set collection(indexNumber) = listNode

        With collection(indexNumber)
            ' Make the collection compatible for objects as well as normal variables
            If isObject(data) Then
                set .data = data
            else
                .data = data
            End If

            .prevNode = lastItemIndex    ' The previous node of the new node is the current
                                         ' last node reference
            .nextNode = null             ' As it is the last item, there is no reference
                                         ' to the next item
            .index() = indexNumber       ' Set the index of the node to a unique number

            If not isnull(.prevNode) Then     ' If the newly created node has a left neighbour:
                collection(.prevNode).nextNode = indexNumber    ' the nextnode reference of the left
            else                                                ' neighbour is the index of the newly created
                firstItemIndex = .index       ' Else, this is the first node and the first node reference is the
            end if                            ' index of the newly created node
        end with

        lastItemIndex = indexNumber          ' As this is the last node, set the reference to this indexnumber
        indexNumber = indexNumber + 1        ' make a new indexnumber for a unique reference next time
        nodeCount = nodeCount + 1            ' and increment the nodecounter
    End sub

    Public property get getlast()
        If nodeCount = 0 Then exit property                ' No nodes? exit!

        If isobject(collection(lastItemIndex).data) then   ' Object or variant?
            Set getlast = collection(lastItemIndex).data   ' return object
        else
            getlast = collection(lastItemIndex).data       ' return variant
        end if   
    End Property

    Public property get getfirst()

        If nodeCount = 0 Then exit property

        If isobject(collection(firstItemIndex).data) then
            Set getfirst = collection(firstItemIndex).data
        else
            getfirst = collection(firstItemIndex).data
        end if
   
    End Property

    Public sub deletelast()

        If nodeCount = 0 Then exit sub    'Exit on no nodes

        Dim tempLastIndex
        tempLastIndex = lastItemIndex     'Make a temp for the last index number
       
        ' Check if there is a previous node
        If not isnull(collection(lastItemIndex).prevNode)  Then   
                ' Set the reference for the last item to the index of the left neighbour
            lastItemIndex = collection(collection(lastItemIndex).prevNode).index
                ' Set the reference for the next node of the left neighbour to null
            collection(lastItemIndex).nextNode = null
        End If

        ' destroy the node element
        Set collection(tempLastIndex) = nothing

        ' decrement the node counter
        nodeCount = nodeCount - 1
    End Sub

    Public sub deletefirst()

        If nodeCount = 0 Then exit sub
       
        Dim tempFirstIndex
        tempFirstIndex = firstItemIndex

        ' Check if there is a next node
        If not isnull(collection(firstItemIndex).nextNode)  Then
                ' Set the reference for the first item to the index of the right neighbour
            firstItemIndex = collection(collection(firstItemIndex).nextNode).index
                ' Set the reference for the previous node of the right neighbour to null
            collection(firstItemIndex).prevNode = null
        End If

        Set collection(tempFirstIndex) = nothing
        nodeCount = nodeCount - 1
    End Sub

    Public property get count()
        'return the amount of nodes
        count = nodeCount
    End Property
   
end class 


Some test statements to show how it works::


Dim ll, mc
Set ll = linkedList

    ll.add "first"
    ll.add "second"
    ll.add "third"
    ll.add "fourth"
    ll.add "fifth"
   
msgbox ll.getFirst()            ' >first
msgbox ll.getLast()             ' >fifth

' Delete the first item
ll.deletefirst
msgbox ll.getFirst()            ' >second

msgbox ll.count                 ' >4

' Delete the last two items
ll.deletelast
ll.deletelast
msgbox ll.getLast()             ' >third


The linked list class makes it very easy to create stacks and queues. Here is an example of how to create a stack:


Public function stack()
    set stack = new clsStack
End Function

Class clsStack

    Private ll
    Private Sub Class_Initialize    ' Setup Initialize event.
        set ll = linkedList         ' Create a linked list instance
    End Sub

    Public function pop()
        If ll.count = 0 Then exit function    ' No items in the list
        pop = ll.getlast()          ' Return the last item
        ll.deleteLast               ' and delete it
    End Function

    Public sub push(element)       
        ll.add element              ' Add an item to the list
    End sub

    Public function peek()           
        peek = ll.getlast()         ' Peek at the top item
    End Function

End Class

And some sample code for a little demonstration:

Dim myStack
set myStack = stack         ' Set as new stack

myStack.push "item1"        ' Add some items
myStack.push "item2"
myStack.push "item3"

msgbox myStack.pop()        ' >item3
msgbox myStack.peek()       ' >item2
msgbox myStack.pop()        ' >item2 

The thing that is missing for generic use is an insertbefore() and an insertafter() method on the linked list. But to implement this, you'll need a virtual reference table that maps the collection() array index to a chronologic ánd continuous index. Another way to do this is a looping mechanism where you can walk through the elements with a getnext() or getprevious() method.
For now, the stack and queue functionality is sufficient for my needs.