Example test program for Keyed Linked List
Code: Select all
#Include Once "windows.bi"
#Include Once "clsKeyList.bas"
' Create the actual list. By default the class creates a list
' large enough to hold 20 items. Once that limit is reached, the
' list will grow in size by another 20 items, etc. You can control
' how much to grow the list by either through the constructor
' or by using the GrowBy property.
'
' Dim cList As clsKeyList = 100 ' allow list to grow by 100 items
' - or -
' cList.GrowBy = 100
'
'
' Keys must be unique otherwise the data of the found key simply gets updated
' with the new information rather than added.
'
' The class allows you add items as either String, Integer, Double or
' any arbitrary memory location and size. This is accomplished by the class
' simply overloading the AddItem function call.
'
' cList.Additem( "1000", 32456 ) ' <-- add an integer with a key of "1000"
' cList.Additem( "1000", @e, len(e)) ' <-- add an EMPLOYEE_TYPE structure/record held
' in variable "e" With a Key of "1000"
'
' You can use the convenience class property GetKeyString(i) to retrieve the key for the
' current active node.
' Data values can be retrieved using several convenience properties depending on the
' type of data being stored.
' cList.GetDataString(i) ' Retrieves a string (based on zstring or wstring stored data)
' ' If an integer or double is stored in the data area then that
' ' value is returned in string format.
' cList.GetDataInteger(i) ' Retrieves an integer
' cList.GetDataDouble(i) ' Retrieves a double
' There is no convenience property to retrieve unstructured data stored in the node. You must
' maniuplate the node.pData as you require.
'
Dim cList As clsKeyList
Dim node As clsListNode
Dim i As Integer
With cList
.AddItem( "1", "Paul Squires" )
.AddItem( "2", "Harry Potter" )
.AddItem( "3", "Lord Voldemort" )
.AddItem( "4", "Ron Weasley" )
.AddItem( "5", "Hermione Granger" )
.AddItem( "6", "Albus Dumbledore" )
.AddItem( "7", "Bellatrix Lestrange" )
.AddItem( "8", "Hedwig" )
.AddItem( "9", "Tom Riddle" )
.AddItem( "10", "Sirius Black" )
End With
' Print the list of items. This demonstrates how to retieve items based
' on their index position. Retrieval is very fast (as fast as array access).
?
? "Print the keys and the strings held in the list."
For i = 0 To cList.Count - 1
If cList.GetByIndex(i) Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
End If
Next
' Retrieve a list item using its key value. This method is a little slower
' because a linear search must be performed on the list in order to match the
' key value. For much faster access (especially if the list is large) consider
' using the clsHashTable class. That class provides almost instant access to
' keys and their associated data with the downside of being having little more
' memory usage.
?
? "Get using Key = 5";
If cList.GetByKey("5") Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
? " FOUND Key: "; cList.GetKeyString, "Data: "; cList.GetDataString
Else
? " KEY NOT FOUND"
End If
?
? "Get using Key = 999999";
If cList.GetByKey("999999") Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
? " FOUND Key: "; cList.GetKeyString, "Data: "; cList.GetDataString
Else
? " KEY NOT FOUND"
End If
?
? "Delete Key = 3";
If cList.DeleteByKey("3") Then
? " FOUND and DELETED"
Else
? " NOT FOUND"
End If
' Keys must be unique in a list. If you try to add data and the key already
' exists then the new data simply replaces the old. This is a very fast way
' of updating an existing list item.
?
? "Change the string held in key = 4"
cList.AddItem( "4", "The text in this item has been updated.")
?
? "Print the keys and the strings held in the list."
For i = 0 To cList.Count - 1
If cList.GetByIndex(i) Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
End If
Next
?
cList.ClearList ' Clear the list so that we can re-use it again if we wish
?
? "Create an Integer list"
With cList
.AddItem( "1", 100 )
.AddItem( "2", 200 )
.AddItem( "3", 300 )
.AddItem( "4", 400 )
End With
?
? "Print the keys and the integers held in the list."
For i = 0 To cList.Count - 1
If cList.GetByIndex(i) Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
' Get the raw Integer value using cList.GetDataInteger. For display
' purposes we can call cList.GetDataString(i) which does the conversion to
' string for us.
? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
End If
Next
?
cList.ClearList ' Clear the list so that we can re-use it again if we wish
?
? "Create a Double list"
With cList
.AddItem( "1", 14521.5879 )
.AddItem( "2", 547.4754 )
.AddItem( "3", 548968.77 )
.AddItem( "4", 98487456.436 )
End With
?
? "Print the keys and the doubles held in the list."
For i = 0 To cList.Count - 1
If cList.GetByIndex(i) Then
' if we needed to manipulate the node data directly then we would
' call the GetNode property. In this case, we do not need to.
'node = cList.GetNode(i)
' Get the raw Double value using cList.GetDataDouble. For display
' purposes we can call cList.GetDataString(i) which does the conversion to
' string for us.
? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
End If
Next
?
? "Done."
Sleep
Keyed Linked List - Source Code (clsKeyList.bas)
Code: Select all
''
'' clsKeyList
''
Type clsListNode
sKey As String
pData As Any Ptr
nDataType As Byte ' 0:ZString ptr, 1:WString ptr, 2:Unstructured, 3:Integer ptr, 4:Double ptr
End Type
Type clsKeyList
Private:
m_nGrowBy As Integer ' how big to grow the list by when needed
m_nCount As Integer ' current number of elements in the list
m_nCurrent As Integer ' current position in the list
m_arrayList(Any) As clsListNode
Declare Function _CreateNode() As Integer
Declare Function _DeleteNode( ByVal nIndex As Integer ) As Integer
Public:
Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const String) As Integer
Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const WString) As Integer
Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Integer) As Integer
Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Double) As Integer
Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nAddr As Any Ptr, ByRef nSize As Integer) As Integer
Declare Function GetByIndex( ByVal nIndex As Integer ) As Integer
Declare Function GetByKey( ByRef sKey As Const String ) As Integer
Declare Function ClearList() As Integer
Declare Function DeleteByIndex( ByVal nIndex As Integer ) As Integer
Declare Function DeleteByKey( ByRef sKey As Const String ) As Integer
Declare Function GetNode( ByVal nIndex As Integer ) ByRef As clsListNode
Declare Function GetKeyString( ByVal nIndex As Integer = -1 ) As String
Declare Function GetDataString( ByVal nIndex As Integer = -1) As String
Declare Function GetDataInteger( ByVal nIndex As Integer = -1) As Integer
Declare Function GetDataDouble( ByVal nIndex As Integer = -1 ) As Double
Declare Property GrowBy( ByVal nValue As Integer)
Declare Property GrowBy() As Integer
Declare Property Count() As Integer
Declare Constructor ( ByVal nInitalGrowBy As Integer = -1)
Declare Destructor
End Type
''
''
Constructor clsKeyList( ByVal nInitalGrowBy As Integer = -1)
m_nGrowBy = Iif( nInitalGrowBy = -1, 20, nInitalGrowBy)
m_nCount = 0
End Constructor
''
''
Destructor clsKeyList
this.ClearList
End Destructor
''
''
Property clsKeyList.GrowBy( ByVal nValue As Integer)
If nValue <= 0 Then Exit Property
this.m_nGrowBy = nValue
End Property
Property clsKeyList.GrowBy() As Integer
Property = this.m_nGrowBy
End Property
''
''
Property clsKeyList.Count() As Integer
Property = this.m_nCount
End Property
''
''
Function clsKeyList.ClearList() As Integer
' Deallocate all manually allocated memory in this list
For i As Integer = LBound(m_arrayList) To Ubound(m_arrayList)
Deallocate m_arrayList(i).pData
Next
Erase m_arrayList
m_nCount = 0
Function = True
End Function
''
''
Function clsKeyList._CreateNode() As Integer
Dim ub As Integer = Ubound(m_arrayList)
m_nCount = m_nCount + 1
' Determine if the lists need to be grown in order to
' accomodate the new node.
If m_nCount > ub Then
ReDim Preserve m_arrayList(ub + m_nGrowBy) As clsListNode
End If
Return m_nCount - 1 ' zero based position in array
End Function
''
''
Function clsKeyList.AddItem Overload ( ByRef sKey As Const String, _
ByRef sData As Const String _
) As Integer
' If key already exists in this list then simply update the
' node with the new data, otherwise create the new node with
' data at the end of the list.
If this.GetByKey(sKey) Then
' m_nCurrent is already set in GetByKey if found successfully
Else
m_nCurrent = this._CreateNode()
End If
m_arrayList(m_nCurrent).pData = CAllocate(1, Len(sData)+1)
m_arrayList(m_nCurrent).nDataType = 0 ' zstring ptr
m_arrayList(m_nCurrent).sKey = sKey
*Cast(ZString Ptr, m_arrayList(m_nCurrent).pData) = sData
Return True
End Function
''
''
Function clsKeyList.AddItem Overload ( ByRef sKey As Const String, _
ByRef sData As Const WString _
) As Integer
' If key already exists in this list then simply update the
' node with the new data, otherwise create the new node with
' data at the end of the list.
If this.GetByKey(sKey) Then
' m_nCurrent is already set in GetByKey if found successfully
Else
m_nCurrent = this._CreateNode()
End If
m_arrayList(m_nCurrent).pData = CAllocate(1, Len(sData)+1)
m_arrayList(m_nCurrent).nDataType = 1 ' wstring ptr
m_arrayList(m_nCurrent).sKey = sKey
*Cast(WString Ptr, m_arrayList(m_nCurrent).pData) = sData
Return True
End Function
''
''
Function clsKeyList.AddItem Overload ( ByRef sKey As Const String, _
ByRef nData As Integer _
) As Integer
' If key already exists in this list then simply update the
' node with the new data, otherwise create the new node with
' data at the end of the list.
If this.GetByKey(sKey) Then
' m_nCurrent is already set in GetByKey if found successfully
Else
m_nCurrent = this._CreateNode()
End If
m_arrayList(m_nCurrent).pData = CAllocate(1, Len(Integer))
m_arrayList(m_nCurrent).nDataType = 3 ' integer ptr
m_arrayList(m_nCurrent).sKey = sKey
*Cast(Integer Ptr, m_arrayList(m_nCurrent).pData) = nData
Return True
End Function
''
''
Function clsKeyList.AddItem Overload ( ByRef sKey As Const String, _
ByRef nData As Double _
) As Integer
' If key already exists in this list then simply update the
' node with the new data, otherwise create the new node with
' data at the end of the list.
If this.GetByKey(sKey) Then
' m_nCurrent is already set in GetByKey if found successfully
Else
m_nCurrent = this._CreateNode()
End If
m_arrayList(m_nCurrent).pData = CAllocate(1, Len(Integer))
m_arrayList(m_nCurrent).nDataType = 4 ' double ptr
m_arrayList(m_nCurrent).sKey = sKey
*Cast(Double Ptr, m_arrayList(m_nCurrent).pData) = nData
Return True
End Function
''
''
Function clsKeyList.AddItem Overload ( ByRef sKey As Const String, _
ByRef nAddr As Any Ptr, _
ByRef nSize As Integer _
) As Integer
' If key already exists in this list then simply update the
' node with the new data, otherwise create the new node with
' data at the end of the list.
If this.GetByKey(sKey) Then
' m_nCurrent is already set in GetByKey if found successfully
Else
m_nCurrent = this._CreateNode()
End If
m_arrayList(m_nCurrent).sKey = sKey
If nSize > 0 Then
m_arrayList(m_nCurrent).pData = CAllocate(1, nSize)
MemCpy m_arrayList(m_nCurrent).pData, nAddr, nSize
End If
Return True
End Function
''
''
Function clsKeyList.GetByIndex( ByVal nIndex As Integer ) As Integer
If (nIndex >=0) And (nIndex < m_nCount) Then
m_nCurrent = nIndex
Return True
End If
Return False
End function
''
''
Function clsKeyList.GetByKey( ByRef sKey As Const String ) As Integer
For i As Integer = LBound(m_arrayList) To Ubound(m_arrayList)
If m_arrayList(i).sKey = sKey Then
m_nCurrent = i
Return True
End If
Next
Return False
End Function
''
''
Function clsKeyList.GetNode( ByVal nIndex As Integer = -1) ByRef As clsListNode
If nIndex <> -1 Then this.GetByIndex(nIndex)
If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
(m_nCurrent <= Ubound(m_arrayList)) Then
Return m_arrayList(m_nCurrent)
End If
End Function
''
''
Function clsKeyList.GetKeyString( ByVal nIndex As Integer = -1 ) As String
If nIndex <> -1 Then this.GetByIndex(nIndex)
If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
(m_nCurrent <= Ubound(m_arrayList)) Then
Return m_arrayList(m_nCurrent).sKey
End If
End Function
''
''
Function clsKeyList.GetDataString( ByVal nIndex As Integer = -1) As String
If nIndex <> -1 Then this.GetByIndex(nIndex)
If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
(m_nCurrent <= Ubound(m_arrayList)) Then
Select Case m_arrayList(m_nCurrent).nDataType
Case 0 ' ztring ptr
Return *Cast(ZString Ptr, m_arrayList(m_nCurrent).pData)
Case 1 ' wstring ptr
Return *Cast(WString Ptr, m_arrayList(m_nCurrent).pData)
Case 2 ' unstructured data
' The programmer need to manipulate the node data directly
' in order to get meaningful data. Therefore, simply
' return a null string.
Return ""
Case 3 ' Integer ptr
Return Str(*Cast(Integer Ptr, m_arrayList(m_nCurrent).pData))
Case 4 ' Double ptr
Return Str(*Cast(Double Ptr, m_arrayList(m_nCurrent).pData))
End Select
End If
End Function
''
''
Function clsKeyList.GetDataInteger( ByVal nIndex As Integer = -1) As Integer
If nIndex <> -1 Then this.GetByIndex(nIndex)
If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
(m_nCurrent <= Ubound(m_arrayList)) Then
If m_arrayList(m_nCurrent).nDataType = 3 Then
Return *Cast(Integer Ptr, m_arrayList(m_nCurrent).pData)
End If
End If
Return 0 ' not an integer being stored in the data area
End Function
''
''
Function clsKeyList.GetDataDouble( ByVal nIndex As Integer = -1) As Double
If nIndex <> -1 Then this.GetByIndex(nIndex)
If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
(m_nCurrent <= Ubound(m_arrayList)) Then
If m_arrayList(m_nCurrent).nDataType = 4 Then
Return *Cast(Double Ptr, m_arrayList(m_nCurrent).pData)
End If
End If
Return 0 ' not an double being stored in the data area
End Function
''
''
Function clsKeyList._DeleteNode( ByVal nIndex As Integer ) As Integer
' Private function that compresses the array and frees any allocated pData memory.
Deallocate m_arrayList(nIndex).pData
' Do the delete
For i As Integer = nIndex To Ubound(m_arrayList) - 1
m_arrayList(i) = m_arrayList(i+1)
Next
Deallocate m_arrayList(m_nCount).pData ' free the allocated memory in pData
m_nCount = m_nCount - 1
Return True
End Function
''
''
Function clsKeyList.DeleteByIndex( ByVal nIndex As Integer ) As Integer
If this.GetByIndex(nIndex) Then
this._DeleteNode(nIndex)
Return True
End If
Return False
End Function
''
''
Function clsKeyList.DeleteByKey( ByRef sKey As Const String ) As Integer
If this.GetByKey(sKey) Then
this._DeleteNode(m_nCurrent)
Return True
End If
Return False
End Function