strawman list package: sorting

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

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