What about a circular array to handle the collection? You can even preallocate objects ahead of time…say you have an aray of 1000 droplets like so:
int ARRAY_SIZE = 1000;
Droplet droplets[] = new Droplet[ARRAY_SIZE ]
int startindex = 0
int endindex = 0
// prefill the array, or create objects on the fly.
To insert an object, just increment endIndex % ARRAY_SIZE and make sure you don’t increment onto startIndex. This gives you ordering, fast index, and after your array is filled up, you can reuse the objects outside of the index range…for example if at somepoint in your code you have 600 droplets in your code, and then you need to remove a droplet and add a droplet in an iteration, your start and end index will increment to 1 and 601…2 and 602…etc (provided you have 600 droplets on the screen right now, but you are always loosing 1 and gaining one each frame…eventually you will get to the point where your start index is 900 and your end index is 499…it keeps cycling! And instead of maing new objects, when you insert, you can check to see if you already created a droplet in the new endIndex position, and if so, reset the value instead of re-creating the object. It’s like object pooling! Does this make sense? And empty list is when startIndex = endIndex. Your list is full when endIndex + 1 % ARRAY_SIZE = startIndex.
I also realized that if you use soft referenes, you can allocate a HUGE array and as memory is needed the soft references will be collected. Deletion means that you swap a strong reference with a weak one in the array in addition to incrementing start index. Hmm, interesting, total theory tho, not sure how it would perform.
Oh oh oh! I forgot to say what happens when you run out of room but you need to have more objects in the collection. Well, after thinking about it a little bit, you can recreate a collection array at the new size (Say, increment by ARRAY_SIZE) and use ArrayCopy to copy the segments of the array to the new array collection, and reset the start/end indexes if necessary. This is only complicated when the start index is physically after the end index (the list overlapps) because in this case you need to copy the beginningof the array to the middle of the new array…so if you have the following:
startIndex = 900
end index = 200
You create your new array holder
Droplet newArray[] = new Droplet[droplets.size + ARRAY_SIZE]
and then you do the array copy copying the contents from endIndex + 1 to droplets.size():
System.arraycopy(droplets, endIndex + 1, newArray, 0, droplets.size - endIndex + 1);
System.arraycopy(droplets, 0, newArray, droplets.size - endIndex + 1, endIndex);
endIndex = droplets.size;
And you only need to do this when endIndex < startIndex, otherwise it’s a straightforward array copy from the old array to the new array.
-Chris
