The Trunk: Collections-ul.601.mcz

David T. Lewis uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.601.mcz

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

Name: Collections-ul.601
Author: ul
Time: 19 January 2015, 8:43:39.075 pm
UUID: 02a48b9d-87a4-4ae0-9ae5-42a2f22e08ea
Ancestors: Collections-mt.600

- Added FloatCollection >> #asFloatArray which gives slightly better performance.

OrderedDictionary changes:
- Compact eagerly on removal. This ensures that the order Array is always compact: its elements between 1..tally are the associations stored in the dictionary in insertion order.
- Removed the lastIndex variable, because it's always the same as tally.
- Since order is compact, access by index takes O(1) time, and to copy the order array, we can always use a fast primitive.
- use nil in #sort instead of a block
- #errorOutOfBounds is only understood by SequenceableCollections
- avoid the use of fractions, use integer operations instead
- don't sort the order array when it only has one element

=============== Diff against Collections-mt.600 ===============

Item was added:
+ ----- Method: FloatCollection>>asFloatArray (in category 'adding') -----
+ asFloatArray
+ "Optimized version"
+
+ ^array copyFrom: firstIndex to: lastIndex!

Item was changed:
  Dictionary subclass: #OrderedDictionary
+ instanceVariableNames: 'order'
- instanceVariableNames: 'order lastIndex'
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Sequenceable'!
 
  !OrderedDictionary commentStamp: 'mt 1/16/2015 10:42' 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.
 
  The growth operation compacts the index and takes O(n) additional time.
 
  NOTE: This is still no instance of SequenceableCollection. Having this, some protocols are missing and may require working on #associations, which is an Array and thus sequenceable.!

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

Item was changed:
  ----- Method: OrderedDictionary>>atIndex: (in category 'accessing') -----
  atIndex: integer
 
+ integer > tally ifTrue: [ self error: 'indices are out of bounds' ].
+ ^order at: integer!
- ^ self atIndex: integer ifAbsent: [self errorOutOfBounds]!

Item was changed:
  ----- Method: OrderedDictionary>>atIndex:ifAbsent: (in category 'accessing') -----
  atIndex: integer ifAbsent: exceptionBlock
  "As we are sequenceable, provide index-based access."
 
+ integer > tally ifTrue: [ ^exceptionBlock value ].
+ ^order at: integer ifAbsent: exceptionBlock!
- | found |
- found := 0.
- self associationsDo: [:element |
- (found := found + 1) = integer ifTrue: [
- ^ element]].
-
- ^ exceptionBlock value!

Item was changed:
  ----- Method: OrderedDictionary>>atNewIndex:put: (in category 'private') -----
  atNewIndex: index put: anObject
 
+ super atNewIndex: index put: anObject.
+ order at: tally 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>>copyFrom:to: (in category 'copying') -----
  copyFrom: startIndex to: endIndex
  "Answer a copy of the receiver that contains elements from position
  startIndex to endIndex."
 
+ | result |
+ result := self class new: endIndex + startIndex + 1.
+ order from: startIndex to: endIndex do: [ :association |
+ result add: association copy ].
+ ^result!
- self fixEmptySlots.
- ^ self shallowCopy postCopyFrom: startIndex to: endIndex!

Item was removed:
- ----- 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 removed:
- ----- 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 + 1 * 3 // 4.
+ order
+ replaceFrom: 1
+ to: tally
+ with: oldOrder
+ startingAt: 1!
- order := self class arrayType new: (anInteger * (3/4)) ceiling.
- self fillOrderFrom: oldOrder.!

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

Item was changed:
  ----- Method: OrderedDictionary>>isSorted (in category 'sorting') -----
  isSorted
+ "Return true if the receiver is sorted by #<=."
- "Return true if the receiver's keys are sorted by #<=."
 
- self fixEmptySlots.
  ^ order
  isSortedBetween: 1
+ and: tally!
- and: lastIndex!

Item was changed:
  ----- Method: OrderedDictionary>>postCopy (in category 'copying') -----
  postCopy
  "We must not copy associations again but retrieve them from the array, which is already a copy. See super."
 
  super postCopy.
+ order := order copy.
+ 1 to: tally do: [ :index |
+ order at: index put: (array at: (self scanFor: (order at: index) key)) ]!
- order := order collect: [:association |
- association ifNotNil: [array at: (self scanFor: association key)]].!

Item was removed:
- ----- Method: OrderedDictionary>>postCopyFrom:to: (in category 'copying') -----
- postCopyFrom: startIndex to: endIndex
- "Adapted from SequenceableCollection and OrderedCollection."
-
- | oldOrder newArraySize newOrderSize |
- newArraySize := self class goodPrimeAtLeast: ((endIndex - startIndex + 1) * (5/4) "add 25%") ceiling.
- newOrderSize := (newArraySize * (3/4)) ceiling. "remove 25%"
-
- oldOrder := order.
- order := self class arrayType new: newOrderSize.
- array := self class arrayType new: newArraySize.
-
- startIndex to: endIndex do: [:index | | element |
- element := (oldOrder at: index) copy.
- order at: index - startIndex + 1 put: element.
- array at: (self scanFor: element key) put: element].
-
- lastIndex := endIndex - startIndex + 1.
- tally := lastIndex.
-
-
- !

Item was changed:
  ----- Method: OrderedDictionary>>removeKey:ifAbsent: (in category 'removing') -----
  removeKey: key ifAbsent: aBlock
 
+ | result |
+ result := super removeKey: key ifAbsent: [ ^aBlock value ].
+ (self scanOrderFor: key) ifNotNil: [ :index |
+ order
+ replaceFrom: index
+ to: tally
+ with: order
+ startingAt: index + 1 ].
+ . order at: tally + 1 put: nil.
+ ^result!
- (self scanOrderFor: key) ifNotNil: [:index |
- order at: index put: nil].
- ^ super removeKey: key ifAbsent: aBlock!

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

Item was changed:
  ----- Method: OrderedDictionary>>sort (in category 'sorting') -----
  sort
 
+ self sort: nil!
- self sort: [:a1 :a2| a1 key <= a2 key].!

Item was changed:
  ----- Method: OrderedDictionary>>sort: (in category 'sorting') -----
  sort: aSortBlock
  "Like in OrderedCollection, sort the associations according to the sort block."
 
+ tally <= 1 ifTrue: [ ^self ].
+ order
+ mergeSortFrom: 1
+ to: tally
+ by: aSortBlock!
- self ifNotEmpty: [
- self fixEmptySlots.
- order
- mergeSortFrom: 1
- to: lastIndex
- by: aSortBlock].!