List remove not working? v0.008 (fixed)

Community Forums/Monkey2 Talk/List remove not working? v0.008 (fixed)

therevills

(Posted 2016) [#1]

When I do the following, the bullet does not remove:

Bullet.list.Remove(b)

Also you can sometimes do "Print "test" instead of "Print("test")".

Runnable code here:

#Import "<std>"
#Import "<mojo>"

Using std..
Using mojo..

Class MyWindow Extends Window
	Method New(title:String, width:Int, height:Int)
		Super.New(title, width, height, WindowFlags.Resizable)
		ClearColor = Color.Black
		SwapInterval=1
		
		For Local i:Int = 0 To 9
			New Bullet(Width/2, Height/2, Rnd(10), Rnd(10), 45)
		Next
	End
	
	Method OnRender( canvas:Canvas ) Override
		Bullet.UpdateAll()
		App.RequestRender()
		canvas.DrawText( "Hello World!",Width/2,Height/2,.5,.5 )
		Bullet.RenderAll(canvas)
	End
End

Class Bullet
	Global list:List<Bullet> = New List<Bullet>
	Field xv:Float, yv:Float
	Field x:Float, y:Float
	Field rotation:Float
	Field canvas:Canvas
	Field life:Float
	
	Method New(x:Float, y:Float, xv:Float, yv:Float, life:Float)
		Self.x = x
		Self.y = y
		Self.xv = xv
		Self.yv = yv
		Self.life = life
		list.AddLast(Self)
	End
	
	Function UpdateAll:Void()
		If Not list Return
		For Local b:Bullet = Eachin list
			
			b.Update()

			If b.life < 0
				Print("REMOVE b.life = "+b.life)
				Bullet.list.Remove(b)
				b = Null
			End
		Next
	End
	
	Method Update:Void()
		x = x + xv
		y = y + yv
		
		life -= 1
		If x < 0 x = 640
		If x > 640 x = 0
		If y < 0 y =480
		If y > 480 y = 0
	End
	
	Function RenderAll:Void(canvas:Canvas)
		If Not list Return
		For Local b:Bullet = Eachin list
			b.Render(canvas)
		Next		
	End
	
	Method Render:Void(canvas:Canvas)
		Local tmul:Float
		If life <= 15.0
			tmul = life / 15.0
		Else
			tmul = 1.0
		Endif
		canvas.DrawLine(x, y, x + xv, y + yv)
		canvas.DrawText(life, x, y)
	End
End

Function Main()
	New AppInstance
	New MyWindow("Hello World", 640, 480)
	App.Run()
End

dawlane

(Posted 2016) [#2]

Looks like there are a few issues with container types. Either that or I'm missing something.

' MX1 example
Class CObject
	Field data:Int
	Field id:Int
	
	Method New(id:Int, data:Int)
		Self.id = id
		Self.data = data
	End Method
End Class

Function Main()
	Local stack:=New Stack<CObject>
	Local val:Int[]=[1,2,3,4,5,6,7,8,9,10]
	For Local i:Int=0 Until val.Length
		stack.Push(New CObject(i,val[i]))
	Next
	
	For Local i:CObject=Eachin stack
		Print "Remove loop: "+i.data
		If i.data = 8 Or i.data = 5 stack.Remove(stack.Find(i))
		'If i.data = 8 Or i.data = 5 stack.Remove(i) ' Error : Unable to find overload for Remove(CObject).
	Next
	
	For Local i:CObject=Eachin stack
		Print "Result loop: "+i.data
	Next
End

This should be the mx2 version of the code above

' MX2 example
#Import "<std>"

Using std..

Class CObject
	Field data:Int
	Field id:Int
	
	Method New(id:Int, data:Int)
		Self.id = id
		Self.data = data
	End Method
End Class

Function Main()
	Local stack:=New Stack<CObject>
	Local val:= New Int[](1,2,3,4,5,6,7,8,9,10)
	For Local i:Int=0 Until val.Length
		stack.Push(New CObject(i,val[i]))
	Next
	
	For Local i:CObject=Eachin stack
		Print "Remove loop: "+i.data
		'If i.data = 5 stack.Remove(stack.FindIndex(i)) ' stack.FindIndex(i) throws Error : Can't find overload for 'Remove(...)' with argument types (int)
		If i.data = 5 stack.Remove(i) ' Uncaught Monkey 2 Exception: Concurrent list modification. In MonkeyX you would get Error : Unable to find overload for Remove(CObject).
	Next
	
	For Local i:CObject=Eachin stack
		Print "Result loop: "+i.data
	Next
End

Note: Using Erase causes errors along the same lines. I haven't look at maps yet.

marksibly

(Posted 2016) [#3]

Remove is indeed broken - just committed a fix.

The 'concurrent list modification' error is new to mx2 and indicates a container was modified while you were iterating through it.

Monkey1 allowed/ignored this, but included a kludge to make it 'sort of' work with lists. But in general, modifying a container while iterating through it can produce 'weird' results, eg (mx1):

Function Main()

	Local stack:=New IntStack
	
	For Local i:=0 Until 10
		stack.Push( i )
	Next
	
	For Local i:=Eachin stack
		stack.Remove( i )
	Next
	
	Print stack.Length

End

...prints '5'! This is because after the current element is removed, the next element gets moved down to the current element, which is promptly 'skipped over' by the 'Next'. For other container types, the side effects are different, but still unpredictable.

Lists in mx1 included a work around to (try to) deal with this - basically, when you remove a node from a list, the node's 'succ' and 'pred' fields are not modified, allowing Next to use the 'succ' field of the 'dead' node if you happen to remove the current item - but it's not a complete fix by any means. There are still ways to remove items from a list in mx1 that could potentially leave you iterating through 'removed' elements!

If you want to remove stuff from a container while you're iterating through it, you should iterate manually and remove items with the iterator 'Erase' method, eg:

	Local it:=list.All()

	While Not it.AtEnd
		
		Local b:=it.Current
			
		b.Update()

		If b.life < 0
			Print("REMOVE b.life = "+b.life)
			it.Erase()
		Else
			it.Bump()
		Endif
	Wend

This is a little longer winded, but means the iterator gets a chance to do any 'fixups' necessary to keep Eachin working properly when you erase the current element.

It is also much faster than list.Remove(), which does a linear search. An iterator has direct access to the node so there is no search involved, the node is just directly removed.

I *could* leave the List hack in I guess, but there is no such hack for other container types and it's not even a 'complete' solution for Lists. I much prefer the new stricter approach as it's both safer and faster.

I suspect this will be controversial, but it is IMO the right thing to do...

BTW, here's my currently preferred way to update a stack of 'removable' items...

Local put:=0
For Local get:=0 Until _stack.Length
   Local item:=_stack[get] ; get+=1
   If item.RemoveMe() Continue
   _stack[put]=item ; put+=1
Wend
_stack.Resize( put )

I only ever really use lists for 'deques' these days. They have a lot of overhead (eg: extra 'node' allocation + lousy memory access pattern) and I urge others to try to avoid them too!

Leo Santos

(Posted 2016) [#4]

I like this new behavior.

The new error surprised me yesterday as I was converting old code (that recursively destroys an entity and its children, then the children's children, removing entities from all lists they belong to, etc. ), but it was indeed a "dangerous" situation and I feel that the new style is safer.

marksibly

(Posted 2016) [#5]

I suspect c#/java guys will be OK with it, bmx/monkey1 guys will hate it!

dawlane

(Posted 2016) [#6]

I think a few examples will definitely have to go in to the documentation at some point to clearly explain this.
And a much better explanation of the Iterator structure with it Bump/Erase/AtEnd/Current.

Nobuyuki

(Posted 2016) [#7]

I thought it was common knowledge for mx1 users not to mess with containers' "element count" when iterating through them. Same with using lists to store data you want to have any kind of random access for at any point. About the only thing I can think of that I've used List<T> for in monkey1 was y-order sorting. MX1 Stacks (really more like dynamically allocating arrays with extra stack functions) just seemed way more efficient for most things, so I don't understand the controversy behind it unless Lists were used far more in the bmax days when I wasn't around...

therevills

(Posted 2016) [#8]

Bmax only has a List (TList) container type and I'm pretty lazy so I like concurrent list modifications (I can live without it, but it is nice).

For Local b:Bullet = Eachin list
	If b.dead Then list.Remove(b)
Next

Local it := list.All()
While Not it.AtEnd
	Local b:Bullet = it.Current
	If b.dead
		it.Erase()
	Else
		it.Bump()
	End
End