[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
|