TList of Type objects

[_PJ_]

Forgive me if I'm misunderstanding, but it seems the behaviour for managing obtjercts with a list involvoes somerthing like this:

Type MyType
Field JustAField:Int

Global MasterMyTypeList:TList=New TList

Method New()
  MasterMyTypeList.AddLast(Self)
End Method

Function Create:MyType()
  Local MT.MyType=New MyType
  Return MT
End Function

'This is the bit I'm curious about

Function DoSomethingToAllInstancesListed()
  Local MT.MyType
  For MT = EachIn MasterMyTypeList
    MT.DoAThing
  Next
End Function

End Type

____________


Now let's imagine DoAThing is a removal method:

Method DoAThing()
Self.Remove
End Method


___


The documentation explains that Remove "scans the list"...
But we're alredy iterating through the entire list!

So this is going to be O(n!) ?

Is there a way of directly accessing the list index and removing the object at that position?

[Henri]

In NG it would be possible to remove instances from a list while iterating.

In legacy you would add your to-be-removed instances to a another list, iterate it and invoke the remove-method of the main list then.

Like:

Code (blitzmax) Select Expand



Strict

Local list:TList = New TList

' Create some objects
For Local i:Int = 0 To 50
list.addlast( t.Create( String(i) ) )
Next

Local removeList:TList = New TList

' Remove every tenth object
For Local a:t = EachIn list
If Not (Int(a.s) Mod 10) Then removeList.addlast(a)
Next

For Local a:t = EachIn removeList
Print "To be removed: " + a.s
list.Remove(a)
Next

' Show result
For Local a:t = EachIn list
Print a.s
Next


Type t
Field s:String

Function Create:t(value:String)
Local a:t = New t
a.s = value

Return a
EndFunction
EndType

-Henri

[Derron]

What Henri wrote is because there is an "iterator" used when iterating over the list items. This iterator might stumble over removals/additions to the list while iterating over it.
So if you had "1,2,3,4,5,6,7,8,9" to iterate over, and on "3" decide to remove it, the next item might be skipped and instead of "4" the "5" is handled as next item.
This is avoided by using a "toRemove" array or list.


@ O(n!)
When doing an "list.AddLast(obj)" that method returns an "TLink" object. You can use this "TLink" to directly access the item in the list and skip "searching" through the list until the desired object is found. so in essence:

Type TMyType
  Field link:TLink
...
End Type

myType.link = list.AddLast(myType)
'remove:
myType.link.Remove()


bye
Ron

[_PJ_]

When doing an "list.AddLast(obj)" that method returns an "TLink" object. You can use this "TLink" to directly access the item in the list and skip "searching" through the list until the desired object is found. so in essence:

Type TMyType
  Field link:TLink
...
End Type

myType.link = list.AddLast(myType)
'remove:
myType.link.Remove()

Great! The return type of TLink was just what I needed



bye
Ron
[/quote]

[Derron]

Pay attention when adding an object to multiple lists, you would need to have a "TLink" for each list it gets added to.
(of course you could have a "links:TLink[]" array to clear up all at the same time, but this coding style - even the TLink itself - is contrary to a "parent-child"-relationship-approach in which an added child does not need to know about the parent (the one holding the list)). Depends on your coding favor.

bye
Ron

[_PJ_]

I thought I'd generate some sample test investigating how to effectively remove objects without multiply iterating.

Please ignore the fact I am iterating through the objects to identify the one at the mouse cursor - similarly, ignore the iteration to ensure no two bodies are placed in the same cell - tat was just a sloppy quick & easy solution to ensure the scenario correctly.

I've tried a numebnr of metrhods to "Remove" links or objects from the list - but they don't seem to function.
I am clearly misunderstanding something -

I'm, also a little unsure when the documentation suggests that "LinkRemoveList" for example is to "Remove Objects from a List" does that refer tot he Object within the list, or the "Link" as an object in its own right?

Code Select Expand


SuperStrict

Type TBody
Field X:Int
Field Y:Int

