Re: [FIX] SortedCollectionFix-sr

Richard,

Richard A. O'Keefe wrote:
>       - >>addLast: should be forbidden as >>addFirst is already;
> 
> Why should addLast: or addFirst: be given a complete veto?
> 
> Why not
>     addFirst: anItem
>         self isEmpty ifTrue: [^super addFirst: anItem].
>       (sortBlock
>           ifNil: [anItem <= self first]
>           ifNotNil: [sortBlock value: anItem value: self first]
>       ) ifFalse: [
>           self error: 'new item would be out of order'
>       ].
>       ^super addFirst: anItem.
> 
>     addLast: anItem
>       self isEmpty ifTrue: [^super addLast: anItem].
>       (sortBlock
>           ifNil: [self last <= anItem]
>           ifNotNil: [sortBlock value: self last value: anItem]
>       ) ifFalse: [
>           self error: 'new item would be out of order'
>       ].
>       ^super addLast: anItem.
> 
> This way we DON'T have to invent a new method to use when someone
> wants to build up a SortedCollection one element at a time and knows
> they can do it in the correct order, and we still don't allow these
> methods to spoil the order of the collection.
> 
> 
> 

The short answer
----------------
The current situation for SortedCollections
- is inconsistent: >>addFirst: is forbidden, >>addLast: not;
- semantically incorrect: using >>addLast: easily leads to a not sorted
SortedCollection.

I've wanted to fix this.


The longer answer
-----------------

Prenote: your suggestion is *semantically* correct. But there are
psychological/practical reasons against introducing it.

Why does a programmer use #addLast:? He wants to build a Collection in an
explicit order.
Why does a programmer use a SortedCollection? He wants to have a Collection,
which automatically ensures an order of added elements.

Using >>addLast: for a SortedCollection means to try to give an explicit
order  to something, which has an automatically 'built in' one. This mostly
is a programmer error. And it violates encapsulation: I have to know, which
built in order the SortedCollection has, to use >>addLast: correctly along
your suggestion. By using >>add: instead, there would be no problem.

So there remains the performance thing: using SortedCollection>>add:
multiple times means, that each object has to be sorted in immediately. It
is probably more performant to have a private add method, which just adds an
element, while leaving the SortedCollection in an inconsistent state, and
>>reSort it afterwards, when all elements have been added. That has been my
idea of introducing the 'bypass' method for clients which really know about
the internals.

BTW: In the ANSI standard (revision 1.9) *protocol* <SortedCollection>
doesn't conform to protocol <OrderedCollection>, which is the only one
defining >>addFirst: and  >>addLast:. This makes sense to me.



Implementation notes
--------------------

To the private SortedCollection>>addLastWithoutSorting: there could also be
added
- >>addWithoutSorting: and
- >>addFirstWithoutSorting:;
for - very few! - clients using the *internals*. After using one of these
methods >>reSort should be called to ensure consistency.
Note: I haven't proved the implicit assumption here, that >>reSort'ing an
already sorted SortedCollection is faster than adding elements in arbitrary
order.

Another - cleaner - variant avoiding these internal methods: collecting the
to be added elements in another - not sorted! - Collection and calling
SortedCollection>>addAll: for them.



Greetings,

Stephan
-- 
Stephan Rudlof (sr@xxxxxxxxx)
   "Genius doesn't work on an assembly line basis.
    You can't simply say, 'Today I will be brilliant.'"
    -- Kirk, "The Ultimate Computer", stardate 4731.3