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,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-11 16:23:52 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!fu-berlin.de!uni-berlin.de!ppp-1-91.cvx1.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Mon, 12 Nov 2001 00:20:17 -0000 Message-ID: <9sn4qm$13g29j$2@ID-25716.news.dfncis.de> References: NNTP-Posting-Host: ppp-1-91.cvx1.telinco.net (212.1.136.91) X-Trace: fu-berlin.de 1005524631 37226803 212.1.136.91 (16 [25716]) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Xref: archiver1.google.com comp.lang.ada:16311 Date: 2001-11-12T00:20:17+00:00 List-Id: "Steven Deller" wrote in message news:mailman.1005507140.5856.comp.lang.ada@ada.eu.org... > ... > I see no difficulty with iteration doing inserts and deletes, even with > other simultaneous iterators. It is a simple matter to define the > semantics to be unambiguous, particularly if you use positions that are > "in between" elements and semantics like: > delete following item > delete preceding item > get value of following item > get value of preceding item > move to next position (skip over an element) > move to previous position (skip backwards over an element) > goto head of list (position before first item) > goto tail of list (position after last item) > is at end of list (boolean) > is at beginning of list (boolean) > > These are all well defined, even for empty lists. (a) I don't think they are really that well defined. (b) Implementing these operations is complicated. In more detail: (a) What if I do "delete preceding item" twice? Does it delete two items (the preceding one and the one before that)? [In which case, at what position do I end up?] Does it raise an exception (Item_Already_Deleted)? [In which case, how do I delete backwards twice?] Does it just delete one item (the second delete being effectively ignored)? One of these semantics can be chosen, but I don't think it's obvious which. Poor confused user. On the other hand, I think an operation such as "delete the third item" is pretty obvious and unambiguous. (b) For a list based on an array, the operation: "delete the third item" is easy to implement, and fairly efficient for short lists; "insert before the third item" is ditto; and "replace the third item" is both easy and efficient (for any length of list). For a list based on a linked-list, the implementations of these operations are easy, and pretty efficient for short lists and for operations near to either end of the list. So I think the design based on indexed positioning wins 'on points', as it were. -- Best wishes, Nick Roberts