[squeak-dev] The Trunk: Collections-ar.129.mcz

Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ar.129.mcz

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

Name: Collections-ar.129
Author: ar
Time: 13 September 2009, 5:17:44 am
UUID: 64ca8d2a-4608-ab4c-b4f4-bdbe61efcdab
Ancestors: Collections-cbc.128, Collections-ul.128

Merging Collections-ul.128:

- introduced #new:streamContents: in SequenceableCollection class. It's like #streamContents: but if you know the size of the new collection this method doesn't copy the result.
- updated SequenceableCollection class >> #streamContents: to use #new:streamContents:, kept the original default size 100.
- also updated Dictionary >> #association, Bag >> #sortedCounts and Dictionary >> #keysSortedSafely to use #new:streamContents:.

- introduced #sort: in OrderedCollection. It uses Array's merge sort to sort the internal array. This is much faster than sorting with SortedCollection (though it uses an extra Array object). Also added #sort which uses the same default block as Array >> #sort.
- updated Bag >> #sortedCounts, Bag >> #sortedElements, Dictionary >> #keysSortedSafely, SequenceableCollection >> #sortBy: to use OrderedCollection's or Array's #sort method which can be significantly faster in these cases.

- modified OrderedCollection class >> #newFrom: to avoid reallocating the internal array of the new OrderedCollection when the sender of #newFrom: doesn't extend the collection.

- changed the variable name from anOrderedCollection to aCollection in OrderedCollection >> #addAllLast: since it is being used with other Collections. Also changed the comment which seems to be superfluous.

All related tests are green.

=============== Diff against Collections-cbc.128 ===============

Item was changed:
  ----- Method: Bag>>sortedCounts (in category 'accessing') -----
  sortedCounts
  "Answer with a collection of counts with elements, sorted by decreasing
  count."
 
+ ^(Array new: contents size streamContents: [ :stream |
+ contents associationsDo: [ :each |
+ stream nextPut: each value -> each key ] ])
+ sort: [:x :y | x >= y ];
+ yourself!
- | counts |
- counts := SortedCollection sortBlock: [:x :y | x >= y].
- contents associationsDo:
- [:assn |
- counts add: (Association key: assn value value: assn key)].
- ^ counts!

Item was changed:
  ----- Method: Dictionary>>associations (in category 'accessing') -----
  associations
  "Answer a Collection containing the receiver's associations."
+
+ ^Array new: self size streamContents: [ :stream |
+ self associationsDo: [ :each | stream nextPut: each ] ]!
- | out |
- out := WriteStream on: (Array new: self size).
- self associationsDo: [:value | out nextPut: value].
- ^ out contents!

Item was changed:
  ----- Method: OrderedCollection>>addAllLast: (in category 'adding') -----
+ addAllLast: aCollection
+ "Add each element of aCollection at the end of the receiver.
+ Answer aCollection."
- addAllLast: anOrderedCollection
- "Add each element of anOrderedCollection at the end of the receiver.
- Answer anOrderedCollection."
 
+ aCollection do: [ :each | self addLast: each].
+ ^aCollection!
- anOrderedCollection do: [:each | self addLast: each].
- ^anOrderedCollection!

Item was changed:
  ----- Method: SequenceableCollection>>sortBy: (in category 'copying') -----
  sortBy: aBlock
  "Create a copy that is sorted.  Sort criteria is the block that accepts two arguments.
  When the block is true, the first arg goes first ([:a :b | a > b] sorts in descending
  order)."
 
+ ^ self asOrderedCollection
+ sort: aBlock;
+ yourself!
- ^ (self asSortedCollection: aBlock) asOrderedCollection!

Item was added:
+ ----- Method: OrderedCollection>>sort: (in category 'sorting') -----
+ sort: aSortBlock
+ "Sort this array using aSortBlock. The block should take two arguments
+ and return true if the first element should preceed the second one."
+
+ self ifNotEmpty: [
+ array
+ mergeSortFrom: firstIndex
+ to: lastIndex
+ by: aSortBlock ]!

Item was changed:
  ----- Method: Dictionary>>keysSortedSafely (in category 'accessing') -----
  keysSortedSafely
+ "Answer an Array containing the receiver's keys."
+
- "Answer a SortedCollection containing the receiver's keys."
  | sortedKeys |
+ sortedKeys := Array new: self size streamContents: [ :stream |
+ self keysDo: [ :each | stream nextPut: each ] ].
+ sortedKeys sort: [ :x :y |
+ "Should really be use <obj, string, num> compareSafely..."
+ ((x isString and: [ y isString ])
+ or: [ x isNumber and: [ y isNumber ] ])
+ ifTrue: [ x < y ]
+ ifFalse: [ x class == y class
+ ifTrue: [ x printString < y printString ]
+ ifFalse: [ x class name < y class name ] ] ].
+ ^sortedKeys!
- sortedKeys := SortedCollection new: self size.
- sortedKeys sortBlock:
- [:x :y |  "Should really be use <obj, string, num> compareSafely..."
- ((x isString and: [y isString])
- or: [x isNumber and: [y isNumber]])
- ifTrue: [x < y]
- ifFalse: [x class == y class
- ifTrue: [x printString < y printString]
- ifFalse: [x class name < y class name]]].
- self keysDo: [:each | sortedKeys addLast: each].
- ^ sortedKeys reSort!

