[squeak-dev] The Trunk: Collections-mt.593.mcz

commits at source.squeak.org commits at source.squeak.org
Thu Jan 15 16:14:59 UTC 2015


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

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

Name: Collections-mt.593
Author: mt
Time: 15 January 2015, 5:14:16.888 pm
UUID: 0316ee3c-b9ec-f845-9474-8df35a929d8b
Ancestors: Collections-mt.592

New ordered dictionary added, which keeps track of the insertion order.

=============== Diff against Collections-mt.592 ===============

Item was added:
+ Dictionary subclass: #OrderedDictionary
+ 	instanceVariableNames: 'order lastIndex'
+ 	classVariableNames: ''
+ 	poolDictionaries: ''
+ 	category: 'Collections-Sequenceable'!
+ 
+ !OrderedDictionary commentStamp: '<historical>' prior: 0!
+ I am an ordered dictionary. I have an additional index (called 'order') to keep track of the insertion order of my associations.
+ 
+ The read access is not affected by the additional index.
+ 
+ Storing new data updates the index in O(1) for new keys. Keys that are already present involve actions in O(n) to update the insertion order.
+ 
+ The growth operation compacts the index and takes O(n) additional time.!

Item was added:
+ ----- 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.
+ 			index := self scanOrderFor: anAssociation key.
+ 			order at: lastIndex put: (order at: index).
+ 			order at: index put: nil.
+ 			lastIndex = order size ifTrue: [self fixEmptySlots]]].
+ 	
+ 	^ anAssociation!

Item was added:
+ ----- Method: OrderedDictionary>>associationsDo: (in category 'enumerating') -----
+ associationsDo: aBlock
+ 	"Iterate over the order instead of the internal array."
+ 
+ 	lastIndex = 0 ifTrue: [^ self].
+ 	1 to: lastIndex do: [:index |
+ 		(order at: index) ifNotNil: [:element |
+ 			aBlock value: element]].!

Item was added:
+ ----- 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 added:
+ ----- Method: OrderedDictionary>>atNewIndex:put: (in category 'private') -----
+ atNewIndex: index put: anObject
+ 
+ 	lastIndex := lastIndex + 1.
+ 	order at: lastIndex put: anObject.
+ 	
+ 	super atNewIndex: index put: anObject.!

Item was added:
+ ----- Method: OrderedDictionary>>fillOrderFrom: (in category 'private') -----
+ fillOrderFrom: anArray
+ 
+ 	| arraySize |
+ 	arraySize := lastIndex.
+ 	lastIndex := 0.
+ 	1 to: arraySize do: [:index |
+ 		(anArray at: index) ifNotNil: [:object |
+ 			lastIndex := lastIndex + 1.
+ 			order at: lastIndex put: object]].!

Item was added:
+ ----- Method: OrderedDictionary>>fixEmptySlots (in category 'private') -----
+ fixEmptySlots
+ 	"Remove all nil slots in the order index to avoid overflow."
+ 
+ 	self fillOrderFrom: order.!

Item was added:
+ ----- Method: OrderedDictionary>>growTo: (in category 'private') -----
+ growTo: anInteger
+ 
+ 	| oldOrder |
+ 	super growTo: anInteger.
+ 	oldOrder := order.
+ 	order := self class arrayType new: anInteger.
+ 	self fillOrderFrom: oldOrder.!

Item was added:
+ ----- Method: OrderedDictionary>>initialize: (in category 'private') -----
+ initialize: n
+ 
+ 	super initialize: n.
+ 	order := self class arrayType new: n.
+ 	lastIndex := 0.!

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

Item was added:
+ ----- 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]].
+ 	
+ 	lastIndex = order size
+ 		ifTrue: [self errorNoFreeSpace]
+ 		ifFalse: [^ self order at: lastIndex + 1 "nil"].!



More information about the Squeak-dev mailing list