[Pharo-project] 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
2009/12/23 Stéphane Ducasse <stephane.ducasse@inria.fr>:
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
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 Pharo-project@lists.gforge.inria.fr 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.
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
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
On Wed, Dec 23, 2009 at 4:58 PM, Adrian Kuhn <akuhn@iam.unibe.ch> 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:
In those cases will be cool to write first all the tests than make the things to fail and then write the code to fix them :) But ok...not everybody have that time.
--AA
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
"Adrian" == Adrian Kuhn <akuhn@iam.unibe.ch> 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 <merlyn@stonehenge.com> <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
On Wed, 23 Dec 2009, Randal L. Schwartz wrote:
"Adrian" == Adrian Kuhn <akuhn@iam.unibe.ch> 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!
Well, squeak trunk has this, try: #(1 2 3) sort: #>=. Levente
-- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <merlyn@stonehenge.com> <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 Pharo-project@lists.gforge.inria.fr 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?
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 ]
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 Pharo-project@lists.gforge.inria.fr 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
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?
OrderedCollection as in VW the order is based on addition order. I think that what I'm implemented is more UniqueOrderedCollection than OrderedSet
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
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Dec 23, 2009, at 6:08 PM, 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?
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
--AA
-- 4th Workshop on Dynamic Languages and Applications Submit papers by March 31, 2010. http://bit.ly/dyla2010
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr 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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Dec 23, 2009, at 6:09 PM, Levente Uzonyi wrote:
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.
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
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
On Dec 23, 2009, at 6:09 PM, Levente Uzonyi wrote:
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.
Why not an OrderedCollection?
That's doable, but removal cost would be O(n) instead of O(1), though removal from sets/dictionaries is rare in smalltalk. Of course this means that the cost of accessing an element by index is O(n) instead of O(1), but I wouldn't expect a set to be indexable even if it's "ordered". Levente
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Levente Uzonyi <leves@...> writes:
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.
You're right. I confused ordered and sorted. --AA
2009/12/23 Adrian Kuhn <akuhn@iam.unibe.ch>:
Levente Uzonyi <leves@...> writes:
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.
That's probably why Stephane proposed a UniqueOrderedCollection: he must have the expectation that this collection can be indexed in O(1) Nicolas
You're right.
I confused ordered and sorted.
--AA
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
That's probably why Stephane proposed a UniqueOrderedCollection: he must have the expectation that this collection can be indexed in O(1)
Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set. I will rename it because OrderedSet is not a good name because this is not a Set. Now this is boring because this is not an OrderedCollection (or you do not have to be forced to implement insert:after:..... I really see that the collection classes suffers from single inheritance and sometimes are too fat. A Nilish collection would be a fun exercise. May be we should start and get a cool OOPSLA paper out of that. Stef
:-D when even the ANSI standard has a sort of "multiple inheritance" diagram to explain its collection hierarchy, you see this suffering is lingering for a long time behaving as some Lost characters. . .! <warning> all the possible puns intended by the author or to be discovered by more careful reading are there to be enjoyed and are not accidental1 </warning> Well, now that nanotraits and a figment to have something like a mixin in Squeak/Pharo is around the corner, who knows??!! -- Cesar Rabak Em 23/12/2009 16:28, Stéphane Ducasse < stephane.ducasse@inria.fr > escreveu:
That's probably why Stephane proposed a UniqueOrderedCollection: he must have the expectation that this collection can be indexed in O(1)
Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set. I will rename it because OrderedSet is not a good name because this is not a Set. Now this is boring because this is not an OrderedCollection (or you do not have to be forced to implement insert:after:..... I really see that the collection classes suffers from single inheritance and sometimes are too fat. A Nilish collection would be a fun exercise. May be we should start and get a cool OOPSLA paper out of that. Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Stéphane Ducasse wrote:
Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set.
Could you clarify? What's an example? What is the index of something that you add but was already there? Regards, -Martin
Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set.
Could you clarify? What's an example?
In Moose we build package representation in which the order is important first references is more important that second. Now my colleagues used an OrderedSet to keep the order but make sure that he can use add: (but did not care of possible duplicates).
What is the index of something that you add but was already there?
From his example the index is more important per se as soon as the order is kept since after he iterates on this data structure to build visualization.
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Stéphane Ducasse <stephane.ducasse@...> writes:
I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set.
A simple method should do that job Collection >> #addIfAbsent: element (self includes: element) ifFalse: [ self add: element ] usage coll := OrderedCollection new. coll addIfAbsent: #foo. coll addIfAbsent: #bar. coll addIfAbsent: #qux. coll addIfAbsent: #bar. self assert: coll asArray = #(foo bar qux). --AA
2009/12/23 Adrian Kuhn <akuhn@iam.unibe.ch>:
Stéphane Ducasse <stephane.ducasse@...> writes:
I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set.
A simple method should do that job
  Collection >> #addIfAbsent: element     (self includes: element) ifFalse: [ self add: element ]
usage
  coll := OrderedCollection new.   coll addIfAbsent: #foo.   coll addIfAbsent: #bar.   coll addIfAbsent: #qux.   coll addIfAbsent: #bar.   self assert: coll asArray = #(foo bar qux).
--AA
Yes in O(n)... The challenge was to provide a fast implementation.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
can be defined on Collection since it does not work on Array. Now extending Collection that way produce non API polymorphic objects! Defining a new class with specializing add: is MUCH better because of that exact purpose. Please do not propose to extend Collection with method only working for a subset we have enough to them On Dec 23, 2009, at 10:55 PM, Adrian Kuhn wrote:
Stéphane Ducasse <stephane.ducasse@...> writes:
I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set.
A simple method should do that job
Collection >> #addIfAbsent: element (self includes: element) ifFalse: [ self add: element ]
usage
coll := OrderedCollection new. coll addIfAbsent: #foo. coll addIfAbsent: #bar. coll addIfAbsent: #qux. coll addIfAbsent: #bar. self assert: coll asArray = #(foo bar qux).
--AA
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Adrian Kuhn wrote:
Levente Uzonyi <leves@...> writes:
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.
You're right.
I confused ordered and sorted.
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1). Regards, -Martin
On Wed, 23 Dec 2009, Martin McClure wrote:
Adrian Kuhn wrote:
Levente Uzonyi <leves@...> writes:
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.
You're right.
I confused ordered and sorted.
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1).
I don't see the point here. Without a tree structure (just a list) it's O(1) for both. Levente
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Levente Uzonyi wrote:
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1).
I don't see the point here. Without a tree structure (just a list) it's O(1) for both.
How do you get O(1) for sorted inserts into a list? That's usually considered an O(n) operation. Or am I misunderstanding what you mean by list? Regards, -Martin
On Wed, 23 Dec 2009, Martin McClure wrote:
Levente Uzonyi wrote:
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1).
I don't see the point here. Without a tree structure (just a list) it's O(1) for both.
How do you get O(1) for sorted inserts into a list? That's usually considered an O(n) operation. Or am I misunderstanding what you mean by list?
Well, just realized that you are thinking about a sorted set. The original idea was to create an ordered set. Levente
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
I just would like to point out that English plus the use of some [of their] overloaded words may create havoc in a discussion. TreeSets would be a common data structure to implement *sorted* sets in Smalltalk parlance. Although /ordered/ and /sorted/ may be synonyms in lay English, in Smalltalk the use of "Ordered" in the Collection classes has to the property of being indexable and sequenceable which other languages will call the behaviour of "random access". just my 0.0199999.... Em 23/12/2009 14:34, Adrian Kuhn < akuhn@iam.unibe.ch > escreveu: Stéphane 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 Pharo-project@lists.gforge.inria.fr 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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged. Stef
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
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.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful). If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm). Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Dec 23, 2009, at 6:43 PM, Levente Uzonyi wrote:
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
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.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful).
Indeed I understand that now. sort is much better bette because it is orthogonal to the datastructure
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Ok I will have a look.
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2009/12/23 Levente Uzonyi <leves@elte.hu>:
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
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.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful).
The only case should be to keep collection automatically sorted when its contents further evolves... Of course, using repeated #add: is inefficient (#addAll: has a rule for sorting once or at every #add:).
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346 Nicolas
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Let me know if we can integrate them and we will. Stef
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346
levente I compared in Squeak Arrayed ... sort: nil mergeFirst: first middle: middle last: last into: dst by: aBlock ... [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ (aBlock ifNil: [ val1 <= val2 ] ifNotNil: [ aBlock value: val1 value: val2 ]) ifTrue: [ dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [ dst at: (out := out + 1) put: val2. (i2 := i2 + 1) <= last ifTrue: [ val2 := self at: i2 ] ] ]. ... in pharo Arrayed ... sort: [:a :b | a <= b] mergeFirst: first middle: middle last: last into: dst by: aBlock ... [(i1 <= middle) and: [i2 <= last]] whileTrue: [(aBlock value: val1 value: val2) ifTrue: [dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [dst at: (out := out + 1) put: val2. i2 := i2 + 1. i2 <= last ifTrue: [val2 := self at: i2]]]. what is the best? Stef
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
levente
I compared
in Squeak
Arrayed ... sort: nil
mergeFirst: first middle: middle last: last into: dst by: aBlock
... [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ (aBlock ifNil: [ val1 <= val2 ] ifNotNil: [ aBlock value: val1 value: val2 ]) ifTrue: [ dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [ dst at: (out := out + 1) put: val2. (i2 := i2 + 1) <= last ifTrue: [ val2 := self at: i2 ] ] ]. ...
in pharo
Arrayed ... sort: [:a :b | a <= b]
mergeFirst: first middle: middle last: last into: dst by: aBlock ... [(i1 <= middle) and: [i2 <= last]] whileTrue: [(aBlock value: val1 value: val2) ifTrue: [dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [dst at: (out := out + 1) put: val2. i2 := i2 + 1. i2 <= last ifTrue: [val2 := self at: i2]]].
what is the best?
It's a hack, I took it from SortedCollection's quicksort implementation. This gives the best performance if you're sorting by <= which is the default. Levente
Stef
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
mergeFirst: first middle: middle last: last into: dst by: aBlock
... [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ (aBlock ifNil: [ val1 <= val2 ] ifNotNil: [ aBlock value: val1 value: val2 ]) ifTrue: [ dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [ dst at: (out := out + 1) put: val2. (i2 := i2 + 1) <= last ifTrue: [ val2 := self at: i2 ] ] ]. ...
It's a hack, I took it from SortedCollection's quicksort implementation. This gives the best performance if you're sorting by <= which is the default.
Thanks for the explanation.
Levente Uzonyi <leves@...> writes:
It's a hack, I took it from SortedCollection's quicksort implementation. This gives the best performance if you're sorting by <= which is the default.
Shouldn't `sort` do what `sort: nil` does? A simple `aBlock ifNil: [ ^self sort ]` might be more intention revealing (of course assumed that `sort` implements a #<= based sort :) --AA
On Wed, 23 Dec 2009, Adrian Kuhn wrote:
Levente Uzonyi <leves@...> writes:
It's a hack, I took it from SortedCollection's quicksort implementation. This gives the best performance if you're sorting by <= which is the default.
Shouldn't `sort` do what `sort: nil` does?
A simple `aBlock ifNil: [ ^self sort ]` might be more intention revealing (of course assumed that `sort` implements a #<= based sort :)
In squeak #sort is implemented as self sort: nil. So that check would mean infinite recursion. Levente
--AA
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Wed, 23 Dec 2009, Nicolas Cellier wrote:
2009/12/23 Levente Uzonyi <leves@elte.hu>:
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
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.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful).
The only case should be to keep collection automatically sorted when its contents further evolves...
Indeed.
Of course, using repeated #add: is inefficient (#addAll: has a rule for sorting once or at every #add:).
That's true, but #addAll:'s rule is not generally useful. For example: | s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100000) ] timeToRun ===> 24698 | s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100001) ] timeToRun ===> 1124 (+1 element makes a big difference) And in squeak: | s | s := (1 to: 300000) asOrderedCollection. [ s addAll: (1 to: 100000); sort ] timeToRun ===> 763 (mergesort beats quicksort) So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't. Levente
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346
Nicolas
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Of course, using repeated #add: is inefficient (#addAll: has a rule
for sorting once or at every #add:).
That's true, but #addAll:'s rule is not generally useful. For example:
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100000) ] timeToRun ===> 24698
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100001) ] timeToRun ===> 1124 (+1 element makes a big difference)
why + 1 makes a so big difference?
And in squeak: | s | s := (1 to: 300000) asOrderedCollection. [ s addAll: (1 to: 100000); sort ] timeToRun ===> 763 (mergesort beats quicksort)
cool. This is fun to see that during years we pushed so that squeak moves and we got bashed for that and now squeak is moving because of us. At least we succeeded in something.
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
Levente
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346
Nicolas
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
Of course, using repeated #add: is inefficient (#addAll: has a rule
for sorting once or at every #add:).
That's true, but #addAll:'s rule is not generally useful. For example:
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100000) ] timeToRun ===> 24698
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100001) ] timeToRun ===> 1124 (+1 element makes a big difference)
why + 1 makes a so big difference?
Because #addAll: has a simple check that doesn't care about the performance of the different methods of addition: addAll: aCollection aCollection size > (self size // 3) ifTrue: [aCollection do: [:each | self addLast: each]. self reSort] ifFalse: [aCollection do: [:each | self add: each]]. ^ aCollection A better check could solve this, but who wants to come up with a formula that's easy to calculate (aka fast) and gives accurate results? Levente
And in squeak: | s | s := (1 to: 300000) asOrderedCollection. [ s addAll: (1 to: 100000); sort ] timeToRun ===> 763 (mergesort beats quicksort)
cool. This is fun to see that during years we pushed so that squeak moves and we got bashed for that and now squeak is moving because of us. At least we succeeded in something.
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
Levente
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346
Nicolas
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
why + 1 makes a so big difference?
Because #addAll: has a simple check that doesn't care about the performance of the different methods of addition:
addAll: aCollection aCollection size > (self size // 3) ifTrue: [aCollection do: [:each | self addLast: each]. self reSort] ifFalse: [aCollection do: [:each | self add: each]]. ^ aCollection
A better check could solve this, but who wants to come up with a formula that's easy to calculate (aka fast) and gives accurate results?
Thanks. I like these kind of conversation because they deeply illustrate what I always like in Smalltalk: learning by reading the system. Stef
Levente Uzonyi wrote:
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
I was slightly confused by this, but now think I see what you're saying. Most #as* selectors return an instance of a different class, but answer self if the receiver is already of that class. But collections always answer a copy, even if it is already of that class. Wondering why this was designed this way... Perhaps it's the expected mutability of collections? When you send #asInteger, you don't care if you get the receiver back, because it's not mutable. But with a collection you almost always mutate it. In the case of #asString, Strings are mutable, but are not *commonly* mutated. Regards, -Martin
On Wed, 23 Dec 2009, Martin McClure wrote:
Levente Uzonyi wrote:
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
I was slightly confused by this, but now think I see what you're saying.
Most #as* selectors return an instance of a different class, but answer self if the receiver is already of that class. But collections always answer a copy, even if it is already of that class.
All collections answer self, except instances of OrderedCollection SortedCollection and CharacterSet (at least in squeak).
Wondering why this was designed this way...
I think these methods (#asOrderedCollection #asSortedCollection #asCharacterSet) were added later than the others and those who added them didn't think about this implementation detail.
Perhaps it's the expected mutability of collections? When you send #asInteger, you don't care if you get the receiver back, because it's not mutable. But with a collection you almost always mutate it. In the
That's not true, LargeIntegers are mutable. I don't have numbers, but I think that most senders of #as* don't mutate the collection. Levente
case of #asString, Strings are mutable, but are not *commonly* mutated.
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2009/12/23 Levente Uzonyi <leves@elte.hu>:
On Wed, 23 Dec 2009, Martin McClure wrote:
Levente Uzonyi wrote:
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
I was slightly confused by this, but now think I see what you're saying.
Most #as* selectors return an instance of a different class, but answer self if the receiver is already of that class. But collections always answer a copy, even if it is already of that class.
All collections answer self, except instances of OrderedCollection SortedCollection and CharacterSet (at least in squeak).
Not to be confused with (self as: Array) that always answer a copy in Squeak/Pharo. While looking at it, FixedIdentitySet asArray ^ self, is this really expected ? Nicolas
Wondering why this was designed this way...
I think these methods (#asOrderedCollection #asSortedCollection #asCharacterSet) were added later than the others and those who added them didn't think about this implementation detail.
Perhaps it's the expected mutability of collections? When you send #asInteger, you don't care if you get the receiver back, because it's not mutable. But with a collection you almost always mutate it. In the
That's not true, LargeIntegers are mutable. I don't have numbers, but I think that most senders of #as* don't mutate the collection.
Levente
case of #asString, Strings are mutable, but are not *commonly* mutated.
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Nicolas Cellier wrote:
While looking at it, FixedIdentitySet asArray ^ self, is this really expected ?
FixedIdentitySet is a very odd beast. I'm afraid I don't see the value of it at all, but I haven't looked at the code that uses it. Regards, -Martin
2009/12/23 Martin McClure <martin@hand2mouse.com>:
Nicolas Cellier wrote:
While looking at it, FixedIdentitySet asArray ^ self, is this really expected ?
FixedIdentitySet is a very odd beast. I'm afraid I don't see the value of it at all, but I haven't looked at the code that uses it.
Regards,
-Martin
Yes, very bad example, only used in traits implementation and should be considered as private, so who ever use it should learn to not send asArray, nor any other inherited message but a few. I suspect inheriting basicAt: basicAt:put: and basicSize: should be enough, which completely disqualify the choice of superclass, but I won't bother more. Anyway, I'm impressed by (Array allSubclasses size), I would expect zero as a good number. Nicolas
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Nicolas Cellier wrote:
SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful).
The only case should be to keep collection automatically sorted when its contents further evolves...
Yes, that has always been its only purpose. And it seems valuable, though I'd like to see it expanded to a collection with 0-n automatically-maintained sort orders, rather than exactly one sort order. Regards, -Martin
Stéphane Ducasse wrote:
Not all collections are sortable and #sort: is sorting in-place, so it's hardly doable.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
OrderedCollection, Array, and SortedCollection by design all have different semantics, not just different internal implementations. In such a case you cannot expect to be able to interchange them in all circumstances. In many cases you can, but when for instance you use #sortBlock: you'd better not have an Array or OrderedCollection, and when you use #add: you'd better not have an Array, because those classes do not support the *meanings* of those selectors. Regards, -Martin
On Dec 23, 2009, at 10:57 PM, Martin McClure wrote:
Stéphane Ducasse wrote:
Not all collections are sortable and #sort: is sorting in-place, so it's hardly doable.
But it would be nice to have sort: and sortBlock: polymorph. Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged.
OrderedCollection, Array, and SortedCollection by design all have different semantics, not just different internal implementations. In such a case you cannot expect to be able to interchange them in all circumstances.
sure but when I know what I'm doing iterating for example I should be able and sorting them before iterating is a good motivation to iterate on them.
In many cases you can, but when for instance you use #sortBlock: you'd better not have an Array or OrderedCollection, and when you use #add: you'd better not have an Array, because those classes do not support the *meanings* of those selectors.
Yes I know :) Now not having sort in SortedCollection is a lack of vision. Stef
On Wed, Dec 23, 2009 at 1:45 AM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2009/12/23 Stéphane Ducasse <stephane.ducasse@inria.fr>:
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
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 :)
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
On Wed, 23 Dec 2009, Julian Fitzell 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.
+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
So that's what VASt/Seaside/Grease are doing... I encourage you to follow our lead. :)
Julian
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Wed, Dec 23, 2009 at 9:22 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Wed, 23 Dec 2009, Julian Fitzell wrote:
#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.
Meh... Interval shouldn't inherit #at:put: either, but it does. It's just life with the Collection hierarchy we have. In fact, on VW at least, #sort: is implemented in terms of #at:put: so trying to sort an Interval just triggers an Exception saying "you cannot store into an Interval". But how platforms choose to implement it is really up to them - the goal is that any Collection that should be sortable in place responds to #sort and #sort: somehow, whether that's through inheritance, traits, or multiple implementations, I don't (personally) care.
#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
Yes, Intervals are a bit weird in this case - again, I'd lean towards #shouldNotImplement unless it fails naturally in some other way but I don't feel strongly about it. Our platforms tests will test for it on individual classes; again, how exactly the behaviour ends up on each of those classes is not that important to me. Julian
On Dec 24, 2009, at 9:54 AM, Julian Fitzell wrote:
On Wed, Dec 23, 2009 at 9:22 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Wed, 23 Dec 2009, Julian Fitzell wrote:
#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.
Meh... Interval shouldn't inherit #at:put: either, but it does. It's just life with the Collection hierarchy we have. In fact, on VW at least, #sort: is implemented in terms of #at:put: so trying to sort an Interval just triggers an Exception saying "you cannot store into an Interval".
But how platforms choose to implement it is really up to them - the goal is that any Collection that should be sortable in place responds to #sort and #sort: somehow, whether that's through inheritance, traits, or multiple implementations, I don't (personally) care.
Yes so SortedCollection should understand short: too.
#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
sorted is bad name
Yes, Intervals are a bit weird in this case - again, I'd lean towards #shouldNotImplement unless it fails naturally in some other way but I don't feel strongly about it. Our platforms tests will test for it on individual classes; again, how exactly the behaviour ends up on each of those classes is not that important to me.
Julian
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
#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.
Why? what would be the reason not to use sortBlock: for others? I like this consortium design that neglects basic polymorphism. May be in the future ANSI 1996 will look so old that we will be done with it.
#asSortedCollection is defined by ANSI on Collection and returns an instance of SortedCollection.
Yes it makes sense.
#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.
I think that collection hierarchy shows the little of single inheritance and this is normal. Of course Interval is Sequenceable but I imagine cannot be sorted in place. Still some leaves like OrderedCollection could be really polymorphic. Now we would have it on OrderedCollection too and the subclasses of Sequenceable which make sense.
#sorted, #sorted: -- VW already has this. VA is adding it.
What is sorted? a boolean predicate method? What a bad name. Did they forgot Kent? I remember this cool period where moose stopped to work because sort was changed. They introduced that in VW and broke all our code by changing the sort: semantics. Now I checked and here is what I read SequenceableCollection>>sorted: aBlock "Return a sorted copy of the receiver using aBlock as the sort criteria. e.g. #(1 4 -5 -2 3) sorted: [:a :b | a abs <= b abs] returns a sorted copy of the receiver as #(1 -2 3 4 -5)" SequenceableCollection>>sorted "Return a sorted copy of the receiver." SequenceableCollection>>sort "Sort the receiver in place." Which clearly does not work on subclasses, of course. (1 to: -100 by: 3 ) sorted: [:a :b | a abs <= b abs] Why they did not use sortBlock: and sort: ? So we have conceptually sortInPlace: -> does not copy sort: -> does not do a copy as in pharo/squeak and VW and both could use sortBlock: (accessor and instance creation for SortedCollection) sort "Sort the receiver in place."
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.
Please not this is bogus. It does not work with certain subclasses of Sequenceable And much more important it has a bad name. Because with a nice name sortCopy then it would be much better. So with one method in VW you can get it sortCopy ^ self sorted
#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.
Yes. I would discard it.
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.
Yes we could probably remove them.
So that's what VASt/Seaside/Grease are doing... I encourage you to follow our lead. :)
:) yes but you can also avoid to propagate bad names in the community and sorted is a bad one. Because collections are not functional style as point in smalltalk so I have no clue to know if I get a new object or not.
Julian
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Stéphane Ducasse wrote:
#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.
Why? what would be the reason not to use sortBlock: for others?
The intention is different. #sortBlock: tells a collection to maintain itself as sorted even after additions and deletions. This message is not appropriate for collections that do not have that ability. #sortBlock: is not the best name for this functionality, but I think it's bad to use #sortBlock: with a different meaning.
#sorted, #sorted: -- VW already has this. VA is adding it.
What is sorted? a boolean predicate method? What a bad name. Did they forgot Kent?
An example of my previous message -- this name is confusing and should probably not be used.
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.
Please not this is bogus. It does not work with certain subclasses of Sequenceable And much more important it has a bad name. Because with a nice name sortCopy then it would be much better. So with one method in VW you can get it
sortCopy ^ self sorted
+1 Regards, -Martin
#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.
Why? what would be the reason not to use sortBlock: for others?
The intention is different. #sortBlock: tells a collection to maintain itself as sorted even after additions and deletions. This message is not appropriate for collections that do not have that ability.
#sortBlock: is not the best name for this functionality, but I think it's bad to use #sortBlock: with a different meaning.
I agree :) Now SortedCollection should understand sort too which uses sortBlock: My main concern is polymorphism between collection which are nearly the same!
#sorted, #sorted: -- VW already has this. VA is adding it.
What is sorted? a boolean predicate method? What a bad name. Did they forgot Kent?
An example of my previous message -- this name is confusing and should probably not be used.
Yes I agree
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.
Please not this is bogus. It does not work with certain subclasses of Sequenceable And much more important it has a bad name. Because with a nice name sortCopy then it would be much better. So with one method in VW you can get it
sortCopy ^ self sorted
+1
2009/12/23 Julian Fitzell <jfitzell@gmail.com>:
On Wed, Dec 23, 2009 at 1:45 AM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2009/12/23 Stéphane Ducasse <stephane.ducasse@inria.fr>:
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
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 :)
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.
Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo.
#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.
And in the future, change semantic as a filter before sorting like proposed here...
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
#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.
Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo.
Fun I always hated it may be because the change broke our code. Stef
Nicolas Cellier wrote:
#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.
Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo.
I fear that #sorted is too close to #sort, but with very different semantics, and could cause confusion. I'd think twice before following VW's lead on this one. Is this a common enough case to be warrant its own selector, instead of "myCollection copy sort" which is much clearer in intent? If so, perhaps #copySorted would be clearer? Regards, -Martin
2009/12/23 Martin McClure <martin@hand2mouse.com>:
Nicolas Cellier wrote:
#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.
Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo.
I fear that #sorted is too close to #sort, but with very different semantics, and could cause confusion. I'd think twice before following VW's lead on this one. Is this a common enough case to be warrant its own selector, instead of "myCollection copy sort" which is much clearer in intent? If so, perhaps #copySorted would be clearer?
Regards,
-Martin
I'd like a selector that I can apply to any collection like a Set too. For example, in some implementations keys are a Set (original st80) in others keys are an Array (Squeak trunk/Pharo). So, in order to have more portable pieces of code I ended up with (self keys asArray sort). Maybe the most simple thing would be to define Collection>>sort ^self asArray sort
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2009/12/23 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/12/23 Martin McClure <martin@hand2mouse.com>:
Nicolas Cellier wrote:
#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.
Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo.
I fear that #sorted is too close to #sort, but with very different semantics, and could cause confusion. I'd think twice before following VW's lead on this one. Is this a common enough case to be warrant its own selector, instead of "myCollection copy sort" which is much clearer in intent? If so, perhaps #copySorted would be clearer?
Regards,
-Martin
I'd like a selector that I can apply to any collection like a Set too. For example, in some implementations keys are a Set (original st80) in others keys are an Array (Squeak trunk/Pharo). So, in order to have more portable pieces of code I ended up with (self keys asArray sort). Maybe the most simple thing would be to define Collection>>sort ^self asArray sort
Arg, I pressed tab, then (oops) space and sent the message too soon... I wanted to add this comment: "Sort the collection in place if possible, otherwise answer a sorted Array. Subclasses that can sort in place should override this message."
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Nicolas Cellier wrote:
I'd like a selector that I can apply to any collection like a Set too. For example, in some implementations keys are a Set (original st80) in others keys are an Array (Squeak trunk/Pharo). So, in order to have more portable pieces of code I ended up with (self keys asArray sort). Maybe the most simple thing would be to define Collection>>sort ^self asArray sort
Arg, I pressed tab, then (oops) space and sent the message too soon... I wanted to add this comment: "Sort the collection in place if possible, otherwise answer a sorted Array. Subclasses that can sort in place should override this message."
Interesting. Possibly good. But what would you do when you knew you wanted a *copy* that was sorted? "myCollection copy sort" would work, but might or might not create two copies, depending on whether the original class was one that could be sorted in place. I'm now leaning toward defining #copySorted or some such on Collection for this purpose. And *maybe* also doing what you propose with #sort. Regards, -Martin
Arg, I pressed tab, then (oops) space and sent the message too soon... I wanted to add this comment: "Sort the collection in place if possible, otherwise answer a sorted Array. Subclasses that can sort in place should override this message."
Interesting. Possibly good. But what would you do when you knew you wanted a *copy* that was sorted? "myCollection copy sort" would work, but might or might not create two copies, depending on whether the original class was one that could be sorted in place.
I'm now leaning toward defining #copySorted or some such on Collection for this purpose. And *maybe* also doing what you propose with #sort.
+ 1 This is good it means that the solution is not obvious :)
I'd like a selector that I can apply to any collection like a Set too. For example, in some implementations keys are a Set (original st80) in others keys are an Array (Squeak trunk/Pharo). So, in order to have more portable pieces of code I ended up with (self keys asArray sort). Maybe the most simple thing would be to define Collection>>sort ^self asArray sort
May be and to redefine it on OrderedCollection, ArrayedCollection and SortedCollection Now in VW sorted consistently do a copy and sort inplace is only define for sequenceable (which does not work for interval) this is what VW does with sorted Stef
participants (9)
-
Adrian Kuhn -
csrabak＠bol.com.br -
Julian Fitzell -
Levente Uzonyi -
Mariano Martinez Peck -
Martin McClure -
merlyn＠stonehenge.com -
Nicolas Cellier -
Stéphane Ducasse