[squeak-dev] The Inbox: Collections-ul.913.mcz
Levente Uzonyi
leves at caesar.elte.hu
Mon Sep 28 15:44:57 UTC 2020
Hi Marcel,
On Mon, 28 Sep 2020, Marcel Taeumel wrote:
> Hi Levente.
> It looks like #arraySize is "private" or at least "tests only", right? I understand that you need a better accessor in tests regarding that growth behavior. Well, you could just add #arraySize via meta-programming to the test
> case where you need it. Hmm...
Not really. It's used by HashedCollection >> #removeAll, MethodDictionary
>> #compact, and MethodDictionary class >> #compactAllInstances. The
latter two are in Kernel, which I forgot to push to the Inbox.
But we can entirely avoid introducing the new selector by using the
existing private/tests-only #array selector, and send #size to the object
it returns.
Levente
>
> So, +1 for fixing #capacity. Not sure about #arraySize though ... :-)
>
> Best,
> Marcel
>
> Am 28.09.2020 01:22:39 schrieb commits at source.squeak.org <commits at source.squeak.org>:
>
> Levente Uzonyi uploaded a new version of Collections to project The Inbox:
> http://source.squeak.org/inbox/Collections-ul.913.mcz
>
> ==================== Summary ====================
>
> Name: Collections-ul.913
> Author: ul
> Time: 28 September 2020, 1:19:09.686632 am
> UUID: 03eb89d7-ea1f-4116-99eb-0181542610f7
> Ancestors: Collections-eem.912
>
> HashedCollection changes:
> - make #capacity return the actual capacity of the collection instead of the size of the internal array. This change is obviously not backwards compatible.
> - introduce #arraySize to return the size of the internal array
> - improve the performance of #isEmpty when tally is 0
>
> OrderedDictionary changes;
> - make it a subclass of PluggableDictionary. This lets one create e.g. an ordered identity dictionary without creating a subclass with duplicated behavior
> - simplify #initialize and #growTo: now that #capacity is accurate
>
> =============== Diff against Collections-eem.912 ===============
>
> Item was added:
> + ----- Method: HashedCollection>>arraySize (in category 'accessing') -----
> + arraySize
> + "Answer the size of the internal array of the receiver."
> +
> + ^array size!
>
> Item was changed:
> ----- Method: HashedCollection>>capacity (in category 'accessing') -----
> capacity
> + "Answer the current capacity of the receiver - aka the number of elements the receiver can hold without growing."
> - "Answer the current capacity of the receiver."
>
> + ^ array size * 3 // 4!
> - ^ array size!
>
> Item was changed:
> ----- Method: HashedCollection>>isEmpty (in category 'testing') -----
> isEmpty
> "For non-weak collections, we can use the tally to speed up the empty check. For weak collections, we must use the traditional way because the tally is unreliable. Also see #size vs. #slowSize."
>
> + tally = 0 ifTrue: [ ^true ].
> + ^array class isWeak and: [ super isEmpty ]!
> - ^ array class isWeak
> - ifFalse: [ tally = 0 ]
> - ifTrue: [ super isEmpty ]!
>
> Item was changed:
> ----- Method: HashedCollection>>removeAll (in category 'removing') -----
> removeAll
> "remove all elements from this collection.
> Preserve the capacity"
>
> + self initialize: self arraySize!
> - self initialize: self capacity!
>
> Item was changed:
> + PluggableDictionary subclass: #OrderedDictionary
> - Dictionary subclass: #OrderedDictionary
> instanceVariableNames: 'order'
> 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>>growTo: (in category 'private') -----
> growTo: anInteger
>
> - | oldOrder |
> super growTo: anInteger.
> + order := order grownBy: self capacity - order size!
> - 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!
>
> Item was changed:
> ----- Method: OrderedDictionary>>initialize: (in category 'private') -----
> initialize: n
>
> super initialize: n.
> + order := self class arrayType new: self capacity!
> - order := self class arrayType new: n + 1 * 3 // 4!
>
>
>
>
More information about the Squeak-dev
mailing list
|