[ENH] OrderedCollection>>removeAllSuchThat: speedup

Richard A. O'Keefe ok at atlas.otago.ac.nz
Fri Apr 27 03:41:03 UTC 2001


Some time after 2.7 the removeAllSuchThat: methods were revised
to just remove and not return the removed elements, making their
names inconsistent with other methods such as removeFirst.
Luckily, that doesn't break any of my code.  However, the
OrderedCollection>>removeAllSuchThat: method in Squeak 3.0 is an
O(N**2) method.  Here is an O(N) method.

'From Squeak3.0 of 4 February 2001 [latest update: #3552] on 27 April 2001 at 3:36:48 pm'!

!OrderedCollection methodsFor: 'removing' stamp: 'raok 4/27/2001 15:35'!
removeAllSuchThat: aBlock 
	"Remove each element of the receiver for which aBlock evaluates to true.
	 The method in Collection is O(N^2), this is O(N)."

	|n|
	n _ firstIndex.
	firstIndex to: lastIndex do: [:index|
	    (aBlock value: (array at: index)) ifFalse: [
			array at: n put: (array at: index).
			n _ n + 1]].
	n to: lastIndex do: [:index | array at: index put: nil].
	lastIndex _ n - 1! !





More information about the Squeak-dev mailing list