Re: Translate this into Ada ...

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

In article <321C5BB1.3B2F@eurocontrol.fr>, Richard Irvine
<Richard.Irvine@eurocontrol.fr> writes: 

|> In general one might like to have more than one
|> iterator for the same collection type, each
|> iterator implementing a different traversal
|> policy but all having the same protocol.

By "more than one iterator", Richard means "more than one iteration
algorithm", not "more than one iterator object".

The approach I described already supports more than one iteration
algorithm.  You simply derive a different concrete iterator type from the
abstract iterator type for each algorithm you wish to support, and
override the Current_Item, At_The_End, and Advance subprograms for each
type with versions appropriate for that type's algorithm.  You must
declare new functions with the same profile as New_Iterator_For,
returning iterators of each type.  (You still have to override
New_Iterator_For, so you might as well designate one of the iterator
types as the "standard" one and have New_Iterator_For be a renaming of
that type's constructor function.) For example: 

   with Generic_Abstract_Collections;

   generic

      type Element_Type is private;

   package Binary_Trees is

      package Abstract_Element_Collections is
         new Generic_Abstract_Collections (Element_Type);

      type Tree_Type is
         new Abstract_Element_Collections.Collection_Type with private;

      Iterator_Error: exception renames
                         Abstract_Element_Collections.Iterator_Error;

      --------------------------
      -- Preorder traversals: --
      --------------------------

      type Preorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Preorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Preorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Preorder_Traversal_Type);

      function New_Preorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      -------------------------
      -- Inorder traversals: --
      -------------------------

      type Inorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Inorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Inorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Inorder_Traversal_Type);

      function New_Inorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      --------------------------
      -- Endorder traversals: --
      --------------------------

      type Endorder_Traversal_Type is
         new Abstract_Element_Collections.Iterator_Type with private;

      function Current_Item
         (Iterator: Endorder_Traveral_Type) return Element_Type;

      function At_The_End (Iterator: Endorder_Traversal_Type) return Boolean;

      procedure Advance (Iterator: in out Endorder_Traversal_Type);

      function New_Endorder_Traversal
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class;

      ---------------------------
      -- "Standard" traversal: --
      ---------------------------

      -- Since the inherited version of New_Iterator_For is abstract,
      --    it must be overridden.

      function New_Iterator_For
         (Tree: Tree_Type)
         return Abstract_Element_Collections.Iterator_Type'Class
         renames New_Inorder_Traversal;

   private

      ...

   end Binary_Trees;

The purpose of declaring New_Iterator_For to be abstract in
Generic_Abstract_Collections was to create an obligation on the part of
the programmer declaring a concrete type to provide a concrete
constructor function.  Unfortunately, it creates one obligation per
collection type rather than one obligation per iterator type.  The fix is
to replace the declaration

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

with

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

(with the parameter made classwide so that New_Iterator_For does not
become a primitive operation of more than one tagged type, which is
illegal).

Then each iterator type in the example above inherits one version of
New_Iterator_For, which must be overridden: 

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Preorder_Traversal_Type;

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Inorder_Traversal_Type;

   function New_Iterator_For
      (Collection: Abstract_Element_Collections.Collection_Type'Class)
      return Endorder_Traversal_Type;

(In a typical call on New_Iterator_For, the usual overload resolution
rules determine which version is being called based on the result type
expected in the context of the call.)

Unfortunately, in the bodies of these functions, the parameter Collection
must be converted downward in the inheritance hierarchy to Tree_Type in
order to access the internal representation of Tree_Type, and this
involves a useless run-time check.

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