Re: List container: Insert and Delete

[Pascal Obry <p.obry@wanadoo.fr>]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> 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"