The Inbox: Collections-fbs.489.mcz

> Frank Shearar uploaded a new version of Collections to project The Inbox:
> http://source.squeak.org/inbox/Collections-fbs.489.mcz
>
> ==================== Summary ====================
>
> Name: Collections-fbs.489
> Author: fbs
> Time: 20 August 2012, 4:51:36.018 pm
> UUID: d1834809-65b5-46c0-9b26-fea7ec04a946
> Ancestors: Collections-ul.488
>
> SequenceableCollection >> flatten turns a nested SequenceableCollection - a collection of collections of ... -  into a simple collection. Thus, #(1 (2 3) (4)) flatten = #(1 2 3 4).
>
> =============== Diff against Collections-ul.488 ===============
>
> Item was added:
> + ----- Method: SequenceableCollection>>flatten (in category 'copying') -----
> + flatten
> +       | recur stream |
> +       stream := WriteStream on: (Array new: self size). "A lower bound on the final stream count."
> +       recur := [:coll | coll
> +               do: [:each |
> +                       each isCollection
> +                               ifTrue: [recur value: each]
> +                               ifFalse: [stream nextPut: each]]].
> +       recur value: self.
> +       ^ stream contents.!

>   - Chris
>
>
> On Mon, Aug 20, 2012 at 10:54 AM, Frank Shearar <[hidden email]> wrote:
>> On 20 August 2012 16:51,  <[hidden email]> wrote:
>>> Frank Shearar uploaded a new version of Collections to project The Inbox:
>>> http://source.squeak.org/inbox/Collections-fbs.489.mcz
>>>
>>> ==================== Summary ====================
>>>
>>> Name: Collections-fbs.489
>>> Author: fbs
>>> Time: 20 August 2012, 4:51:36.018 pm
>>> UUID: d1834809-65b5-46c0-9b26-fea7ec04a946
>>> Ancestors: Collections-ul.488
>>>
>>> SequenceableCollection >> flatten turns a nested SequenceableCollection - a collection of collections of ... -  into a simple collection. Thus, #(1 (2 3) (4)) flatten = #(1 2 3 4).
>>>
>>> =============== Diff against Collections-ul.488 ===============
>>>
>>> Item was added:
>>> + ----- Method: SequenceableCollection>>flatten (in category 'copying') -----
>>> + flatten
>>> +       | recur stream |
>>> +       stream := WriteStream on: (Array new: self size). "A lower bound on the final stream count."
>>> +       recur := [:coll | coll
>>> +               do: [:each |
>>> +                       each isCollection
>>> +                               ifTrue: [recur value: each]
>>> +                               ifFalse: [stream nextPut: each]]].
>>> +       recur value: self.
>>> +       ^ stream contents.!
>>
>> I've had to implement this a few times now, so I thought it time to
>> offer it up for general consumption. My original implementation was
>> recursive, using #collect: and #inject:into:. This of course used a
>> lot of #copy sends. Using a WriteStream seems more efficient, both in
>> time trials and in looking at MessageTally outputs (where GC usage was
>> a fraction of the recursive implementation, and 40% of CPU time was
>> actually spent in primitives).
>>
>> frank
>>
>
>
>

> On Mon, Aug 20, 2012 at 10:04 AM, Frank Shearar <[hidden email]> wrote:
>> Another way to flatten without flattening would be to have an external
>> iterator: PreOrderTraversal on: myNestedCollection could define all
>> the usual collection methods, and use the underlying collections'
>> #do:. (And such an iterator could iterate over heterogeneous
>> structures too.)
>
> I quite like this approach. I used it in Filesystem, for walking
> directory trees. See FSPreorderGuide, FSPostorderGuide and
> FSBreadthFirstGuide. The term "Guide" comes from the fact that they
> work with Visitors, guiding them around the filesystem.