Best way to iterate through ArrayList?

Newbie & Debugging Questions
#41

Sry for bringing back an old topic, but I am redoing my game engine and I am facing the same problem… Last time I just created a copy as an actual array and iterated through that but that isn’t really efficient…

This is the criteria (kind of):

  • looping through all elements only once (no more, no less)
  • be able to remove any element at random without knowing about it (not just the current one, an entity might remove another entity)
  • hopefully not memory or CPU intensive and any objects are reusable…

Is this possible? I guess if needed, I can kind of find out when an element is removed and which one… I do have a method the developer uses to remove an entity (as they dont have access to the actual arraylist)

#42

I do believe the post right above yours should work. Are there any issues with it that apply to you?

#43

Looping backwards won’t help as matanui wants to remove arbitrary objects from the list, not just the current one.

Perhaps add the “removed” entity to a removed set, without updating the original list. If an entity is in the removed set do not return it from the get(int) method of the list. If you are looping through the collection and encounter a removed entity, then continue. At the end of the logic frame, do entityList.removeAll(removed).

#44
  • Your Entity class should have an extra boolean field in order to indicate it’s “dead”!
  • This way, any Entity can “kill” another, or even itself, by setting it to true.
  • Now when iterating over a List of them, we can issue remove() upon any “dead” Entity!
#45

Requirements still unclear.

Say you have 3 entities:

  • 10
  • 20
  • 30

Q: Do you want to process them in the order 10, 20, 30?
Q: If 20 deletes 30, should 30 then get processed?
Q: Can 20 delete 10, even though 10 has already been processed?
Q: Can 20 delete itself?
Q: If 20 deletes 10, should 30 later still be able to “detect” 10 and delete it again or resurrect it?
Q: Can 20 add a new entity “40”? Should 40 then get processed?
Q: Can 20 add a new entity “15” which next time round will get processed between 10 and 20? Should 15 get processed this time?
Q: Do you always want to process all entities?
Q: If the loop processes only entities matching some selection criteria, what are the answers to the above questions where instead of deleting them, 20 modifies the other entities so they would not have been selected for processing?
Q: How often (in terms of % times through) does an entity get deleted? Added? (Modified?)
Q: Will the number of entities ever exceed a hundred? A thousand? A million? What will the approximate number usually be?

The right answer will depend on all that :smiley:

Yes, dead flags followed by a second cleanup pass are a lo-tech but honourable time-tested method. Some VM garbage collectors even work that way.

#46

I just created my own custom iterator which you can also restart and re-use:


package com.redmintie.redgame.util;

import java.util.List;

import com.redmintie.redgame.core.RGException;

/**
 * Better then Java :)
 * 
 * @author Joshua Minter
 */
public class Iterator<T> {
	private List<T> list;
	private int i;
	public Iterator(List<T> list) {
		this.list = list;
	}
	public void start() {
		i = 0;
	}
	public boolean hasMore() {
		return i < list.size();
	}
	public void remove(int i) {
		if (i < this.i) {
			this.i--;
		}
	}
	public T getNext() {
		if (!hasMore()) {
			throw new RGException("No more elements.");
		}
		T elem = list.get(i);
		i++;
		return elem;
	}
}
#47

I fail to see how that solves any of your problems, in fact it just causes more.

#48

In what way? I have tested it myself and there where no problems… Please explain where you are seeing possible bugs

#49

Weird remove method.

#50

The remove method is called when something is removed from the array.
It just checks if the element that is removed is before the current element and if so, move back 1 element

#51

But that doesn’t remove it. It just makes it the element in the next iteration. (Please correct me if I’m wrong)

#52

No, you call the remove item in the list as well as telling the iterator to remove it… I might fix this up with actually having the iterator remove it from the list…