generics - 您将如何编写对任何类型元素的双链表进行操作的 Ada 通用函数？

Question

如果可能，我将如何编写一个 Ada 泛型函数来操作任何类型元素的 doubly_linked_lists？以下函数规范通过将 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);

因此在数组的情况下，您可以巧妙地精确泛化那些在实例化中可能不同的内容。但是，尝试使用 Ada.Containers.Doubly_Linked_List(T).List 进行类似操作会导致问题。

尝试 1 - 实例化 doubly_linked_list 包的通用过程

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;

这种方法行不通，因为我们无法在通用部分创建包。即使我们可以这样做，当尝试调用它时，我们需要在函数定义之外创建一个 int_dll_type 并匹配它——这在 Ada 中似乎不起作用。在 C++ 中，我可以在两个完全不同的 namespace /类中实例化一个“向量”，但它们引用相同的类型。但是在 Ada 中，我似乎无法在两个不同的包中引用等价物，而没有一个包含另一个。

尝试 2 - 实例化 doubly_linked_list 包的通用过程

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;

将 element_type 泛型移动到包级别，并修复错误“从标记类型派生的类型必须具有扩展名”以及类型定义上的“带空记录”后缀，此编译但调用代码必须使用此专门定义的类型，这意味着如果我们还想要一个在相同类型上运行的 Bar 过程，则不可能独立地制作这些。

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

尝试 3 - 通用化一切

我唯一能想到的就是把泛型都扔到我们能想象到的函数上。此时，我们对所涉及的类型一无所知，这意味着我们需要指定我们需要使用的 doubly_linked_list 的每个函数。

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;

用法:

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

这样做的好处是我可以为数组创建与 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;

但这不是我要实现的目标。我想要一些不那么麻烦的东西，适用于 doubly_linked_lists。使用这种方法，您必须重新定义要使用的列表类型的每个函数。在示例中，我刚刚定义了 Length，但通常我希望函数在 doubly_linked_list 的完整接口(interface)上运行，这意味着编写一大堆相同的代码，只是针对不同的 doubly_linked_list element_types。

我只想在 Ada 中编写与这四行 C++ 等效的代码:

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

可用于任何类型的向量:

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

Answer 1

你可以尝试这样的事情(另见 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;

ma​​in.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;

产生的结果(取决于随机生成器的状态):

输出

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

注意:在您的问题中，您指的是双向链表和 std::vector 的等价物。在 Ada 中，前者在 Ada.Containers.Doubly_Linked_Lists 中实现，后者在 Ada.Containers.Vectors 中实现。