SortedCollection enhancement

204 views
Skip to first unread message

Louis LaBrunda

unread,
Oct 20, 2011, 3:20:02 PM10/20/11
to va-sma...@googlegroups.com
Hi Everyone,

I am working on an enhancement to SortedCollection (a sub-class).  The idea is to supply a collection of method names (symbols) that are used to fetch the value to be compared from the objects being sorted.  This is for complex objects that one wants to sort by many values continuing from one to the next if the first values are equal.

I added two instance variables (methodNames and directionFlags) and their setters and getters.  The methodNames variable is the collection of method names and   directionFlags is a matching collection of booleans that indicate the direction of sorting for each method named (true for ascending and false for descending).  A nil instances of   directionFlags defaults to all ascending.

The comparing is done in #methodNamesCompare:and: (see below).  When methodNames is set, sortBlock is set to:

self sortBlock: [:a :b | self methodNamesCompare: a and: b].

so #methodNamesCompare:and: is called when sortBlock is used for sorting.

When I finish testing I will post a fileout.  In the mean time, if there is any interest in this enhancement, maybe we can get Instantiations to pick it up.  There is no reason for it to be a sub-class if the instance variables and code are added to SortedCollection.  If methodNames is not set, the additional code is not used and does not interfere.

Lou

methodNamesCompare: itemA and: itemB
"Compare the two items based upon the method names in methodNames."
"This method is called from a special sortBlock defined when methodNames is set."
"Errors accessing values by the method names (symbol) are trapped and an attempt is made
  to get a value via #at:. This is to accommodate sorting database rows. Subsequent errors are not trapped."

directionFlags isNil ifTrue: [
directionFlags := Array new: methodNames size.
1 to: methodNames size do: [:i | directionFlags at: i put: true].
].

methodNames with: directionFlags do: [:symbol :direction | | valueA valueB |
valueA := [itemA perform: symbol] when: ExError do: [:signal | signal exitWith: (itemA at: symbol)].
valueB := [itemB perform: symbol] when: ExError do: [:signal | signal exitWith: (itemB at: symbol)].
(valueA < valueB) ifTrue: [^direction].
(valueA > valueB) ifTrue: [^direction not].
].
^true.

Steven LaFavor

unread,
Oct 20, 2011, 5:12:28 PM10/20/11
to va-sma...@googlegroups.com

A long, long time back I found a piece of code that was from a smalltalk article (maybe?).  It introduced a class whose instances would be used as the argument to either asSortedCollection: aBlock or sortBlock: aBlock.
In my current image, the class is called DynamicSortblock, and the methods date back to 2001 (and I think the article was even before that)....

Let me put this out there to see if anyone wants to use it or claim it.  Here's a fileout of the code....

- - - - - - - - - -

Object subclass: #DynamicSortblock

    instanceVariableNames: 'accessors directions '
    classVariableNames: ''
    poolDictionaries: ''!

!DynamicSortblock class publicMethods !

new

        ^super new initialize! !

!DynamicSortblock publicMethods !

addAscendingSelector: aSymbol

        accessors add: aSymbol.
        directions add: true!

addDescendingSelector: aSymbol

        accessors add: aSymbol.
        directions add: false!

COMMENT
        "Instances can be used in place of a sortblock in a Sorted Collection for more flexibility"
!

initialize

        accessors := OrderedCollection new.
        directions := OrderedCollection new!

value: v1 value: v2
        "imitate a sort block by answering the message value:value:"

        ^self
                value: v1
                value: v2
                level: 1!

value: v1 value: v2 level: anInteger
        "use an accessor to compare v1 & v2"

        | accessor ascending c1 c2 |

        accessors size < anInteger
                ifTrue: [         "no more accessors; return true (don't change order)" ^true].
        accessor := accessors at: anInteger.
        ascending := directions at: anInteger.
        ^(c1 := v1 perform: accessor) = (c2 := v2 perform: accessor)
                ifFalse: [
                        ascending
                                ifTrue: [c1 < c2]
                                ifFalse: [c1 > c2]]
                ifTrue: [
                        self
                                value: v1
                                value: v2
                                level: anInteger + 1]! !

DynamicSortblock initializeAfterLoad!

- - - - - - - - - -

You can create instances of it and pass them to SortedCollections like this:

| sb |
sb := DynamicSortblock new
addAscendingSelector: #policyNumber;
addDescendingSelector: #creationTimestamp;
yourself

