sorting

Hi,

I'm trying to implement #<= for a certain class so that I can return its
members as a sorted collection. First of all this led me to something I
would call odd. When you evaluate the first, it will return a walkback, but
when you evaluate the second, it won't. Apparently in the second case the
last member never gets compared.

#('aString' nil 'anotherString') asSortedCollection
#('aString' 'anotherString' nil) asSortedCollection

Now my second issue. When trying to inplement #<= I can't find a way to make
my code less ugly, and I wonder if anybody else has a better suggestion. I'm
trying to sort based on a number of aspects; if both objects have the first
aspect set, then sort on them. If one of them does not have it set and the
other has, then the one without is returned. If neither has the first aspect
set then check the second aspect in the same way. This is what I came up
with:

#<= anotherObject
"firstly test on aspectA"
 ((self aspectA notNil) and: [anotherObject aspectA notNil]) ifTrue: [
  (self aspectA <= anotherObject aspectA) ifTrue: [^self].
  ^anotherObject].
 ((self aspectA notNil) and: [anotherObject aspectA isNil]) ifTrue: [
  ^anotherObject].
 ((self aspectA isNil) and: [anotherObject aspectA notNil]) ifTrue: [
  ^self].
"then test on aspectB"
 ((self aspectB notNil) and: [anotherObject aspectB notNil]) ifTrue: [
  (self aspectB <= anotherObject aspectB) ifTrue: [^self].
  ^anotherObject].
 ((self aspectB notNil) and: [anotherObject aspectB isNil]) ifTrue: [
  ^anotherObject].
 ((self aspectB isNil) and: [anotherObject aspectB notNil]) ifTrue: [
  ^self].
"and so on"

Apart from splitting it into multiple methods (#compareAspectA:
anotherObject), I can't see a way to make this look less procedural. Anybody
any suggestions?

Thanks,

Ted

Hi Ted,

I first came up with something like this;
(BTW <= returns a boolean, true if the receiver object should be returned)

Methods in SortableObject
aspects
   ^#(aspect1 aspect2 aspect3)

canAspect: aSymbol sort: aSortableObject
    ^(self perform: aSymbol) notNil
        or: [(aSortableObject perform: aSymbol) notNil]

findSortableAspectFor: aSortableObject
    ^self aspects detect: [ :each |
        self canAspect: each sort: aSortableObject ] ifNone: [self error]
"??"

isAspect: aSymbol lessThanFor: aSortableObject
     (self perform: aSymbol) isNil ifTrue: [^true].
     (aSortableObject perform: aSymbol) isNil ifTrue: [^false ].
     ^(self perform: aSymbol) <= (aSortableObject perform: aSymbol)

<= aSortableObject
    | aspect |
    aspect := self findSortableAspectFor: aSortableObject.
    ^self isAspect: aspect lessThanFor: aSortableObject
=======================================
I then refactored to;

Change SortableObject>>#<= to;

<= aSortableObject
   self aspects do: [ :each | | values |
        values := SortValues subject1: self subject2: aSortableObject
aspect: each .
        values canSort ifTrue: [^values isLessThan]].
       self error "??"

And Added;
Object subclass: #SortValues
instanceVariableNames: 'aspect value1 value2'

setForSubject1: aSortableObject1 subject2: aSortableObject2 aspect: aSymbol
     aspect := aSymbol.
     value1 := aSortableObject1 perform: aspect.
     value2 := aSortableObject2 perform: aspect.

isLessThan
      value1 isNil | value2 isNil ifTrue: [^value1 isNil].
      ^value1 <= value2

canSort
    ^value1 notNil or: [ value2 notNil]

===================================================
Tests;

sortableObjectClass
    ^SortableObject

testFirstAspectsBothSet
    | o1 o2 o3 |
     o1 := self sortableObjectClass with: 1 with: nil with: nil.
    o2 := self sortableObjectClass with: 2 with: nil with: nil.
     o3 := self sortableObjectClass with: 2 with: nil with: nil.
    self assert: o1 <= o2.
    self assert: o2 <= o3.
    self assert: (o2 <= o1) not

testFirstAspectsNotSet
    | o1 o2 o3 |
     o1 := self sortableObjectClass with: nil with: 1 with: nil.
     o2 := self sortableObjectClass with: nil with: 2 with: nil.
    o3 := self sortableObjectClass with: nil with: 2 with: nil.
    self assert: o1 <= o2.
    self assert: o2 <= o3.
    self assert: (o2 <= o1) not

