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-12 17:29:25 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!fu-berlin.de!uni-berlin.de!ppp-1-18.cvx6.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Tue, 13 Nov 2001 00:51:40 -0000 Message-ID: <9spt1i$14snic$3@ID-25716.news.dfncis.de> References: <3BECA3B7.5020702@telepath.com> <9sjf4n$odm$1@news.huji.ac.il> <9sjkc7$145mhb$1@ID-25716.news.dfncis.de> <3BEDACC0.9A314B54@acm.org> <9sktgm$134npc$3@ID-25716.news.dfncis.de> <3BEEB766.B50C969@acm.org> <9sn4qk$13g29j$1@ID-25716.news.dfncis.de> <3BEFF9D6.607480D@boeing.com> NNTP-Posting-Host: ppp-1-18.cvx6.telinco.net (212.1.156.18) X-Trace: fu-berlin.de 1005614963 38690380 212.1.156.18 (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:16382 Date: 2001-11-13T00:51:40+00:00 List-Id: "Jeffrey Carter" wrote in message news:3BEFF9D6.607480D@boeing.com... > Nick Roberts wrote: > > > > Your delicate distinction between an 'iterator' and a 'position' is a little > > silly. The reasons why it should not be done with iterators are the same as > > the reasons why it should not be done with positions. > > No, the idea that they are the same is a little silly. An iterator, by > definition, is something that iterates. A position within a list does > not iterate. If you can provide an example of a position iterating I > will change my position. I knew I'd get a rocketing for that one! You are, of course, quite right. > > The indexed operations will, of course, be of O(1) for the bounded list, yet > > being both based on the abstract list type, they will be algorithmically > > interchangeable. So there is a deeper reason for my insistence on indexed > > operations: I am trying to make a bigger plan 'come together'. > > They will be O(N) in both versions, unless you make the extremely poor > implementation decision for the bounded version to implement insertions > and deletions by moving entire slices of the underlying array. I suspect > such an implementation will be universally considered unacceptable. > Making insertions and deletions O(N) so that indexing can be O(1) is a > poor choice, especially considering that both can be O(1). I will investigate the possibilities for the implementation of the bounded version. As Ted Dennison intimates somewhere (in answer to this post?), I think an indexed implementation is an interesting idea, but it's performance under various conditions is likely to be a complex matter. > > Finally, my proposal includes all the usual head and tail dicing operations. > > Chopping off, or adding on, one item to either end of a list will be the > > most frequently used operations anyway, for which arguments about indexing > > don't apply. The indexed operations are mainly there for convenience. As I > > showed in an example in another thread, really serious manipulations of > > lists are best done sequentially. > > There are no "usual" head and tail operations for a list. In decades of > using and implementing data structure libraries, TED's specification is > the first I've encountered that emphasizes dequeue- and string-like > operations. There are in functional languages such as LISP. I think they'll be handy for lists sometimes, and are not difficult to implement. > The whole point of a list is that insertions and deletions are needed at > arbitrary positions. If you're only operating at the ends of the > sequence, then you want a dequeue, not a list, and you should not be > using a list. Okay, I agree, and I'm writing a new proposal that has a complete set of 'cursor' operations that do just what (I assume) your position-based strategy intended. Hope to get this to Ted (for his web site) soon (maybe 2-3 days). > > I hope you will look at my proposal, and perhaps be a little more convinced! > > I'll take a look. My thanks, Jeff, for your patience! -- Best wishes, Nick Roberts