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 08:52:39 PST Newsgroups: comp.lang.ada Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!newsfeed.icl.net!shale.ftech.net!news.ftech.net!newspeer.clara.net!news.clara.net!news2.euro.net!uunet!ash.uu.net!xyzzy!nntp From: Jeffrey Carter Subject: Re: List container: Insert and Delete X-Nntp-Posting-Host: e246420.msc.az.boeing.com Content-Type: text/plain; charset=us-ascii Message-ID: <3BEFF9D6.607480D@boeing.com> Sender: nntp@news.boeing.com (Boeing NNTP News Access) Content-Transfer-Encoding: 7bit Organization: The Boeing Company X-Accept-Language: en 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> Mime-Version: 1.0 Date: Mon, 12 Nov 2001 16:33:26 GMT X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit (WinNT; U) Xref: archiver1.google.com comp.lang.ada:16335 Date: 2001-11-12T16:33:26+00:00 List-Id: 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. > 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). The abstraction of a position should be the same for both bounded and unbounded lists. The underlying implementation of a position for a bounded list will be an index into the underlying array, but it is quite likely that the component at index N of the array will not be the Nth element in the list. > 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. 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. > > I hope you will look at my proposal, and perhaps be a little more convinced! I'll take a look. -- Jeffrey Carter