removing from a collection while enumerating it

I have a case where I need to remove certain entries from an
OrderedCollection that will be called very frequently.  I therefore
want to avoid copying the collection (to safely remove while
enumerating) but it seems #reverseDo: can do what I want.

  myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
myCollection remove: each ] ]

Does anyone see any problem with doing this?

An alternative, if iterating in normal order is important, would be a new do method:

doAndPossiblyDelete: aBlock

    | i done curSize |

    i _ 1.
    [i <= (curSize _ self size)] whileTrue: [
        done _ false.
        aBlock
            value: (self at: i)
            value: [
                done ifFalse: [
                    curSize = self size ifTrue: [
                        self removeAt: i.
                        done _ true.
                    ].
                ].
            ].
        curSize < self size ifTrue: [self halt].
        curSize = self size ifTrue: [    "allow user to delete manually"
            i _ i + 1.
        ].
    ].

I have a case where I need to remove certain entries from an
OrderedCollection that will be called very frequently.  I therefore
want to avoid copying the collection (to safely remove while
enumerating) but it seems #reverseDo: can do what I want.

  myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
myCollection remove: each ] ]

Does anyone see any problem with doing this?

Hi Chris,

>I have a case where I need to remove certain entries from an
>OrderedCollection that will be called very frequently.  I therefore
>want to avoid copying the collection (to safely remove while
>enumerating) but it seems #reverseDo: can do what I want.

>  myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
>myCollection remove: each ] ]

>Does anyone see any problem with doing this?

I don't *think* I have a problem but that code could be fragile.  Normally
I add the entry to a delete/remove list and delete them after I have
finished running the collection.  Something like:

myCollection do: [:each | each meetsSomeCriteria ifTrue: [removeList add:
each ] ].
myCollection removeAll: removeList.

or even better:

removeList := myCollection select: [:each | each meetsSomeCriteria].
myCollection removeAll: removeList.

Lou
-----------------------------------------------------------
Louis LaBrunda
Keystone Software Corp.
SkypeMe callto://PhotonDemon
mailto:[hidden email] http://www.Keystone-Software.com

On 03.07.2013, at 11:27, Chris Muller <[hidden email]> wrote:

> I have a case where I need to remove certain entries from an
> OrderedCollection that will be called very frequently.  I therefore
> want to avoid copying the collection (to safely remove while
> enumerating) but it seems #reverseDo: can do what I want.
>
>  myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
> myCollection remove: each ] ]
>
> Does anyone see any problem with doing this?

What's wrong with removeAllSuchThat:?

- Bert -

On Wed, 3 Jul 2013, Chris Muller wrote:

> I have a case where I need to remove certain entries from an
> OrderedCollection that will be called very frequently.  I therefore
> want to avoid copying the collection (to safely remove while
> enumerating) but it seems #reverseDo: can do what I want.
>
>  myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
> myCollection remove: each ] ]
>
> Does anyone see any problem with doing this?

Yes. Once the implementation of #remove:ifAbsent: changes, your code might
break. You should use #removeAllSuchThat: as Bert suggested, which was
designed to do exactly what you want. It has guaranteed O(n) runtime,
unlike your #reverseDo: "hack", which has O(n*n).

If your OrderedCollection is large, then you should probably use
another data structure.


Levente

>
>

Hm, I did not know about removeAllSuchThat:, but in looking at it, I
find two things "wrong" with it.  1) the superclass implementation in
Collection makes a copy of the collection, which is the basis of my
reason to use reverseDo: instead of enumerating a copy myself.

But I'm using an OC and OC overrides it without making the copy.
That's good, but I also need to know which elements were removed.  I
ended up doing it like:

  myCollection removeAllSuchThat: [ : each | each meetsMyCondition
and: [ each doSomething.  true ] ]

I think it would be nice if removeAllSuchThat: could be similar to
remove: in this respect, but at least, unlike Java, Smalltalk lets me
put any "doSomething" expression in the block as long as it finally
evaluates to a boolean.

Thanks.

On Wed, Jul 3, 2013 at 4:19 PM, Bert Freudenberg <[hidden email]> wrote:

One thing to note is that the collection is messed up while in the midst of removal:

a _ #(1 2 3 4 5) asOrderedCollection.
a removeAllSuchThat: [ :each |
    Transcript show: a asString; cr.
    each odd
].
Transcript show: a asString; cr.

so, if your #doSomething were to examine the collection, it might get the wrong impression.

Hm, I did not know about removeAllSuchThat:, but in looking at it, I
find two things "wrong" with it.  1) the superclass implementation in
Collection makes a copy of the collection, which is the basis of my
reason to use reverseDo: instead of enumerating a copy myself.

But I'm using an OC and OC overrides it without making the copy.
That's good, but I also need to know which elements were removed.  I
ended up doing it like:

  myCollection removeAllSuchThat: [ : each | each meetsMyCondition
and: [ each doSomething.  true ] ]

I think it would be nice if removeAllSuchThat: could be similar to
remove: in this respect, but at least, unlike Java, Smalltalk lets me
put any "doSomething" expression in the block as long as it finally
evaluates to a boolean.

Thanks.

On Wed, Jul 3, 2013 at 4:19 PM, Bert Freudenberg [hidden email] wrote:

On 03.07.2013, at 11:27, Chris Muller [hidden email] wrote:

I have a case where I need to remove certain entries from an
OrderedCollection that will be called very frequently.  I therefore
want to avoid copying the collection (to safely remove while
enumerating) but it seems #reverseDo: can do what I want.

 myCollection reverseDo: [ : each | each meetsSomeCriteria ifTrue: [
myCollection remove: each ] ]

Does anyone see any problem with doing this?

What's wrong with removeAllSuchThat:?

- Bert -

On Thu, 4 Jul 2013, Chris Muller wrote:

> Hm, I did not know about removeAllSuchThat:, but in looking at it, I
> find two things "wrong" with it.  1) the superclass implementation in
> Collection makes a copy of the collection, which is the basis of my
> reason to use reverseDo: instead of enumerating a copy myself.

Because there's no other choice. There are collections (e.g. Array) from
which you can't remove elements.

As you pointed out, you can extend the behavior of the current
implementation and collect the removed elements. If it were the other way,
then you couldn't avoid the overhead of collecting and returning the
removed elements. So I think it is the better way.


Levente

Hi Chris,

Just a suggestion but something to think about.  If your collections are too big then maybe you could find a way to segment the data and move the items into a tree structure.  This would solve most of your problems with copying and performance.

All the best,

Ron Teitelbaum