Re: strawman list package: sorting

[Ted Dennison<dennison@telepath.com>]

In article <ubsg7427s.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>      ----------------------------------------------------------------------
>      -- Insert the given item into the given list at the proper location to
>      -- keep it sorted. If Target isn't sorted, the item will still be
>      -- inserted somewhere.
>      ----------------------------------------------------------------------
>      procedure Insert (New_Item : in     Element;
>                        Target   : in out List);
>
>If the lists passed to Insert or Merge aren't sorted, we get
>implementation-defined behavior. In keeping with the philosophy of
>"make it safe, not necessarily efficient", I suggest we eliminate that
>implemenation dependence by keeping a 'sorted' flag in the list.
>Insert and Merge can check that flag, and call Sort as needed. Other
>operations that can invalidate the sort should clear the flag.

It sound like the real issue here is that you want this routine to raise an
exception when the list isn't sorted (iow: has been manipulated with a routine
outside of the sorting package), rather than just going ahead and performing the
insert. 

I'd like to point out that this wouldn't be as simple as you imply. You'd
probably need more than just a simple "sorted" flag, as there may be several
different ways a list could be sorted. We'd need some way to uniquely identify
each sorting package that a list may have, and store that ID in a
"Sorted_As_Per" field. Thinking about it, this could probably be done by making
a tagged type in the private part of the Sorting package, and using its tag.
We'd also probably need to add a couple of routines to check the flag, and to
check the order (and set the flag appropriately).

The "try to do it anyway" semantics I borrowed from the STL, on the theory that
there's probably a good reason for wanting it that way. But the C++ philosophy
is a bit different than Ada's. 

Other that having to do all the extra work, I don't really care that much which
way it is done. But I think we should think(discuss) seriously about so
drasticly increasing the scope of what these routines do. There should be a good
benifit to doing so.

>Also, for situations where the sort key is not a simple function of
>the Element (like a hash), it would be better to have a separate
>generic Key type, and a generic function To_Key (Element):
>
>   generic
>      type Key is private;
>      with function To_Key (Item : in Element) return Key;
>      with function Reverse_Order (First, Second : in Key) return Boolean;
>      From : in Direction;
>   package Sorting is

When we get to making the *.Maps package, this will be a good issue. I don't
think we want to go adding all this extra support to the lists package, because
a Map should really be the structure to use for stuff that you want kept sorted,
looked up by key, etc.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.