testFirstAspectsOneSet
    | o1 o2 o3 |
    o1 := self sortableObjectClass with: 1 with: nil with: nil.
    o2 := self sortableObjectClass with: nil with: nil with: nil.
    self assert: (o1 <= o2) not.
     self assert: o2 <= o1.

testSecondAspectsOneSet
     | o1 o2 o3 |
    o1 := self sortableObjectClass with: nil with: 1 with: nil.
    o2 := self sortableObjectClass with: nil with: nil with: nil.
    self assert: (o1 <= o2) not.
    self assert: o2 <= o1.

Trying to figure out how SortedCollection sorts has made my head hurt in the
past, so I will leave that to others. I am fairly sure that you can find the
"Numerical Recipes" books online, and that Bill Schwab has a link to them on
his pages. Strings use an external library for comparisions, so I would
guess that Dolphin is automatically converting nil to something more
friendly when it is only an argument for a comparison.

What do you think of the two approaches? I think I got your requirements
correct, but didnt know what to do with the boundary condition. Instead of
returning the lessThan object, I returned a boolean, but I think that would
allow you to use the default sort block.

Steve


"Ted Bracht" <[hidden email]> wrote in message
news:8vhpv0$4pqot$[hidden email]...
> Hi,
>
> I'm trying to implement #<= for a certain class so that I can return its
> members as a sorted collection. First of all this led me to something I
> would call odd. When you evaluate the first, it will return a walkback,
but
> when you evaluate the second, it won't. Apparently in the second case the
> last member never gets compared.
>
> #('aString' nil 'anotherString') asSortedCollection
> #('aString' 'anotherString' nil) asSortedCollection
>
> Now my second issue. When trying to inplement #<= I can't find a way to
make
> my code less ugly, and I wonder if anybody else has a better suggestion.
I'm
> trying to sort based on a number of aspects; if both objects have the
first
> aspect set, then sort on them. If one of them does not have it set and the
> other has, then the one without is returned. If neither has the first
aspect Anybody
> any suggestions?
>
> Thanks,
>
> Ted
>
>

Here is a shorter version that repeats on every aspect message.

#<= anotherObject
| oLeft  oRight|
 #(#aspectA #aspectB #aspectC) do: [ :aspect |  
  oLeft := self perform: aspect.
  oRight := anotherObect perform: aspect.

 (oLeft notNil) and: [oRight notNil]) ifTrue: [
  (oLeft <= oRight) ifTrue: [^self].
  ^anotherObject].

 ((oLeft notNil) and: [oRight  isNil]) ifTrue: [  ^anotherObject].

 ((oLeft isNil) and: [oRight notNil]) ifTrue: [  ^self].

]

Costas

"Ted Bracht" <[hidden email]> wrote:

"Ted Bracht" <[hidden email]> wrote:


Here is the result in Squeak