someListOfPolicies asSortedCollection: sb

which would answer the policies in order by policyNumber with the most recent one first.

(all the normal assumptions apply about code...yada yada yada...YMMV)

Should be enough to get this rolling.....

*Steven*

Louis LaBrunda

unread,
Oct 21, 2011, 10:12:16 AM10/21/11
to va-sma...@googlegroups.com
Hi Steven,

DynamicSortblock looks like an interesting approach.  I like that SortedCollection doesn't have to be sub-classed.  I didn't show it but there are a lot of methods that copy the sorted collection and need to be overridden to copy the method names and directionFlags (accessors directions), with a separate class as the sortBlock, that code isn't needed.  I think I will switch to this approach and blend my code into it.

Lou

Steven LaFavor

unread,
Oct 21, 2011, 12:51:14 PM10/21/11
to va-sma...@googlegroups.com
Every time that I used to fool around with the Collection classes, I ran into the same issues :-P

Glad that this helped!

*Steven*

Louis LaBrunda

unread,
Oct 21, 2011, 3:55:14 PM10/21/11
to va-sma...@googlegroups.com
Hi Steven,

Thank you very much for putting me onto DynamicSortblock.  I have created my own version and called it DynamicSortBlock.  I wanted the name to be different (even so slightly) and to match the case of the #sortBlock method.

Attached is a fileout.  And below is the class comment that didn't seem to get filed out with it.  My version works with database rows and other records that answer to #at:.  It also handles nil values well.

Lou

Instances are used as the sortBlock of a SortedCollection to simplify sorting complex classes.
They can also be sent to the #sort: method of other collections like arrays and ordered collections.
It is not in the block family of classes but acts like one by answering the #value:value: message
with a boolean like a sort block would.

It is used by supplying collections of accessors and corresponding directions.
Errors accessing values by the accessors are trapped and an attempt is made to get a value via #at:.
This is to accommodate sorting database rows and other records that respond to #at:.

To sort objects with three ascending accessors:

