Smalltalk › Pharo › Pharo Smalltalk Users

SortedCollection>>reverse answers an inconsistent object in Pharo 6

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

12 messages Options

Richard O'Keefe

SortedCollection>>reverse answers an inconsistent object in Pharo 6

Test case:

   #(1 2 4) asSortedCollection reverse add: 3; yourself

<print it>

The answer *should* be aSortedCollection(4 3 2 1)

but *is* aSortedCollection(4 2 1 3).

This works in Squeak.

The problem is that SortedCollection does not define

#reverse[d] but simply inherits it(them), and the

inherited code pays no attention to the sortBlock.

I propose adding the following two methods to

SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo

defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other

method.  It also has a definition in SequenceableCollection, which is not but is

equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

I know perfectly well what the problem is.

I explained it in my message: the inherited #reversed

method doesn't know the sortBlock exists.

(So whether it is nil or not is not relevant.)

I also know several ways to fix it, and provided

tested source code for one of them in my message.

Using (a <= b) not would be a bad idea as a

sortBlock is supposed to act like #<=, not like #<.

(That has always puzzled me: why take #< as the

fundamental operation in Magnitude but #<= as the

fundamental operation in sorting?  But that is

historic and standard practice.)

On 23 April 2018 at 19:10, Erik Stel <[hidden email]> wrote:

Richard,

The 'problem' is that the result of the (original) #reverse is a
SortedCollection without a sortBlock. Meaning it defaults to comparing
values using #<=. When a new element is added to the reversed collection it
simply assumes all elements are already sorted and uses the (default)
sortBlock to add a new element.

I think the solution should be to have #reverse add an explicit sortBlock
which consists of reversing the original sortBlock or defaulting to [ a: b:
| (a <= b) not ]. (Keep #<= as some classes might depend on only
implementing this)

Cheers,
Erik

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Erik Stel

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

I already deleted my post (within 1 minute after posting 8-) seeing that I
jumped the wagon too early. Sorry for that. Your message and proposed
solution is fine.

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Erik Stel

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

In reply to this post by Richard O'Keefe

Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

"sortBlock is supposed to act like #<=" means

"for every triple of elements x y z that might be

 in the collection,

  b(x,x) is true

  b(x,y) is Boolean

  b(x,y) | b(y,x)

  b(x,y) & b(y,z) implies b(x,z)."

The first condition distinguishes it from #< .

In particular, if you want to sort a sequence

of *identical* elements, the sortBlock must

satisfy b(x,x).

There are other predicates around that act like

<= in the relevant sense: >= for example.

But #beginsWith: and #endsWith: don't satisfy

dichotomy.

On 24 April 2018 at 02:43, Erik Stel <[hidden email]> wrote:

Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

In reply to this post by Erik Stel

Let me offer a simple example.

#(a a) isSortedBy: [:x :y | (x <= y) not]

is false, while

#(a a) isSortedBy: [:x :y | y <= x]

is true.

On 24 April 2018 at 02:43, Erik Stel <[hidden email]> wrote:

Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
"a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Erik Stel

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Why does the sortBlock has to answer true for the same (identical) object? I
have not been able to find where it is specified. And in different locations
I see #> being used as a comparator for the sortBlock. So why is it bad (as
you wrote)? (It seems you describe that SortedCollection should create a
collection with a Total Order, whereas I describe a situation where a Strict
Order is also valid.)

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Denis Kudriashov

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

In reply to this post by Richard O'Keefe

Hi Richard.

I agree with your proposal.

But it force me to think that we should completely move to SortFunction's.

In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".

2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:

Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method. It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

In reply to this post by Erik Stel

As I pointed out yesterday, #sort and its immediate relatives

are not alone.  Look at #isSortedBy: .  When do you want

(#(1 1 1) asSortedCollection: b) isSortedBy: b

to answer false?

There are several reasons for sorting.  One is so that you

can use binary search.  It's rather disconcerting that the

binary search offered in Squeak and Pharo has nothing to do

with sortBlocks.  In several other Smalltalks it does.  It

is not terribly hard to write a binary search using a

sortBlock that acts like #<=.  It is not terribly hard to

write a binary search using a sort block that acts like

#<.  It is harder than it needs to be to write a binary

search that can tolerate either, and the one Smalltalk I

know that does this copes by calling the sortBlock twice

as often as it would need to if it knew one way or the other.

As it happens, my own Smalltalk library lets me do

sortBlock := sortBlock converse, which makes it easy

to do the right thing.  It is possible to implement this

so that the result is as cheap to call as the original.

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

In reply to this post by Denis Kudriashov

(aSortFunction value: x value: y) returns a Boolean;

(aSortFunction value: x value: x) returns true.

So you can already set up a SortedCollection using

a SortFunction.  So yes, that would work.

But there is no reason why #reversed (or my preference,

#converse) could not work on sortBlocks.

On 25 April 2018 at 23:27, Denis Kudriashov <[hidden email]> wrote:

Hi Richard.

I agree with your proposal.
But it force me to think that we should completely move to SortFunction's.
In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".

2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method. It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r

Denis Kudriashov

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

2018-04-25 14:26 GMT+02:00 Richard O'Keefe <[hidden email]>:

(aSortFunction value: x value: y) returns a Boolean;
(aSortFunction value: x value: x) returns true.
So you can already set up a SortedCollection using
a SortFunction. So yes, that would work.

Yes. It was original goal to introduce them.

I created another thread in dev list "SortedCollection based on SortFunction".

But there is no reason why #reversed (or my preference,
#converse) could not work on sortBlocks.

It will. But I think it is bad approach. Because any time you will need new kind of sort operation you will be forced extend BlockClosure.

In general reversed/converse has no meaning for block.

With SortFunction only simple extension #asSortFunction is required.

On 25 April 2018 at 23:27, Denis Kudriashov <[hidden email]> wrote:
Hi Richard.

I agree with your proposal.
But it force me to think that we should completely move to SortFunction's.
In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".

2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method. It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r

Richard O'Keefe

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

You wrote "In general reversed/converse has no meaning for block."

That's entirely an artefact of representing blocks of different

arities by the same class.  In my own Smalltalk, NiladicBlock,

MonadicBlock, DyadicBlock, ... are different classes.  To put it

another way, your statement has exactly the same status as

"In general #value:value: has no meaning for block."

#converse has meaning for *all* DyadicBlocks, it is the

combinator flip f x y = f y x.  For that matter, it could

be generalised to all blocks of arity >= 2 as

[:a1 :a2 ... :an | body] converse

=> [:a2 :a1 ... :an | body]

i.e., flip the first two arguments.

My original implementation of #converse was

DyadicBlock

  methods for: 'combinators'

    converse

      ^[:x :y | self value: y value: x]

    "other combinators"

With a suitable set of combinators, I can do things like

#name ascending thenBy: #age descending thenBy: #weight ascending nilsFirst

without needing a SortFunction class.

​I do like the fact that SortFunction can support both 2-way and 3-way​

comparison.