Finding an object in a list?

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

EOF	(Posted 2005) [#1]

How can I check for the existance of an object in a list without having to iterate through the list?
I'm after a ListFindObject() type of function.
ListFindLink() is closest but how do I get the 'fruit' type object?

Quick example:

Global mylist:TList=CreateList()

Type fruit
	Field name$
	Method New()
		ListAddLast mylist,Self
	End Method
End Type

Local f:fruit

f=New fruit ; f.name$="apple"
f=New fruit ; f.name$="banana"
f=New fruit ; f.name$="pear"
f=New fruit ; f.name$="orange"
f=New fruit ; f.name$="peach"

f=ListFindObject("pear") ????????????????
If f ListRemove mylist,f

klepto2

(Posted 2005) [#2]

Its not very effective but you could do it this way.


Global mylist:TList=CreateList()

Type fruit
	Field name$
	
	Function FindObject:fruit(_Name:String)
		For t:fruit = EachIn mylist
			If t.name = _name Then 
				Return t
				Exit
			EndIf
			Next
			Return
	End Function
	
	Method New()
		ListAddLast mylist,Self
	End Method
	
End Type

Local f:fruit

f=New fruit ; f.name$="apple"
f=New fruit ; f.name$="banana"
f=New fruit ; f.name$="pear"
f=New fruit ; f.name$="orange"
f=New fruit ; f.name$="peach"

f = Null ' Important

f=fruit.FindObject("pear") 

If f ListRemove mylist,f

For f = EachIn mylist

Print f.name

Next

EOF	(Posted 2005) [#3]

I have tried playing with TLink() but always get a Null object ..

Global mylist:TList=CreateList()

Type fruit
	Field name$
End Type

Local f:fruit

f=New fruit ; f.name$="apple"  ; ListAddLast mylist,f
f=New fruit ; f.name$="banana" ; ListAddLast mylist,f
f=New fruit ; f.name$="pear"   ; ListAddLast mylist,f
f=New fruit ; f.name$="orange" ; ListAddLast mylist,f
f=New fruit ; f.name$="peach"  ; ListAddLast mylist,f
'DebugStop

f=FindFruit("pear")
If f Print f.name$ Else Print "not found"
End

Function FindFruit:fruit(value:Object)
	Local t:TLink=ListFindLink(mylist,value)
	If t Return fruit(t.value())
End Function

kyoryu

(Posted 2005) [#4]

Unfortunately, you probably can't. That's just a limitation of linked lists. I plan on making a hash-map module at some point in the near future, just have to get around to it.

klepto2

(Posted 2005) [#5]

Another way to find an object is to give the object a special id and then use this.


Global mylist:TList=CreateList()

Type fruit
	Field name$
	Field id = mylist.Count()
End Type

Local f:fruit

f=New fruit ; f.name$="apple"  ; ListAddLast mylist,f
f=New fruit ; f.name$="banana" ; ListAddLast mylist,f
f=New fruit ; f.name$="pear"   ; ListAddLast mylist,f
f=New fruit ; f.name$="orange" ; ListAddLast mylist,f
f=New fruit ; f.name$="peach"  ; ListAddLast mylist,f

f = fruit(mylist.Valueatindex(2))
If f Print f.name$ Else Print "not found"
End

EOF	(Posted 2005) [#6]

Thanks you two. I've been getting confused by object and value it seems.
Looks like I do need to iterate through the list ..

Global mylist:TList=CreateList()

Type fruit
	Field name$
End Type

Global flag
Local f:fruit

f=New fruit ; f.name$="apple"  ; ListAddLast mylist,f
f=New fruit ; f.name$="banana" ; ListAddLast mylist,f
f=New fruit ; f.name$="pear"   ; ListAddLast mylist,f
f=New fruit ; f.name$="orange" ; ListAddLast mylist,f
f=New fruit ; f.name$="peach"  ; ListAddLast mylist,f
'DebugStop

f=FindFruit("pear")
If f ListRemove mylist,f

For f=EachIn mylist
	Print f.name$
Next

FlushMem
End

Function FindFruit:fruit(name$)
	For Local fr:fruit=EachIn mylist
		If fr.name$=name$ Return fr
	Next
	Return Null
End Function

Tibit

(Posted 2005) [#7]

You can always give an object an unique handle. See my bottom example. This does not replace the need to find objects by field but in many cases you can save both time and code by having direct links to objects;types you use often.

When you used MyList.FindLink("Pear") you gave the method an String and it cannot convert that to an object. In other words that string was not found in the list. In the example below I add strings to the list. You could do the same with 'real' objects also. Depends on what you really want to do in the end.

Strict
Global MyList:TList
	MyList = CreateList()
	MyList.AddLast("Pear")
	MyList.AddLast("Apple")
	MyList.AddLast("Banana")

Print "--LIST--"
For Local Fruit$ = EachIn MyList
	Print Fruit
Next

'Let's say we want to add an Orange after Pear
Print "Insert Orange After Pear"
MyList.InsertAfterLink("Orange" , MyList.FindLink("Pear") )

Print "Remove Apple"
MyList.FindLink("Apple").Remove()

Print "--LIST--"
For Local Fruit$ = EachIn MyList
	Print Fruit
Next

Global mylist:TList=CreateList()

Type fruit
	Field name$
	Method New() ListAddLast mylist,Self EndMethod
End Type

Global flag
Local f:fruit

Apple:Fruit		=	New fruit ; f.name$="apple" 
Banana:Fruit	=	New fruit ; f.name$="banana" 
Pear:Fruit		=	New fruit ; f.name$="pear"  
Orange:Fruit	=	New fruit ; f.name$="orange" 
Peach:Fruit		=	New fruit ; f.name$="peach" 


Print "This fruit is a "+Pear.Name
'Finds and remove pear
mylist.Remove( Pear )

For f=EachIn mylist
	Print f.name$
Next

Hope those examples shed some light on Lists =)

Sweenie

(Posted 2005) [#8]

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.

Azathoth

(Posted 2005) [#9]

Why not just give your object a compare method? FindLink will use it.

Type TMe
	Field name:String
	
	Function Create:TMe(n:String)
		Local x:TMe=New TMe
		x.name=n
		Return x
	EndFunction
	
	Method ToString:String()
		Return name
	EndMethod
	
	Method Compare:Int(o:Object)
		other:TMe=TMe(o)
		If other
			If name=other.name
				Return 0
			ElseIf name<other.name
				Return -1
			ElseIf name>other.name
				Return 1
			EndIf
		EndIf
	EndMethod
EndType


Local l:TList

l=New TList

l.AddLast(TMe.Create("AB"))
l.AddLast(TMe.Create("BB"))
l.AddLast(TMe.Create("BC"))

link:TLink=l.FindLink(TMe.Create("BB"))

DebugLog link.value().tostring()

EOF	(Posted 2005) [#10]

This opens up a whole new world. Its just a matter of knowing how to tackle them. Waves first example will do for me since I only need to have a list of lines read from a file.

Thanks everyone. Good stuff indeed.