RE: [FIX] SortedCollectionFix-sr

Hi Stephan,

While I agree mostly with your reasoning (not entirely though because I
think Richard has a number of equally good arguments wrt. to consistency
of collection operations) there's one issue I strongly disagree with:

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

You don't have to use #add; you can use #addAll: which will choose the
right way to add the elements dynamically. Your proposal is actually
_really_ bad for optimization since it assumes "outside knowledge" about
the way SortedCollection is implemented and renders any attempt to
really optimize _it_ (instead of lots of clients guessing what a
reasonably good optimization would be) pretty much useless. Spreading
out "meager client side optimizations" while breaking the polymorphic
protocol is never a good idea - if you want to optimize then choose a
central, high-level, intent revealing place (such as, in fact,
SortedCollection>>addAll:) and don't ever have the client
second-guessing the structure and behavior of the object in question.

Cheers,
  - Andreas

> -----Original Message-----
> From: squeak-dev-admin@xxxxxxxxxxxxxxxxxxxxxxxxxx 
> [mailto:squeak-dev-admin@xxxxxxxxxxxxxxxxxxxxxxxxxx] On 
> Behalf Of Stephan Rudlof
> Sent: Thursday, September 26, 2002 7:25 PM
> To: squeak-dev@xxxxxxxxxxxxxxxxxxxxxxxxxx
> Subject: 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
> 
>