Dynamic ArrayList (with circular doubly linked list under the hood)

Post by **fxm** » Sep 06, 2024 8:53

About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)

fxm wrote: ↑Sep 05, 2024 19:39 Using this new destruction member method, compared to a user destruction loop (user data destruction + element destruction in a same loop), allows to gain a factor of about 30% on the destruction time.
Should we then validate this idea?

Test code with the file to include modified accordingly:

Code: Select all

' DynamicArrayList.bi modified

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    ' Allocates memory for new node
    Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
    If newNodePtr = 0 Then Return 0
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    ' Deallocates memory for the node
    Deallocate(searchNodePtr)
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        ' Allocates memory for new node
        Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return This.nbrUserNode
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            Deallocate(nodePtr->prevNodePtr)
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            Deallocate(nodePtr->prevNodePtr)
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one  by transverse access
    This.DestroyAllNthPosition()
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   ";
    For I As Integer = 1 To 5
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print " .....";
    For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print
End Sub

Sub destroy(ByVal p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Integer position
    
    Dim As DynamicArrayList dal1
    Dim As DynamicArrayList dal2
    Print "Two Dynamic ArrayLists pointing to """ & N & """ dynamic integers :"
    For I As Integer = 1 To N
        dal1.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal1)
    For I As Integer = 1 To N
        dal2.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal2)
    Print
    Print "   Time to destroy all elements + the dynamic user data :"
    Print "      - by using a user loop for the first Dynamic ArrayList :"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal1.SuppressTheNthPosition(1))
    Next i
    Print "         " & Timer - t & " s"
    Print "      - by using the member method for the second Dynamic ArrayList :"
    t = Timer
    dal2.DestroyAllNthPosition(@destroy)
    Print "         " & Timer - t & " s"
End Sub

Test(1000000)
Print "--------------------------------------------------------------------"
Test(3000000)
Print "--------------------------------------------------------------------"
Test(5000000)
Print "--------------------------------------------------------------------"
Test(7000000)
Print "--------------------------------------------------------------------"
Test(9000000)

Sleep

Output example:

Code: Select all

Two Dynamic ArrayLists pointing to "1000000" dynamic integers :
    1 2 3 4 5 ..... 999996 999997 999998 999999 1000000
    1 2 3 4 5 ..... 999996 999997 999998 999999 1000000

   Time to destroy all elements + the dynamic user data :
      - by using a user loop for the first Dynamic ArrayList :
         0.1290565999519799 s
      - by using the member method for the second Dynamic ArrayList :
         0.08200879994598154 s
--------------------------------------------------------------------
Two Dynamic ArrayLists pointing to "3000000" dynamic integers :
    1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000
    1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000

   Time to destroy all elements + the dynamic user data :
      - by using a user loop for the first Dynamic ArrayList :
         0.3774869000394574 s
      - by using the member method for the second Dynamic ArrayList :
         0.2655347000473967 s
--------------------------------------------------------------------
Two Dynamic ArrayLists pointing to "5000000" dynamic integers :
    1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000
    1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000

   Time to destroy all elements + the dynamic user data :
      - by using a user loop for the first Dynamic ArrayList :
         0.6417374999850267 s
      - by using the member method for the second Dynamic ArrayList :
         0.4314474999961249 s
--------------------------------------------------------------------
Two Dynamic ArrayLists pointing to "7000000" dynamic integers :
    1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000
    1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000

   Time to destroy all elements + the dynamic user data :
      - by using a user loop for the first Dynamic ArrayList :
         0.8864024000415611 s
      - by using the member method for the second Dynamic ArrayList :
         0.6022076999993828 s
--------------------------------------------------------------------
Two Dynamic ArrayLists pointing to "9000000" dynamic integers :
    1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
    1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000

   Time to destroy all elements + the dynamic user data :
      - by using a user loop for the first Dynamic ArrayList :
         1.11212479997738 s
      - by using the member method for the second Dynamic ArrayList :
         0.7666473000202814 s

I would prefer to add this member method to the DynamicArrayList structure, which makes it easier for the user to manually destroy the list elements and its associated data if necessary.

Post by **fxm** » Sep 07, 2024 12:14

fxm wrote: ↑Sep 06, 2024 8:53 About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)

Added the member method 'Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)' in the 'DynamicArrayList' type:
- To destroy in one shoot all elements of the list, the user can call this member procedure, passing as optional argument a user procedure (callback) to also destroy (if necessary) from the member procedure internal loop his own dynamic data at the same time than the list elements.

These 3 posts have been updated.

Post by **fxm** » Sep 12, 2024 12:15

fxm wrote: ↑Aug 29, 2024 16:25 - For a preserved dynamic array, inserting (or deleting) an element at the end of the array is the best case in terms of execution time, otherwise it can be much worse when the insertion (or deletion) position is far from the end because all elements from the insertion position (or after the deletion position) have additionally to be shifted.
- For the Dynamic ArrayList, the insertion (or deletion) position has almost no effect on the execution time.

Test code:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintArray(array() As Integer)
    Print "            array:";
    If (Ubound(array) + 1) = 0 Then
        Print " empty";
    Elseif (Ubound(array) + 1) <= 10 Then
        For I As Integer = 0 To Ubound(array)
            Print array(I);
        Next I
    Else
        For I As Integer = 1 To 5
            Print array(I - 1);
        Next I
        Print " .....";
        For I As Integer = Ubound(array) - 4 To Ubound(array)
            Print array(I);
        Next I
    End If
    Print
End Sub

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Long array()
    Dim As DynamicArrayList dal
    
    Print
    Print "Preserved dynamic array of integers:"
    Print "   By acting only from the end of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        Redim Preserve array(Ubound(array) + 1)
        array(Ubound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "   By acting only from the beginning of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    Redim Preserve array(Ubound(array) + 1)
    array(Lbound(array)) = 1
    For I As Integer = 2 To N
        Redim Preserve array(Ubound(array) + 1)
        FB_Memmove(array(Lbound(array) + 1), array(Lbound(array)), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        array(Lbound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        FB_Memmove(array(Lbound(array)), array(Lbound(array) + 1), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print
    
    Print "Dynamic ArrayList pointing to dynamic integers:"
    Print "   By acting only from the end of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "   By acting only from the beginning of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 1)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print
End Sub

Test(5000)
Print "--------------------------------------------------------------------"
Test(10000)
Print "--------------------------------------------------------------------"
Test(30000)
Print "--------------------------------------------------------------------"
Test(60000)

Sleep

Output example:

Code: Select all

Preserved dynamic array of integers:
   By acting only from the end of the array:
      Time to increase the array step by step up to 5000 elements:
         0.0006975000759439354 s
            array: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
      Time to decrease the array step by step up to 0 element:
         0.0004722000704759921 s
            array: empty
   By acting only from the beginning of the array:
      Time to increase the array step by step up to 5000 elements:
         0.006149299884668835 s
            array: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
      Time to decrease the array step by step up to 0 element:
         0.005664100097419578 s
            array: empty

Dynamic ArrayList pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 5000 elements:
         0.001034800063621333 s
            list: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
      Time to decrease the list step by step, up to 0 element:
         0.000546199929544855 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 5000 elements:
         0.001758899901801669 s
            list: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
      Time to decrease the list step by step, up to 0 element:
         0.0006361998839565786 s
            list: empty

--------------------------------------------------------------------

Preserved dynamic array of integers:
   By acting only from the end of the array:
      Time to increase the array step by step up to 10000 elements:
         0.001257399970768347 s
            array: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
      Time to decrease the array step by step up to 0 element:
         0.001068000088025656 s
            array: empty
   By acting only from the beginning of the array:
      Time to increase the array step by step up to 10000 elements:
         0.0219928001037033 s
            array: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
      Time to decrease the array step by step up to 0 element:
         0.02092620003111278 s
            array: empty

Dynamic ArrayList pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 10000 elements:
         0.002987899914046466 s
            list: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
      Time to decrease the list step by step, up to 0 element:
         0.001579099906393822 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 10000 elements:
         0.00231859990446992 s
            list: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
      Time to decrease the list step by step, up to 0 element:
         0.001407299953825714 s
            list: empty

--------------------------------------------------------------------

Preserved dynamic array of integers:
   By acting only from the end of the array:
      Time to increase the array step by step up to 30000 elements:
         0.003644799999847237 s
            array: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
      Time to decrease the array step by step up to 0 element:
         0.002756000055342156 s
            array: empty
   By acting only from the beginning of the array:
      Time to increase the array step by step up to 30000 elements:
         0.2054611000864952 s
            array: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
      Time to decrease the array step by step up to 0 element:
         0.2067085000668385 s
            array: empty

Dynamic ArrayList pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 30000 elements:
         0.007203299971251909 s
            list: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
      Time to decrease the list step by step, up to 0 element:
         0.006684799898835081 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 30000 elements:
         0.00683309997282322 s
            list: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
      Time to decrease the list step by step, up to 0 element:
         0.005087799908778834 s
            list: empty

--------------------------------------------------------------------

Preserved dynamic array of integers:
   By acting only from the end of the array:
      Time to increase the array step by step up to 60000 elements:
         0.009835400026190655 s
            array: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
      Time to decrease the array step by step up to 0 element:
         0.007979600000567189 s
            array: empty
   By acting only from the beginning of the array:
      Time to increase the array step by step up to 60000 elements:
         0.7594995999510274 s
            array: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
      Time to decrease the array step by step up to 0 element:
         0.7474576999555893 s
            array: empty

Dynamic ArrayList pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 60000 elements:
         0.01554709993968117 s
            list: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
      Time to decrease the list step by step, up to 0 element:
         0.01119940009459697 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 60000 elements:
         0.01170210008638151 s
            list: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
      Time to decrease the list step by step, up to 0 element:
         0.008671499908473379 s
            list: empty

In the above results, for inserting/suppressing elements:
- When using a preserve array, acting from the array beginning compared to acting from the array end increases the exécution time by a factor 10 to 100 depending on array size.
- When using the Dynamic ArrayList, there is not notable difference in execution time between acting from the list beginning and acting from the list end, and this whatever the list size.

Post by **fxm** » Oct 03, 2024 14:57

Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.

Only this post has been updated.

shadow008 · Post by **shadow008** » Oct 03, 2024 16:12

fxm wrote: ↑Oct 03, 2024 14:57 Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.

I had done this test myself in the past on personal projects, but this was on allocations of 100s to 10,000s of items only. The resulting segment allocations were usually <10KB in size, and I had seen barely measurable performance difference. I had came to the conclusion:

1. Callocate effectively loaded the entire memory segment into cache as part of zeroing out the segment
2. The segments usually fit into L1 cache
3. Therefore, the only difference between Allocate + fill and Callocate + fill was the additional iteration over the callocated segment, which was entirely in low level cache, and thus did not make any considerable performance difference.

At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?

Post by **fxm** » Oct 03, 2024 16:43

shadow008 wrote: ↑Oct 03, 2024 16:12 At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?

Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).

Post by **fxm** » Oct 03, 2024 18:30

fxm wrote: ↑Oct 03, 2024 16:43
shadow008 wrote: ↑Oct 03, 2024 16:12 At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?
Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).

Simple example with only the 'CAllocate' / 'Allocate' time taken into account:

Code: Select all

#define allocNbr 10000000

Dim As Double t
Redim As Any Ptr parray(1 To allocNbr)

For N As Integer = 1 To 5
    Print "Time for " & allocNbr & " 'Callocate' of 3 pointers each : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, 3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I

    Print "Time for " & allocNbr & " 'Allocate' of 3 pointers each  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    Print
Next N

Erase parray
Sleep

Output example:

Code: Select all

Time for 10000000 'Callocate' of 3 pointers each : 0.7727757000153872 s
Time for 10000000 'Allocate' of 3 pointers each  : 0.5569001999748195 s

Time for 10000000 'Callocate' of 3 pointers each : 0.7536964999775364 s
Time for 10000000 'Allocate' of 3 pointers each  : 0.5533465999784255 s

Time for 10000000 'Callocate' of 3 pointers each : 0.7513144000059526 s
Time for 10000000 'Allocate' of 3 pointers each  : 0.560658500011499 s

Time for 10000000 'Callocate' of 3 pointers each : 0.7622070999868811 s
Time for 10000000 'Allocate' of 3 pointers each  : 0.5542497999804255 s

Time for 10000000 'Callocate' of 3 pointers each : 0.7434600999982592 s
Time for 10000000 'Allocate' of 3 pointers each  : 0.5390733000285479 s

Speedup of about 25% here.

Note: it is surprising when using 'New', we find an execution time comparable to that of 'Allocate' (better than 'CAllocate'), while the memory is set to 0.
Example with an UDT of 3 pointers to be compatible with 'New':

Code: Select all

#define allocNbr 10000000

Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type

Dim As Double t
Redim As DoublyLinkedNode Ptr parray(1 To allocNbr)

For N As Integer = 1 To 3
    Print "Time for " & allocNbr & " 'Callocate' of UDT (3 pointers) : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'Allocate' of UDT (3 pointers)  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'New' of UDT (3 pointers)       : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = New DoublyLinkedNode
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Delete'     : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Delete(parray(I))
    Next I
    t = Timer - t
    Print t & " s"
    Print
Next N

Erase parray
Sleep

Output example:

Code: Select all

Time for 10000000 'Callocate' of UDT (3 pointers) : 0.9042052000002663 s
   Time for 10000000 'Deallocate' : 0.3417718000007319 s
Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6365616000034109 s
   Time for 10000000 'Deallocate' : 0.3315588000019929 s
Time for 10000000 'New' of UDT (3 pointers)       : 0.6527570999982508 s
   Time for 10000000 'Delete'     : 0.4361705000013423 s

Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7977705999997653 s
   Time for 10000000 'Deallocate' : 0.3519302000023714 s
Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6200587000020903 s
   Time for 10000000 'Deallocate' : 0.341211499998618 s
Time for 10000000 'New' of UDT (3 pointers)       : 0.6394830000023006 s
   Time for 10000000 'Delete'     : 0.4483076000033428 s

Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7915781999985043 s
   Time for 10000000 'Deallocate' : 0.3403417999994574 s
Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6272025000029693 s
   Time for 10000000 'Deallocate' : 0.3491629999966825 s
Time for 10000000 'New' of UDT (3 pointers)       : 0.6726065999964668 s
   Time for 10000000 'Delete'     : 0.4498922999965451 s

Post by **fxm** » Oct 05, 2024 11:56

Dynamic ArrayList: Pre-allocating memory for nodes ('DynamicArrayListWithPreAlloc.bi')

I tested the possibility of using pre-allocated memory for the nodes, in order to improve the execution time for inserting and suppressing positions in the list.
The user can set the number of pre-allocated nodes using an optional parameter at construction time.

Only a rudimentary pre-allocation of nodes can be used to obtain speed up of performance:
- individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated (no time to scan the allocated memory to find a free node),
- if all pre-allocated nodes are freed, the full pre-allocation memory becomes back available,
- pre-allocated memory block cannot be resized (no time to readjust the pointers of all used nodes in allocated memory block),
- once that the end of the pre-allocated memory for nodes is reached, the next nodes are allocated individually.

Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

- DynamicArrayListWithPreAlloc.bi:

Code: Select all

' DynamicArrayListWithPreAlloc.bi

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor

- Test code:

Code: Select all

#include "DynamicArrayListWithPreAlloc.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub destroy(Byval p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    
    Scope
        Print "Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal
        For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope

    Scope
        Print "Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal = DynamicArrayList(N)
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope
End Sub

Test(9000000)

Sleep

Output example:

Code: Select all

Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 9000000 elements:
         1.498154600001138 s
            list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
      Time to decrease the list step by step, up to 0 element:
         1.025472899999013 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 9000000 elements:
         1.406190900000343 s
            list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
      Time to destroy the list in one shoot:
         0.7894261999986991 s
            list: empty

Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:
   By acting only from the end of the list:
      Time to increase the list step by step, up to 9000000 elements:
         0.9478515000013648 s
            list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
      Time to decrease the list step by step, up to 0 element:
         0.7321279999994452 s
            list: empty
   By acting only from the beginning of the list:
      Time to increase the list step by step, up to 9000000 elements:
         0.9181955000000759 s
            list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
      Time to destroy the list in one shoot:
         0.5359600999990555 s
            list: empty

Post by **fxm** » Oct 11, 2024 14:25

fxm wrote: ↑Oct 05, 2024 11:56 Dynamic ArrayList: Pre-allocating memory for nodes
.....
The user can set the number of pre-allocated nodes using an optional parameter at construction time.
.....
Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

The reference posts 1/4 and 3/4 have been updated with this improved version of the 'DynamicArrayList' type:
added memory pre-allocating for nodes, set (or not) by the user at instance construction time.

Post by **fxm** » Oct 19, 2024 16:10

File to include "DynamicArrayList.bi" : Added the 'NumberOfPreAllocAvailable' public property.

Tunning the pre-allocated memory size for nodes:

The number of pre-allocated nodes available throughout the execution is difficult to predict because it mainly depends on the configuration of the different suppressing sequences (in pre-allocated memory or not) compared to the inserting sequences:
- Individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated.
- If all pre-allocated nodes are freed, the full pre-allocation memory becomes back available.

As a result, this public property has been added.

The reference post 1/4 has been updated with this improved version of the 'DynamicArrayList' type:
added the 'NumberOfPreAllocAvailable' public property.

Post by **fxm** » Oct 20, 2024 11:49

fxm wrote: ↑Oct 19, 2024 16:10 File to include "DynamicArrayList.bi" : Added the 'NumberOfPreAllocAvailable' public property.

Tunning the pre-allocated memory size for nodes:

The number of pre-allocated nodes available throughout the execution is difficult to predict because it mainly depends on the configuration of the different suppressing sequences (in pre-allocated memory or not) compared to the inserting sequences:
- Individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated.
- If all pre-allocated nodes are freed, the full pre-allocation memory becomes back available.

As a result, this public property has been added.

- Very simple inserting/suppressing sequences to already understand the difficulty of predicting at any runtime the number of available pre-allocated nodes:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "   '";
    For I As Integer = 1 To dal.ReturnNumberOfPosition()
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print " '     => number of pre-allocated nodes now available : " & dal.NumberOfPreAllocAvailable
End Sub

Print "Creating an empty list with 4 pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(4)
PrintList(dal)
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the end of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 0)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the end of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the beginning of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 1)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the beginning of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the end of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 0)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the beginning of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the beginning of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 1)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the end of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    PrintList(dal)
Wend
Print

Sleep

Output:

Code: Select all

Creating an empty list with 4 pre-allocated nodes:
   ' '     => number of pre-allocated nodes now available : 4

----------------------------------------------------------------------

Inserting 8 elements 1 by 1 from the end of the list:
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' 1 2 '     => number of pre-allocated nodes now available : 2
   ' 1 2 3 '     => number of pre-allocated nodes now available : 1
   ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0

Suppressing all elements 1 by 1 from the end of the list:
   ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 '     => number of pre-allocated nodes now available : 1
   ' 1 2 '     => number of pre-allocated nodes now available : 2
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' '     => number of pre-allocated nodes now available : 4

----------------------------------------------------------------------

Inserting 8 elements 1 by 1 from the beginning of the list:
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' 2 1 '     => number of pre-allocated nodes now available : 2
   ' 3 2 1 '     => number of pre-allocated nodes now available : 1
   ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 8 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0

Suppressing all elements 1 by 1 from the beginning of the list:
   ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 3 2 1 '     => number of pre-allocated nodes now available : 1
   ' 2 1 '     => number of pre-allocated nodes now available : 2
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' '     => number of pre-allocated nodes now available : 4

----------------------------------------------------------------------

Inserting 8 elements 1 by 1 from the end of the list:
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' 1 2 '     => number of pre-allocated nodes now available : 2
   ' 1 2 3 '     => number of pre-allocated nodes now available : 1
   ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
   ' 1 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0

Suppressing all elements 1 by 1 from the beginning of the list:
   ' 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
   ' 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
   ' 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
   ' 5 6 7 8 '     => number of pre-allocated nodes now available : 4
   ' 6 7 8 '     => number of pre-allocated nodes now available : 4
   ' 7 8 '     => number of pre-allocated nodes now available : 4
   ' 8 '     => number of pre-allocated nodes now available : 4
   ' '     => number of pre-allocated nodes now available : 4

----------------------------------------------------------------------

Inserting 8 elements 1 by 1 from the beginning of the list:
   ' 1 '     => number of pre-allocated nodes now available : 3
   ' 2 1 '     => number of pre-allocated nodes now available : 2
   ' 3 2 1 '     => number of pre-allocated nodes now available : 1
   ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
   ' 8 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0

Suppressing all elements 1 by 1 from the end of the list:
   ' 8 7 6 5 4 3 2 '     => number of pre-allocated nodes now available : 0
   ' 8 7 6 5 4 3 '     => number of pre-allocated nodes now available : 0
   ' 8 7 6 5 4 '     => number of pre-allocated nodes now available : 0
   ' 8 7 6 5 '     => number of pre-allocated nodes now available : 4
   ' 8 7 6 '     => number of pre-allocated nodes now available : 4
   ' 8 7 '     => number of pre-allocated nodes now available : 4
   ' 8 '     => number of pre-allocated nodes now available : 4
   ' '     => number of pre-allocated nodes now available : 4

- More turbulent example with a reproducible pseudo-random sequence for the inserting then suppressing positions (list of 26 elements with 26 pre-allocated nodes):

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "   '";
    For I As Integer = 1 To dal.ReturnNumberOfPosition()
        Print *Cptr(String Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print "'   => nbr of pre-alloc nodes now available : " & dal.NumberOfPreAllocAvailable
End Sub

Print "Creating an empty list with 26 pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(26)
PrintList(dal)
Print
Print "Inserting 26 elements 1 by 1 at randomly position:"
For I As Integer = 1 To 26
    Dim As Integer N = Int(Rnd() * (dal.ReturnNumberOfPosition() + 1) + 1)
    dal.InsertInNthPosition(New String(Chr(64 + I)), N)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 at randomly position:"
While dal.ReturnNumberOfPosition() > 0
    Dim As Integer N = Int(Rnd() * dal.ReturnNumberOfPosition() + 1)
    Delete Cptr(String Ptr, dal.SuppressTheNthPosition(N))
    PrintList(dal)
Wend
Print

Sleep

Output:

Code: Select all

Creating an empty list with 26 pre-allocated nodes:
   ''   => nbr of pre-alloc nodes now available : 26

Inserting 26 elements 1 by 1 at randomly position:
   'A'   => nbr of pre-alloc nodes now available : 25
   'BA'   => nbr of pre-alloc nodes now available : 24
   'BCA'   => nbr of pre-alloc nodes now available : 23
   'BCAD'   => nbr of pre-alloc nodes now available : 22
   'BCAED'   => nbr of pre-alloc nodes now available : 21
   'BCAFED'   => nbr of pre-alloc nodes now available : 20
   'BCGAFED'   => nbr of pre-alloc nodes now available : 19
   'BCGAFEDH'   => nbr of pre-alloc nodes now available : 18
   'BCGAFEDHI'   => nbr of pre-alloc nodes now available : 17
   'BCGAFEDHIJ'   => nbr of pre-alloc nodes now available : 16
   'BCGAFKEDHIJ'   => nbr of pre-alloc nodes now available : 15
   'BCGAFKEDLHIJ'   => nbr of pre-alloc nodes now available : 14
   'MBCGAFKEDLHIJ'   => nbr of pre-alloc nodes now available : 13
   'MBCGAFKEDNLHIJ'   => nbr of pre-alloc nodes now available : 12
   'OMBCGAFKEDNLHIJ'   => nbr of pre-alloc nodes now available : 11
   'OMBCGAFPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 10
   'QOMBCGAFPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 9
   'QOMBCGAFRPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 8
   'QOMBCGAFRPKEDNLSHIJ'   => nbr of pre-alloc nodes now available : 7
   'QOMBCGAFRPKEDNLSTHIJ'   => nbr of pre-alloc nodes now available : 6
   'QOMBCGAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBCVGAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 4
   'QOMBCVGWAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 3
   'QOMBCVGWAFRXPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 2
   'QOMBCVGWAFYRXPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 1
   'QOMBCVGWAFYRXPZKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 0

Suppressing all elements 1 by 1 at randomly position:
   'QOMBCVGWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
   'QOMBCVWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
   'QOMBVWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
   'QOMBVWAFYRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 1
   'QOMBVWAFRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 2
   'QOMBVWFRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 2
   'QOMBVWFRPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 3
   'QOMBVFRPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 4
   'QOMBVFRPKEDNLSTIJ'   => nbr of pre-alloc nodes now available : 4
   'QOMBVFRPEDNLSTIJ'   => nbr of pre-alloc nodes now available : 4
   'QOMBFRPEDNLSTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBFRPEDNSTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBFRPEDNTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBFREDNTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBREDNTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBRENTIJ'   => nbr of pre-alloc nodes now available : 5
   'QOMBRENTI'   => nbr of pre-alloc nodes now available : 5
   'QOMRENTI'   => nbr of pre-alloc nodes now available : 5
   'QOMRNTI'   => nbr of pre-alloc nodes now available : 5
   'QOMRTI'   => nbr of pre-alloc nodes now available : 5
   'QOMRI'   => nbr of pre-alloc nodes now available : 5
   'QORI'   => nbr of pre-alloc nodes now available : 5
   'QOR'   => nbr of pre-alloc nodes now available : 5
   'QO'   => nbr of pre-alloc nodes now available : 5
   'Q'   => nbr of pre-alloc nodes now available : 5
   ''   => nbr of pre-alloc nodes now available : 26

Post by **fxm** » Nov 08, 2024 10:01

File to include "DynamicArrayList.bi" : Improvement of element access time

Accessing an element of a linked list is the most penalized function because of its transversal access, node by node, from a known node position to the targeted node.

- Present principle of accessing a node from the starting dummy node by using an indirection loop:

Code: Select all

nodePtr = @dummyNode
For I As Integer = 1 To posNodeIndex
    nodePtr = nodePtr->nextNodePtr
Next I

- Improvement principle of the code by using a loop of nested indirections (up to 10 here):

Code: Select all

nodePtr = @dummyNode
Do
    Select Case As Const posNodeIndex
    Case 0
        Exit Do
    Case 1
        nodePtr = nodePtr->nextNodePtr : Exit Do
    Case 2
        nodePtr = nodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 3
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 4
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 5
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 6
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 7
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 8
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case 9
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr : Exit Do
    Case Else
        nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
        posNodeIndex -= 10
    End Select
Loop

On the below usage example, the improvement is about 30% on element access (checking 100000 elements at randomly positions).

- Test code with the current DynamicArrayList.bi body included in the code:

Code: Select all

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Property NumberOfPreAllocAvailable() As Integer
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Property DynamicArrayList.NumberOfPreAllocAvailable() As Integer
    Return This.nbrPreAllocDone - This.preAllocNbr
End Property

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Const As Integer Nbr = 100000

Print "Creating a list with " & Nbr & " pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(Nbr)
For I As Integer = 1 To Nbr
    dal.InsertInNthPosition(New Long(I), 0)
Next I
PrintList(dal)
Print "Checking " & Nbr & " elements at randomly positions:"
Dim As Double t = Timer
For I As Integer = 1 To Nbr
    Dim As Integer N = Int(Rnd() * Nbr + 1)
    If *Cptr(Long Ptr, dal.ReturnFromNthPosition(N)) <> N Then Print "   Checking failed"
Next I
t = Timer - t
Print Using "#####.## s"; t
Print "Suppressing all " & Nbr & " elements:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
Wend
PrintList(dal)
Print

Sleep

Output:

Code: Select all

Creating a list with 100000 pre-allocated nodes:
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
    8.53 s
Suppressing all 100000 elements:
   list: empty

- Test code with the modified DynamicArrayList.bi body included in the code:

Code: Select all

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Property NumberOfPreAllocAvailable() As Integer
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Declare Function TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If This.nbrPreAllocDone = 0 Then
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        End If
    Else
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        End If
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex)
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        Else
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex - This.nbrUserNode - 1)
        End If
    End If
    Return nodePtr
End Function

Function DynamicArrayList.TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
    If n > 0 Then
        ' forward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case 1
                Return nodePtr->nextNodePtr
            Case 2
                Return nodePtr->nextNodePtr->nextNodePtr
            Case 3
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 4
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 5
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 6
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 7
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 8
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 9
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case Else
                nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
                n -= 10
            End Select
        Loop
    ElseIf n < 0 Then
        ' backward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case -1
                Return nodePtr->prevNodePtr
            Case -2
                Return nodePtr->prevNodePtr->prevNodePtr
            Case -3
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -4
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -5
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -6
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -7
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -8
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -9
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case Else
                nodePtr = nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
                n += 10
            End Select
        Loop
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Property DynamicArrayList.NumberOfPreAllocAvailable() As Integer
    Return This.nbrPreAllocDone - This.preAllocNbr
End Property

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Const As Integer Nbr = 100000

Print "Creating a list with " & Nbr & " pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(Nbr)
For I As Integer = 1 To Nbr
    dal.InsertInNthPosition(New Long(I), 0)
Next I
PrintList(dal)
Print "Checking " & Nbr & " elements at randomly positions:"
Dim As Double t = Timer
For I As Integer = 1 To Nbr
    Dim As Integer N = Int(Rnd() * Nbr + 1)
    If *Cptr(Long Ptr, dal.ReturnFromNthPosition(N)) <> N Then Print "   Checking failed"
Next I
t = Timer - t
Print Using "#####.## s"; t
Print "Suppressing all " & Nbr & " elements:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
Wend
PrintList(dal)
Print

Sleep

Output:

Code: Select all

Creating a list with 100000 pre-allocated nodes:
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
    5.73 s
Suppressing all 100000 elements:
   list: empty

[edit]
The reference post 1/4 has been updated with this improved version of the 'DynamicArrayList' type:
'DynamicArrayList.bi' improved for element access time..

Post by **fxm** » Nov 09, 2024 20:27

File to include "DynamicArrayList.bi" : Improvement of element access time (continuation)

Improved management to memorize the 2 nodes most recently accessed by the user.

On the same below usage example, the improvement is about 25% on element access (checking 100000 elements at randomly positions).

- Test code with the current DynamicArrayList.bi body included in the code:

Code: Select all

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Property NumberOfPreAllocAvailable() As Integer
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Declare Function TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If This.nbrPreAllocDone = 0 Then
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        End If
    Else
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        End If
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex)
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        Else
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex - This.nbrUserNode - 1)
        End If
    End If
    Return nodePtr
End Function

Function DynamicArrayList.TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
    If n > 0 Then
        ' forward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case 1
                Return nodePtr->nextNodePtr
            Case 2
                Return nodePtr->nextNodePtr->nextNodePtr
            Case 3
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 4
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 5
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 6
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 7
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 8
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 9
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case Else
                nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
                n -= 10
            End Select
        Loop
    ElseIf n < 0 Then
        ' backward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case -1
                Return nodePtr->prevNodePtr
            Case -2
                Return nodePtr->prevNodePtr->prevNodePtr
            Case -3
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -4
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -5
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -6
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -7
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -8
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -9
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case Else
                nodePtr = nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
                n += 10
            End Select
        Loop
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Property DynamicArrayList.NumberOfPreAllocAvailable() As Integer
    Return This.nbrPreAllocDone - This.preAllocNbr
End Property

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Const As Integer Nbr = 100000

Print "Creating a list with " & Nbr & " pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(Nbr)
For I As Integer = 1 To Nbr
    dal.InsertInNthPosition(New Long(I), 0)
Next I
PrintList(dal)
Print "Checking " & Nbr & " elements at randomly positions:"
Dim As Double t = Timer
For I As Integer = 1 To Nbr
    Dim As Integer N = Int(Rnd() * Nbr + 1)
    If *Cptr(Long Ptr, dal.ReturnFromNthPosition(N)) <> N Then Print "   Checking failed"
Next I
t = Timer - t
Print Using "#####.## s"; t
Print "Suppressing all " & Nbr & " elements:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
Wend
PrintList(dal)
Print

Sleep

Output:

Code: Select all

Creating a list with 100000 pre-allocated nodes:
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
    5.82 s
Suppressing all 100000 elements:
   list: empty

- Test code with the modified DynamicArrayList.bi body included in the code:

Code: Select all

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Property NumberOfPreAllocAvailable() As Integer
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Declare Function TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If (posNodeIndex > This.recent1NodeIndex) And (This.recent1NodeIndex > This.nbrUserNode Shr 2) Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Elseif posNodeIndex < This.recent2NodeIndex Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If (posNodeIndex > This.recent1NodeIndex) And (This.recent1NodeIndex > This.nbrUserNode Shr 2) Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Elseif posNodeIndex < This.recent2NodeIndex Then
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        Else
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If (posNodeIndex > This.recent1NodeIndex) And (This.recent1NodeIndex > This.nbrUserNode Shr 2) Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Elseif posNodeIndex < This.recent2NodeIndex Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If (posNodeIndex > This.recent1NodeIndex) And (This.recent1NodeIndex > This.nbrUserNode Shr 2) Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Elseif posNodeIndex < This.recent2NodeIndex Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If This.nbrPreAllocDone = 0 Then
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            Next I
        End If
    Else
        If destroy <> 0 Then
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                destroy(nodePtr->prevNodePtr->userPtr)
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        Else
            For I As Integer = 1 To This.nbrUserNode
                nodePtr = nodePtr->nextNodePtr
                If (nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1]) Then
                    ' Deallocates memory for the node
                    Deallocate(nodePtr->prevNodePtr)
                End If
            Next I
        End If
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex)
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent1NodePtr, posNodeIndex - This.recent1NodeIndex)
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.TraverseNodes(This.recent2NodePtr, posNodeIndex - This.recent2NodeIndex)
        Else
            ' dummy node closest to targeted position
            nodePtr = This.TraverseNodes(@This.dummyNode, posNodeIndex - This.nbrUserNode - 1)
        End If
    End If
    Return nodePtr
End Function

Function DynamicArrayList.TraverseNodes(ByVal nodePtr As DoublyLinkedNode Ptr, ByVal n As Integer) As DoublyLinkedNode Ptr
    If n > 0 Then
        ' forward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case 1
                Return nodePtr->nextNodePtr
            Case 2
                Return nodePtr->nextNodePtr->nextNodePtr
            Case 3
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 4
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 5
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 6
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 7
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 8
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case 9
                Return nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
            Case Else
                nodePtr = nodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr->nextNodePtr
                n -= 10
            End Select
        Loop
    ElseIf n < 0 Then
        ' backward iteration
        Do
            Select Case As Const n
            Case 0
                Return nodePtr
            Case -1
                Return nodePtr->prevNodePtr
            Case -2
                Return nodePtr->prevNodePtr->prevNodePtr
            Case -3
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -4
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -5
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -6
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -7
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -8
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case -9
                Return nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
            Case Else
                nodePtr = nodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr->prevNodePtr
                n += 10
            End Select
        Loop
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Property DynamicArrayList.NumberOfPreAllocAvailable() As Integer
    Return This.nbrPreAllocDone - This.preAllocNbr
End Property

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Const As Integer Nbr = 100000

Print "Creating a list with " & Nbr & " pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(Nbr)
For I As Integer = 1 To Nbr
    dal.InsertInNthPosition(New Long(I), 0)
Next I
PrintList(dal)
Print "Checking " & Nbr & " elements at randomly positions:"
Dim As Double t = Timer
For I As Integer = 1 To Nbr
    Dim As Integer N = Int(Rnd() * Nbr + 1)
    If *Cptr(Long Ptr, dal.ReturnFromNthPosition(N)) <> N Then Print "   Checking failed"
Next I
t = Timer - t
Print Using "#####.## s"; t
Print "Suppressing all " & Nbr & " elements:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
Wend
PrintList(dal)
Print

Sleep

Output:

Code: Select all

Creating a list with 100000 pre-allocated nodes:
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
    4.16 s
Suppressing all 100000 elements:
   list: empty

The reference post 1/4 has been updated with this improved version of the 'DynamicArrayList' type:
'DynamicArrayList.bi' improved for element access time.

Post by **fxm** » Nov 13, 2024 15:23

fxm wrote: ↑Oct 05, 2024 11:56 Dynamic ArrayList: Pre-allocating memory for nodes
.....
The user can set the number of pre-allocated nodes using an optional parameter at construction time.
.....
Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

This improvment impacts not only the element insertion and suppression, but also the element access time, because the nodes are thus stored in contiguous memory locations so that decreases the CPU cache misses, even for randomly position access.

Test code:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "   list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub test(Byval NbrOfElements As Integer, Byval NbrOfPreAllocatedNodes As Integer)
    Dim As Double t

    Print "Creating a list of " & NbrOfElements & " with " & NbrOfPreAllocatedNodes & " pre-allocated nodes:"
    t = Timer
    Dim As DynamicArrayList dal = DynamicArrayList(NbrOfPreAllocatedNodes)
    For I As Integer = 1 To NbrOfElements
        dal.InsertInNthPosition(New Long(I), 0)
    Next I
    t = Timer - t
    Print Using "   runtime:####.#### s"; t
    PrintList(dal)
    Print "Checking " & NbrOfElements & " elements at randomly positions:"
    Randomize(0)
    t = Timer
    For I As Integer = 1 To NbrOfElements
        Dim As Integer N = Int(Rnd() * NbrOfElements + 1)
        If *Cptr(Long Ptr, dal.ReturnFromNthPosition(N)) <> N Then Print "   Check: failed" : Sleep : End
    Next I
    t = Timer - t
    Print Using "   runtime:####.#### s"; t
    Print "   Check: successful"
    Print "Suppressing all " & NbrOfElements & " elements:"
    t = Timer
    While dal.ReturnNumberOfPosition() > 0
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    Wend
    t = Timer - t
    Print Using "   runtime:####.#### s"; t
    PrintList(dal)
    Print
End Sub

test(100000, 0)
test(100000, 100000)

Sleep

Code: Select all

Creating a list of 100000 with 0 pre-allocated nodes:
   runtime:   0.0188 s
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
   runtime:   4.6741 s
   Check: successful
Suppressing all 100000 elements:
   runtime:   0.0149 s
   list: empty

Creating a list of 100000 with 100000 pre-allocated nodes:
   runtime:   0.0125 s
   list: 1 2 3 4 5 ..... 99996 99997 99998 99999 100000
Checking 100000 elements at randomly positions:
   runtime:   4.1696 s
   Check: successful
Suppressing all 100000 elements:
   runtime:   0.0127 s
   list: empty

Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Doubly linked list (optimized) [under the hood to build a Dynamic ArrayList]

Re: Doubly linked list (optimized) [under the hood to build a Dynamic ArrayList]

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Re: Dynamic ArrayList (with circular doubly linked list under the hood)