Keyed Linked List
Example test program for Keyed Linked List
#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)
''
'' 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
Hash Table
Example test program for Hash Table
#Include Once "windows.bi"
#Include Once "clsHashTable.bas"
' Create the actual hash table. By default the class creates a hash table
' large enough to hold 500 slots. You can control how large the table size
' is through overloading the constructor (once set, the table size can
' not be changed).
'
' Dim cHash As clsHashTable ' table size of 500 slots and
' ' lists can grow by 20 items (default)
'
' Dim cHash As clsHashTable = 1000 ' table size of 1000 slots and
' ' lists can grow by 20 items (default)
'
' Dim cHash As clsHashTable = clsHashTable(5000, 50)
' ' table size of 1000 slots and
' ' lists can grow by 50 items
' ' at a time (see below)
'
' The hash of the key to find/add is computed and then converted to
' a 'slot' that falls within the TableSize range. This slot is where
' the linked list begins for all keys having that hash value. The keys
' are stored in a simple list (dynamic array) and is not sorted (this
' arrangement is plenty fast even for large lists and it decreases the
' complexity of the algorithm).
'
' You can change the default number of items that will be stored in a
' linked list by using the GrowListsBy property. By default this value
' is 20 items. When the list reaches this amount it will grow by an
' additional GrowListsBy amount.
' cHash.GrowListsBy = 100
'
' The key is found iterating through the linked list at the initial
' found hash 'slot'. If the key matches then the search is over. When
' adding a Key/Data, if the Key already exists then the new Data simply
' replaces the old data.
' -----------------------------------------
' | 0 | 0 | 121120 | 0 | 0 | 0 | <--- m_hList(n) (if > 0 then pointer to clsKeyList)
' -----------------------------------------
' | 4366 | clsListNode item ( linked list )
' --------
' | 2314 | clsListNode item ( linked list )
' --------
' | etc.. |
' --------
'
' 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.
'
' cHash.Additm( "1000", 32456 ) ' <-- add an integer with a key of "1000"
' cHash.Additm( "1000", @e, len(e)) ' <-- add an EMPLOYEE_TYPE structure/record held
' in variable "e" With a Key of "1000"
'
Dim cHash As clsHashTable = clsHashTable(5000, 50)
Dim sKey As String
Dim sData As String
Dim i As Integer
' Create random keys and data to load into the hash table
Randomize Timer
'' Function to a random number in the range [first, last), or {first <= x < last}.
Function rnd_range (first As Double, last As Double) As String
Function = Str( Fix(Rnd * (last - first) + first) )
End Function
For i = 1 To 10000
sKey = rnd_range( 100000, 999999 )
sData = "Data" & Str(i)
cHash.AddItem sKey, sData
Next
?
? "COUNT = "; cHash.Count
?
If cHash.FindItem( "100000" ) 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 = cHash.GetNode
? " FOUND Key: "; cHash.GetKeyString, "Data: "; cHash.GetDataString
Else
? " KEY NOT FOUND"
End If
?
? " UPDATE or ADD data for Key = 500000"
cHash.AddItem WSTR("500000"), "This is updated data for Key 500000"
?
? "Delete Key = 500000";
If cHash.DeleteItem("500000") Then
? " FOUND and DELETED"
Else
? " NOT FOUND"
End If
?
? "COUNT = "; cHash.Count
'?
'? "ITERATE THE LIST"
'cHash.MoveFirst
'Do Until cHash.Eof
' ? "Key: "; cHash.GetKeyString, "Data: "; cHash.GetDataString
' cHash.MoveNext
'Loop
' Rather than iterate the list and output it to the screen, we will
' print it to a disk file.
?
? "Debug data output to _debug.txt file"
cHash.Debug( "_debug.txt" )
? "Debug file created."
cHash.ClearTable
? "Done."
Sleep
Hash Table - Source Code (clsHashTable.bas)
#Include Once "clsKeyList.bas"
''
'' clsHashTable
''
''
''
''
Type clsHashTable
Private:
m_nTableSize As Integer ' how big the main hash list is
m_nCount As Integer ' current number of elements in all lists in the hash table
m_nSlot As Integer ' current position in the hash list
m_nGrowListsBy As Integer ' how big to grow the linked lists by when needed
' Iterating the hash table (iterating uses the m_nSlot postion to know what the
' current linked list, and the nLLIndex to position within that linked list)
m_nEOF As Integer ' signals that we are at the end of the table
m_nLLIndex As Integer ' position within the current m_nSlot linked list
m_hList(Any) As clsKeyList Ptr
Declare Function _GetSlot( ByRef sKey As Const String ) 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 FindItem( ByRef sKey As Const String ) As Integer
Declare Function DeleteItem( ByRef sKey As Const String ) As Integer
Declare Function ClearTable() As Integer
Declare Function GetNode() ByRef As clsListNode
Declare Function GetKeyString() As String
Declare Function GetDataString() As String
Declare Function GetDataInteger() As Integer
Declare Function GetDataDouble() As Double
Declare Property Count() As Integer
Declare Function MoveFirst() As Integer
Declare Function MoveNext() As Integer
Declare Property Eof() As Integer
Declare Property GrowListsBy( ByVal nValue As Integer)
Declare Property GrowListsBy() As Integer
Declare Function Debug( ByRef sFilename As Const String = "_debug.txt" ) As Integer
Declare Constructor ( ByVal nTableSize As Integer = -1, ByVal nGrowListsBy As Integer = -1)
Declare Destructor
End Type
''
''
Constructor clsHashTable( ByVal nTableSize As Integer = -1, ByVal nGrowListsBy As Integer = -1)
m_nTableSize = Iif( nTableSize = -1, 500, nTableSize)
m_nGrowListsBy = Iif( nGrowlistsBy = -1, 20, nGrowlistsBy)
m_nCount = 0
ReDim m_hList(m_nTableSize) As clsKeyList Ptr
End Constructor
''
''
Destructor clsHashTable
this.ClearTable
End Destructor
''
''
Property clsHashTable.Count() As Integer
m_nCount = 0
For i As Integer = LBound(m_hList) To Ubound(m_hList)
If m_hList(i) Then
m_nCount = m_nCount + m_hList(i)->Count
End If
Next
Property = this.m_nCount
End Property
''
''
Property clsHashTable.Eof() As Integer
Property = this.m_nEOF
End Property
''
''
Property clsHashTable.GrowListsBy( ByVal nValue As Integer)
If nValue <= 0 Then Exit Property
this.m_nGrowListsBy = nValue
End Property
Property clsHashTable.GrowListsBy() As Integer
Property = this.m_nGrowListsBy
End Property
''
''
Function clsHashTable.ClearTable() As Integer
' Deallocate all manually allocated memory in this list
For i As Integer = LBound(m_hList) To Ubound(m_hList)
If m_hList(i) Then
Delete m_hList(i)
End If
Next
Erase m_hList
m_nCount = 0
Return True
End Function
''
''
'' Compute the hash value of the incoming key to determine the slot
''
Function clsHashTable._GetSlot( ByRef sKey As Const String ) As Integer
Dim nLen As Integer = Len(sKey)
Dim accul As UInteger = 0
Dim last As UInteger = 0
Dim i As Integer = 0
For i = 0 To nLen - 1
last = accul
accul = (accul Shl 5 )
accul = accul - last + sKey[i]
Next
Function = (accul Mod m_nTableSize)
End Function
''
''
Function clsHashTable.AddItem Overload ( ByRef sKey As Const String, _
ByRef sData As Const String _
) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position.
If m_hList(nPosition) = Null Then
m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
End If
' Add the key/data to the linked list at nPosition in the hash array
m_hList(nPosition)->AddItem(sKey, sData)
Return True
End Function
''
''
'Function clsHashTable.AddItem Overload ( ByRef sKey As Const String, _
' ByRef sData As Const WString _
' ) As Integer
'
' Dim nPosition As Integer = this._GetSlot(sKey)
'
' ' Determine if a linked list exists at this position.
' If m_hList(nPosition) = Null Then
' m_hList(nPosition) = New clsKeyList
' End If
'
' ' Add the key/data to the linked list at nPosition in the hash array
' m_hList(nPosition)->AddItem(sKey, sData)
'
' Return True
'
'End Function
''
''
Function clsHashTable.AddItem Overload ( ByRef sKey As Const String, _
ByRef nData As Integer _
) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position.
If m_hList(nPosition) = Null Then
m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
End If
' Add the key/data to the linked list at nPosition in the hash array
m_hList(nPosition)->AddItem(sKey, nData)
Return True
End Function
''
''
Function clsHashTable.AddItem Overload ( ByRef sKey As Const String, _
ByRef nData As Double _
) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position.
If m_hList(nPosition) = Null Then
m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
End If
' Add the key/data to the linked list at nPosition in the hash array
m_hList(nPosition)->AddItem(sKey, nData)
Return True
End Function
''
''
Function clsHashTable.AddItem Overload ( ByRef sKey As Const String, _
ByRef nAddr As Any Ptr, _
ByRef nSize As Integer _
) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position.
If m_hList(nPosition) = Null Then
m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
End If
' Add the key/data to the linked list at nPosition in the hash array
m_hList(nPosition)->AddItem(sKey, nAddr, nSize)
Return True
End Function
''
''
Function clsHashTable.FindItem( ByRef sKey As Const String ) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position. If it does
' not then create the list.
If m_hList(nPosition) = Null Then Return False
' Search the linked list to find the sKey at this hash position
' because multiple keys could be hashed to the same linked list.
If m_hList(nPosition)->GetByKey(sKey) Then
m_nSlot = nPosition
Return True
End If
m_nSlot = -1
Return False
End Function
''
''
Function clsHashTable.DeleteItem( ByRef sKey As Const String ) As Integer
Dim nPosition As Integer = this._GetSlot(sKey)
' Determine if a linked list exists at this position.
If m_hList(nPosition) = Null Then Return False
m_nSlot = -1
If m_hList(nPosition)->DeleteByKey(sKey) Then
' If there are no more entries in this linked list then destroy it
If m_hList(nPosition)->Count = 0 Then
Delete m_hList(nPosition)
m_hList(nPosition) = Null
End If
Return True
End If
Return False
End Function
''
''
Function clsHashTable.GetNode() ByRef As clsListNode
If m_nSlot >= 0 Then
If m_hList(m_nSlot) <> Null Then
Return m_hList(m_nSlot)->GetNode(m_nLLIndex)
End If
End If
End Function
''
''
Function clsHashTable.GetKeyString() As String
If m_nSlot >= 0 Then
If m_hList(m_nSlot) <> Null Then
Return m_hList(m_nSlot)->GetKeyString(m_nLLIndex)
End If
End If
End Function
''
''
Function clsHashTable.GetDataString() As String
If m_nSlot >= 0 Then
If m_hList(m_nSlot) <> Null Then
Return m_hList(m_nSlot)->GetDataString(m_nLLIndex)
End If
End If
End Function
''
''
Function clsHashTable.GetDataInteger() As Integer
If m_nSlot >= 0 Then
If m_hList(m_nSlot) <> Null Then
Return m_hList(m_nSlot)->GetDataInteger(m_nLLIndex)
End If
End If
End Function
''
''
Function clsHashTable.GetDataDouble() As Double
If m_nSlot >= 0 Then
If m_hList(m_nSlot) <> Null Then
Return m_hList(m_nSlot)->GetDataDouble(m_nLLIndex)
End If
End If
End Function
''
''
Function clsHashTable.MoveFirst() As Integer
m_nSlot = -1
m_nEOF = False
For i As Integer = LBound(m_hList) To Ubound(m_hList)
If m_hList(i) <> Null Then
m_nLLIndex = 0
m_nSlot = i: Exit For
End If
Next
If (m_nSlot = -1) Then
m_nEOF = True: Return True
End If
m_hList(m_nSlot)->GetByIndex(m_nLLIndex)
Return m_nEOF
End Function
''
''
Function clsHashTable.MoveNext() As Integer
Dim nNextList As Integer = -1
m_nEOF = False
' Determine if we are finished iterating the current linked list. If we
' are finished then try to move to the next linked list until we reach
' the end of the hash table.
m_nLLIndex = m_nLLIndex + 1
If m_hList(m_nSlot)->GetByIndex(m_nLLIndex) Then
Return m_nEOF
End If
' Try to get the next linked list
For i As Integer = m_nSlot + 1 To Ubound(m_hList)
If m_hList(i) <> Null Then
m_nLLIndex = 0
nNextList = i
m_nSlot = i: Exit For
End If
Next
If (nNextList = -1) Then
m_nEOF = True: Return True
End If
m_hList(m_nSlot)->GetByIndex(m_nLLIndex)
Return m_nEOF
End Function
''
''
Function clsHashTable.Debug( ByRef sFilename As Const String = "_debug.txt" ) As Integer
Dim nHighSlot As Integer ' slot with most keys
Dim nHighCount As Integer ' #items in the high slot
Dim nGrowBy As Integer
Dim st As String
Dim f As Integer
Dim crlf As String = Chr(13,10)
For i As Integer = LBound(m_hList) To Ubound(m_hList)
If (i Mod 50) = 0 Then
? "Reading slot "; i; " of "; Ubound(m_hList)
End If
st += "Slot: " & i
If m_hList(i) = Null Then
st += " <NULL>" & crlf
Continue For
Else
st += " (Count:" & m_hList(i)->Count & ")" & crlf
If m_hList(i)->Count >= nHighCount Then
nHighCount = m_hList(i)->Count
nHighSlot = i
End If
End If
nGrowBy = m_hList(i)->GrowBy
For y As Integer = 0 To m_hList(i)->Count - 1
st += " Index: " & y & " Key: " & m_hList(i)->GetKeyString(y) & " Data: " & m_hList(i)->GetDataString(y) & crlf
Next
st += crlf
Next
st = "HASHTABLE DEBUG FILE" & crlf & _
"TableSize = " & m_nTableSize & " slots" & crlf & _
"Total Count = " & this.Count & " items" & crlf & _
"Highest Slot# = " & nHighSlot & " (" & nHighCount & " items)" & crlf & _
"List GrowBy = " & nGrowBy & crlf & _
crlf & st
f = Freefile
Open sFilename For Output As #f
Print #f, st
Close #f
Function = 0
End Function
Updated original post to correct GetKeyString and GetDataString per my post on the FB forum: http://www.freebasic.net/forum/viewtopic.php?f=7&t=23902#p211207