Removing objects from list in update loop
Monkey Forums/Monkey Programming/Removing objects from list in update loop
| ||
I have a class TCreature that has its own global list of creatures. In the update function of TCreature, all creatures in the list are updated, except if their fActive field is false, in which case I would like to remove them from the list. I have this code:Class TCreature Global gList:List<TCreature> = New List<TCreature> Field fActive:Bool Function updateAll() For Local creature:TCreature = Eachin gList If (creature.fActive) Then creature.update() Else gList.RemoveEach(creature) End If Next End Function End I was wondering if this is the most effective way. I suppose RemoveEach will itself look through the list to remove all objects that equal "creature", which seems like more work than necessary since the loop is already looking at the correct TCreature. That is why I thought I should use a loop over the list's Nodes instead, but I couldn't figure out how to do that. Something like Local node:Node<TCreature> = ... ' start with the first node in the list, update their values (TCreatures) or remove the node from the list ' until all nodes of the list have been visited Does someone know how to do that, or would the first method I posted be acceptable? :) |
| ||
| the second is much something like this:
Class TCreature
[....]
field link:List.Node<TCreature>
[....]
creature.link = gList.addLast(creature) 'adds the object to the list and stores the object's node address in link
[....]
creature.link.remove() ' removes the object from the list instantly
end
[Edit] Ops! forgot that(post #3). |
| ||
Links are better. Donīt forget to call it field link:List.Node<TCreature> or you will get an error. Mfg Suco |
| ||
| Thanks guys. So the trick is to give each TCreature its own Node field, so that it can in a sense remove itself from the list! This I will do. |
| ||
| what are those signs mean? <> I mean in the case that is presented above |
| ||
What is wrong with a simplegList.Remove(creature) I use this within a a For/Eachin loop all the time. |
| ||
| What is wrong with a simple gList.Remove(creature) That is what I would have used, but I didn't know it existed, it seems to be missing from the documentation on List. Thanks for this suggestion too. what are those signs mean? <> Following the word Node there has to be an explanation to Monkey as to what type of object the Node will be containing (or pointing at). This type is written between < and >. Not for a particular reason but just to separate it from the other code.(Or in the case of List<TCreature>, it tells Monkey that the list will hold objects of type TCreature, so it will be a list of TCreatures.) |
| ||
gList.remove(creature) this will become slower as the list grows in size. while Node.Remove(), removes itself directly with out having to search for the object in the list. List.Remove calls removeEach which goes through the list once it finds the object, it uses Node.Remove to remove it. Look at the "list.monkey" source code if in doubt. [edit] a note for everybody that uses list.remove, it says in the source code that it's being deprecated to use list.RemoveEach instead. that would explain why it's not being documented Interesting how the use of wording creates a sense of trust in some people. :) |
| ||
| Thanks for the info. Actually I must have missread that info about the node.Remove feature and just used it accidently in a way which is still supported. Cool. |
| ||
| Is it possible then, to have two lists. One for active instances and one for inactive instances? And as you Create/Destroy these items, you just remove them from one of the lists and add it to the other? Is there any reason why I shouldn't do this? |
| ||
| That is exactly what I did with the SURVIBALL game I have in the App section but there is a small problem. Every time an object is added to the list, a new object is created a "Node" and every time an object is removed the node is deleted. which made the moving of data from list to list somewhat pointless. A better way is to create your own class to manage nodes yourself. |
| ||
Yes, I could do
Class TCreature
Global gFirst:TCreature
Global gLast:TCreature
Field fPrevious:TCreature
Field fNext:TCreature
' ...
End
and thus create a custom linked list of TCreature objects, with a set of functions to manage it. But for the moment I will stick to the monkey list and its methods! |
| ||
| in case it wasn't clear, I was commenting on raz suggestion not yours Foppy. |
| ||
| Yes I understood! :) |
| ||
| Sorry to somewhat hijack this thread now but Jesse That is exactly what I did with the SURVIBALL game I have in the App section but there is a small problem. Every time an object is added to the list, a new object is created a "Node" and every time an object is removed the node is deleted. which made the moving of data from list to list somewhat pointless. A better way is to create your own class to manage nodes yourself. So doing someList.AddLast( Object ) will always create a new node? Is it possible to manipulate the already existing node? I'm still not entirely sure what properties a node has! |
| ||
| a node is a link class that creates chain. A node has three fields. a reference to the previous node, the object it's storing, and a reference to the next node. Every time a node is added, it's attached to either end of the chain. The List class is used to manipulate the chain. it stores the address of the first node and last node. From there it accesses the rest of the nodes by going from one end to the other. Two ways for the list to do what you want is to either modify the list class to accept nodes as input or to extend the class List to accept nodes as input. but for either you would need to also modify the node class to be able to add existing nodes. As it stands, now, the node class only accepts self created nodes. look in the right panel under nav->monkey-> modules->monkey->native->list.monkey to open the list.monkey module. it contain the List class and the node class. From there you can see how it works. |
| ||
| Cheers Jesse, got ya, so like a queue of people, each knowing the one before them and the one after then? I'll give the module a look. |
| ||
| correct. :) |
| ||
I think this does it with out having to modify the Node Class(untested):Class superList<Object> Extends List<Object> Method nodeAddLast:Void(node:Node) _head._succ._succ = node node._pred = _head._succ _head._succ = node node._succ = _head End Method Method nodeAddFirst:Void(node:Node) _head._pred._pred = node node._succ = _head._pred _head._pred = node node._pred = _head End Method End Class [edit] but since _head is private the only way for this to work is to insert the methods in to the List module. I really wish Mark didn't make the public domain modules with private fields. makes it hard to extend. |
| ||
| In every other language modifying a list will always invalidate an iterator, unless the iterator supports the removal itself. This seems to only work in monkey due to the specific way the enumerator works, but there is no way to make it 'fast' and make it easy to use. I would recommend Mark add some functions to use nodes, like access the first node of a list, and access the next node. So you could enumerate like this:
local current:=creatureList.FirstNode
while current
current.Value.Update()
if current.Value.IsAlive
current = current.Next
else
current = creatureList.Remove( current )
end
end while
This is how C++ works, and is the cleanest way to do this I know of, where the 'node' is effectively an iterator, and the list remove can ensure it's valid. It is also kind of odd that the only way to get the start/end nodes is via AddFirst/AddLast. |
| ||
| In every other language modifying a list will always invalidate an iterator, unless the iterator supports the removal itself. The enumerator for Diddy's ArrayList support dynamic item removal. You just have to grab it manually. Local en:AbstractEnumerator<TCreature> = creatures.Enumerator() While en.HasNext() Local item:TCreature = en.NextObject() ' do stuff here en.Remove() End It also stores items in a dynamically-resizing array, so no need to instantiate new Node objects whenever you add an item. |
| ||
Lowercase "l" worked for me. Uppercase did not.field link:list.Node<TCreature> |
| ||
| invalidating your iterator is generally a good thing. If you were iterating on a list of objects for example, and then something you called decided to modify that list, say remove the next element or sort it, then your iterator would keep going as if nothing was wrong and you would have a hard to find and reproduce bug in your software. But if the iterator gets invalidated it will immediately assert when it tries to use the invalid iterator. |
   |