#('aString' nil 'anotherString') asSortedCollection.
  -->a SortedCollection('aString' 'anotherString' #nil)

#('aString' 'anotherString' nil) asSortedCollection.
  -->  a SortedCollection('aString' 'anotherString' #nil)

#('aString' 'yetanotherString' nil) asSortedCollection.
  -->  a SortedCollection('aString' #nil 'yetanotherString')

But it does not give a walkback.

Costas

Ted,

> I'm trying to implement #<= for a certain class so that I can return its
> members as a sorted collection. First of all this led me to something I
> would call odd. When you evaluate the first, it will return a walkback,
but
> when you evaluate the second, it won't. Apparently in the second case the
> last member never gets compared.
>
> #('aString' nil 'anotherString') asSortedCollection
> #('aString' 'anotherString' nil) asSortedCollection

This is not all that surprising. The first brings up a walkback because the
sort algorithm trys to execute:

nil <= aString.

Since <= is not defined for UndefinedObject this quite rightly brings up a
walkback. In the second case, you'll find that all members are still being
compared, it's just that this time the algorithm chooses to evaluate:

aString <= nil

This eventually percolates down to String>>_collate: which answers -2 to
such a comparison (rather than signalling an error). One might expect this
to throw an exception but it is not required by the ANSI standard to do so.
If you look at the standard you find that <= is not part of the general
protocol for Object. Instead it is part of <magnitude> and is refined in
<readableString>. In both cases the comment for <= states that "The result
is undefined if the receiver and operand are not comparable".

So the point is that it does not make sense to put different "types" of
object in a SortedCollection if you are relying on the default sort block
that makes use of <=. In general, it is often "poor form" to fall back on
the default sortblock anyway. Overriding <= for a class to give it a sorting
capability seems sensible but often it is not. Instances of your class may
require different collating sequences in different circumstances so applying
a broadbrush meaning to <= can be inappropriate. Usually, it is better not
to rely on <= sorting but to provide specific sort blocks for your
SortedCollections.

Best regards,

Andy Bower
Dolphin Support
http://www.object-arts.com

---
Visit the Dolphin Smalltalk Wiki Web
http://www.object-arts.com/wiki/html/Dolphin/FrontPage.htm
---

Costas

"Costas Menico" <[hidden email]> wrote in message
news:[hidden email]...
I would imagine that is because it treats #nil in an literal array as a
symbol whose sequence of characters is 'nil', whereas Dolphin parses it as
the nil object.

Try this instead, which I predict will give a walkback in Squeak too:

    (Array with: 'aString' with: nil with: 'anotherString')
asSortedCollection

Regards

Blair

Hi Costas and Andy,

> > I'm trying to implement #<= for a certain class so that I can return its
> > members as a sorted collection. First of all this led me to something I
> > would call odd. When you evaluate the first, it will return a walkback,
> but
> > when you evaluate the second, it won't. Apparently in the second case
the
> > last member never gets compared.
> >
> > #('aString' nil 'anotherString') asSortedCollection
> > #('aString' 'anotherString' nil) asSortedCollection
>
> This is not all that surprising. The first brings up a walkback because
the so.
> If you look at the standard you find that <= is not part of the general
> protocol for Object. Instead it is part of <magnitude> and is refined in
> <readableString>. In both cases the comment for <= states that "The result
> is undefined if the receiver and operand are not comparable".
>
> So the point is that it does not make sense to put different "types" of
> object in a SortedCollection if you are relying on the default sort block
> that makes use of <=. In general, it is often "poor form" to fall back on
> the default sortblock anyway. Overriding <= for a class to give it a
sorting
> capability seems sensible but often it is not. Instances of your class may
> require different collating sequences in different circumstances so
applying
> a broadbrush meaning to <= can be inappropriate. Usually, it is better not
> to rely on <= sorting but to provide specific sort blocks for your
> SortedCollections.
>

(also looking at the Squeak result Costas showed) so basically the
conclusion is that the standard sorting becomes unreliable when certain
aspects to be sorted can return nil. I can agree with the walkback in my
first example, I would have expected a walkback in the second example as
well. In the Squeak result it looks like Squeak tries to interpret nil as a
string......

Thanks,

Ted

Steve and Costas,


>
> I first came up with something like this;
> (BTW <= returns a boolean, true if the receiver object should be returned)

yeah, you're right, I noticed that after I sent the mail.

>
>

Thanks alot for your suggestions. Looks loads better than my initial
procedural attempt.

Based on your suggestions I've come up with the following solution:

compareWith: anotherObject forAspects: arrayOfAspects
 | mine his |
 mine := self perform: (arrayOfAspects at: 1).
 his := anotherObject perform: (arrayOfAspects at: 1).
 (mine isNil and: [his isNil]) ifTrue: [
  (arrayOfAspects size > 1) ifFalse: [^false].
  ^(self compareWith: anotherObject forAspects:
   (arrayOfAspects copyFrom: 2 to: arrayOfAspects size))].
 mine isNil ifTrue: [^false].
 his isNil ifTrue: [^true].
 ^(mine <= his)

This solves the problem when both objects answer nil to the aspect. It then
compares the two by the next aspect in the array, until it runs out of
aspects. This will answer the ones with nil at the end; #(1 2 3 nil)

Thanks again for your suggestions.

Ted

[hidden email] (Ted Bracht) wrote (abridged):
> Now my second issue. When trying to inplement #<= I can't find a way
> to make my code less ugly, and I wonder if anybody else has a better
> suggestion. I'm trying to sort based on a number of aspects; if
> both objects have the first aspect set, then sort on them. If one
> of them does not have it set and the other has, then the one without
> is returned. If neither has the first aspect set then check the
> second aspect in the same way.

Are you sure? #<= traditionally answers a Boolean, not one of the
objects. It sounds like you are implementing a #min: function instead.

Returning true/false will help a bit as you can replace code like:

    condition ifTrue: [^self].
    ^anotherObject

with:

   ^condition

It also helps if you first determine which aspect is non-nil for one of
the objects, so that then you know you are certain to return. Thus:

  ((self aspectA notNil) and: [anotherObject aspectA notNil]) ifTrue: [
   (self aspectA <= anotherObject aspectA) ifTrue: [^self].
  ((self aspectA notNil) and: [anotherObject aspectA isNil]) ifTrue: [
   ^anotherObject].
  ((self aspectA isNil) and: [anotherObject aspectA notNil]) ifTrue: [
   ^self].

becomes:

   ((self aspectA notNil) or: [anotherObject aspectA notNil]) ifTrue: [
       ^(anotherObject aspectA isNil
           or: [self aspectA <= anotherObject aspectA]]

This simple rewriting enormously simplifies the code. The next step is
tricky. I would very much like to put the code that compares a single
aspect into its own routine, but it really needs to return 3 results:
true, false and incomparable. It is probably clearest to express this
fairly directly, using nil for incomparable, and the #ifNotNil: idiom:

    min: anotherObject
        ^self <= anotherObject
            ifTrue: [self]
            ifFalse: [anotherObject]

    <= anotherObject
        (self compareAspect: self aspectA with: anotherObject aspectA)
            ifNotNil: [:result|^result].
        (self compareAspect: self aspectB with: anotherObject aspectB)
            ifNotNil: [:result|^result].
        (self compareAspect: self aspectC with: anotherObject aspectC)
            ifNotNil: [:result|^result].
        ^false

   compareAspect: selfAspect with: anotherAspect
       (selfAspect isNil and: [anotherAspect isNil])
           ifTrue: [^nil].
       ^anotherAspect isNil or: [selfAspect <= anotherAspect]

We can use #perform: and a loop if we want:

    min: anotherObject
        ^self <= anotherObject
            ifTrue: [self]
            ifFalse: [anotherObject]

    <= anotherObject
        #(aspectA aspectB aspectC) do: [:each|
            (self compareObject: anotherObject aspect: each)
                ifNotNil: [:result|^result]].
        ^false

    compareObject: anotherObject aspect: aSelector
        ^self
            compareAspect: (self perform: aSelector)
            with: (anotherObject perform: aSelector)

   compareAspect: selfAspect with: anotherAspect
       (selfAspect isNil and: [anotherAspect isNil])
           ifTrue: [^nil].
       ^anotherAspect isNil or: [selfAspect <= anotherAspect]

I suppose this is better, although in some ways it feels more complex
because selectors are not such a direct representation of the aspects. It
introduces a kind of packing/unpacking step which is not part of the
original problem. It's probably slower, too.

#ifNil and #ifNotNil: are not standard Dolphin but they are worth
knowing. Possible definitions are:

    Object>>ifNil: aBlock
        ^self
    Object>>ifNotNil: aBlock
        ^aBlock value: self

    UndefinedObject>>ifNil
        ^aBlock value
    UndefinedObject>>ifNotNil: aBlock
        ^nil

I believe there is some dispute over the exact definitions, especially
whether the blocks should take arguments. #ifNil: is commonly used to
implement cacheing, eg:
    value
        ^value := value ifNil: [self defaultValue]

#ifNotNil: is not needed so often but seems to fit here.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

Hi Dave,

>
> Are you sure? #<= traditionally answers a Boolean, not one of the
> objects. It sounds like you are implementing a #min: function instead.

yeah, you're right. It should return a boolean.

>


>
> This simple rewriting enormously simplifies the code. The next step is
> tricky. I would very much like to put the code that compares a single
> aspect into its own routine, but it really needs to return 3 results:
> true, false and incomparable.

I came to that same conclusion. Disadvantage of that is that you can't use
the different aspect comparison routines directly in a sort block. You
always have to wrap them in something else that returns a boolean if the
aspect comparison routine returns nil.

I've seen definitions of #ifNil: and #ifNotNil: before, and it surprises me
that they're not part of the base image.

Thanks for your suggestions as well.

>   Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
>       [hidden email]      |   And close your eyes with holy dread,
>                               |  For he on honey dew hath fed
>  http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

Ted