How would you write an Ada generic function operating on doubly_linked_lists of any type of element?

Question

If possible, how would I write an Ada generic function operating on doubly_linked_lists of any type of element? The following function specification illustrates what I want by constraining Array_Type to be an array of the element_type given.

generic
   type element_type is private;
   type Array_Type is array (Positive range <>) of element_type;
procedure Shuffle_Array (List : in out Array_Type);

A procedure can be instantiated from this given an element_type and strictly a corresponding array_type, while the bounds of the array are still left to the particular instantiation to vary.

procedure IntArrayFoo is new Foo(element_type => Integer, array_type => Integer_Array);

So in the case of arrays, you can neatly genericize precisely that which may differ in instantiations. However, trying to do the analoguous with Ada.Containers.Doubly_Linked_List(T).List leads to problems.

Attempt 1 - generic procedure instantiating the doubly_linked_list package

with Ada.Containers.Doubly_Linked_Lists;

package shufit is
   generic
      type element_type is private;
      package int_dll is new Ada.Containers.Doubly_Linked_Lists(Element_Type => Integer);
      type int_dll_type is new int_dll.List;
   procedure Foo (List : in out int_dll_type);
end shufit;

That approach won't work because we can't create a package in the generic section. Even if we could do this, when trying to call this we need to make an int_dll_type outside the function definition and yet matching it - which doesn't seem to work in Ada. In C++, I can have a 'vector' instantiated in two completely different namespaces/classes, and yet they refer to the same type. But in Ada, I don't seem to be able to refer to the equivalent in two different packages, without one including the other.

Attempt 2 - generic procedure instantiating the doubly_linked_list package

with Ada.Containers.Doubly_Linked_Lists;

generic
   type element_type is private;
package shufit is
   package int_dll is new Ada.Containers.Doubly_Linked_Lists(Element_Type => Integer);
   type int_dll_type is new int_dll.List with null record;
   procedure Foo (List : in out int_dll_type);
end shufit;

Having moved the element_type generic up to the package level, and fixed the error 'type derived from tagged type must have extension' with the 'with null record' suffix on the type definition, this compiles but the calling code must use this specifically defined type, which means if we also want a Bar procedure that operates on the same type, it is not possible to make these independently.

package shufit_pack is new shufit(element_type => Integer);
a : shufit_pack.int_dll_type;

Attempt 3 - genericize everything

The only thing I can think of is to just throw all the generics at the function we can imagine. At this point, we know nothing about the type involved, which means we need to specify every function of doubly_linked_list that we need to use.

shufit.ads:

package shufit is
   generic
      type element_type is private;
      type list_type is private;
      with function Length (List : in list_type) return Integer;
   procedure Foo (List : in out list_type);
end shufit;

shufit.adb:

with Ada.Text_IO;

package body shufit is
   procedure Foo (List : in out list_type) is
      i : Integer := Length(List);
   begin
      Ada.Text_IO.Put_Line(Integer'Image(i));
   end Foo;
end shufit;

usage:

package int_dll is new Ada.Containers.Doubly_Linked_Lists(Element_Type => Integer);
type int_dll_type is new int_dll.List with null record;

function IntDLL_Length (List : in int_dll_type) return Integer is
begin
   return Integer(List.Length);
end IntDLL_Length;

procedure shuf_intdll is new shufit.Foo(element_type => Integer, list_type => int_dll_type, Length => IntDLL_Length);

The nice thing about this is that I can make the same function work for arrays as for doubly_linked_lists:

procedure Main
   type IntArray is array (1..10) of Integer;

   function ArrayLength (List : in IntArray) return Integer is
   begin
      return List'Last - List'First + 1;
   end;

   procedure shuf is new shufit.Foo(element_type => Integer, list_type => IntArray, Length => ArrayLength);

   a : IntArray := (others => 5);
begin
   shuf(a);
end Main;

But that's not what I'm trying to achieve. I want something less cumbersome that works for doubly_linked_lists. With this approach, you have to redefine every function of the list type you want to use. In the example I have just defined Length, but typically I want the function to operate on the full interface of doubly_linked_list, which means writing a whole bunch of code identically, just for different doubly_linked_list element_types.

I just want to write the equivalent in Ada to these four lines of C++:

template<typename T>
void Foo(vector<T> t){
   cout << t.size() << endl;
}

Which could be used for vectors of any type:

int main(){
  vector<int> a = {0, 1};
  Foo(a);
  return 0;
}

DeeDee DeeDee · Accepted Answer · 2019-10-02T19:13:38

You might try something like this (see also RM 12.7):

shuffle_list.ads

with Ada.Containers.Doubly_Linked_Lists;

generic
   with package DLL is new Ada.Containers.Doubly_Linked_Lists (<>);
procedure Shuffle_List (List : in out DLL.List);

shuffle_list.adb

with Ada.Containers;      use Ada.Containers;       --  for Count_Type
with GNAT.Random_Numbers; use GNAT.Random_Numbers; 

procedure Shuffle_List (List : in out DLL.List) is
begin   

   if List.Is_Empty then
      return;
   end if;

   --  A poor man's shuffle routine.

   declare

      function Random is
        new Random_Discrete (Count_Type);

      Gen      : Generator;      
      List_New : DLL.List;

   begin

      Reset (Gen);

      while not List.Is_Empty loop
         declare            
            Pos : Count_Type := Random (Gen, 1, List.Length);
            Cur : DLL.Cursor := List.First;            
         begin

            for K in 1 .. Pos - 1 loop
               DLL.Next (Cur);
            end loop;

            --  Move element from one list to the other.
            DLL.Splice
              (Target   => List_New,
               Before   => List_New.First,
               Source   => List,
               Position => Cur);

         end;
      end loop;

      DLL.Move
        (Target => List,
         Source => List_New);

   end;   

end Shuffle_List;

main.adb

with Ada.Text_IO;
with Ada.Containers.Doubly_Linked_Lists;

with Shuffle_List;

procedure Main is

   use Ada.Text_IO;

   package List_Int is
     new Ada.Containers.Doubly_Linked_Lists (Integer);

   procedure Shuffle_List_Int is
     new Shuffle_List (List_Int);

   List : List_Int.List;

begin

   --  Create a list.
   for K in 0 .. 9 loop
      List.Append (K);
   end loop;

   --  Show the list.
   Put_Line ("Input: ");
   for Elem of List loop
      Put (Elem'Image & " ");
   end loop;
   New_Line;

   --  Shuffle the list.
   Shuffle_List_Int (List);

   --  Show the result.
   Put_Line ("Output: ");
   for Elem of List loop
      Put (Elem'Image & " ");
   end loop;
   New_Line;

end Main;

Which yields (depending on the state of the random generator):

output

Input: 
 0  1  2  3  4  5  6  7  8  9 
Output: 
 5  3  2  8  6  9  1  4  7  0

Note: in your question, you refer to both a doubly linked list and an equivalent of std::vector. In Ada, the first is implemented in Ada.Containers.Doubly_Linked_Lists, the latter in Ada.Containers.Vectors.

How would you write an Ada generic function operating on doubly_linked_lists of any type of element?

Attempt 1 - generic procedure instantiating the doubly_linked_list package

Attempt 2 - generic procedure instantiating the doubly_linked_list package

Attempt 3 - genericize everything

1 Answers