Java collections good for gaming?

[kappa]

bleb that new version is even nicer, it can now completely replace ArrayList, Bag looks to becoming the ultimate gaming collection

btw not sure about this but couldn’t you change

public boolean removeAll( Collection<?> c )
{
		boolean changed = false;

		Iterator<?> iter = c.iterator();
		while( iter.hasNext() )
		{
			changed |= remove( iter.hasNext() );
		}

		return changed;
}

to

public boolean removeAll(Collection<?> c) 
{
		
	boolean changed = false;		

	for (int i = 0; i < c.size(); i++) {
		changed |= remove(c.get(i));
	}

	return changed;
}

if it is correct it would avoid creating an iterator which might be faster.

[bleb]

It might be faster in some cases, but not in others. Some collections are very good at random access, such as ArrayList, and some are not so good, such as LinkedList.
Using the iterator means that c’s implementation gets to decide what is the most efficient way to access its members, which is a good thing.

edit: I missed the obvious answer: Collection does not have a get( int index ) method.

[zingbat]

What a suprise. So ArrayList is far from being as fast as people dreamed of.

I found an interesting book chapter about OO code performance optimization here:
http://gee.cs.oswego.edu/dl/oosdw3/ch25.html

Initialy come from this article:
http://www.cs.cmu.edu/~jch/java/speed.html

“Give me a wee while and I’ll knock up a version that implements java.util.Collection”

Why not creating a collection wraper on Bag instead of making it implement the Collection interface?

I have eard that using interfaces will make method calls a bit slower, but i have also eard the javac -O will make this irrelevant.

PS: Also if the Bag class is made final it may become a tad faster.

[cylab]

@kapta

bleb that new version is even nicer, it can now completely replace ArrayList, Bag looks to becoming the ultimate gaming collection

btw not sure about this but couldn’t you change

public boolean removeAll( Collection<?> c )
{
		boolean changed = false;

		Iterator<?> iter = c.iterator();
		while( iter.hasNext() )
		{
			changed |= remove( iter.next() );
		}

		return changed;
}

to

public boolean removeAll(Collection<?> c) 
{
		
	boolean changed = false;		

	for (int i = 0; i < c.size(); i++) {
		changed |= remove(c.get(i));
	}

	return changed;
}

if it is correct it would avoid creating an iterator which might be faster.

I think the best of both worlds would be:

public boolean removeAll(Collection<?> c) 
{
		
	boolean changed = false;		
	Iterator<?> iter = c.iterator();
	int l= c.size();

	for (int i = 0; i < l; i++)
	{
		changed |= remove( iter.next() );
	}

	return changed;
}

that would at least avoid the hasNext checks…

[fletchergames]

Bag is buggy. When I plugged it into an existing game instead of the ArrayLists I was using, it stopped working. All I used it for was the following: add elements to the Bag, iterate over the elements in the Bag, and sometimes remove an element using the iterator. I verified that it was after I removed the an element that the game started crashing, but I don’t see what the problem is. I did not create a minimal test case where this occurs, so I don’t know if you’ll be able to reproduce the bug.

The clear method should be changed to check for the condition where the Bag is empty. Otherwise, calling the clear method on an empty Bag causes an IllegalArgumentException in the Arrays call.

What good’s the indexOf method? There’s no get method to use the index. I think it’s best that it doesn’t have a get method because this forces the person using the Bag class to use an Iterator. Using an Iterator preserves the conception that the Bag is a bag of unordered elements, not an array.

I did write one additional method: getRandomElement(). I believe this is a useful method that preserves the Bag concept, unlike a general get method.

I attached my version of Bag, which is basically the same as the previous except for the bug fix and the additional method. I also sorted the methods alphabetically and put the inner class and the variables at the bottom (since they’re private anyways).

Seeing this Bag class suggests to me that we could write our own public domain classes that anyone on the Java Games Forum could modify. This would result in some nice open source code. When mixing the Bag class with my own code, I stored it in the jgf.util package. The “jgf” package could be the standard package for code from the Java Games Forum if we ever started writing public domain classes with any frequency.

[bleb]

[quote]Bag is buggy
[/quote]
As I said, untested : Quick someone! Keep the community data-structure effort going and write some unit tests!

As to the indexOf() method, I agree that it should be made private, else users may be tempted to save the index for use at a later time when it may be wrong. With the getRandomElement method, may I suggest that you also add a version that takes a Random object as an argument, so repeatable behaviour can be had if desired?

[Riven]

This:

public E remove( int index )
{
	E o = array[ index ];
	array[ index ] = array[ size ];
	array[ size ] = null;
	size--;

	return o;
}

Should be:

public E remove( int index )
{
	size--;
	E o = array[ index ];
	array[ index ] = array[ size ];
	array[ size ] = null;

	return o;
}

as ‘size’ is the amount of objects in the bag, so array[size] is either array.length (ArrayIndexOutOfBounds) or null (the one after the last object)

Disclaimer: I didn’t run/test anything.

oNyx version didn’t have this bug BTW.

[pepijnve]

Here’s a version with all the previously mentioned fixes and a test class.

[bleb]

This is going well isn’t it?

Find attached yet another version that:

Fixes the attribution, so mad props go to oNyx as they should
Added a get( index ) method, so random access is possible
Added a warning in the javadocs of indexOf(), to the effect that indices can change at any time.

