December 2009 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Collections-ul.260.mcz

by StÃ©phane Ducasse

Thanks for the notice. I think that OrderedCollection should understand sort: :) Stef On Dec 23, 2009, at 6:06 PM, Levente Uzonyi wrote: > On Wed, 23 Dec 2009, StÃ©phane Ducasse wrote: > >> http://code.google.com/p/pharo/issues/detail?id=1660 >> and in the inbox. > > Note that this is just a fix in squeak, and it only works if OrderedCollection understands #sort:, which is not the case in pharo. > > > Levente > >> >> Stef >> >> >> >> On Dec 23, 2009, at 1:22 PM, StÃ©phane Ducasse wrote: >> >>> Hi Levente >>> >>> why don't you help us too? >>> >>> Stef >>> >>> >>>> From: commits(a)source.squeak.org >>>> Date: December 23, 2009 12:29:08 PM GMT+01:00 >>>> To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org >>>> Subject: [squeak-dev] The Trunk: Collections-ul.260.mcz >>>> Reply-To: squeak-dev(a)lists.squeakfoundation.org >>>> >>>> Levente Uzonyi uploaded a new version of Collections to project The Trunk: >>>> http://source.squeak.org/trunk/Collections-ul.260.mcz >>>> >>>> ==================== Summary ==================== >>>> >>>> Name: Collections-ul.260 >>>> Author: ul >>>> Time: 23 December 2009, 12:23:32 pm >>>> UUID: de4b02f8-b0aa-5e47-93f7-4a3e3c300060 >>>> Ancestors: Collections-ul.259 >>>> >>>> - make sure that SortedCollection's #sort and #sort: update the sortBlock >>>> >>>> =============== Diff against Collections-ul.259 =============== >>>> >>>> Item was added: >>>> + ----- Method: SortedCollection>>sort: (in category 'sorting') ----- >>>> + sort: aSortBlock >>>> + "Sort this collection using aSortBlock. The block should take two arguments >>>> + and return true if the first element should preceed the second one. >>>> + If aSortBlock is nil then <= is used for comparison." >>>> + >>>> + super sort: aSortBlock. >>>> + sortBlock := aSortBlock! >>>> >>>> >>> >>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

> #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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

>> > > 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

Dec. 23, 2009

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Collections-ul.260.mcz

by Levente Uzonyi

On Wed, 23 Dec 2009, StÃ©phane Ducasse wrote: > Hi Levente > > why don't you help us too? > I'm helping you, but not directly, I'm just a lurker here. One of my friends once said: the pharo guys are also squeak developers. I guess the opposite is also true. Levente > Stef > > >> From: commits(a)source.squeak.org >> Date: December 23, 2009 12:29:08 PM GMT+01:00 >> To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org >> Subject: [squeak-dev] The Trunk: Collections-ul.260.mcz >> Reply-To: squeak-dev(a)lists.squeakfoundation.org >> >> Levente Uzonyi uploaded a new version of Collections to project The Trunk: >> http://source.squeak.org/trunk/Collections-ul.260.mcz >> >> ==================== Summary ==================== >> >> Name: Collections-ul.260 >> Author: ul >> Time: 23 December 2009, 12:23:32 pm >> UUID: de4b02f8-b0aa-5e47-93f7-4a3e3c300060 >> Ancestors: Collections-ul.259 >> >> - make sure that SortedCollection's #sort and #sort: update the sortBlock >> >> =============== Diff against Collections-ul.259 =============== >> >> Item was added: >> + ----- Method: SortedCollection>>sort: (in category 'sorting') ----- >> + sort: aSortBlock >> + "Sort this collection using aSortBlock. The block should take two arguments >> + and return true if the first element should preceed the second one. >> + If aSortBlock is nil then <= is used for comparison." >> + >> + super sort: aSortBlock. >> + sortBlock := aSortBlock! >> >> > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

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

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

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(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

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(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009