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"