Ooops
January 19, 2021, 05:48:09 AM

Author Topic: [bmx] Hashtable with integer keys and values by Pineapple [ 1+ years ago ]  (Read 450 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Hashtable with integer keys and values
Author : Pineapple
Posted : 1+ years ago

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

Code :
Code: BlitzMax
  1. '       --+-----------------------------------------------------------------------------------------+--
  2. '         | This code was originally written by Sophie Kirschner (meapineapple@gmail.com) and it is |  
  3. '         | released as public domain. Please do not interpret that as liberty to claim credit that |  
  4. '         | is not yours, or to sell this code when it could otherwise be obtained for free because |  
  5. '         |                    that would be a really shitty thing of you to do.                    |
  6. '       --+-----------------------------------------------------------------------------------------+--
  7.  
  8. SuperStrict
  9.  
  10. Import brl.linkedlist
  11.  
  12.  
  13. ' Example program
  14.  
  15. Rem
  16.  
  17. ' Create the hash
  18. Local hash:inthash=inthash.Create(32)
  19.  
  20. ' For each index up to 128, insert index*4 as the associated value
  21. For Local i%=0 Until 128
  22.         hash.insert i,i*4
  23. Next
  24.  
  25. ' Print some examples
  26. Print "Sampling some inserted values..."
  27. Print "4 * 4 = "+hash.find(4)
  28. Print "4 * 12 = "+hash.find(12)
  29. Print "4 * 100 = "+hash.find(100)
  30.  
  31. ' Demonstrate removal
  32. Print "Removing value at index 8..."
  33. hash.remove(8)
  34. Print "Retrieving: 4 * 8 = "+hash.find(8)
  35.  
  36. EndRem
  37.  
  38.  
  39. ' class for mapping ints to other ints
  40. Type inthash
  41.         ' contains the data
  42.         Field bucket:TList[]
  43.         ' thrown error message that hopefully you'll never have to see
  44.         Const accesserror$="inthash buckets not initialized, use setsize before accessing contents"
  45.         ' returns a new inthash of specified size
  46.         Function Create:inthash(size%)
  47.                 Local n:inthash=New inthash
  48.                 n.setsize(size)
  49.                 Return n
  50.         End Function
  51.         ' set inthash bucket array size
  52.         Method setsize(size%)
  53.                 bucket=New TList[size]
  54.         End Method
  55.         ' clear hash
  56.         Method clear()
  57.                 For Local i%=0 Until bucket.length
  58.                         bucket[i]=Null
  59.                 Next
  60.         End Method
  61.         ' create copy of inthash
  62.         Method copy:inthash()
  63.                 Local c:inthash=New inthash
  64.                 c.setsize(bucket.length)
  65.                 For Local i%=0 Until bucket.length
  66.                         If bucket[i]
  67.                                 c.bucket[i]=New TList
  68.                                 For Local node:inthashnode=EachIn bucket[i]
  69.                                         Local add:inthashnode=inthashnode.Create(node.index,node.value)
  70.                                         add.link=c.bucket[i].addlast(add)
  71.                                 Next
  72.                         EndIf
  73.                 Next
  74.                 Return c
  75.         End Method
  76.         ' insert value at index
  77.         Method insert:inthashnode(index%,value%)
  78.                 Assert bucket,accesserror
  79.                 Local i%=Abs(index Mod bucket.length)
  80.                 If Not bucket[i] bucket[i]=New TList
  81.                 Local node:inthashnode=inthashnode.Create(index,value)
  82.                 node.link=bucket[i].addlast(node)
  83.                 Return node
  84.         End Method
  85.         ' retrieve value at index (returns 0 if none exists)
  86.         Method find%(index%)
  87.                 Local node:inthashnode=findnode(index)
  88.                 If node Return node.value
  89.                 Return 0
  90.         End Method
  91.         ' removes node for index (returns 1 if successful, 0 if none existed)
  92.         Method remove%(index%)
  93.                 Local node:inthashnode=findnode(index)
  94.                 If node node.remove;Return 1
  95.                 Return 0
  96.         End Method
  97.         ' retrieve node for index (returns null if none exists)
  98.         Method findnode:inthashnode(index%)
  99.                 Assert bucket,accesserror
  100.                 Local i%=Abs(index Mod bucket.length)
  101.                 If bucket[i]
  102.                         For Local n:inthashnode=EachIn bucket[i]
  103.                                 If n.index=index Return n
  104.                         Next
  105.                 EndIf
  106.                 Return Null
  107.         End Method
  108. End Type
  109.  
  110. ' inthash contains inthashnodes in each bucket
  111. Type inthashnode
  112.         ' index and associated value
  113.         Field index%,value%
  114.         ' list link recorded for swift removal
  115.         Field link:TLink
  116.         ' returns a new inthashnode with specified arguments
  117.         Function Create:inthashnode(index%,value%)
  118.                 Local n:inthashnode=New inthashnode
  119.                 n.index=index;n.value=value
  120.                 Return n
  121.         End Function
  122.         ' remove the inthashnode from its bucket
  123.         Method remove()
  124.                 If link link.remove
  125.         End Method
  126. End Type


Comments :


Brucey(Posted 1+ years ago)

 Cool :-)Are arrays of TLists more efficient that arrays of Arrays?


Pineapple(Posted 1+ years ago)

 I doubt it, but it's certainly easier to write this way :P


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal