[squeak-dev] The Trunk: Collections-ul.282.mczcommits at source.squeak.org commits at source.squeak.orgMon Jan 25 22:15:13 UTC 2010
Levente Uzonyi uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-ul.282.mcz ==================== Summary ==================== Name: Collections-ul.282 Author: ul Time: 25 January 2010, 10:56:13.924 pm UUID: 44962376-0c2e-ea4c-9fce-9fb056cd768b Ancestors: Collections-nice.281 In the HashedCollection hierarchy: - cosmetic changes: use #ifNotNil: if possible - use unary symbols instead of blocks with a single unary send - removed unnecessary line from #atRandom - restored correct compatibility method for #fullCheck In Dictionary: - make sure that #associationsSelect: works with PluggableDictionary by using #copyEmpty instead of #species + #new - deprecated #keyForIdentity:, because it's similar to #keyAtIdentityValue:ifAbsent: In WeakKeyDictionary: - #rehash throws away nil keys, so we don't have to iterate twice over array - don't let the key go away in #noCheckNoGrowFillFrom: In WeakKeyToCollectionDictionary: - don't let the key go away in #noCheckNoGrowFillFrom: - removed #finalizeValues because it became same as super In WeakSet: - #do:after: doesn't skip the first element if anElement is nil - speed up #slowSize - don't rehash twice in #grow, just count the occupied slots first with #slowSize Other: - simplified a few KeyedSet's methods - added #collect: to PluggableDictionary (super doesn't copy the blocks) =============== Diff against Collections-nice.281 =============== Item was changed: + ----- Method: IdentityDictionary>>keyAtValue:ifAbsent: (in category 'accessing') ----- - ----- Method: IdentityDictionary>>keyAtValue:ifAbsent: (in category 'private') ----- keyAtValue: value ifAbsent: exceptionBlock "Answer the key that is the external name for the argument, value. If there is none, answer the result of evaluating exceptionBlock." + ^super keyAtIdentityValue: value ifAbsent: exceptionBlock! - self associationsDo: - [:association | value == association value ifTrue: [^ association key]]. - ^ exceptionBlock value! Item was changed: ----- Method: Set>>noCheckNoGrowFillFrom: (in category 'private') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require." 1 to: anArray size do: [ :index | + (anArray at: index) ifNotNil: [ :object | - | object | - (object := anArray at: index) ifNotNil: [ array at: (self scanForEmptySlotFor: object) put: object ] ]! Item was changed: ----- Method: WeakSet>>noCheckNoGrowFillFrom: (in category 'private') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils and flag to me assuming that I don't contain any of them, they are unique and I have more free space than they require." tally := 0. 1 to: anArray size do: [ :index | + (anArray at: index) ifNotNil: [ :object | + object == flag ifFalse: [ - | object | - ((object := anArray at: index) == flag or: [ - object == nil ]) ifFalse: [ array at: (self scanForEmptySlotFor: object) put: object. + tally := tally + 1 ] ] ]! - tally := tally + 1 ] ]! Item was changed: ----- Method: WeakKeyDictionary>>finalizeValues: (in category 'finalization') ----- finalizeValues: finiObjects "Remove all associations with key == nil and value is in finiObjects. This method is folded with #rehash for efficiency." | oldArray | oldArray := array. array := Array new: oldArray size. tally := 0. + 1 to: array size do: [ :index | + (oldArray at: index) ifNotNil: [ :association | + association key ifNotNil: [ :key | "Don't let the key go away" + (finiObjects includes: association value) ifFalse: [ + array + at: (self scanForEmptySlotFor: key) + put: association. + tally := tally + 1 ] ] ] ]! - 1 to: array size do:[ :i | - | association | - (association := oldArray at: i) ifNotNil: [ - | key | - ((key := association key) == nil and: [ "Don't let the key go away" - finiObjects includes: association value ]) - ifFalse: [ - array - at: (self scanForEmptySlotFor: key) - put: association. - tally := tally + 1 ] ] ]! Item was changed: ----- Method: WeakSet>>grow (in category 'private') ----- grow "Grow the elements array if needed. Since WeakSets just nil their slots, a lot of the occupied (in the eyes of the set) slots are usually empty. Doubling size if unneeded can lead to BAD performance, therefore we see if reassigning the <live> elements to a Set of similiar size leads to a sufficiently (50% used here) empty set first" + tally // 2 < self slowSize + ifTrue: [ super grow ] + ifFalse: [ self rehash ] + ! - | oldTally | - oldTally := tally. - self rehash. - oldTally // 2 < tally ifTrue: [ super grow ]! Item was changed: ----- Method: WeakSet>>growTo: (in category 'private') ----- growTo: anInteger "Grow the elements array and reinsert the old elements" | oldElements | oldElements := array. + array := WeakArray new: anInteger withAll: flag. - array := WeakArray new: anInteger. - array atAllPut: flag. self noCheckNoGrowFillFrom: oldElements! Item was changed: ----- Method: HashedCollection>>atRandom: (in category 'accessing') ----- atRandom: aGenerator "Answer a random element of the receiver. Uses aGenerator which + should be kept by the user in a variable and used every time. Use + this instead of #atRandom for better uniformity of random numbers because - should be kept by the user in a variable and used every time. Use - this instead of #atRandom for better uniformity of random numbers because only you use the generator. Causes an error if self has no elements." + | rand | - self emptyCheck. rand := aGenerator nextInt: self size. + self doWithIndex: [ :each :index | + index = rand ifTrue: [ ^each ] ]! - self doWithIndex:[:each :ind | - ind = rand ifTrue:[^each]]. - ^ self errorEmptyCollection - ! Item was changed: ----- Method: KeyedSet>>member: (in category 'adding') ----- member: newObject "Include newObject as one of the receiver's elements, if already exists just return it" | index | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. index := self scanFor: (keyBlock value: newObject). + (array at: index) ifNotNil: [ :element | ^element ]. - (array at: index) ifNotNil: [^ array at: index]. self atNewIndex: index put: newObject. ^ newObject! Item was changed: + ----- Method: WeakSet>>add: (in category 'adding') ----- - ----- Method: WeakSet>>add: (in category 'public') ----- add: newObject "Include newObject as one of the receiver's elements, but only if not already present. Answer newObject" | index element | newObject ifNil: [self error: 'Sets cannot meaningfully contain nil as an element']. index := self scanFor: newObject. ((element := array at: index) == flag or: [ element == nil ]) ifTrue: [self atNewIndex: index put: newObject]. ^newObject! Item was changed: ----- Method: KeyedSet>>at:ifAbsent: (in category 'accessing') ----- at: key ifAbsent: aBlock "Answer the value associated with the key or, if key isn't found, answer the result of evaluating aBlock." + ^(array at: (self scanFor: key)) ifNil: [ aBlock value ]! - | obj | - obj := array at: (self scanFor: key). - obj ifNil: [^ aBlock value]. - ^ obj! Item was changed: + ----- Method: WeakSet>>includes: (in category 'testing') ----- - ----- Method: WeakSet>>includes: (in category 'public') ----- includes: anObject + ^(array at: (self scanFor: anObject)) + ifNil: [ false ] + ifNotNil: [ :object | object ~~ flag ]! - | element | - ^((element := array at: (self scanFor: anObject)) == flag or: [ element == nil ]) not! Item was changed: ----- Method: Dictionary>>noCheckNoGrowFillFrom: (in category 'private') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require." 1 to: anArray size do: [ :index | + (anArray at: index) ifNotNil: [ :association | - | object | - (object := anArray at: index) ifNotNil: [ array + at: (self scanForEmptySlotFor: association key) + put: association ] ]! - at: (self scanForEmptySlotFor: object key) - put: object ] ]! Item was changed: ----- Method: KeyedSet>>initialize: (in category 'private') ----- initialize: n + super initialize: n. + keyBlock := #key - keyBlock := [:element | element key]. ! Item was changed: ----- Method: WeakKeyDictionary>>keysDo: (in category 'accessing') ----- keysDo: aBlock "Evaluate aBlock for each of the receiver's keys." self associationsDo: [ :association | + (association key) ifNotNil: [ :key | "Don't let the key go away" - | key | - (key := association key) ifNotNil: [ "Don't let the key go away" aBlock value: key ] ].! Item was changed: ----- Method: Dictionary>>add: (in category 'adding') ----- add: anAssociation + | index | - | index element | index := self scanFor: anAssociation key. + (array at: index) - (element := array at: index) ifNil: [ self atNewIndex: index put: anAssociation ] + ifNotNil: [ :element | element value: anAssociation value ]. - ifNotNil: [ element value: anAssociation value ]. ^anAssociation! Item was changed: ----- Method: WeakSet>>do:after: (in category 'public') ----- do: aBlock after: anElement - | each startIndex | + | startIndex | + tally = 0 ifTrue: [ ^self ]. + startIndex := anElement + ifNil: [ 0 ] + ifNotNil: [ self scanFor: anElement ]. + startIndex + 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :object | + object == flag ifFalse: [ + aBlock value: object ] ] ]! - tally = 0 ifTrue: [^self]. - startIndex := anElement ifNil: [1] ifNotNil: - [self scanFor: anElement]. - startIndex + 1 to: array size do: - [:index | - ((each := array at: index) == nil or: [each == flag]) - ifFalse: [aBlock value: each] - ]! Item was changed: + ----- Method: WeakSet>>remove:ifAbsent: (in category 'removing') ----- - ----- Method: WeakSet>>remove:ifAbsent: (in category 'public') ----- remove: oldObject ifAbsent: aBlock | index | index := self scanFor: oldObject. (array at: index) == flag ifTrue: [ ^ aBlock value ]. array at: index put: flag. tally := tally - 1. self fixCollisionsFrom: index. ^oldObject! Item was changed: ----- Method: WeakKeyDictionary>>finalizeValues (in category 'finalization') ----- finalizeValues "remove all nil keys and rehash the receiver afterwards" - | assoc | - 1 to: array size do: [ :index | - (assoc := array at: index) ifNotNil: [ - assoc key ifNil: [ array at: index put: nil ] ] ]. self rehash! Item was changed: ----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') ----- goodPrimeAtLeast: lowerLimit "Answer the next good prime >= lowerlimit. If lowerLimit is larger than the largest known good prime, just make it odd." | primes low mid high prime | primes := self goodPrimes. low := 1. high := primes size. lowerLimit > (primes at: high) ifTrue: [ + ^lowerLimit bitOr: 1 ]. - ^lowerLimit even - ifTrue: [ lowerLimit + 1 ] - ifFalse: [ lowerLimit ] ]. [ high - low <= 1 ] whileFalse: [ mid := high + low // 2. prime := primes at: mid. prime = lowerLimit ifTrue: [ ^prime ]. prime < lowerLimit ifTrue: [ low := mid ] ifFalse: [ high := mid ] ]. (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ]. ^primes at: high! Item was changed: ----- Method: Dictionary>>at:put: (in category 'accessing') ----- at: key put: anObject "Set the value at key to be anObject. If key is not found, create a new entry for key and set is value to anObject. Answer anObject." + | index | - | index assoc | index := self scanFor: key. + (array at: index) + ifNil: [ self atNewIndex: index put: (Association key: key value: anObject) ] + ifNotNil: [ :association | association value: anObject ]. + ^anObject! - assoc := array at: index. - assoc - ifNil: [self atNewIndex: index put: (Association key: key value: anObject)] - ifNotNil: [assoc value: anObject]. - ^ anObject! Item was changed: ----- Method: KeyedSet>>keysSorted (in category 'accessing') ----- keysSorted + ^self keys sort! - | keys | - keys := SortedCollection new. - self do: [:item | keys add: (keyBlock value: item)]. - ^ keys! Item was changed: ----- Method: WeakSet>>slowSize (in category 'public') ----- slowSize "Careful!! Answer the maximum amount of elements in the receiver, not the exact amount" + | count | + count := 0. + 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :object | + object == flag ifFalse: [ + count := count + 1 ] ] ]. + ^tally := count! - tally := array inject: 0 into: - [:total :each | (each == nil or: [each == flag]) - ifTrue: [total] ifFalse: [total + 1]]. - ^tally! Item was changed: ----- Method: WeakKeyDictionary>>noCheckNoGrowFillFrom: (in category 'private') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils and flag to me assuming that I don't contain any of them, they are unique and I have more free space than they require." tally := 0. + 1 to: anArray size do:[ :index | + (anArray at: index) ifNotNil: [ :association | + association key ifNotNil: [ :key | "Don't let the key go away" + array + at: (self scanForEmptySlotFor: key) + put: association. + tally := tally + 1 ] ] ]! - 1 to: anArray size do:[ :i | - | association | - (association := anArray at: i) ifNotNil: [ - array - at: (self scanForEmptySlotFor: association key) - put: association. - tally := tally + 1 ] ]! Item was changed: ----- Method: WeakKeyToCollectionDictionary>>noCheckNoGrowFillFrom: (in category 'as yet unclassified') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils and associations with empty collections (or with only nils) to me assuming that I don't contain any of them, they are unique and I have more free space than they require." tally := 0. + 1 to: anArray size do: [ :index | + (anArray at: index) ifNotNil: [ :association | + association key ifNotNil: [ :key | "Don't let the key go away" + | cleanedValue | + (cleanedValue := association value copyWithout: nil) isEmpty + ifFalse: [ + association value: cleanedValue. + array + at: (self scanForEmptySlotFor: key) + put: association. + tally := tally + 1 ] ] ] ]! - 1 to: anArray size do:[ :i | - | association cleanedValue | - ((association := anArray at: i) == nil or: [ - (cleanedValue := association value copyWithout: nil) isEmpty ]) - ifFalse: [ - association value: cleanedValue. - array - at: (self scanForEmptySlotFor: association key) - put: association. - tally := tally + 1 ] ]! Item was changed: ----- Method: HashedCollection class>>rehashAll (in category 'initialization') ----- rehashAll "HashedCollection rehashAll" + self allSubclassesDo: #rehashAllInstances! - self allSubclassesDo: [ :each | each rehashAllInstances ]! Item was changed: ----- Method: HashedCollection>>fullCheck (in category 'compatibility') ----- fullCheck "This is a private method, formerly implemented in Set, that is no longer required. It is here for compatibility with external packages only." + "Keep array at least 1/4 free for decent hash behavior" + + array size * 3 < (tally * 4) ifTrue: [ self grow ]! - ^ self - ! Item was changed: ----- Method: KeyedSet>>noCheckNoGrowFillFrom: (in category 'private') ----- noCheckNoGrowFillFrom: anArray "Add the elements of anArray except nils to me assuming that I don't contain any of them, they are unique and I have more free space than they require." 1 to: anArray size do: [ :index | + (anArray at: index) ifNotNil: [ :object | - | object | - (object := anArray at: index) ifNotNil: [ array at: (self scanForEmptySlotFor: (keyBlock value: object)) put: object ] ]! Item was changed: ----- Method: Dictionary>>associationsSelect: (in category 'enumerating') ----- associationsSelect: aBlock "Evaluate aBlock with each of my associations as the argument. Collect into a new dictionary, only those associations for which aBlock evaluates to true." | newCollection | + newCollection := self copyEmpty. + self associationsDo: [ :each | + (aBlock value: each) ifTrue: [ newCollection add: each ] ]. - newCollection := self species new. - self associationsDo: - [:each | - (aBlock value: each) ifTrue: [newCollection add: each]]. ^newCollection! Item was changed: ----- Method: Dictionary>>associationsDo: (in category 'enumerating') ----- associationsDo: aBlock "Evaluate aBlock for each of the receiver's elements (key/value associations)." tally = 0 ifTrue: [ ^self]. 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :element | + aBlock value: element ] ]! - | each | - (each := array at: index) - ifNotNil: [ aBlock value: each ] ]! Item was changed: ----- Method: Set>>do: (in category 'enumerating') ----- do: aBlock tally = 0 ifTrue: [ ^self ]. 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :element | + aBlock value: element ] ]! - | each | - (each := array at: index) - ifNotNil: [ aBlock value: each ] ]! Item was changed: + ----- Method: Dictionary>>keyForIdentity: (in category 'accessing') ----- - ----- Method: Dictionary>>keyForIdentity: (in category 'testing') ----- keyForIdentity: anObject "If anObject is one of the values of the receive, return its key, else return nil. Contrast #keyAtValue: in which there is only an equality check, here there is an identity check" + self deprecated: 'Use #keyAtIdentityValue:ifAbsent:'. + ^self keyAtIdentityValue: anObject ifAbsent: nil! - self associationsDo: [:assoc | assoc value == anObject ifTrue: [^ assoc key]]. - ^ nil! Item was changed: + ----- Method: WeakSet>>do: (in category 'enumerating') ----- - ----- Method: WeakSet>>do: (in category 'public') ----- do: aBlock tally = 0 ifTrue: [ ^self ]. 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :object | + object == flag ifFalse: [ + aBlock value: object ] ] ]! - | each | - ((each := array at: index) == nil or: [ each == flag ]) - ifFalse: [ aBlock value: each ] ]! Item was changed: + ----- Method: WeakSet>>like: (in category 'accessing') ----- - ----- Method: WeakSet>>like: (in category 'public') ----- like: anObject "Answer an object in the receiver that is equal to anObject, nil if no such object is found. Relies heavily on hash properties" | element | ^(element := array at: (self scanFor: anObject)) == flag ifFalse: [ element ]! Item was changed: ----- Method: WeakKeyDictionary>>at:put: (in category 'accessing') ----- at: key put: anObject "Set the value at key to be anObject. If key is not found, create a new entry for key and set is value to anObject. Answer anObject." + | index | - | index element | key ifNil: [ ^anObject ]. index := self scanFor: key. + (array at: index) - (element := array at: index) ifNil: [ self atNewIndex: index put: (WeakKeyAssociation key: key value: anObject) ] + ifNotNil: [ :association | association value: anObject ]. - ifNotNil: [ element value: anObject ]. ^anObject! Item was changed: + ----- Method: WeakSet>>collect: (in category 'enumerating') ----- - ----- Method: WeakSet>>collect: (in category 'public') ----- collect: aBlock + + | newSet | - | each newSet | newSet := self species new: self size. + tally = 0 ifTrue: [ ^newSet ]. + 1 to: array size do: [ :index | + (array at: index) ifNotNil: [ :object | + object == flag ifFalse: [ + newSet add: (aBlock value: object) ] ] ]. - tally = 0 ifTrue: [^newSet ]. - 1 to: array size do: - [:index | - ((each := array at: index) == nil or: [each == flag]) - ifFalse: [newSet add: (aBlock value: each)] - ]. ^newSet! Item was changed: ----- Method: HashedCollection class>>rehashAllInstances (in category 'initialization') ----- rehashAllInstances "Do not use #allInstancesDo: because rehash may create new instances." + self allInstances do: #rehash! - self allInstances do: [ :each | each rehash ] ! Item was changed: + ----- Method: WeakSet>>size (in category 'accessing') ----- - ----- Method: WeakSet>>size (in category 'public') ----- size "Careful!! Answer the maximum amount of elements in the receiver, not the exact amount" ^tally! Item was added: + ----- Method: PluggableDictionary>>collect: (in category 'enumerating') ----- + collect: aBlock + "Evaluate aBlock with each of my values as the argument. Collect the resulting values into a collection that is like me. Answer with the new collection." + + | newCollection | + newCollection := (self species new: self size) + hashBlock: hashBlock; + equalBlock: equalBlock; + yourself. + self associationsDo: [ :each | + newCollection at: each key put: (aBlock value: each value) ]. + ^newCollection + + ! Item was removed: - ----- Method: WeakKeyToCollectionDictionary>>finalizeValues (in category 'as yet unclassified') ----- - finalizeValues - self rehash!
More information about the Squeak-dev mailing list |