Marcel Taeumel uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-mt.595.mcz==================== Summary ====================
Name: Collections-mt.595
Author: mt
Time: 16 January 2015, 9:09:51.827 am
UUID: 6cc6dbdd-293b-1747-a983-1cdd512bb383
Ancestors: Collections-topa.594
Some fixes to the OrderedDictionary implementation and its class comment was updated.
=============== Diff against Collections-topa.594 ===============
Item was changed:
Dictionary subclass: #OrderedDictionary
instanceVariableNames: 'order lastIndex'
classVariableNames: ''
poolDictionaries: ''
category: 'Collections-Sequenceable'!
+ !OrderedDictionary commentStamp: 'mt 1/16/2015 09:08' prior: 0!
- !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.
+ The index is updated in O(1) [time] when inserting new keys. For present keys, that insertion involves actions in O(n) to move the respective element to the end of the order.
- 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 changed:
----- 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 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]].
lastIndex = order size
ifTrue: [self errorNoFreeSpace]
+ ifFalse: [^ order at: lastIndex + 1 "nil"].!
- ifFalse: [^ self order at: lastIndex + 1 "nil"].!
Locked
