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=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,1d6e3e408a840ae9 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-07 06:55:59 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!news.maxwell.syr.edu!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: Subject: Re: strawman list package: sorting Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Mon, 07 Jan 2002 09:55:51 EST Organization: http://www.newsranger.com Date: Mon, 07 Jan 2002 14:55:51 GMT Xref: archiver1.google.com comp.lang.ada:18598 Date: 2002-01-07T14:55:51+00:00 List-Id: In article , 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.