SortedCollection sortBlock: (DynamicSortBlock accessors: #(#a1 #a2 #a3).

To sort objects with four accessors (ascending descending ascending descending):

SortedCollection sortBlock: (DynamicSortBlock accessors: #(#a1 #a2 #a3 #a4) directions: #(true false true false).


DynamicSortBlock.st

jtu...@objektfabrik.de

unread,
Oct 22, 2011, 5:20:41 AM10/22/11
to va-sma...@googlegroups.com
Lou,

this kind of sorting is needed in so many situations, and it is good you posted your code and discussed your idea, even (or even more so because) someone came up with a better way of solving it. Thanks for sharing your code (also to Steven).



One additional idea for the api:


SortedCollection sortBlock: (DynamicSortBlock accessors: #(#a1 #a2 #a3 #a4) directions: #(true false true false).


I somehow think that the following might work better: 

SortedCollection sortBlock: (DynamicSortBlock accessors: (OrderedCollection with: #a1->true with: #a2->false)).

or even better sequences like 
DynamicSortBlock new
  ascending: #a1; "or maybe asc: for faster typing"
  descending: a2; "or desc:"
  yourself.

to configure a DynamicSortBlock?

which add these associations.

Why do I think so? Because being myself I would end up with two different-sized collections due to my fingers typing out of sync with my brain ;-)

And of course I hope to see the code on VASTGoodies soon ;-)

BTW: Have you seen this: http://www.smalltalk.org/components/SortCriteria.html ?  I like the name SortCriteria, but dislike that SortedCollection would still have a setter named sortBlock: ;-)

Joachim

Douglas Swartz

unread,
Oct 22, 2011, 5:49:24 PM10/22/11
to va-sma...@googlegroups.com
Apparently this is a Smalltalk idiom many of us have
independently created to simplify the specification of complex sort
criteria. I built a SortBlock class a few years ago also.
I don't have the code handy, but I believe it was instantiated in
the manner:

SortBlock with: #getter1 -> 'Ascending'
with: #getter2 -> 'Dscending'
with: aTwoArgumentBlock.


The extension beyond the examples given to-date is the block argument
type. This argument type is essentially the same as a standard
sortBlock. This makes it easy to to include a comparison other than
simple getter comparisons in the sort.

Doug Swartz

Saturday, October 22, 2011, 4:20:41 AM, you wrote:

> Lou,

> this kind of sorting is needed in so many situations, and it is
> good you posted your code and discussed your idea, even (or even
> more so because) someone came up with a better way of solving it.
> Thanks for sharing your code (also to Steven).

> One additional idea for the api:


> SortedCollection sortBlock: (DynamicSortBlock accessors: #(#a1 #a2
> #a3 #a4) directions: #(true false true false).


> I somehow think that the following might work better:

> SortedCollection sortBlock: (DynamicSortBlock accessors:
> (OrderedCollection with: #a1->true with: #a2->false)).

> or even better sequences like
> DynamicSortBlock new
> ascending: #a1; "or maybe asc: for faster typing"
> descending: a2; "or desc:"
> yourself.

> to configure a DynamicSortBlock?

> which add these associations.

> Why do I think so? Because being myself I would end up with two
> different-sized collections due to my fingers typing out of sync with my brain

> And of course I hope to see the code on VASTGoodies soon

> BTW: Have you seen this:


> http://www.smalltalk.org/components/SortCriteria.html ? I like the
> name SortCriteria, but dislike that SortedCollection would still have a setter named sortBlock:

> Joachim

--
Best regards,
Douglas mailto:swartzco...@gmail.com

Marten Feldtmann

unread,
Oct 23, 2011, 4:33:11 AM10/23/11
to va-sma...@googlegroups.com
At least when working with Unicode you should consider adding a locale information, when sorting Strings. I added a subclass of SortedCollection in my ICU wrapper.

Perhaps a customable SortedCollection would be in general pretty nice in VA.



jtu...@objektfabrik.de

unread,
Oct 24, 2011, 12:09:26 AM10/24/11
to va-sma...@googlegroups.com
Marten,

is there any additional gain in subclassing SortedCollecion over using a Unicode-specialized DynamicSortBlock? Being a layperson in Unicode, I would expect that the meat of sorting lies in the comparisons, which would completely be handled by the DynamicSortBlock, right? The only drawback is that a developer would have to remember to use a Unicode aware comparison Block instead of simply a Block as we're used to... right?

But bringing up the Unicode problem is a good thing, because we should be prepared for the changes to come when VAST will support Unicode (which is announced for "any time soon").

Maybe we've now collected some good input for Instantiations for their work on Unicode...

Joachim  

Louis LaBrunda

unread,
Oct 24, 2011, 10:44:09 AM10/24/11
to va-sma...@googlegroups.com
Hey Joachim,

I kind of like the idea of using Associations.  Maybe I can come up with a way of using both.  Turn the associations into the two collections I have now or vice versa.  What do you think?  Is the #with:do: faster than running one collection of associations?

I will think about it.

Lou

P.S.  I hadn't seen the link.

jtu...@objektfabrik.de

unread,
Oct 24, 2011, 2:15:21 PM10/24/11
to va-sma...@googlegroups.com
Hi Lou,

I can't answer your question about performance, but my concern would mostly be valid data. It needs to be ensured that there is an asc/desc indicaor for each getter, because all attempts to find a default will be wrong in most situations.

(If I have 4 getters and 3 asc/desc indicators, which one will be asc by default???).

I must admit do:with: was new to me ;-) But if you play with these options, maybe you can let us know what you find out...

Joachim

Louis LaBrunda

unread,
Oct 25, 2011, 10:22:57 AM10/25/11
to va-sma...@googlegroups.com
Hi Joachim,

I decided to meet your needs by keeping what I had and adding a method (and a few others for completeness).  I added #sortCriteria: as a class (to answer a new DynamicSortBlock) and instance method (to set the accessors and directions).  It takes an ordered collection of associations where the key is an accessor and the value is a boolean direction.  These values are used to set the instance variables (accessors and directions).

This method allows you to do this:

 SortedCollection sortBlock: (DynamicSortBlock sortCriteria: (OrderedCollection with: #a1->true with: #a2->false)).

which is similar to your suggestion:

> SortedCollection sortBlock: (DynamicSortBlock accessors:
> (OrderedCollection with: #a1->true with: #a2->false)).

So everyone can see what we are talking about, I have included the #value:value: method below.  I don't think there would be much of a performance difference between running a collection of associations or the two collections I use with the #with:do:.  Someone can still get into trouble by setting the accessors and directions separately but #with:do: will go boom and point out the discrepancy on the first test.  I think being able to just supply the accessors and have the have the directions all default to ascending is worth the risk.

I have attached a fresh fileout and will see about adding it to VASTGoodies soon.

Lou

value: itemA value: itemB
"Compare the two items based upon the accessors and directions."

"Errors accessing values by the accessors are trapped and an attempt is made to get a value via #at:."
"This is to accommodate sorting database rows and other records that respond to #at:."
"Subsequent errors are not trapped."
"Note: nil values are treated as less than their corresponding value."

self directions isEmpty ifTrue: [self accessors size timesRepeat: [directions add: true]].

self accessors with: self directions do: [:accessor :direction | | valueA valueB |
valueA := [itemA perform: accessor] when: ExError do: [:signal | signal exitWith: (itemA at: accessor)].
valueB := [itemB perform: accessor] when: ExError do: [:signal | signal exitWith: (itemB at: accessor)].
(valueA = valueB) ifFalse: [
valueA isNil ifTrue: [^direction].
valueB isNil ifTrue: [^direction not].

(valueA < valueB) ifTrue: [^direction].
(valueA > valueB) ifTrue: [^direction not].
].
].
^true.
DynamicSortBlock.st

Louis LaBrunda

unread,
Oct 25, 2011, 2:19:15 PM10/25/11
to va-sma...@googlegroups.com
Hi All,

Sorry for replying to my own post but I had a typo in the previous fileout so this attachment fixes it.

Also, I want to point out to Joachim, that there are methods like #addAscendingAccessor: and #addDescendingAccessor: that add the accessor and its corresponding direction at once.  Perhaps I should add shorted named versions of the same methods like #addAscAccr: and #addDescAccr: or #addAsc: and #addDesc: or whatever?  Any ideas?

Lou
DynamicSortBlock.st

jtu...@objektfabrik.de

unread,
Oct 25, 2011, 2:24:05 PM10/25/11
to va-sma...@googlegroups.com
Hi Louis,

re: defaulting: you could of course add functionality to each setter of a selector name that adds a default of ascending for it if the user doesn't provide it. It's only impossible to do it when multiple selectors are added at once.

So an addCriteria: aSelector which calls addCriteria: ascending: aBoolean with a default of true is also helpful. (or addAccessor: and addAccessor:ascending: if you want).

Still I think this is a helpful extension. Think of sorting containers (which I still dream of after so many years) and such...

Best of Luck


Joachim


jtu...@objektfabrik.de

unread,
Oct 25, 2011, 2:38:01 PM10/25/11
to va-sma...@googlegroups.com
Okay, so you thought of the very same thing ;-)

Well, I don't like APIs stuffed with lots of synonyms for the very same functionality, so you shouldn't add too many methods with the same semantics. I usually try to find the right names by writing them on my white board and think about what exactly I want an object to do for me. 

If I had to choose (and being a non-native english speaker), I'd go with:

addCriterion(Named): aSymbol
addCriterion(Named): aSymbol ascending: aBoolean
addDescendingCriterion(Named): aSymbol

or, if these names are too long:

add:
add:asc:
addDesc:

Not sure I'd put them on the class side, because adding two criteria by using the class method would look somewhat strange:

(DynamicSortBlock add: #firstname) addDesc: #dayOfBirth. 

But all of that is very esoteric and doesn't help the functionality at all ;-)

Joachi

Louis LaBrunda

unread,
Oct 26, 2011, 9:57:17 AM10/26/11
to va-sma...@googlegroups.com
Hi Joachim,

Thanks for all your comments.  I am strongly leaning toward adding the following and dropping the longer named methods.

#add:
#addAsc:
#addDesc:

Where the parameter of #add: is an association.  I might allow a symbol and default the direction to ascending.  I'm open to suggestions on that.

The parameters for #addAsc: and #addDesc: would be symbols.

Lou

jtu...@objektfabrik.de

unread,
Oct 27, 2011, 4:32:19 PM10/27/11
to va-sma...@googlegroups.com
Hi Lou,

while your API suggeestions are just fine, an addAsc: wouldn't really be needed, because add: would just default to ascending sort if it's not an Association (Did I mention I usually dislike Associations for API's that are used with some business logic?.... oh, it was me who came up with the idea... hmmm.... ;-) )

On the other hand, a missing addAsc: would somehow break the concept of meeting expectations. So maybe I'd even have all of these:

add: (with an assoc or a Symbol that is treated as if it came with a ->true)
addAsc:
addDesc: 
(both of which call add:asc: to make things clear)

But this is getting really esoteric now ;-)

Joachim

Louis LaBrunda

unread,
Nov 1, 2011, 10:53:07 AM11/1/11
to va-sma...@googlegroups.com
Hi Joachim,

Thanks for your comments.  I decided to go with the methods as described in my last post:

#add:
#addAsc:
#addDesc:

Where the parameter of #add: is an association. I might allow a symbol and default the direction to ascending. I'm open to suggestions on that.

The parameters for #addAsc: and #addDesc: would be symbols.

I have attached the latest fileout.  I hope all these attachments are not a problem for the forum.

For those wondering why I chose to use a boolean the represent the direction instead if a symbol like #Asc or atom like ##Asc, which would be clearer, looking at the the code in #value:value: should tell the story.

Ordinarily one would test the direction and then test for < or > based upon the direction.  Using booleans for the direction eliminates that test and allows the direction value to be the return value of   #value:value:.  This makes for less code and then arguably simpler code.  The test for = and nil protect the code from blowing up with nil values and treats them as less than.

Lou
DynamicSortBlock.st

Joachim Tuchel

unread,
Sep 17, 2014, 3:06:58 AM9/17/14
to va-sma...@googlegroups.com
Hi Lou,

I had this thread somewhere in the back of my head and am happy I found it.
I will soon need to add some complex sorting to tables and would like to give your code a try.

So: is the file out still current? (If it was my code, there would be around 78 fixes of stupid typos and such over three years)
Would you consider putting it onto vast goodies?


Thanks,

Joachim

Joachim Tuchel

unread,
Sep 17, 2014, 3:09:10 AM9/17/14
to va-sma...@googlegroups.com
I again,

I forgot to ask the most important question ;-)
Does your implementation support switching between ascending/descending for one or more criteria once a collection has been sorted? I guess this is just a matter of changing a boolean and resorting the collection, right?

Joachim

Louis LaBrunda

unread,
Sep 17, 2014, 2:34:58 PM9/17/14
to va-sma...@googlegroups.com
Hi Joachim,

I have attached a fresh copy of the file out of the DynamicSortBlock class, just in case although I don't think there have been many if any changes.  I should put it in VAST Goodies but right now it is in an app with lots of other little classes so I will need to pull it out into its own app.

DynamicSortBlock acts like a two argument block of code and is used any place a sort block can be used.  It does its work in the #value:value: method (see its comment).  The rest of the methods just make it ease to setup.  It contains two matching ordered collections: #accessors and #directions.  The #accessors collection contains symbols that represent methods of the objects being sorted that should answer the value of interest.  The #directions collection contains booleans (true or false) that represent the direction of sorting for its corresponding accessor (true means ascending, false means descending).  This allows some parts of the sort to be ascending while others are descending.  For example if you are sorting products by descending price and ascending name.

Now to answer your question:

Does your implementation support switching between ascending/descending for one or more criteria once a collection has been sorted? I guess this is just a matter of changing a boolean and resorting the collection, right?

Yes.  DynamicSortBlock is a pretty light weight class, so you could just have two or more defined however you like but the #accessors and #directions collections are exposed and you can do what you like to then.  So, if you wanted to change one or more directions you could or replace the whole collection of directions.  But I think having two instances of DynamicSortBlock would be best.

I hope you find it useful, I have.  Just ask if you have any questions.

Lou
DynamicSortBlock.st

Joachim Tuchel

unread,
Sep 22, 2014, 3:36:52 AM9/22/14
to va-sma...@googlegroups.com
Thanks Lou,

I'll start using it very soon now. I'll let you know if I see any problems or enhancements. 
About VASTGoodies: Not sure I understand your problem. You can move the class to another application and stuff it into a config map. That should be pretty much it, no?


Joachim

Louis LaBrunda

unread,
Sep 22, 2014, 9:26:31 AM9/22/14
to va-sma...@googlegroups.com


On Monday, September 22, 2014 3:36:52 AM UTC-4, Joachim Tuchel wrote:
Thanks Lou,

I'll start using it very soon now. I'll let you know if I see any problems or enhancements. 

Great!
 
About VASTGoodies: Not sure I understand your problem. You can move the class to another application and stuff it into a config map. That should be pretty much it, no?


Not really a problem.  Just need to decide where to put it (some existing app, a new app, whatever) and do it.
Reply all
Reply to author
Forward
0 new messages