Item was added:
+ ----- Method: SequenceableCollection class>>new:streamContents: (in category 'stream creation') -----
+ new: newSize streamContents: blockWithArg
+
+ | stream |
+ stream := WriteStream on: (self new: newSize).
+ blockWithArg value: stream.
+ stream position = newSize
+ ifTrue: [ ^stream originalContents ]
+ ifFalse: [ ^stream contents ]!

Item was changed:
  ----- Method: OrderedCollection class>>newFrom: (in category 'instance creation') -----
  newFrom: aCollection
  "Answer an instance of me containing the same elements as aCollection."
 
+ ^(self new: aCollection size)
+ resetTo: 1;
+ addAll: aCollection;
+ yourself
- | newCollection |
- newCollection := self new: aCollection size.
- newCollection addAll: aCollection.
- ^newCollection
 
  " OrderedCollection newFrom: {1. 2. 3}
  {1. 2. 3} as: OrderedCollection
  {4. 2. 7} as: SortedCollection
  "!

Item was added:
+ ----- Method: OrderedCollection>>sort (in category 'sorting') -----
+ sort
+ "Sort this array into ascending order using the '<=' operator."
+
+ self sort: [:a :b | a <= b]!

Item was changed:
  ----- Method: SequenceableCollection class>>streamContents: (in category 'stream creation') -----
  streamContents: blockWithArg
+
+ ^self new: 100 streamContents: blockWithArg!
- | stream |
- stream := WriteStream on: (self new: 100).
- blockWithArg value: stream.
- ^stream contents!

Item was changed:
  ----- Method: Bag>>sortedElements (in category 'accessing') -----
  sortedElements
  "Answer with a collection of elements with counts, sorted by element."
 
+ ^contents associations
+ sort;
+ yourself!
- | elements |
- elements := SortedCollection new.
- contents associationsDo: [:assn | elements add: assn].
- ^elements!

Hey!

> Andreas Raab uploaded a new version of Collections to project The Trunk:
> Merging Collections-ul.128:
>
> - introduced #new:streamContents: in SequenceableCollection class. It's like #streamContents: but if you know the size of the new collection this method doesn't copy the result.
> - updated SequenceableCollection class >> #streamContents: to use #new:streamContents:, kept the original default size 100.
> - also updated Dictionary >> #association, Bag >> #sortedCounts and Dictionary >> #keysSortedSafely to use #new:streamContents:.
>
> - introduced #sort: in OrderedCollection. It uses Array's merge sort to sort the internal array. This is much faster than sorting with SortedCollection (though it uses an extra Array object). Also added #sort which uses the same default block as Array >> #sort.

Great.

> - updated Bag >> #sortedCounts, Bag >> #sortedElements, Dictionary >> #keysSortedSafely, SequenceableCollection >> #sortBy: to use OrderedCollection's or Array's #sort method which can be significantly faster in these cases.
>
> - modified OrderedCollection class >> #newFrom: to avoid reallocating the internal array of the new OrderedCollection when the sender of #newFrom: doesn't extend the collection.
>
> - changed the variable name from anOrderedCollection to aCollection in OrderedCollection >> #addAllLast: since it is being used with other Collections. Also changed the comment which seems to be superfluous.

Now that we are actually touching these classes again :) - how about
adding Collection>>removeAll? With proper implementations in subclasses.

I don't have a current trunk in front of me, so perhaps it has already
been done. Why you may ask? It preserves identity (instead of creating a
new collection) and it can be implemented really fast in some
subclasses. A default implementation in Collection can be:

"self copy do: [:each | self remove: each]" ...or whatever.

A few years back when I proposed it... well :)

regards, Göran

Hi again!

Göran Krampe wrote:
A link into that thread:

http://lists.squeakfoundation.org/pipermail/squeak-dev/2002-August/043750.html

Hehe, it was 7 years ago. And oh, btw, sitting in front of VS2008 (don't
ask why) and in C# I find the method Clear() in both List and
Dictionary. It is IMHO silly, silly, silly that we don't have something
similar.

regards, Göran

On 14.09.2009, Göran Krampe wrote:
>> how about adding Collection>>removeAll?

+1

- Bert -

+1 for a removeAll

While we're at it, I would like to add a "flatten" method to Collections.
This method removes all nesting from a collection (Strings are kept intact).
I find myself using this method regularily in Ruby and usually have to
revert to inject:into: or local copies to achieve the same effect in
Squeak. I implemented that method some time ago in my image, I added an
example and pushed that method to the inbox.

Regards,
Tim

Göran Krampe wrote:
> Now that we are actually touching these classes again :) - how about
> adding Collection>>removeAll? With proper implementations in subclasses.
>
> I don't have a current trunk in front of me, so perhaps it has already
> been done.

Not yet.

<hint>Someone needs to write the code. That could be you.</hint>

Cheers,
   - Andreas

I think I have an implementation, and I'm sure Keith has one too.

Nicolas

2009/9/14 Andreas Raab <[hidden email]>:

And implementation is at http://bugs.squeak.org/view.php?id=7177

Nicolas

2009/9/14 Nicolas Cellier <[hidden email]>: