Hashtable with integer keys and values

Tweet blitzmax code-archives algorithms
(Posted 7 months ago) RonTek

Simple but hopefully useful, provides 1:1 mapping for ints

Author: Pineapple

'       --+-----------------------------------------------------------------------------------------+--
'         | This code was originally written by Sophie Kirschner ([email protected]) and it is |  
'         | released as public domain. Please do not interpret that as liberty to claim credit that |  
'         | is not yours, or to sell this code when it could otherwise be obtained for free because |  
'         |                    that would be a really shitty thing of you to do.                    |
'       --+-----------------------------------------------------------------------------------------+--


Import brl.linkedlist

' Example program


' Create the hash
Local hash:inthash=inthash.Create(32)

' For each index up to 128, insert index*4 as the associated value
For Local i%=0 Until 128
        hash.insert i,i*4

' Print some examples
Print "Sampling some inserted values..."
Print "4 * 4 = "+hash.find(4)
Print "4 * 12 = "+hash.find(12)
Print "4 * 100 = "+hash.find(100)

' Demonstrate removal
Print "Removing value at index 8..."
Print "Retrieving: 4 * 8 = "+hash.find(8)


' class for mapping ints to other ints
Type inthash
        ' contains the data
        Field bucket:TList[]
        ' thrown error message that hopefully you'll never have to see
        Const accesserror$="inthash buckets not initialized, use setsize before accessing contents"
        ' returns a new inthash of specified size
        Function Create:inthash(size%)
                Local n:inthash=New inthash
                Return n
        End Function
        ' set inthash bucket array size
        Method setsize(size%)
                bucket=New TList[size]
        End Method
        ' clear hash
        Method clear()
                For Local i%=0 Until bucket.length
        End Method
        ' create copy of inthash
        Method copy:inthash()
                Local c:inthash=New inthash
                For Local i%=0 Until bucket.length
                        If bucket[i]
                                c.bucket[i]=New TList
                                For Local node:inthashnode=EachIn bucket[i]
                                        Local add:inthashnode=inthashnode.Create(node.index,node.value)
                Return c
        End Method
        ' insert value at index
        Method insert:inthashnode(index%,value%)
                Assert bucket,accesserror
                Local i%=Abs(index Mod bucket.length)
                If Not bucket[i] bucket[i]=New TList
                Local node:inthashnode=inthashnode.Create(index,value)
                Return node
        End Method
        ' retrieve value at index (returns 0 if none exists)
        Method find%(index%)
                Local node:inthashnode=findnode(index)
                If node Return node.value
                Return 0
        End Method
        ' removes node for index (returns 1 if successful, 0 if none existed)
        Method remove%(index%)
                Local node:inthashnode=findnode(index)
                If node node.remove;Return 1
                Return 0
        End Method
        ' retrieve node for index (returns null if none exists)
        Method findnode:inthashnode(index%)
                Assert bucket,accesserror
                Local i%=Abs(index Mod bucket.length)
                If bucket[i]
                        For Local n:inthashnode=EachIn bucket[i]
                                If n.index=index Return n
                Return Null
        End Method
End Type

' inthash contains inthashnodes in each bucket
Type inthashnode
        ' index and associated value
        Field index%,value%
        ' list link recorded for swift removal
        Field link:TLink
        ' returns a new inthashnode with specified arguments
        Function Create:inthashnode(index%,value%)
                Local n:inthashnode=New inthashnode
                Return n
        End Function
        ' remove the inthashnode from its bucket
        Method remove()
                If link link.remove
        End Method
End Type

Reply To Topic (minimum 10 characters)

Please log in to reply