From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,1d6e3e408a840ae9,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-01-06 13:17:09 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail
From: Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>
Newsgroups: comp.lang.ada
Subject: strawman list package: sorting
Date: 06 Jan 2002 16:08:23 -0500
Organization: NASA Goddard Space Flight Center
Message-ID: <ubsg7427s.fsf@gsfc.nasa.gov>
NNTP-Posting-Host: anarres.gsfc.nasa.gov
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: skates.gsfc.nasa.gov 1010351537 4695 128.183.220.71 (6 Jan 2002
 21:12:17 GMT)
X-Complaints-To: dscoggin@cne-odin.gsfc.nasa.gov
NNTP-Posting-Date: 6 Jan 2002 21:12:17 GMT
User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.7
Xref: archiver1.google.com comp.lang.ada:18592
Date: 2002-01-06T21:12:17+00:00
List-Id: <comp.lang.ada>

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