Removing elements while Iterating over a collection?

Yoshiki Ohshima yoshiki at squeakland.org
Tue Mar 22 00:57:26 UTC 2005


  Filip,

> can anybody kindly explain me whether the following code has or has not the 
> Classic Smalltalk Bug
> i.e."Removing elements while iterating over a Collection" or why is
> it so?

  It depends on the implementation of #do method for the object bound
to animationList, but probably it does.

  An explanation is that the #do: method is likely to keep track of
the index to the next element to be evaluated, no matter it is
Sequenceable or not.  However, #remove: messes up the assumption of
which one would be the next.

  I'd write the method in two split loops something like:

Scheduler>>processAnimations
    animationList do: [:anim | anim update: currentTime].
    animationList _ animationList reject: [:anim | anim isDone].

> Am I missing anything very important here?
> Is this a kind of optimization?

  * If you're dealing with some kind of animation, the cost of
    iteration(s) should be so insignificant.  Iterating twice is
    almost free.

  * If it is a SortedCollection, it will try to re-sort the collection
    everytime one element is removed by #reject:.  It may be really
    costly.  If you split the loops, you can tweak only the next line
    to get do a clever thing:

       newList _ SortedCollection sortBlock: [:a :b | ...].
       newList addAll: (animationList asArray reject: [:anim | anim isDone]).

    Or, if #isDone elements are coalesed, you could do something different:

       "These two lines don't work as-is, but just to give an idea..."
       deleteIndex _ animationList lastIndexOfSuchThat: [:a | a isDone].
       animationList _ animationList copyFrom: deleteIndex+1 to animationList size.

  * If you split it to two loops, it is more robust for future
    modification.  For example, you might want to show the animation
    twice on two different screens.  In that case, no matter how
    many times you call the first line,  you can simply clean up
    things with the second line.

  * If the animationList is a kind of SortedCollection, possibly
    sorted by the time or something, consider to use Heap.  If you
    always remove the elements from the beginning, it may be faster.

Kent Beck discusses the best practices in his books.

-- Yoshiki



More information about the Squeak-dev mailing list