strawman list package: sorting

strawman list package: sorting

[Stephen Leake]

Here's the current strawman Sorting nested package:

   -------------------------------------------------------------------------
   -- Sorting sub-package.
   -- To sort in increasing order, use the ">" routine for the Reverse_Order
   -- parameter. To sort in decreasing order, substitute your "<" routine for
   -- the Reverse_Order parameter. :-)
   -------------------------------------------------------------------------
   generic
      with function Reverse_Order (First, Second : in Element) return Boolean;
      From : in Direction;
   package Sorting is
      ----------------------------------------------------------------------
      -- Sort the given list.
      ----------------------------------------------------------------------
      procedure Sort (Subject : in out List);

      ----------------------------------------------------------------------
      -- 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);

      ----------------------------------------------------------------------
      -- Merge the source sorted list into the target sorted list in such a way
      -- that the result is still sorted. Source will be an empty list after
      -- this operation. Even if one of the lists isn't sorted to start with,
      -- the target list will contain all elements that both lists started out
      -- with.
      ----------------------------------------------------------------------
      procedure Merge (Target : in out List;
                       Source : in out List);
   end Sorting;

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.

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

That way, the hash value for New_Item in Insert can be computed just
once. Or the hash value for all elements on the list can be cached.

-- 
-- Stephe

Re: strawman list package: sorting

[Ted Dennison]

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.