On Fri, 13 Nov 2009, Igor Stasenko wrote:

> 2009/11/13 Andreas Raab <andreas.raab at gmx.de>:
>> Hi -
>>
>> I just noticed a subtle bug in Set>>fixCollisionsFrom: namely here:
>>
>> [ (element := self keyAt: (index := index \\ array size + 1)) == nil ]
>> whileFalse: [...].

Nice find, and the fix looks nice too, except for:
- every implementor of #keyAt: should implement #keyOfElement:
- it won't work with MethodDictionary
- it's slow, compared to what it could be

I uploaded another approach to the inbox (Kernel-ul.295 and 
Collections-ul.188). It implements #fixCollisionsFrom: where its required 
and removes all implementors of #keyAt:. All kernel and collecions 
tests are green and the remove performance should be a bit better than 
before for all sets and dictionaries, while the number of methods didn't 
change (though loc is a bit more than before).

Levente

> Here the fix (i suppose).
>
> fixCollisionsFrom: start
> 	"The element at start has been removed and replaced by nil.
> 	This method moves forward from there, relocating any entries
> 	that had been placed below due to collisions with this one."
>
> 	| element index |
> 	index := start.
> 	[ (element := array at: (index := index \\ array size + 1)) == nil ]
> whileFalse: [
> 		| newIndex |
> 		(newIndex := self scanFor: ( self keyOfElement: element ) = index ifFalse: [
> 			self swap: index with: newIndex ] ]
>
> where:
>
> Set >> keyOfElement: elem
>  ^ elem
>
> and
>
> Dictionary >> keyOfElement: elem
>  ^ elem key
>
> and we can get rid of #keyAt:
>
>
>> Cheers,
>>  - Andreas
>>
>>
>
>
>
> -- 
> Best regards,
> Igor Stasenko AKA sig.
>
>