Re: List container strawman

["Matthew Heaney" <mheaney@on2.com>]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9svf7q$161cka$1@ID-25716.news.dfncis.de...
> Have I missed something in this discussion? If it is, as I get the
> impression, over whether the data type (the type of each element of a
list)
> generic parameter should be private or limited private, I think I can give
> you the definitive answer.

The problem is worse, because most of the participants in this discussion
have assumed that "list" means a polylithic structure (elements are shared),
a la LISP.  This is an incorrect model.  The container abstraction is
monolithlic, and refering to it as a "list" only means that it has constant
time insertion and removal.  So you don't need "construct" or "cons" or
"singleton" or "head" or "tail" or whatever.

Furthermore, you can add an item to the list at the front, back, or
somewhere in the middle.  You can remove any iteim of the list.

with Ada.Finalization;
generic
   type Item_Type is private;
   with function "=" (L, R : Item_Type) return Boolean is <>;
package Lists is
   type List_Type is private;  --implies Controlled
   procedure Push_Front (List : in out List_Type; Item : in Item_Type);
   procedure Push_Back (List : in out List_Type; Item : in Item_Type);
   procedure Pop_Front (List : in out List_Type);
   procedure Pop_Back (List : in out List_Type);
   function Front (List : List_Type) return Item_Type;
   function Back (List : List_Type) return Item_Type;
   function Length (List : List_Type) return Natural;

   type Iterator_Type (List : access List_Type) is limited private;
   procedure Insert (Iterator : in Iterator_Type; Item : in Item_Type);
   procedure Remove (Iterator : in out Iterator_Type);
   procedure Advance (Iterator : in out Iterator_Type);
   procedure Backup (Iterator : in out Iterator_Type);
   function Item (Iterator : in Iterator_Type) return Item_Type;
--or maybe
--type Iterator_Type is private;
--function Front (List : List_Type) return Iterator_Type;
--function Back (List : List_Type) return Iterator_Type;
--bounded form would probably require:
--function Front (List : access List_Type) return Iterator_Type;
--procedure Insert (List : in out List_Type; Iterator : Iterator_Type; Item
: Item_Type);
--procedure Remove (List : in out List_Type; Iterator : in out
Iterator_Type);
--etc
...
end;

That's the general idea.  I'm undecided about how to declare the iterator
type, because the limited form may have a false sense of security, e.g.

declare
   List : aliased Integer_Lists.List_Type;
begin
   Push_Front (List, 42);
   declare
      Iter : Iterator_Type (List'Access);
   begin
      Pop_Front (List);
      X := Item (Iter); --uh oh
   end;
end;

it may be simpler to just

declare
   List : List_Type;
   Iter : Iterator_Type;
begin
   Push_Front (List, 42);
   Iter := Front (List);
...
end;

It may also be necessary to use "First" and "Last" to refer to the first and
last elements in the sequence, and "Front" and "Back" to refer to the nonce
values that immediately preceed First and immediately follow Last, eg

declare
   List : List_Type;
   Iter : Iterator_Type := First (List);
begin
   while Iter /= List.Back loop
      ...
      Remove (List, Iter);
   end loop;
end;

You could then use First and Back to specify a half-open range, a la the STL
in C++.

Some food for thought...