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 05:53:27 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!news.tele.dk!small.news.tele.dk!130.133.1.3!fu-berlin.de!uni-berlin.de!ppp-3-72.cvx5.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Mon, 12 Nov 2001 13:54:08 -0000 Message-ID: <9sok8j$142am0$3@ID-25716.news.dfncis.de> References: NNTP-Posting-Host: ppp-3-72.cvx5.telinco.net (212.1.154.72) X-Trace: fu-berlin.de 1005573204 37825216 212.1.154.72 (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:16321 Date: 2001-11-12T13:54:08+00:00 List-Id: I'm not qoting your reply, I'll just say I find it pretty persuasive. (And very well argued.) I have actually e-mailed my proposal based on indexed positioning; hopefully Ted will put it up on the web site soon. Do have a look at it. My most solidified idea regarding an alternative way of indicating positions was based on 'markers' which marked items in the list (rather than being notionally inserted inbetween two adjacent items). Is it really better to have starkly inter-item positioning, or would it actually be better to say that if item X is marked, "delete forward" means delete the item X, whereas "delete backward" means delete the item preceding X? This would be analogous to the way the cursor in most word processors deletes characters. The procedures could be named to reflect this model, e.g.: procedure Delete_from_Marker ( Marker: in out Unbounded_Marker; Count: in Natural := 1); procedure Delete_Before_Marker ( Marker: in out Unbounded_Marker; Count: in Natural := 1); The idea was to be able to set a marker to any item in a list. The marker could then be advanced up or retired down the list. The item it marks can be retrieved for inspection. The item at the marker can be deleted or replaced, but ONLY if there are no other markers set on it. This means having a counter in each node (but that's okay), but it does provide a rudimentary form of locking (handy for some algorithms); a basic implementation would raise an exception on breach of this locking, but a multi-tasking alternative could perform a wait. Insert and append operations would need to have versions that return a marker. There would need to be a few extra operations (e.g. "copy marker"). These operations would be efficient for a linked-list implementation, but not for a array-based one (for long lists). Again, that's okay (just not ideal). Do you like this idea? Shall I work up a new proposal based on this? Would it be worth having both approaches (both index-based and marker-based)? (I quite favour having both. Students should be taught to use the markers.) -- Best wishes, Nick Roberts