Re: Translate this into Ada ...

[ncohen@watson.ibm.com (Norman H. Cohen)]

In article <3219E6E2.2F5@eurocontrol.fr>, Richard Irvine
<Richard.Irvine@eurocontrol.fr> writes:

|> We would like all lists in an application to be read using an iterator
|> with operations like:
|>
|>   function  theCurrentItem( theIterator :        Iterator ) return
|> ItemType;
|>   function  atTheEnd      ( theIterator :        Iterator ) return
|> Boolean;
|>   procedure goToTheNext   ( theIterator : in out Iterator );
|>
|> Furthermore, since an iterator has to be created for a particular list
|> and since the implementation of an iterator is dependent on that of the
|> list
|> we would like all list types to have a (constructor) operation like
|>
|>   function  aNewIteratorFor( theList : List ) return Iterator;
|>
|> This design decision should apply to all types of list, regardless of
|> the ItemType and regardless of the implementation of the lists.

One approach is a generic, each instance of which declares a root
abstract type for collections and a root abstract type for iterators.
The instance declares all of the above operations as abstract
subprograms.

The package in which you declare your list type derives both a new list
type from the root abstract collection type and a new iterator type from
the root abstract iterator type.  It provides concrete subprograms to
override each of the inherited abstract operations.  Since the concrete
collection type and the concrete iterator type are declared in the same
package, the bodies for these operations have access to the
implementations for both concrete types.

Here is a generic template like that I have described:

   generic

      type Item_Type (<>) is limited private;

   package Generic_Abstract_Collections is

      type Collection_Type is abstract tagged private;
      type Iterator_Type is abstract tagged private;

      function New_Iterator_For
         (Collection: Collection_Type) return Iterator_Type'Class
         is abstract;

      function Current_Item (Iterator: Iterator_Type) return Item_Type
         is abstract;

      function At_The_End (Iterator: Iterator_Type) return Boolean
         is abstract;

      procedure Advance (Iterator: in out Iterator_Type) is abstract;

      Iterator_Error: exception;
         -- Raised by Current_Item or Advance invoked with an iterator that is
         --    not currently positioned at an item.
   private

      type Collection_Type is abstract tagged null record;
      type Iterator_Type is abstract tagged null record;

   end Generic_Abstract_Collections;


(New_Iterator_For has a classwide result because it is not permitted to
be a primitive operation of more than one tagged type.)  Here is a sample
application, to a collection of integers implemented as a linked list:


   with Generic_Abstract_Collections;

   package Integer_Lists is

      package Abstract_Integer_Collections is
         new Generic_Abstract_Collections (Item_Type => Integer);

      type Integer_List_Type is
         new Abstract_Integer_Collections.Collection_Type with private;

      type Integer_List_Iterator_Type is
         new Abstract_Integer_Collections.Iterator_Type with private;

      Iterator_Error: exception renames
                         Abstract_Integer_Collections.Iterator_Error;

      -- Concrete subprograms to override inherited abstract subprograms:

      function New_Iterator_For
         (Collection: Integer_List_Type)
         return Abstract_Integer_Collections.Iterator_Type'Class;

      function Current_Item
         (Iterator: Integer_List_Iterator_Type) return Integer;

      function At_The_End
         (Iterator: Integer_List_Iterator_Type) return Boolean;

      procedure Advance (Iterator: in out Integer_List_Iterator_Type);

      -- Other Integer_List_Type operations could be declared here.

   private

      type Cell_Type;
      type Cell_Pointer_Type is access Cell_Type;
      type Cell_Type is
         record
            Value : Integer;
            Link  : Cell_Pointer_Type;
         end record;

      type Integer_List_Type is
         new Abstract_Integer_Collections.Collection_Type with
            record
               First_Cell: Cell_Pointer_Type;
            end record;

      type Integer_List_Iterator_Type is
         new Abstract_Integer_Collections.Iterator_Type with
            record
               Next_Cell: Cell_Pointer_Type := null;
            end record;

   end Integer_Lists;


   package body Integer_Lists is

      function New_Iterator_For
         (Collection: Integer_List_Type)
         return Abstract_Integer_Collections.Iterator_Type'Class is
      begin
         return Integer_List_Iterator_Type'
            (Abstract_Integer_Collections.Iterator_Type with
             Next_Cell => Collection.First_Cell);
      end New_Iterator_For;

      function Current_Item
         (Iterator: Integer_List_Iterator_Type) return Integer is
      begin
         if Iterator.Next_Cell = null then
            raise Iterator_Error;
         else
            return Iterator.Next_Cell.Value;
         end if;
      end Current_Item;

      function At_The_End (Iterator: Integer_List_Iterator_Type) return Boolean is
      begin
         return Iterator.Next_Cell = null;
      end At_The_End;

      procedure Advance (Iterator: in out Integer_List_Iterator_Type) is
      begin
         if Iterator.Next_Cell = null then
            raise Iterator_Error;
         else
            Iterator.Next_Cell := Iterator.Next_Cell.Link;
         end if;
      end Advance;

      -- [Bodies of other Integer_List_Type operations.]

   end Integer_Lists;

Note that the return type of New_Iterator_For is the classwide type for
the root Iterator_Type declared in the generic instance (i.e., the return
type for the version of New_Iterator_For inherited by Integer_List_Type),
not for the derived type Integer_List_Iterator_Type.  However, the
function body returns an Integer_List_Iterator_Type object.

It might be more appropriate to make Iterator_Type limited (since it
represents the state of an in-progress loop iteration, something that it
does not make sense to copy).  In this case, the New_Iterator_For
function should be replaced by a procedure Start_Iteration with an out
parameter of Iterator_Type.  Also, if operations are provided to insert
items in or delete items from a collection, a decision must be made about
the semantics of iterating over a list while it is being updated, and the
implementation of iterators must account for insertions and deletions
during iteration.

--
Norman H. Cohen    ncohen@watson.ibm.com