Field PopulationID:TLink

Function Create:TBody()
Local Body:TBody=New TBody
'Add the newly created Body to the Population list
Body.PopulationID = Population.AddLast(Body)
Return Body
End Function

Method Destroy()
' None of these seem to work: HOw to ensure removal of the object and memory cleanup?

'Population.Remove(PopulationID)

'ListRemoveLink(Population,PopulationID)

'Population.RemoveLink(PopulationID)
'PopulationID.Remove

GCCollect
End Method

Method DrawCell()
DrawRect((X*CELL_SIZE)+1,(Y*CELL_SIZE)+1,CELL_SIZE-2,CELL_SIZE-2)
End Method
End Type

Const POP_MAX:Int = 500 'Maximum Total Population

Global Population:TList 'Iterable List of objects in Population
Global GPU:TGraphics 'Graphics Mode Object

Const CELL_SIZE:Int = 8
Global CELL_X:Int
Global CELL_Y:Int

Runtime

Function Runtime()
Initialise
Loop
CloseDown
End Function

Function Initialise()
InitialiseGPU
InitialisePopulation
End Function

Function InitialiseGPU()
SetGraphicsDriver(GLMax2DDriver(),GRAPHICS_BACKBUFFER)

GPU:TGraphics=Graphics(DesktopWidth(),DesktopHeight(),DesktopDepth(),DesktopHertz())
CELL_X = GraphicsWidth()/CELL_SIZE
CELL_Y = GraphicsHeight()/CELL_SIZE

End Function

Function InitialisePopulation()
Population = CreateList()

Local Iter:Int
For Iter= 1 To POP_MAX
CreateRandomBody()
Next
End Function

Function Loop()
While (Not(KeyHit(KEY_ESCAPE)))
LoopUpdate
Wend
End Function

Function LoopUpdate()
UpdateDisplay
CheckInput
End Function

Function UpdateDisplay()
DrawCells
DrawDiagnostics
Flip
End Function

Function DrawDiagnostics()
DrawText(GCMemAlloced(),0,0)
End Function

Function DrawCells()
Local Iter:TBody
For Iter=EachIn Population
Iter.DrawCell
Next
End Function

Function CheckInput()
If (MouseHit(1)>0)
FindAndRemoveBodyInCell(GetMouseCellX(),GetMouseCellY())
End If
End Function

Function GetMouseCellX:Int()
Local X:Int=MouseX()
Return X/CELL_SIZE
End Function

Function GetMouseCellY:Int()
Local Y:Int=MouseY()
Return Y/CELL_SIZE
End Function


Function UnInitialiseGPU()
EndGraphics()
End Function

Function UnInitialise()
UnInitialiseGPU
End Function

Function CloseDown()
UnInitialise
GCCollect
End
End Function

Function CreateRandomBody:TBody()
Local X:Int=Rand(0,CELL_X-1)
Local Y:Int=Rand(0,CELL_Y-1)

While(GetIsAlreadyHere(X,Y))
' I know this is horrendous, but it's just a easy insurance and not relevant to the actual problem investigated

X=Rand(0,CELL_X-1)
Y=Rand(0,CELL_Y)-1
Wend

Local Body:TBody=TBody.Create()
Body.X=X
Body.Y=Y

Return Body
End Function

Function GetIsAlreadyHere:Int(X:Int,Y:Int)
Local Iter:TBody
For Iter=EachIn Population
If Iter.X=X And Iter.Y=Y Then Return True
Next
Return False
End Function

Function FindAndRemoveBodyInCell:TBody(X:Int,Y:Int)
Local Iter:TBody
Local Found:TBody
For Iter=EachIn Population
If (Iter.X=X And Iter.Y=Y)
Found=Iter
Exit
End If
Next
If (Found<>Null)
Found.Destroy
End If
End Function


[_PJ_]

Now I feel stupid

So I had omitted a "cls" from the drawing routine, so of course the filled cells drawn to the buffer would persist even if not re-drawn (due to destruction of their objects) on subsequent loops.

