Gem #9: Classwide Operations, Iterators, and Generic Algorithms

by Matthew Heaney —On2 Technologies

Let's get started…

In the last gem, we used a stack class to demonstrate factory functions (to construct iterator objects), and implemented an assignment operation that dispatched on the type of the target stack. We mentioned in passing that that operation could be implemented by dispatching on the source stack, so let's show how to do that.

We reorder the parameters so that the Source stack is first in the parameter list (so that it's the “distinguished receiver” of a prefix-style call), and change its type from classwide to specific. We also change the name of the operation from Assign to Copy, per convention. The new declaration is as follows:

   procedure Copy
     (Source : Stack;
      Target : in out Stack'Class) is abstract;

In the earlier example, we had to populate the target stack in reverse, so that the elements would be in the correct order. We were able to do that because the operation was implemented by the specific type, and hence it had direct access to the representation of the (target) stack. Here the target type is classwide, so the only way to populate it is in forward order, using Push. That means we'll have to iterate over the source stack in reverse, so that the items are properly ordered in the target.

The bounded stack type is implemented as an array, so implementing Copy is easy because the bottom of the stack begins at the beginning of the array:

   procedure Copy
     (Source : Stack;  -- bounded stack (array-based)
      Target : in out Stacks.Stack'Class)
   is
   begin
      Target.Clear;

      for I in 1 .. Source.Top_Index loop    -- from bottom to top
         Target.Push (Source.Elements (I));  -- Elements is the array
      end loop;
   end Copy;

We also said in the earlier gem that the operation need not be primitive for the type. If we change the source stack's type to classwide, then the operation itself becomes classwide:

   procedure Copy2  -- classwide op, not primitive
     (Source : Stack'Class;
      Target : in out Stack'Class);

If we make the type of the source stack classwide, then we'll need a different way to iterate over items of the source stack in reverse order, since we don't have access to its representation anymore.

To do that we'll amend the cursor type to include some additional operations. First we'll add a new factory function, to construct a cursor object that (initially) designates the element at the bottom of the stack:

   function Bottom_Cursor
     (Container : not null access constant Stack)
     return Cursor'Class is abstract;

We'll also need an operation to move the cursor to the element that precedes the current item:

   procedure Previous (Position : in out Cursor) is abstract;

That gives us everything we need to turn Copy into a classwide operation, so that it only needs to be implemented once:

   procedure Copy2
     (Source : Stack'Class;
      Target : in out Stack'Class)
   is
      C : Cursor'Class := Bottom_Cursor (Source'Access);
      
   begin
      Target.Clear;
      
      while C.Has_Element loop
         Target.Push (C.Element);
         C.Previous;
      end loop;
   end Copy2;

Note that we declared the classwide stack operation in the root package (see stacks.ads), but it could have just as easily been declared as a generic child procedure:

  generic
  procedure Stacks.Generic_Copy3
    (Source : Stack'Class;
     Target : in out Stack'Class);

Actually, we could move the operation out of the package hierarchy entirely:

  with Stacks;
  generic
     with package Stack_Types is new Stacks (<>);
     use Stack_Types;
  procedure Generic_Stack_Copy4
    (Source : Stack'Class;
     Target : in out Stack'Class);

We can generalize this even more, such that the copy algorithm works for any kind of stack:

  generic
     type Stack_Type (<>) is limited private;
     type Cursor_Type (<>) is private;
     type Element_Type (<>) is private;

     with function Bottom_Cursor 
       (Stack : Stack_Type) 
       return Cursor_Type is <>;
     with procedure Push
       (Stack : in out Stack_Type;
        Item  : Element_Type) is <>;
     with procedure Previous   
       (Cursor : in out Cursor_Type) is <>;
     …
  procedure Generic_Stack_Copy5
    (Source : Stack_Type;
     Target : in out Stack_Type);

This illustrates the difference between the dynamic polymorphism of tagged types and the static polymorphism of generics. There is no need for a stack class anymore (having a dedicated copy operation that works only for types in that class), since the generic algorithm works for any stack. (This is exactly how the standard container library is designed. Container types are tagged, but they are not members of a common class.)

Instantiating this operation on our stack type is easy, since the names of the generic actual operations match the names of the generic formal operations, so we don't need to specify them explicitly (since the generic formals are marked as accepting a <> default):

  procedure Test_Copy5 (S : Stack) is
     procedure Copy5 is
        new Generic_Stack_Copy5
       (Stack,
        Cursor,
        Integer); -- default everything else

     T : Stack (S.Length);

  begin
     Copy5 (Source => S, Target => T);
  end;

But why stop there? We can write a generic copy algorithm for any kind of container. We just need to generalize iteration a little, to mean “visit these items in the way that makes sense for this source container,” and generalizing insertion, to mean “add this element in the way that makes sense for this target container.” The declaration would be:

  generic
     type Container_Type (<>) is limited private;
     type Cursor_Type (<>) is private;
     type Element_Type (<>) is private;

     with function First
       (Container : Container_Type) 
       return Cursor_Type is <>;
     with procedure Insert
       (Container : in out Container_Type;
        Item      : Element_Type) is <>;
     with procedure Advance
       (Cursor : in out Cursor_Type) is <>;

  procedure Generic_Copy6
    (Source : Container_Type;
     Target : in out Container_Type);

We can instantiate this using our stack type, but note that the generic actuals no longer match the generic formals, so we need to specify them explicitly:

  procedure Test_Copy6 (S : Stack) is
     procedure Copy6 is
        new Generic_Copy6
       (Stack,
        Cursor,
        Integer,
        First => Bottom_Cursor,
        Insert => Push,
        Advance => Previous);

     T : Stack (S.Length);

  begin
     Copy6 (Source => S, Target => T);
  end;

One assumption we've made here is that the source and target containers have the same type. Suppose we would like to copy the items in a stack to, say, an array. One approach would be to introduce another generic formal container type (a “source container” type that is distinct from the “target container” type), but there's another way. Consider the implementation of the copy algorithm:

  procedure Generic_Copy6
    (Source : Container_Type;
     Target : in out Container_Type)
  is
     C : Cursor_Type := First (Source);

  begin
     Clear (Target);
     while Has_Element (C) loop
        Insert (Target, Element (C));
        Advance (C);
     end loop;
  end Generic_Copy6;

Notice that the only thing we do with the source container is to use it to construct a cursor. If we pass in the cursor directly, that eliminates any mention of the source stack, which in turn allows the source and target containers to be different types. Our algorithm now becomes:

  generic
     type Container_Type (<>) is limited private;
     type Cursor_Type (<>) is private;
     type Element_Type (<>) is private;
     …
  procedure Generic_Copy7
    (Source : Cursor_Type;
     Target : in out Container_Type);

We can now copy from an integer stack to an array like this:

  procedure Copy_From_Stack_To_Array (S : in out Stack) is
    T : Integer_Array (1 .. S.Length);
    I : Positive := T'First;

    procedure Insert
      (Container : in out Integer_Array;
       Item      : Integer)
    is
    begin
       Container (I) := Item;
       I := I + 1;
    end;

    procedure Copy7 is
       new Generic_Copy7
      (Integer_Array,
       Cursor,
       Integer,
       Advance => Next);

 begin
    Copy7 (Source => S.Top_Cursor, Target => T);
 end Copy_From_Stack_To_Array;

The target “container” is just an array. The only special thing we need to do is synthesize an insertion operation, to pass as the generic actual. We can also use the same algorithm to go the other way, from an array to a stack:

  procedure Copy_From_Array_To_Stack (S : Integer_Array) is
    T : Stack (S'Length);

    function Has_Element (I : Natural) return Boolean is
    begin
       return I > 0;
    end;

    function Element (I : Natural) return Integer is
    begin
       return S (I);
    end;

    procedure Advance (I : in out Natural) is
    begin
       I := I - 1;
    end;

    procedure Copy7 is
       new Generic_Copy7
      (Stack,
       Natural,
       Integer,
       Insert => Push);

  begin
    Copy7 (Source => S'Last, Target => T);
  end Copy_From_Array_To_Stack;

Now the source container is an array, and the “cursor” is just the array index (an integer subtype). We have the familiar problem of ensuring that the target stack is populated in the correct order. As before, we simply iterate over the array in reverse, by passing the index S'Last as the initial cursor value, and then “advancing” the cursor by decrementing the index value.

The algorithm can be generalized further still. In this final version, we eliminate the generic formal element type. That means we'll need to modify the generic formal Insert operation, by passing the source cursor as a parameter instead of the source element. The declaration of the generic algorithm now becomes:

  generic
     type Container_Type (<>) is limited private;
     type Cursor_Type (<>) is private;

     with procedure Insert
       (Target : in out Container_Type;
        Source : Cursor_Type) is <>;
     …
  procedure Generic_Copy8
    (Source : Cursor_Type;
     Target : in out Container_Type);

The algorithm is now agnostic about the mapping from cursor to element (since it doesn't even know about elements), which is more flexible, since it allows the client to choose whatever mechanism is the most efficient. To use the new algorithm, all we need to do is make a slight change to the generic actual Insert procedure, as follows:

  procedure Copy_From_Stack_To_Array (S : in out Stack) is
    T : Integer_Array (1 .. S.Length);
    I : Positive := T'First;

    procedure Insert
      (Target : in out Integer_Array;
       Source : Cursor)  -- now a cursor instead of an element
    is
    begin
       Target (I) := Element (Source);
       I := I + 1;
    end;

    procedure Copy8 is
       new Generic_Copy8
      (Integer_Array,
       Cursor,
       Advance => Next);

 begin
    Copy8 (Source => S.Top_Cursor, Target => T);
 end Copy_From_Stack_To_Array;

The basic idea is that a generic algorithm can be used over a wide range of containers (including array types). A cursor provides access to the elements in a container, but as we've seen, once you have a cursor then the container itself sort of disappears. From the point of view of a generic algorithm, a container is merely a sequence of items.

Related Source Code

Ada Gems example files are distributed by AdaCore and may be used or modified for any purpose without restrictions.