I figured I should re-forward this enhancement to the list with the proper
subject, so that it gets picked up by the Bug Fixes Archive (at 
http://swiki.gsug.org/SQFIXES/ ).

(Looks good to me, btw.)

- Doug Way
  dway at mat.net


---------- Forwarded message ----------
Date: Fri, 21 Jan 2000 17:57:43 -0800
From: Pierre Roy <pierre at create.ucsb.edu>
To: Squeak mailing list <squeak at cs.uiuc.edu>
Subject: Improvement
Resent-Date: 22 Jan 2000 01:56:55 -0000
Resent-From: squeak at cs.uiuc.edu
Resent-cc: recipient list not shown: ;

Hi everyone,

The select method is not redefined in class SortedCollection.  It is
inherited from class OrderedCollection.  However, this method uses add:
which is particularily slow with SortedCollection since it computes the
insertion index for each new elements.

I propose to redefine select: in class SortedCollection as follows:

    select: aBlock
        | newCollection |
        newCollection := self copyEmpty.
        self do: [:each | (aBlock value: each) ifTrue: [newCollection
addLast: each]].
        ^ newCollection

This is safe because select: goes through receiver from the begining to
the end... therefore the order of the arguments need not be checked
again, assuming the receiver is correctly sorted.

If for some reason or another select: shouldn't be redefined, one can
simply replace existing select: in OrderedCollection by the method
above.

This is probably better, unless one implements a new subclass of
OrderedCollection that doesn't implement addLast:

Hope this will help.  For info, on my G3, the following instruction:

    receiver select: [:each | each >= a and: [each < b]]

runs on a 6,000 element list in 93 milliseconds with the modified select
method instead of 16 seconds for the current implementation.

-Pierre