I am still a little concerned, though  -the GCMemAllocated is unchanged - is this because the peak amount of RAM used is still available (makes sense to maintain in case it's required) or is there a leak?

Is there some better function command one can use to gauge the current RAM usage?

Code Select Expand


SuperStrict

Type TBody
Field X:Int
Field Y:Int

Field PopulationID:TLink

Function Create:TBody()
Local Body:TBody=New TBody
'Add the newly created Body to the Population list
Body.PopulationID = Population.AddLast(Body)
Return Body
End Function

Method Destroy()
ListRemoveLink(Population,PopulationID)
PopulationID=Null
End Method

Method DrawCell()
DrawRect((X*CELL_SIZE)+1,(Y*CELL_SIZE)+1,CELL_SIZE-2,CELL_SIZE-2)
End Method
End Type

Const POP_MAX:Int = 500 'Maximum Total Population

Global Population:TList 'Iterable List of objects in Population
Global GPU:TGraphics 'Graphics Mode Object

Const CELL_SIZE:Int = 8
Global CELL_X:Int
Global CELL_Y:Int

Runtime

Function Runtime()
Initialise
Loop
CloseDown
End Function

Function Initialise()
InitialiseGPU
InitialisePopulation
End Function

Function InitialiseGPU()
SetGraphicsDriver(GLMax2DDriver(),GRAPHICS_BACKBUFFER)

GPU:TGraphics=Graphics(DesktopWidth(),DesktopHeight(),DesktopDepth(),DesktopHertz())
CELL_X = GraphicsWidth()/CELL_SIZE
CELL_Y = GraphicsHeight()/CELL_SIZE

End Function

Function InitialisePopulation()
Population = CreateList()

Local Iter:Int
For Iter= 1 To POP_MAX
CreateRandomBody()
Next
End Function

Function Loop()
While (Not(KeyHit(KEY_ESCAPE)))
LoopUpdate
Wend
End Function

Function LoopUpdate()
CheckInput
UpdateDisplay
End Function

Function UpdateDisplay()
Cls
DrawCells
DrawDiagnostics
Flip
End Function

Function DrawDiagnostics()
DrawText(GCMemAlloced(),0,0)
End Function

Function DrawCells()
Local Iter:TBody
For Iter=EachIn Population
Iter.DrawCell
Next
End Function

Function CheckInput()
If (MouseHit(1)>0)
FindAndRemoveBodyInCell(GetMouseCellX(),GetMouseCellY())
End If
End Function

Function GetMouseCellX:Int()
Local X:Int=MouseX()
Return X/CELL_SIZE
End Function

Function GetMouseCellY:Int()
Local Y:Int=MouseY()
Return Y/CELL_SIZE
End Function


Function UnInitialiseGPU()
EndGraphics()
End Function

Function UnInitialise()
UnInitialiseGPU
End Function

Function CloseDown()
UnInitialise
GCCollect
End
End Function

Function CreateRandomBody:TBody()
Local X:Int=Rand(0,CELL_X-1)
Local Y:Int=Rand(0,CELL_Y-1)

While(GetIsAlreadyHere(X,Y))
' I know this is horrendous, but it's just a easy insurance and not relevant to the actual problem investigated

X=Rand(0,CELL_X-1)
Y=Rand(0,CELL_Y)-1
Wend

Local Body:TBody=TBody.Create()
Body.X=X
Body.Y=Y

Return Body
End Function

Function GetIsAlreadyHere:Int(X:Int,Y:Int)
Local Iter:TBody
For Iter=EachIn Population
If Iter.X=X And Iter.Y=Y Then Return True
Next
Return False
End Function

Function FindAndRemoveBodyInCell:TBody(X:Int,Y:Int)
Local Iter:TBody
Local Found:TBody
For Iter=EachIn Population
If (Iter.X=X And Iter.Y=Y)
Found=Iter
Iter=Null
Exit
End If
Next
If (Found<>Null)
Found.Destroy
found=Null
End If
GCCollect
End Function