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-13 09:46:17 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!newshub2.rdc1.sfba.home.com!news.home.com!sjcppf01.usenetserver.com!usenetserver.com!news-west.rr.com!lsnws01.we.mediaone.net!typhoon.san.rr.com!not-for-mail Message-ID: <3BF15C70.B7EF23E6@san.rr.com> From: Darren New Organization: Boxes! X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete References: <9sn4qm$13g29j$2@ID-25716.news.dfncis.de> <9sok8i$142am0$2@ID-25716.news.dfncis.de> <3BF004F4.F74AE461@boeing.com> <9sp5up$g5o$1@nh.pace.co.uk> <3BF0827A.DCF2213C@acm.org> <9sra40$b8p$1@nh.pace.co.uk> <5DaI7.23016$xS6.35866@www.newsranger.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Tue, 13 Nov 2001 17:46:43 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: typhoon.san.rr.com 1005673603 66.75.151.160 (Tue, 13 Nov 2001 09:46:43 PST) NNTP-Posting-Date: Tue, 13 Nov 2001 09:46:43 PST Xref: archiver1.google.com comp.lang.ada:16430 Date: 2001-11-13T17:46:43+00:00 List-Id: Ted Dennison wrote: > Should we remove all basic-looking routines from either > implementation with time behavior >=O(N). Definitely not. All that will do is force people to recreate the functionality they need anyway, except without the benefit of being able to access the internal structures. For example, I strongly suggest that there be a mechanism to translate between positions and integer offsets and back. This is an O(N) operation, obviously, compared to the O(1) of moving the position. However, if someone has a list that they want to stuff out to a file, along with an offset (say, the one currently on the screen), they need a way to handle that. Denying the ability to translate between positions and integers just means that someone's going to write code full of things like offset := offset + 1; pos := Next(pos); Indeed, Tcl for many many years had O(N) access to arrays (called "lists" there, the maps being called arrays), and it wasn't really a problem. If you had a 1000 element list, it was still quick enough. If you had a really large list, you did it some other way if the performance was too bad. So don't leave out functionality just because it's hard to do *efficiently*. O(2**N) is still darn fast if N is 10 or the multiplier is in microseconds. Basically, the library has to be useful for small programs too, or you've (a) missed the point and (b) done little to help promote Ada. The languages that are great for million-line beasts and excrutiating for 100-line programs never really get very popular outside their niches. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. You will soon read a generic fortune cookie.