C/sorting.and.searching.cormen.algo/src/vah.txt

   1 VERSION 1.0 CLASS
   2 BEGIN
   3   MultiUse = -1  'True
   4   Persistable = 0  'NotPersistable
   5   DataBindingBehavior = 0  'vbNone
   6   DataSourceBehavior  = 0  'vbNone
   7   MTSTransactionMode  = 0  'NotAnMTSObject
   8 END
   9 Attribute VB_Name = "CHash"
  10 Attribute VB_GlobalNameSpace = False
  11 Attribute VB_Creatable = True
  12 Attribute VB_PredeclaredId = False
  13 Attribute VB_Exposed = False
  14 Option Explicit
  15
  16 ' hash table, array Method
  17
  18 Private Node As CNode                  ' class for allocating nodes
  19
  20 Private NextNode() As Long             ' next node
  21 Private key() As Variant               ' keys
  22 Private rec() As Variant               ' record
  23
  24 Private HashTableSize As Long          ' Size of HashTable
  25 Private HashTable() As Long            ' HashTable(0..HashTableSize-1)
  26 Private GrowthFactor As Single                ' growth factor
  27
  28 Private Function Hash(ByVal KeyVal As Variant) As Long
  29 '   inputs:
  30 '       KeyVal                key
  31 '   returns:
  32 '       hashed value of key
  33 '   action:
  34 '       Compute hash value based on KeyVal.
  35 '
  36     Hash = KeyVal Mod HashTableSize
  37 End Function
  38
  39 Public Sub Insert(ByVal KeyVal As Variant, ByRef RecVal As Variant)
  40 '   inputs:
  41 '       KeyVal                key of node to insert
  42 '       RecVal                record associated with key
  43 '   action:
  44 '       Inserts record RecVal with key KeyVal.
  45 '
  46     Dim p As Long
  47     Dim p0 As Long
  48     Dim bucket As Long
  49
  50     ' allocate node and insert in table
  51
  52     ' insert node at beginning of list
  53     bucket = Hash(KeyVal)
  54     p = Node.Alloc()
  55     If p > UBound(key) Then
  56         ReDim Preserve NextNode(1 To UBound(NextNode) * GrowthFactor)
  57         ReDim Preserve key(1 To UBound(key) * GrowthFactor)
  58         ReDim Preserve rec(1 To UBound(rec) * GrowthFactor)
  59     End If
  60     p0 = HashTable(bucket)
  61     HashTable(bucket) = p
  62     NextNode(p) = p0
  63     key(p) = KeyVal
  64     rec(p) = RecVal
  65 End Sub
  66
  67
  68 Public Sub Delete(ByVal KeyVal As Variant)
  69 '   inputs:
  70 '       KeyVal                key of node to delete
  71 '   action:
  72 '       Deletes record with key KeyVal.
  73 '   error:
  74 '       errKeyNotFound
  75 '
  76     Dim p0 As Long
  77     Dim p As Long
  78     Dim bucket As Long
  79
  80    ' delete node containing key from table
  81
  82     ' find node
  83     p0 = 0
  84     bucket = Hash(KeyVal)
  85     p = HashTable(bucket)
  86     Do While p <> 0
  87         If key(p) = KeyVal Then Exit Do
  88         p0 = p
  89         p = NextNode(p)
  90     Loop
  91     If p = 0 Then Raise errKeyNotFound, "CHash.Delete"
  92
  93     ' p designates node to delete, remove it from list
  94     If p0 <> 0 Then
  95         ' not first node, p0 points to previous node
  96         NextNode(p0) = NextNode(p)
  97     Else
  98         ' first node on chain
  99         HashTable(bucket) = NextNode(p)
 100     End If
 101
 102     Node.Free (p)
 103     Set rec(p) = Nothing
 104 End Sub
 105
 106 Public Function Find(ByVal KeyVal As Variant) As Variant
 107 '   inputs:
 108 '       KeyVal                key of node to delete
 109 '   returns:
 110 '       record associated with key
 111 '   action:
 112 '       Finds record with key KeyVal
 113 '   error:
 114 '       errKeyNotFound
 115 '
 116     Dim p As Long
 117
 118     '  find node containing key
 119
 120     p = HashTable(Hash(KeyVal))
 121     Do While p <> 0
 122         If key(p) = KeyVal Then Exit Do
 123         p = NextNode(p)
 124     Loop
 125
 126     If p = 0 Then Raise errKeyNotFound, "CHash.Find"
 127
 128     Find = rec(p)
 129 End Function
 130
 131 Public Sub Init( _
 132         ByVal TableSizeVal As Long, _
 133         ByVal InitialAllocVal As Long, _
 134         ByVal GrowthFactorVal As Single)
 135
 136     ' save values
 137     HashTableSize = TableSizeVal
 138     GrowthFactor = GrowthFactorVal
 139
 140     ' initialize hash table
 141     ReDim HashTable(0 To TableSizeVal - 1)
 142
 143     ' initialize nodes
 144     ReDim key(1 To InitialAllocVal)
 145     ReDim NextNode(1 To InitialAllocVal)
 146     ReDim rec(1 To InitialAllocVal)
 147     Set Node = New CNode
 148     Node.Init InitialAllocVal, GrowthFactorVal
 149 End Sub
 150
 151 Public Sub Class_Terminate()
 152
 153     ' terminate hash table
 154     ' chained nodes are deleted automatically,
 155     ' as they're no longer referenced
 156     Set Node = Nothing
 157 End Sub