Marcel Taeumel uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-mt.599.mcz

==================== Summary ====================

Name: Collections-mt.599
Author: mt
Time: 19 January 2015, 9:11:48.572 am
UUID: 48da0044-2d14-3048-b9f0-90a215344a36
Ancestors: Collections-ul.598

Implemented "First wins"-strategy wrt. to the order of associations. Allowed for simplifying the code.

Order array does only grow to 75% to mitigate the greediness of the Dictionary.

=============== Diff against Collections-ul.598 ===============

Item was removed:
- ----- Method: OrderedDictionary>>add: (in category 'adding') -----
- add: anAssociation
- 
- 	| oldLastIndex oldCapacity |
- 	oldLastIndex := lastIndex.
- 	oldCapacity := self capacity.
- 
- 	super add: anAssociation.
- 
- 	(lastIndex = oldLastIndex or: [self capacity > oldCapacity]) ifTrue: [
- 		| index |
- 		"The association was already present or we grew. We need to update the order."
- 		index := self scanOrderFor: anAssociation key.
- 		index = lastIndex ifFalse: [
- 			lastIndex := lastIndex + 1.
- 			order at: lastIndex put: (order at: index).
- 			order at: index put: nil.
- 			lastIndex = order size ifTrue: [self fixEmptySlots]]].
- 	
- 	^ anAssociation!

Item was removed:
- ----- Method: OrderedDictionary>>at:put: (in category 'accessing') -----
- at: key put: anObject
- 
- 	| oldLastIndex oldCapacity |
- 	oldLastIndex := lastIndex.
- 	oldCapacity := self capacity.
- 
- 	super at: key put: anObject.
- 	
- 	(lastIndex = oldLastIndex or: [self capacity > oldCapacity]) ifTrue: [
- 		| index |
- 		"The association was already present or we grew. We need to update the order."
- 		index := self scanOrderFor: key.
- 		index = lastIndex ifFalse: [
- 			lastIndex := lastIndex + 1.
- 			order at: lastIndex put: (order at: index).
- 			order at: index put: nil.
- 			lastIndex = order size ifTrue: [self fixEmptySlots]]].
- 	
- 	^ anObject!

Item was changed:
  ----- Method: OrderedDictionary>>atNewIndex:put: (in category 'private') -----
  atNewIndex: index put: anObject
  
+ 	lastIndex = order size ifTrue: [
+ 		self fixEmptySlots].
+ 
  	lastIndex := lastIndex + 1.
  	order at: lastIndex put: anObject.
  	
  	super atNewIndex: index put: anObject.!

Item was changed:
  ----- Method: OrderedDictionary>>fixEmptySlots (in category 'private') -----
  fixEmptySlots
  	"Remove all nil slots in the order index to avoid overflow."
  
+ 	lastIndex = tally ifTrue: [^ self].
  	self fillOrderFrom: order.!

Item was changed:
  ----- Method: OrderedDictionary>>growTo: (in category 'private') -----
  growTo: anInteger
  
  	| oldOrder |
  	super growTo: anInteger.
  	oldOrder := order.
+ 	"Grow only to 75%. See #atNewIndex:put: in HashedCollection."
+ 	order := self class arrayType new: (anInteger * (3/4)) ceiling.
- 	order := self class arrayType new: anInteger.
  	self fillOrderFrom: oldOrder.!

Item was changed:
  ----- Method: OrderedDictionary>>initialize: (in category 'private') -----
  initialize: n
  
  	super initialize: n.
+ 	order := self class arrayType new: (n * (3/4)) ceiling.
- 	order := self class arrayType new: n.
  	lastIndex := 0.!

Item was changed:
  ----- Method: OrderedDictionary>>removeKey:ifAbsent: (in category 'removing') -----
  removeKey: key ifAbsent: aBlock
  
+ 	(self scanOrderFor: key) ifNotNil: [:index |
+ 		order at: index put: nil].
- 	order at: (self scanOrderFor: key) put: nil.
  	^ super removeKey: key ifAbsent: aBlock!

Item was changed:
  ----- Method: OrderedDictionary>>scanOrderFor: (in category 'private') -----
  scanOrderFor: anObject
  
  	1 to: lastIndex do: [:index |
  		| element |
  		((element := order at: index) notNil and: [anObject = element key])
  			ifTrue: [^ index]].
  	
+ 	^ nil!
- 	lastIndex = order size
- 		ifTrue: [self errorNoFreeSpace]
- 		ifFalse: [^ order at: lastIndex + 1 "nil"].!