Finding an object in a list?

BlitzMax Forums/BlitzMax Beginners Area/Finding an object in a list?

The forum is locked. These are the original blitzbasic.com forums, kept so they can still be read. No new topics, replies or edits can be made here. To join in, head over to the Blitz3D+ forums.

Here is my version of a hashtable.
I'm sure someone can make a better one, but it has worked so far for me...

Type TListNode
 Field NextNode:TListNode
 Field PrevNode:TListNode
 Field Key:String
 Field Value:Object

 'Method Delete()
  'Print "Key "+Key + " says: -"+Chr(34)+"yeah, I'm free!"+Chr(34)
 'End Method

 Method FindKey:Int(Key:String)
  Local CurrNode:TListNode = Self
  Repeat
   If CurrNode.Key = Key Then Return True
   If CurrNode.NextNode = Null Then Exit
   CurrNode = CurrNode.NextNode
  Forever
  Return False
 End Method

 Method RemoveKey:Int(Key:String)
  Local CurrNode:TListNode = Self
  Repeat

   If CurrNode.Key = Key Then 
	If Not(CurrNode.PrevNode = Null) Then 
     CurrNode.PrevNode.NextNode = CurrNode.NextNode
	 If Not(CurrNode.NextNode=Null) Then CurrNode.NextNode.PrevNode = CurrNode.PrevNode
	 FlushMem()
    EndIf

    Return True
   EndIf	

   If CurrNode.NextNode = Null Then Exit
   CurrNode = CurrNode.NextNode
  Forever
  Return False
 End Method

 Method CutPrevNodeLinks()
  Local CurrNode:TListNode = Self
  'Simply go through all nodes and cut the prevnode link...
  Repeat
   CurrNode.PrevNode = Null
   If CurrNode.NextNode = Null Then Exit
   CurrNode = CurrNode.NextNode
  Forever
  
 End Method

 Method GetValueByKey:Object(Key:String)
  Local CurrNode:TListNode = Self
  Repeat
   If CurrNode.Key = Key Then Return CurrNode.Value
   If CurrNode.NextNode = Null Then Exit
   CurrNode = CurrNode.NextNode
  Forever
  Return Null
 End Method

 Method Add:Int(Key:String,Value:Object)

  Local CurrNode:TListNode = Self

   Repeat
    If CurrNode.Key = Key Then Return False
    If CurrNode.NextNode = Null Then Exit
    CurrNode = CurrNode.NextNode
   Forever

  CurrNode.NextNode = New TListNode
  CurrNode.NextNode.Key = Key
  CurrNode.NextNode.Value = Value
  CurrNode.NextNode.PrevNode = CurrNode

  Return True

 End Method

End Type

Type HashTable

 Field Buckets:Int		  ' The nr of rows in the array
 Field HTable:TListNode[]  

 Method New()
  Buckets = 4093 ' Prime...
  HTable = HTable[..Buckets]
  ClearTable()  
 End Method

 Method ClearTable()
  For Local i=0 To Buckets-1
   HTable[i] = Null
  Next
 End Method

 Function Create:HashTable(NrOfBuckets:Int = 4093)
  Local NewHT:HashTable = New HashTable
  NewHT.Buckets = NrOfBuckets
  NewHT.HTable = NewHT.HTable[..NrOfBuckets]
  NewHT.ClearTable()
  Return NewHT
 End Function

 Method Add:Int(Key:String,Value:Object)

  FlushMem()

  Local hash = HashValue(Key)

  If HTable[hash] = Null Then	'Ok, no collision. Just create a node here...
   HTable[hash] = New TListNode
   HTable[hash].Key = Key
   HTable[hash].Value = Value
   Return True
  Else 'Collision, make sure the key doesn't exist already. If it doesn't add a new node at the end...
    Return HTable[hash].Add(Key,Value) 
  EndIf	

 End Method

 Method GetValue:Object(Key:String)
  Local hash = HashValue(Key)
  If HTable[hash] = Null Then Return Null
  Return HTable[hash].GetValueByKey(Key)
 End Method

 Method Remove:Int(Key:String)
  Local hash = HashValue(Key)
  If HTable[hash] = Null Then Return Null
  If HTable[hash].Key = Key Then 'Remove Rootnode
   HTable[hash] = HTable[hash].NextNode
   FlushMem()
  Else
   'Print "Removed Sub Node"
   Return HTable[hash].RemoveKey(Key)
  EndIf
 End Method

 Method RemoveAllKeys()
  For Local i = 0 To Buckets-1
	If Not(HTable[i]=Null) Then 
	 HTable[i].CutPrevNodeLinks()
     HTable[i] = Null
     FlushMem() ' This should release all nodes
    EndIf
  Next
 End Method


 Method ContainsKey:Int(Key:String)
  Local hash = HashValue(Key)
  If HTable[hash] = Null Then Return False
  Return HTable[hash].FindKey(Key) 
 End Method

 Method HashValue:Int(Key:String)
  'Return Key Mod Buckets
  Local hash
  For Local i=0 To Key.Length-1
   hash = hash*613 + Key[i]
  Next
  
  If hash>=0 Then Return hash Mod Buckets Else Return -hash Mod Buckets

 End Method

End Type



Use it like this...

Local MyTable:HashTable = HashTable.Create(500)

MyTable.Add("Apple","I'm an apple!")
MyTable.Add("Pear","I'm a pear!")
MyTable.Add("Orange","I'm an orange!")

Print String(MyTable.GetValue("Pear"))

If MyTable.ContainsKey("Peach")=False then Print "No peach in the table"



Each key must be unique and if you try to add one that already exist, it will just skip adding it.