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=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=unavailable autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 103376,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-11 19:51:25 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!fr.usenet-edu.net!usenet-edu.net!enst!enst.fr!not-for-mail From: "Steven Deller" Newsgroups: comp.lang.ada Subject: RE: List container: Insert and Delete Date: Sun, 11 Nov 2001 22:48:34 -0500 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: Reply-To: comp.lang.ada@ada.eu.org NNTP-Posting-Host: marvin.enst.fr Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-Trace: avanie.enst.fr 1005537084 38337 137.194.161.2 (12 Nov 2001 03:51:24 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Mon, 12 Nov 2001 03:51:24 +0000 (UTC) To: Return-Path: X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal In-Reply-To: <9sn4qm$13g29j$2@ID-25716.news.dfncis.de> X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org X-Mailman-Version: 2.0.6 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , List-Archive: Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: archiver1.google.com comp.lang.ada:16314 Date: 2001-11-11T22:48:34-05:00 > (a) What if I do "delete preceding item" twice? Does it > delete two items (the preceding one and the one before that)?=20 > [In which case, at what position do I end up?] Does it raise=20 > an exception (Item_Already_Deleted)? [In which case, how do I=20 > delete backwards twice?] Does it just delete one item (the=20 > second delete being effectively ignored)? One of these=20 > semantics can be chosen, but I don't think it's obvious=20 > which. Poor confused user. On the other hand, I think an=20 > operation such as "delete the third item" is pretty obvious=20 > and unambiguous. That's a pretty hard stretch to suggest the semantics are confusing. H - 1 - 2 - 3 - T ^ position after 2, before 3 Delete Preceding H - 1 - 3 - T ^ position after 1, before 3 Delete Preceding H - 3 - T ^ position after H, before 3 The semantics are "obvious" as long as positions are "between" elements and not "on" elements.=20 Delete 3rd item is just as "confusing" (No, I don't think it is confusing, just "as confusing" as you make out for position semantics). Once I delete the 3rd item, what if I delete the 3rd again. Does it raise an exception (Item_Already_Deleted) [In which case, how do I delete the next item?] ... As I said, if you speak in terms of pointing "between" elements, the semantics for position operations are straightforward for all operations. Personally, numbering items in a list seems inappropriate to me. I've always thought of associating "positional names" with elements as something other than lists -- arrays perhaps :-). If I do "insert item before item names '1'", do I get an item named '0'? Or do the names of ALL other items in the list change? Yuk. I fundamentally object to something that changes the "name" of EVERY other list item. That just seems to be ripe for erroneous use. > (b) For a list based on an array, the operation: "delete the > third item" is easy to implement, and fairly efficient for=20 > short lists; "insert before the third item" is ditto; and=20 > "replace the third item" is both easy and efficient (for any=20 > length of list). For a list based on a linked-list, the=20 > implementations of these operations are easy, and pretty=20 > efficient for short lists and for operations near to either=20 > end of the list. Delete preceding and delete succeeding for position operations are easy too. As is insert before or insert after position. =20 Trying to keep number references straight in "user code" for a list as inserts/deletes happen would lead (easily) to application errors by less expert users. Off-by-one errors are quite frequent in such situations. =20 > So I think the design based on indexed positioning wins 'on > points', as it were. Only when you are adding up the points :-). I have seen both semantics, and there are times I'd prefer one or the other. But when I want "names" for elements, I use arrays, in which I can't *delete* an item or a name, only make it have a different value. Names (numbers) are constant for arrays once they are created. The numbering approach also has the problem of "dynamic constraints" for index numbers. What happens if I reference List(13) when there are only 12 items in the list? The "position" approach is able to provide "split list" into two parts -- head and tail -- with little effort and with clear semantics (with a "between items" pointer). With numbers, the semantics of split list become consufing :-) -- does "split list at 3rd item" leave the 3rd item in the head or the tail? The semantics are not obvious and I do agree that users need "models" from which semantics are obvious, not an arbitrary list of operational semantics that have to be remembered each on its own. Either approach is simple to implement in terms of the other. The "numbering" semantics require O(N) time in the general case. That, in my mind, is the strongest argument against providing "numbering" of lists. Na=EFve users typically program as if primitive operations are O(1) in time.=20 So I think a design based on indexed positioning can lead to impractical (or erroneous) applications from na=EFve users -- primitive operations ought to be more "user proof". Regards, Steve