I had half a mind to make all the methods that expose access to the underlying array (indexOf(), get( index ), remove( index ) ) private, as they widen the scope for user error, but I think pragmatism wins out here - random access is too useful.
Anyone who is already straying from the cradle of java.util can presumably handle the risk.

[pepijnve]

Personally I would leave the random access stuff out. I can’t say I see the point with this kind of data structure:

• get(int): not sure what this would give you besides slightly faster iteration (since you don’t have to create an iterator).
• remove(int): you need to call indexOf to find the correct index, so this is as fast/slow as remove(Object)
• indexOf(): only seems useful for the above two methods. contains(Object) already provides the only other usage I come up with.

[oNyx]

Nice nice

But I dont like indexOf in its current state, because branching around in the loop is slower than doing it only once (with two loops). So… like:

public int indexOf(Object o){
	if(o!=null){
		for(int i=0;i<size;i++){
			if(o.equals(array[i]){
				return i;
			}
		}
	}else{
		for(int i=0;i<size;i++){
			if(array[i]==null){
				return i;
			}
		}
	}
	return -1;
}

And get(int) and remove(int) are fine… see my example loops (main method of the very first Bag class).

[bleb]

@oNyx

Nice nice

But I dont like indexOf in its current state, because branching around in the loop is slower than doing it only once (with two loops). So… like:

Fair enough, change made.

As to get( index ) and remove( index ), they are needed for random access, as in fletchergames’ getRandomElement() method.
I’m coming round to thinking that indexOf() can only cause harm though. The user can only safely use the returned index immediately to remove an element, so they may as well have used remove( Object ).

I’ll privatise it for now, can anyone think of a use case where it’s needed?

[eMKa]

Seeing the discussion with much interest.

What about opening a sourceforge project for collecting all the jgf’s community code ?

I could copy the few classes that I have in OpenMali (https://www.openmali.org/) and we could include additionally this Bag class and RIven’s precomputed sin/cos and so on…

Of course it’s just a beginning…there would be regular releases for big games and 4k games could just grab the latest source of any file they’d need. And of course, credits are due to anyone who contributed, in date order…

So what’d you think ?

[eMKa]

Hmm… seems like Orangy Tang already had the same idea, see : http://www.java-gaming.org/forums/index.php?topic=15060.0

[CommanderKeith]

@bleb

I’ll privatise it for now, can anyone think of a use case where it’s needed?

Let’s not make it private since as you said, there’s no point protecting me from my own stupidity when I use Bag & do a remove() during a loop that does get().

Also I assume most of us still use
for(inti=0;i<list.size();i++){
list.get(i).doStuff();
}
so making Bag to have the same get(int) method would be ideal.

I often do remove() during a loop of get()'s. For example:
for(int i=0;i<list.size();i++){
if (list.get(i).isDead()){
remove(i);
}
}

Short of using an iterator, I suppose for a Bag we could now loop thru from the back & it’d be doing the same thing as looping forward thru an ArrayList. So for a Bag it’d be:
for(int i=list.size() - 1; i >= 0; i–){
if (list.get(i).isDead()){
remove(i);
}
}

[oNyx]

And there you shot yourself in the foot…

The first remove should be like remove(i–), because the last one gets this slot after the remove and it needs to be checked, too. Same goes for ArrayList, but its the next one which gets this slot and not the last one.

In reverse order its ok, because it doesnt matter what happens with the already checked elements.

[CommanderKeith]

That’s the point I was trying to get across - the forward-loop that we’d normally do in an ArrayList won’t work for Bag, but a backwards loop is OK.

[I wonder if we should change Bag so that the forward-loop works fine like it does with ArrayList. So when we remove(i) it takes one from the front and puts it at i. index Zero will still be the ‘first’ in the list, but it could be stored in the back of the array. That way the forward loop-thru would work but the backwards one wouldn’t.

This might save some re-factoring when converting between ArrayList & Bag…? ]

On second thought, I don’t think that’d work…there goes my foot

[oNyx]

That forward loop would be equally wrong with an ArrayList (as I said).

But its a minor (unsually not visible) glitch. If there are 2 “dead” ones the first one will be removed and the next one during the next iteration. If there are 4, 2 will be removed and 1 during the next iteration and the remaining one in the iteration after that. So… its not a horrible mistake to make. Maybe its even benefitical, because the (slow) shifting will be spread across several frames.

edit: With Bag its of course just silly, because there is no heavy remove penality.

[bleb]

@CommanderKeith

@bleb

I’ll privatise it for now, can anyone think of a use case where it’s needed?

Let’s not make it private since as you said, there’s no point protecting me from my own stupidity when I use Bag & do a remove() during a loop that does get().

You misunderstand. get( index ) and remove( index ) are still public, but indexOf( Object ) is not. I can’t think of a case where it is needed (remove( indexOf( o ) ) can be replaced by remove( o ), and get( indexOf( o ) )… well, there are easier ways… : ). Exposing indexOf() will, AFAICS, just encourage people to save the indexes for later use, when they may very well be erroneous.

I don’t really understand this animosity towards using Iterators. Is it really a bottleneck?

[pepijnve]

@bleb

I don’t really understand this animosity towards using Iterators. Is it really a bottleneck?

I was wondering the same thing. Loops like the ones above seem pretty error prone. Removing items from a collection while iterating over it seems a lot more natural to me using an Iterator. I use the for( statement in my code all the time and it’s never been a cause of performance problems so far…