Fwd: sort: and sortBlock:

Apparently sort: is not understood by SortedCollection :(
And sortBlock: is not understood by ArrayedCollection subclasses :(
So this is cool OrderedCollection does not understand sort:

Could we dare to fix that? Does anybody have a solution?

Stef

ArrayedCollection>>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
                mergeSortFrom: 1
                to: self size
                by: aSortBlock


SortedCollection>>sortBlock: aBlock
        "Answer an instance of me such that its elements are sorted according to
        the criterion specified in aBlock."

        ^(super new: 10) sortBlock: aBlock





_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

2009/12/23 Stéphane Ducasse <[hidden email]>:
Oh that one bugs me...
You also have

asSortedArray
asSortedCollection
asSortedCollection:
sortBy:

A bit too many selectors?

The different semantics currently are:
- sort in place  - #sort and #sort:
- make a sorted copy - #asSortedArray does except if already
isMemberOf: Array and isSorted, #sortBy: does too but is only
understood by SequenceableCollection (stupid)
- make a sorted collection that can further sort added elements -
#asSortedCollection #asSortedCollection:
#sortBlock: has 2 semantics: instance creation and modifying the sort
block of an instance...

And I would like another message to avoid all these keys asArray sort
I spreaded in trunk:
- sort in place if possible (if Sequenceable), or create a sorted
sequence otherwise
But you can understand I did not dare adding a new selector :)

Nicolas

>
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Nicolas

could we build a path to make sure that we can move on?
I would love to write new collection using traits (but I have no time :(
I should finish sometimes what I start -- geesh).

I started to implement OrderedSet (OrderedCollection no duplicate)
but I think that I want probably UniqueOrdered.
I will publish what I have done and ask for feedback and that other can improve.
I like the idea of using the TraitsTest to have coherent sets of behavior.








_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Stéphane Ducasse <stephane.ducasse@...> writes:

>  I started to implement OrderedSet (OrderedCollection no duplicate)
> but I think that I want probably UniqueOrdered.
> I will publish what I have done and ask for feedback and that other can
> improve. I like the idea of using the TraitsTest to have coherent sets of
> behavior.

Oh yeah, TreeSet ftw, missed that already sometime!

> > >> asSortedArray
> > asSortedCollection
> > asSortedCollection:
> > sortBy:

What bugs me is that #sortBy: does not what it says. I would expect that

    aCollection sortBy: [ :each | each name ]

does the same as

    aCollection sort: [ :a :b | a name <= b name ]

if you want that, I can provide a fast implementation of #sortBy:

--AA


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

>>>>> "Adrian" == Adrian Kuhn <[hidden email]> writes:

Adrian> What bugs me is that #sortBy: does not what it says. I would expect that

Adrian>     aCollection sortBy: [ :each | each name ]

Adrian> does the same as

Adrian>     aCollection sort: [ :a :b | a name <= b name ]

And if you could make "aCollection sortBy: #name" also do the same,
bonus points!

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

>> I started to implement OrderedSet (OrderedCollection no duplicate)
>> but I think that I want probably UniqueOrdered.
>> I will publish what I have done and ask for feedback and that other can
>> improve. I like the idea of using the TraitsTest to have coherent sets of
>> behavior.
>
> Oh yeah, TreeSet ftw, missed that already sometime!

what is TreeSet?

Is it not that sortBy: should be used like that
        aCollection sortBy: [ :a :b | a name <= b name ] ?

> if you want that, I can provide a fast implementation of #sortBy:

Now what would be good is to have sort: for all the collections so that we can use them
polymorphically.

I do not really see the use of sortBy: except as a replacement/unification between
sortBlock: and sort:.

I really think that we should polish the collections. They are the foundation.
We should probably have a look at the moose collection extensions you did and
we ported to squeak (not all of them). They are published in Moose/CollectionExtensions

Stef

>
> --AA
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Stéphane Ducasse <stephane.ducasse@...> writes:

> >> I started to implement OrderedSet (OrderedCollection no duplicate)
> >> but I think that I want probably UniqueOrdered.
> >> I will publish what I have done and ask for feedback and that other can
> >> improve. I like the idea of using the TraitsTest to have coherent sets of
> >> behavior.
> >
> > Oh yeah, TreeSet ftw, missed that already sometime!
>
> what is TreeSet?

The common data structure to implement ordered sets. Which one do you use?

--AA


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Randal L. Schwartz <merlyn@...> writes:

> And if you could make "aCollection sortBy: #name" also do the same,
> bonus points!

Even better, you get that for free thanks to Symbol>>#value: :)

--AA





_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

OrderedCollection as in VW the order is based on addition order.

I think that what I'm implemented is more UniqueOrderedCollection than OrderedSet
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, Dec 23, 2009 at 1:45 AM, Nicolas Cellier
<[hidden email]> wrote:
Funnily I just spent last week with John O'Keefe looking at
non-VASt-compatible protocol that Seaside uses, comparing it across
platforms, and pondering which pieces to include tests for in Grease
and which to stop using in Seaside. (by the way, he was happy to add a
whole bunch of "useful" protocol to their base image, which is great
news). I need to write a summary of everything we came up with as well
over the holidays, but in the meantime, here's what we came up with
around sorting:

#sortBlock: is defined by ANSI on SortedCollection as an accessor and
an instance creation method. That's what it sounds like and shouldn't
be implemented on non-sorted collections.


#asSortedCollection is defined by ANSI on Collection and returns an
instance of SortedCollection.


#sort and #sort: -- Squeak/Pharo have it on ArrayedCollection, VW has
it on SequenceableCollection, and VASt will now add it. This sorts the
instance in place.


#sorted, #sorted: -- VW already has this. VA is adding it.
Squeak/Pharo should add it, IMO, but we'll add it to Grease if not. It
returns a sorted copy of SequenceableCollections and a sorted Array of
all other collections.


#sortBy: is silly, as you mention and not supported on any other
platform. We're adding it to our lint rules as a "do not use" method.


We didn't notice #asSortedArray but I think that's a terrible name --
the pattern with #as* methods is that the thing after the "as" should
be a class. That behaviour could be easily achieved with "aCollection
sorted asArray" or "aCollection asArray sort" if really needed.


So that's what VASt/Seaside/Grease are doing... I encourage you to
follow our lead. :)

Julian

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Stéphane Ducasse <stephane.ducasse@...> writes:

> >> what is TreeSet?
> >
> > The common data structure to implement ordered sets. Which one do you use?
>
> OrderedCollection as in VW the order is based on addition order.
>
> I think that what I'm implemented is more UniqueOrderedCollection than
> OrderedSet

Okay, so all basic operations are O(n) and elements are not ordered by their
 natural order. Sounds kinda like a push-only stack with unique elements and
 "global" remove. Mebbe `UniqueStack` is a good name?

Would be nice to get a tree set also then. In a tree set all basic operations
 (add, remove, includes) are O(log n) and elements are ordered by their natural
 order. This could be called `SortedSet` even.

No tree set implementation in Smalltalk out there?

--AA


--
4th Workshop on Dynamic Languages and Applications
Submit papers by March 31, 2010. http://bit.ly/dyla2010


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, 23 Dec 2009, Adrian Kuhn wrote:

> Stéphane Ducasse <stephane.ducasse@...> writes:

> >> I started to implement OrderedSet (OrderedCollection no duplicate)
> >> but I think that I want probably UniqueOrdered.
> >> I will publish what I have done and ask for feedback and that other can
> >> improve. I like the idea of using the TraitsTest to have coherent sets of
> >> behavior.
> >
> > Oh yeah, TreeSet ftw, missed that already sometime!
>
> what is TreeSet?

The common data structure to implement ordered sets. Which one do you use?


IMO ordered sets (where ordering means the same as in OrderedCollection)
should be implemented with a hashtable of linked elements.


Levente



--AA


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, 23 Dec 2009, Adrian Kuhn wrote:

> Stéphane Ducasse <stephane.ducasse@...> writes:

> >> what is TreeSet?
> >
> > The common data structure to implement ordered sets. Which one do you use?
>
> OrderedCollection as in VW the order is based on addition order.
>
> I think that what I'm implemented is more UniqueOrderedCollection than
> OrderedSet

Okay, so all basic operations are O(n) and elements are not ordered by their
  natural order. Sounds kinda like a push-only stack with unique elements and
  "global" remove. Mebbe `UniqueStack` is a good name?

Would be nice to get a tree set also then. In a tree set all basic operations
  (add, remove, includes) are O(log n) and elements are ordered by their natural
  order. This could be called `SortedSet` even.

No tree set implementation in Smalltalk out there?


There's BTree on squeaksource, I have LLRBTree (left-leaning
red-black tree) but that needs some polishing. Probably there are
other implementations too. (I think there's an AVL-tree implementation
somewhere, but i'm unsure.) Trees are rarely useful anyway.


Levente



--AA


--
4th Workshop on Dynamic Languages and Applications
Submit papers by March 31, 2010. http://bit.ly/dyla2010


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, 23 Dec 2009, Randal L. Schwartz wrote:

Well, squeak trunk has this, try: #(1 2 3) sort: #>=.


Levente


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, 23 Dec 2009, Adrian Kuhn wrote:

> Stéphane Ducasse <stephane.ducasse@...> writes:

>  I started to implement OrderedSet (OrderedCollection no duplicate)
> but I think that I want probably UniqueOrdered.
> I will publish what I have done and ask for feedback and that other can
> improve. I like the idea of using the TraitsTest to have coherent sets of
> behavior.

Oh yeah, TreeSet ftw, missed that already sometime!

> > >> asSortedArray
> > asSortedCollection
> > asSortedCollection:
> > sortBy:

What bugs me is that #sortBy: does not what it says. I would expect that

     aCollection sortBy: [ :each | each name ]

does the same as

     aCollection sort: [ :a :b | a name <= b name ]

if you want that, I can provide a fast implementation of #sortBy:


Not all collections are sortable and #sort: is sorting in-place, so it's
hardly doable.


Levente



--AA


_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Wed, 23 Dec 2009, Julian Fitzell wrote:
+1

>
>
> #asSortedCollection is defined by ANSI on Collection and returns an
> instance of SortedCollection.
>

And this shouldn't be used for sorting.

>
> #sort and #sort: -- Squeak/Pharo have it on ArrayedCollection, VW has
> it on SequenceableCollection, and VASt will now add it. This sorts the
> instance in place.
>

The problem here is that not all SequenceableCollections are sortable,
for example instances of Interval can't be sorted. In squeak trunk
ArrayedCollection and OrderedCollection understand both.

>
> #sorted, #sorted: -- VW already has this. VA is adding it.
> Squeak/Pharo should add it, IMO, but we'll add it to Grease if not. It
> returns a sorted copy of SequenceableCollections and a sorted Array of
> all other collections.
>

+1, except for SequenceableCollection, see above

>
> #sortBy: is silly, as you mention and not supported on any other
> platform. We're adding it to our lint rules as a "do not use" method.
>

+1

>
> We didn't notice #asSortedArray but I think that's a terrible name --
> the pattern with #as* methods is that the thing after the "as" should
> be a class. That behaviour could be easily achieved with "aCollection
> sorted asArray" or "aCollection asArray sort" if really needed.
>

+1, also note that in squeak/pharo #as* methods have semantic differences


Levente

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Dec 23, 2009, at 6:08 PM, Adrian Kuhn wrote:

kind of I prefer UniqueOrderedCollection now in VW they have a kind of equivalent named OrderedSet
which is not a treeSet

> Would be nice to get a tree set also then. In a tree set all basic operations
> (add, remove, includes) are O(log n) and elements are ordered by their natural
> order.
Yes I see.

> This could be called `SortedSet` even.
>
> No tree set implementation in Smalltalk out there?

Not from me :)

Stef

_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

On Dec 23, 2009, at 6:09 PM, Levente Uzonyi wrote:

Why not an OrderedCollection?
if we mean UniqueOrderedCollection
For an OrderedSet I imagine that this is because you want a constant access to elements (which happend to be ordered)?
Stef
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

But it would be nice to have sort: and sortBlock: polymorph.
Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.

Stef
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project