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:55:50 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!isdnet!wanadoo.fr!not-for-mail From: Pascal Obry Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: 13 Nov 2001 18:53:42 +0100 Organization: Home - http://perso.wanadoo.fr/pascal.obry Message-ID: References: <9sok8j$142am0$3@ID-25716.news.dfncis.de> <3BF00692.3CFED98C@boeing.com> <9spt1m$14snic$7@ID-25716.news.dfncis.de> NNTP-Posting-Host: avelizy-103-1-2-154.abo.wanadoo.fr Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: wanadoo.fr 1005674149 3233 217.128.15.154 (13 Nov 2001 17:55:49 GMT) X-Complaints-To: abuse@wanadoo.fr NNTP-Posting-Date: 13 Nov 2001 17:55:49 GMT User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 Xref: archiver1.google.com comp.lang.ada:16431 Date: 2001-11-13T17:55:49+00:00 List-Id: "Nick Roberts" writes: > Excellent. I'm calling a marker a 'cursor'. I've already decided I'm going > for the 'inbetween items' model (it's very neat). By having just one cursor > built in to each list object, I think I solve all the problems of > inefficiency, memory greed, and safety (in one fell stroke!). Getting my > proposal to you ASAP. We often say in CLA that others are reinventing the wheel ! For sure others have already designed something like that. Here is a cut-and-paste from EPFL containers library (which I found very good BTW), and here others are Ada guys... << generic type Item_Type is private; with function Equals (Left,Right: Item_Type) return Boolean; package List_Of_Static_Items_G is --------------------------------- --+ OVERVIEW: --+ This package provides lists of unlimited dynamic size with elements --+ of type Item_TYPE, where Item_TYPE is specified by a generic parameter. --+ The type List_TYPE is implemented in such a way that every object has --+ the implied initial value of an empty list. --+ --+ A list appears like this: --+ --+ element element element --+ ____ ____ ____ --+ | | | | | | --+ o------| |-----o-----| |-----o-----| |------o --+ |____| |____| |____| --+ front ^ rear --+ | --+ <---- cursor ----> --+ previous next --+ --+ Possible points of interest (indexes) are located at the start of the --+ list (front), at its end (rear) or on two moving cursors. Indexes never --+ directly reference elements. They only reference inter-element locations --+ (insertion points). Elements are referenced by specifying an index and --+ a related direction (next or previous). --+ In an empty list, the front and the rear collapse into a single location --+ which is simultaneously the only valid cursor position. Every list is --+ initially empty, with its cursors located on this position. --+ The front and the rear also collapse when considering the list as circular. --+ This can be done by setting the Circular parameter in the appropriate --+ operations. --+ --+ --+ PRIMITIVES : --+ CURSOR CONSTRUCTORS : --+ Set_Cursor --+ Set_Cursor_At_Front --+ Set_Cursor_At_Rear --+ Move_Cursor_TO_Next --+ Move_Cursor_TO Previous --+ Find_And_Set_Cursor (2) --+ Find_And_Set_Cursor_G --+ Find_And_Set_Cursor_With_Exception_G --+ CURSOR QUERIES : --+ Cursor_Position (2) --+ IS_Cursor_At_Front --+ IS_Cursor_At_Rear --+ LIST CONSTRUCTORS : --+ Assign --+ Construct --+ Copy --+ Set --+ Modify --+ Insert --+ Remove (2) --+ Swap --+ Move (2) --+ Move_G --+ LIST QUERIES : --+ Size --+ Is_Empty --+ Number --+ Is_Present --+ Get --+ = --+ Are_Identical --+ LIST ITERATORS : --+ Traverse_G --+ Traverse_Modify_G --+ HEAP MANAGEMENT : --+ Destroy --+ Release_Free_List --+ Set_Max_Free_List_Size --+ Free_List_Size --+ >> They have also Queue, Stack, Table. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://perso.wanadoo.fr/pascal.obry --| --| "The best way to travel is by means of imagination"