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,cda33fc7f63c2885 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-09 11:09:17 PST Path: archiver1.google.com!postnews1.google.com!not-for-mail From: dennison@telepath.com (Ted Dennison) Newsgroups: comp.lang.ada Subject: Re: list strawman Date: 9 Jan 2002 11:09:16 -0800 Organization: http://groups.google.com/ Message-ID: <4519e058.0201091109.62feb846@posting.google.com> References: <4519e058.0201081910.51225bf@posting.google.com> NNTP-Posting-Host: 65.115.221.98 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1010603357 22808 127.0.0.1 (9 Jan 2002 19:09:17 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 9 Jan 2002 19:09:17 GMT Xref: archiver1.google.com comp.lang.ada:18701 Date: 2002-01-09T19:09:17+00:00 List-Id: dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0201081910.51225bf@posting.google.com>... > Stephen Leake wrote in message news:... > > I vote for adding 'split'; it nicely compliments 'splice'. > > OK. Next question(s): Can "split" be implemented as the inverse to > "splice", where it spilts from the iterator to the end, or does it > need to go from one iterator to another to be useful? > > If the latter, should "splice" be changed to work the same way? OK. I have bad news on this score. After playing with the code a bit, I came to realise that, while Splice as it stands can be implemented in O(C), Split and any iterator-to-iterator splice would both end up being no better than O(n). The problem is our safe iterators. Since iterators are associated with their list somehow, you have to go through every iterator that got moved and change its list (or invalidate it). There's no way to tell if a iterator's element got moved by our theoretical "Split" without iterating through the affected elements, which is O(n). The current Splice escapes this fate by virtue of the fact that *all* iterators are affected, so the algorithm can be made O(n) in iterators but not in elements. The only other option for other routines would to take the position that all operations that can move a subrange of elements from one list to another invalidate *all* the source lists' iterators. This looks like a good solution on paper, but I think its quite liable to destroy anyone's custom sort algorithm, which was the whole point of this exercise in the first place. So I'm not real sure we have a good reason for "Split" now after all.