Re: [FIX] SortedCollectionFix-sr

Dear Richard,

Richard A. O'Keefe wrote:
> I asked:
>       > Why should addLast: or addFirst: be given a complete veto?
> 
> and gave implementations of #addFirst: and #addLast: which
> complain only when the operation would violate the class invariant.
> 
> Stephen Rudlof replied:
>       The short answer
>       ----------------
>       The current situation for SortedCollections
>       - is inconsistent: >>addFirst: is forbidden, >>addLast: not;
> 
> That was understood and assumed in my question.
> 
>       - semantically incorrect: using >>addLast: easily leads to a not sorted
>       SortedCollection.
>       
> That also was understood and assumed.
> 
> My question is not "what is broken about the present situation",
> but "why not allow these operations to proceed whenever they can
> do so without breaking the class invariant?"
> 

> To expand on this a little:  why not give programmers a way to build
> a sorted collection in linear time when they are able to provide data
> in the right order?


I'm not against this. But please don't use addLast: for this. Use something
like >>addLastAlreadyInOrder: instead. And something like
>>addAllAlreadySorted:, >>addAllProbablyAlreadySorted: or whatever for
adding whole collections.


>       
>       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.
>       
> There are several attitudes a class designer might take.


> The attitude I prefer is
>  - operations should never be allowed to break class invariants

Agreed. (see also my responses to Andreas Raab)

>  - we should avoid introducing operations that often don't work

Agreed: this is my point regarding >>addLast: introduced for SortedCollections:
  it always works for OrderedCollections, but only in very special cases, if
applied to SortedCollections.

>  - but when we are stuck with an operation that CAN be allowed to
>    proceed some of the time we should not be strict bondage and
>    discipline nannies and stop sensible programmers doing sensible
>    things.

This is a contradiction to the previous point: 'proceed *some* of the time'
('*' by me) violates the goal to 'avoid introducing operations that often
don't work'.

> The attitude here is
>  - I am like God; I know exactly how programmers think and they mustn't.

I know what I expect from calling >>addLast:.

>    I can foresee every possible use and know which ones make sense.
>    (OK, this is a caricature, but it is a recognisable one.)
> 
> In this particular instance, it is possible for one and the same
> programmer, at a single instant in time,
> *BOTH* to want to build a collection in a particular order
> *AND* to want that collection to be a sorted collection.
> 
> For example, support I have a sorted collection of numbers,
> call it "fred":
>     fred := #(3 1 4 1 5 9 2 6 5) asSortedCollection.
> Now suppose I want to add 1 to every element.
> THIS IS AN ORDER-PRESERVING TRANSFORMATION.
> So
> 
>     jim := SortedCollection new.
>     fred do: [:each | jim addLast: each + 1].
> 
> will do the job, IF I am allowed to use addLast: when it is safe.
> (Yes, I know I can do fred+1, but the result belongs to the wrong class.)
> 


Good example!
Introduce and use something like >>addLastAlreadyInOrder: instead.


>       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.
> 
> I am not sure how to interpret "mostly" here.
> If it is an empirical statement about how often it does happen,
> then I would be intrigued to know where the evidence came from.


It's not an empirical statement. For me it is a convention to expect an
OrderedCollection if using >>addLast: (also see below).


> 
> In the case where the two orders AGREE, which is the only case my
> versions of #addFirst: and #addLast: allow, it is not an error.
> In the case (of as far as I am aware completely unknown frequency)
> where the two orders do not agree, the error will still be reported.
> 


>       And it violates encapsulation:  I have to know, which built in
>       order the SortedCollection has, to use >>addLast:  correctly
>       along your suggestion.
> 
> No, the sorting order of a sorted collection is part of its ***PUBLIC***
> interface.  Note that SortedCollection>>sortBlock is in the 'accessing'
> category, not the 'private' category.


Agreed: 'encapsulation' is the wrong term here.

My point is: if I'd use >>addLast: I'd expect an OrderedCollection, *not* a
SortedCollection. And ANSI supports this kind of view.


> 
>       By using >>add:  instead, there would be no problem.
>       
> Yes there would.  There would be an *EFFICIENCY* problem.
> 
> Note that I too can claim a psychological reason why addLast: should
> be used in this case rather than add:.  The reason is that in Set
> #add: means "add only if absent", whereas whenever addLast: is allowed
> it will make the collection one element bigger.
> 
>       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.
> 
> "performant" is, to the best of my knowledge, not an English word.
> I certainly haven't been able to find it in any of the paper or
> electronic dictionaries I've just checked.  Try "faster".

I'm wondering, because Leo knows it:
http://dict.leo.org/?search=performant&searchLoc=0&relink=on&spellToler=standard&sectHdr=off&tableBorder=1&cmpType=relaxed&lang=en
But it may be wrong: you are the native speaker!

> 
>       That has been my idea of introducing the 'bypass' method for
>       clients which really know about the internals.

I don't like this (not exactly mine, see also my replies to Andreas Raab)
idea anymore.

>       
> But the ordering used by a sorted collection is most definitely
> NOT a fact about its internals.  It is in some respects the most
> public thing there is about such an object.

Agreed.

> 
> Part of my point is that you don't *need* a bypass method when you
> have addLast: and could make it respect the class invariant.
> 
>       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.
>       
> The ANSI argument was shot down in smoke and billowing flames when I tried
> to apply it to #removeAll:, I don't see why it should have any greater force
> here.  Nothing in the ANSI standard prevents you *adding* methods to
> standard classes; if it did, almost all of the methods in Object would
> have to find another home.

Agreed.
But I stay at my assumption to expect an OrderedCollection if using
>>addLast:. And if you introduce methods *** with the same name *** in other
protocols you break conventions (and ANSI is also a convention).

>       
>       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.
> 
> I suggest allowing methods to proceed that DON'T break the class
> invariant, and this is spurned as breaking encapsulation, even though
> the methods are concerned solely with matters in the public interface.
> 


> Instead, as a better way, Rudlof proposes adding methods that DO break
> the class invariant,

I've corrected this: but there *is* a client in danger breaking it (see
reply to Andreas Raab), since it uses internals. And I've just continued to
allow this instead of fixing this, too.

> and DON'T offer any efficiency advantage.

Haven't measured this (regarding these clients using internal knowledge
about SortedCollection).

<snipped a very interesting proposal to be handled in another reply>


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