May 24, 2020, 11:45:04 PM

Author Topic: TList of Type objects  (Read 993 times)

Offline _PJ_

  • Jr. Member
  • **
  • Posts: 65
TList of Type objects
« on: September 02, 2018, 10:58:49 AM »
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?


Offline Henri

  • Full Member
  • ***
  • Posts: 236
Re: TList of Type objects
« Reply #1 on: September 02, 2018, 11:35:09 AM »
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
  1.  
  2. Strict
  3.  
  4. Local list:TList = New TList
  5.  
  6. ' Create some objects
  7. For Local i:Int = 0 To 50
  8.         list.addlast( t.Create( String(i) ) )
  9. Next
  10.  
  11. Local removeList:TList = New TList
  12.  
  13. ' Remove every tenth object
  14. For Local a:t = EachIn list
  15.         If Not (Int(a.s) Mod 10) Then removeList.addlast(a)
  16. Next
  17.  
  18. For Local a:t = EachIn removeList
  19.         Print "To be removed: " + a.s
  20.         list.Remove(a)
  21. Next
  22.  
  23. ' Show result
  24. For Local a:t = EachIn list
  25.         Print a.s
  26. Next
  27.  
  28.  
  29. Type t
  30.         Field s:String
  31.        
  32.         Function Create:t(value:String)
  33.                 Local a:t = New t
  34.                 a.s = value
  35.                
  36.                 Return a
  37.         EndFunction
  38. EndType

-Henri
- Got 01100011 problems, but the bit ain't 00000001

Offline Derron

  • Hero Member
  • *****
  • Posts: 2968
Re: TList of Type objects
« Reply #2 on: September 02, 2018, 12:13:39 PM »
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

Offline _PJ_

  • Jr. Member
  • **
  • Posts: 65
Re: TList of Type objects
« Reply #3 on: September 02, 2018, 12:15:25 PM »
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]

Offline Derron

  • Hero Member
  • *****
  • Posts: 2968
Re: TList of Type objects
« Reply #4 on: September 02, 2018, 12:28:50 PM »
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

Offline _PJ_

  • Jr. Member
  • **
  • Posts: 65
Re: TList of Type objects
« Reply #5 on: January 11, 2020, 12:00:29 PM »
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]
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

Offline _PJ_

  • Jr. Member
  • **
  • Posts: 65
Re: TList of Type objects
« Reply #6 on: January 18, 2020, 08:18:56 AM »
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]
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

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal