STL in Ada

STL in Ada

[NYGREN JONAS]

I have started to read c.l.a after being away a long time. Found it
interesting
that the question of a 'standard' Ada library (for containers and
algorithms) still
is on the chart.

So I started to think of how one would implement a set of algorithms that
work
over a set of iterators with different capabilities, like in STL. I am
curious if anybody
have come up with any ideas of how this should be done?

I arrived at an outline for a solution given below - is this the best way to
go?

/jonas

-- the iterators:

generic
   type Item_Type is private;
package Iterator is

   -- To Do: Add abstract methods for each Iterator type

   -- A container would derive from the appropriate iterator type
   -- and implement the abstract methods (TBD)

   -- Possible Problem: Output_Iterator. As I understand it
   --                   Forward_Iterator inherits capabilities
   --                   from both Input as well as Output_Iterator
   --                   but there is no (?) way to describe this

   type Root is tagged null record;
   type Input is new Root with null record;
   type Output is new Root with null record;
   type Forward is new Input with null record;
   type Bidirectional is new Forward with null record;
   type Random is new Bidirectional with null record;
end Iterator;

-- the Algos

with Iterator;
generic
   with package An_Iterator is new Iterator (<>);
package Algo is
   generic
      function Less (A, B : An_Iterator.Item_Type) return Boolean;
   function Min (First, Tail : An_Iterator.Forward'Class) return Boolean;
end Algo;

Re: STL in Ada

[Nick Roberts]

It occurs to me that Ada already has, and has always had, a standard
iteration mechanism of a kind: Sequential_IO.

I suggest a scheme based on two ('signature'?) packages, one to provide a
framework for container types ('stores'):


generic
   type Element_Type(<>) is private;

package Communal.Storage is

   type Store_Type is abstract tagged limited private;

   ...

   procedure Reset (Store: in out Store_Type) is abstract;

   ...

end Communal.Storage;


and one to provide a framework for iteration over values in a store:


with IO_Exceptions;

generic
   type Element_Type(<>) is private;
   type Element_Access is access all Element_Type;
   package Storage is new Communal.Storage(Element_Type);
   type Store_Type is new Storage.Store_Type with private;

package Communal.Sequential_Access is

   type File_Type is abstract tagged limited private;

   type File_Mode is (In_File, Out_File, Append_File, Access_File);

   procedure Open (File: in out File_Type; Mode: in File_Mode; Store: in out
Store_Type'Class) is abstract;
   procedure Close (File: in out File_Type) is abstract;

   procedure Reset (File: in out File_Type; Mode: in File_Mode) is abstract;

   procedure Read (File: in out File_Type; Item: out Element_Type) is
abstract;
   procedure Write (File: in out File_Type; Item: in Element_Type) is
abstract;
   procedure Next (File: in out File_Type; Pointer: out Element_Access) is
abstract;

   function Is_Open (File: in File_Type) return Boolean is abstract;
   function Mode (File: in File_Type) return File_Mode is abstract;
   function Store (File: in File_Type) return Storage.Store_Type'Class is
abstract;
   function End_Of_File (File: in File_Type) return Boolean is abstract;

   Status_Error: exception renames IO_Exceptions.Status_Error;
   Mode_Error: exception renames IO_Exceptions.Mode_Error;
   ...

end Communal.Sequential_Access;


Then, an implementation of a container type CT could be declared in a
package such as this:


with Communal.Storage, ...;

generic
   type Element_Type[(<>)] is private;

package [...]CT_Storage is

   package Element_Storage is new Communal.Storage(Element_Type);

   ...

   type CT is new Element_Storage.Store_Type with private;

   ...

end [...]CT_Storage;


and this type could provide 'iterator' facilities in the following form:


with Communal.Sequential_Access, ...;

package CT_Storage.Sequential_Access is

   type Element_Access is access all Element_Type;

   package Element_Sequential_Access is new
Communal.Sequential_Access(Element_Type,Element_Access,Element_Storage,CT);

   type File_Type is new Element_Sequential_Access.File_Type with private;

   subtype File_Mode is Element_Sequential_Access.File_Mode;

   procedure Open (File: in out File_Type; Mode: in File_Mode; Store: in out
CT'Class) is abstract;
   procedure Close (File: in out File_Type) is abstract;

   procedure Reset (File: in out File_Type; Mode: in File_Mode);

   procedure Read (File: in out File_Type; Item: out Element_Type);
   procedure Write (File: in out File_Type; Item: in Element_Type);
   procedure Next (File: in out File_Type; Pointer: out Element_Access);

   function End_Of_File (File: in File_Type) return Boolean;

   Status_Error: exception renames Element_Sequential_Access.Status_Error;
   Mode_Error: exception renames Element_Sequential_Access.Mode_Error;
   ...

end CT_Storage.Sequential_Access;


The idea of the 'Access_File' mode is to allow access-in-place to the
contents of a container, rather than reading or writing copies (which may be
less efficient). In this mode, the procedure 'Next' is successively called
to obtain an access value to each element in the container. Calling 'Next'
in any other mode, or 'Read' or 'Write' in this mode, causes 'Mode_Error' to
be raised.

-------------------------------------------
Nick Roberts    "The Prophylactic Didactic"
-------------------------------------------

NYGREN JONAS wrote in message <36be1ed2.0@d2o41.telia.com>...
[What form should an Ada iterator facility take?]