您将如何编写在任何类型的元素的doubly_linked_lists上运行的Ada泛型函数？

Question

如果可能的话，我将如何编写可在任何类型的元素的doubly_linked_lists上运行的Ada泛型函数？下面的函数规范通过限制Array_Type成为给定element_type的数组来说明我想要的东西。

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

在给定一个element_type和严格对应的array_type的情况下，可以从中实例化一个过程，而数组的边界仍然留给特定的实例来改变。

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;
}

Answer 1

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.