很難索引陣列-有解無憂

我試圖撰寫一個Heap_Sort與Ada.Containers.Generic_Array_Sort（即 with type Index_Type is (<>)）具有類似規范的通用程序，但我不確定是否有處理這種型別索引的好方法。如果我限制Index_Typeto Positive，這沒什么大不了的：

generic
   type Element is private;
procedure Generic_Swap (Left, Right : in out Element);

procedure Generic_Swap (Left, Right : in out Element) is
   Buffer : constant Element := Left;
begin
   Left := Right;
   Right := Buffer;
end Generic_Swap;

generic
   type Element_Type is private;
   type Array_Type is array (Positive range <>) of Element_Type;
   with function ">" (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Heap_Sort (Data : in out Array_Type);

procedure Generic_Heap_Sort (Data : in out Array_Type) is
   function Left_Heap_Index (Root : Positive) return Positive is
      (Root * 2 - Data'First   1);

   function Right_Heap_Index (Root : Positive) return Positive is
      (Root * 2 - Data'First   2);

   procedure Swap is new Generic_Swap (Element_Type);

   procedure Heap_Insert (Index, Heap_Last : in Positive) is
      Left  : constant Positive := Left_Heap_Index (Index);
      Right : constant Positive := Right_Heap_Index (Index);
      Swap_Index : Positive := Index;
   begin
      if Left <= Heap_Last and then Data (Left) > Data (Swap_Index) then
         Swap_Index := Left;
      end if;
      if Right <= Heap_Last and then Data (Right) > Data (Swap_Index) then
         Swap_Index := Right;
      end if;
      if Swap_Index /= Index then
         Swap (Data (Swap_Index), Data (Index));
         Heap_Insert (Swap_Index, Heap_Last);
      end if;
   end Heap_Insert;
begin
   for Index in reverse Data'First .. (Data'Last - Data'First) / 2 loop
      Heap_Insert (Index, Data'Last);
   end loop;
   for Index in reverse Data'First   1 .. Data'Last loop
      Swap (Data (Data'First), Data (Index));
      Heap_Insert (Data'First, Index - 1);
   end loop;
end Generic_Heap_Sort;

但即便如此，我也必須考慮到并非所有陣列都Positive range <>從 1 inLeft_Heap_Index和Right_Heap_Index函式開始。理想情況下，我希望將任何陣列引數Data視為 range 中的元素序列，1 .. Data'Length而不是-5 .. -3or JAN, FEB, MAR，即使陣列型別是由某些離散形式型別的值索引的(<>)。是否可以不定義將表示基于 1 的索引To_Index的System.Min_Int .. System.Max_Int整數轉換為的函式Index_Type，類似于 GNAT 實作中使用的函式Ada.Containers.Generic_Constrained_Array_Sort？

只是為了澄清，下面的代碼有效，但所有的呼叫Convert正是我試圖避免的東西。

generic
   type Element_Type is private;
procedure Generic_Swap (Left, Right : in out Element_Type);

procedure Generic_Swap (Left, Right : in out Element_Type) is
   Buffer : constant Element_Type := Left;
begin
   Left := Right;
   Right := Buffer;
end Generic_Swap;

generic
   type Index_Type is (<>);
   type Element_Type is private;
   type Array_Type is array (Index_Type range <>) of Element_Type;
   with function ">" (Left, Right : Element_Type) return Boolean is <>;
procedure Heap_Sort (Data : in out Array_Type);

procedure Heap_Sort (Data : in out Array_Type) is
   subtype Integer_Index is Positive;

   function Convert (Index : Index_Type) return Integer_Index is
      (Integer_Index'First   Index_Type'Pos (Index) - Index_Type'Pos (Data'First));

   function Convert (Index : Integer_Index) return Index_Type is
      (Index_Type'Val (Index_Type'Pos (Data'First)   Index - Integer_Index'First));

   procedure Swap is new Generic_Swap (Element_Type);

   procedure Heap_Insert (Index, Heap_Last : in Integer_Index) is
      Left_Heap  : constant Integer_Index := Index * 2 - Convert (Data'First)   1;
      Right_Heap : constant Integer_Index := Index * 2 - Convert (Data'First)   2;
      Swap_Index : Integer_Index := Index;
   begin
      if Left_Heap <= Heap_Last and then Data (Convert (Left_Heap)) > Data (Convert (Swap_Index)) then
         Swap_Index := Left_Heap;
      end if;
      if Right_Heap <= Heap_Last and then Data (Convert (Right_Heap)) > Data (Convert (Swap_Index)) then
         Swap_Index := Right_Heap;
      end if;
      if Swap_Index /= Index then
         Swap (Data (Convert (Swap_Index)), Data (Convert (Index)));
         Heap_Insert (Swap_Index, Heap_Last);
      end if;
   end Heap_Insert;
begin
   for Index in reverse Convert (Data'First) .. (Convert (Data'Last) - Convert (Data'First)) / 2 loop
      Heap_Insert (Index, Convert (Data'Last));
   end loop;
   for Index in reverse Index_Type'Succ (Data'First) .. Data'Last loop
      Swap (Data (Data'First), Data (Index));
      Heap_Insert (Convert (Data'First), Convert (Index_Type'Pred (Index)));
   end loop;
end Heap_Sort;

uj5u.com熱心網友回復：

您可以查看離散型別的屬性 Pos 和 Val。您可以將索引與基于 0 的整數位置進行轉換，以便您可以按照您認為合適的方式進行數學運算，然后轉換回 index_type 值。請注意，它們相對于整個 Index_Type 的索引為 0，而不是陣列的第一個元素，因此您仍然需要使用 'First 和 'Last 來處理可以從任何索引開始的陣列，但您也可以封裝它計算到一個函式中，您可以在其中提供您希望邏輯使用的數字索引，并使用函式內部的 Val 方面進行轉換。

例如，如果您想要基于 1 索引的數學索引，您可以創建一個在 Generic_Heap_Sort 程序中宣告的 Swap 程序，如下所示：

   procedure Swap(L,R : Positive) is
        -- Use a -1 to adjust from 1-indexed indices to 0-indexed indices
        L_Index : constant Index_Type   := Index_Type'Val(L-1   Index_Type'Pos(Data'First));
        R_Index : constant Index_Type   := Index_Type'Val(R-1   Index_Type'Pos(Data'First));
        Buffer  : constant Element_Type := Data(L_Index);
   begin
        Data(L_Index) := Data(R_Index);
        Data(R_Index) := Buffer;
   end Swap;

并積極地做你的外部數學。

您還可以查看快捷方式的 'Succ 和 'Pred 屬性，以對索引執行 1 和 -1，而無需在兩者之間進行轉換。

也可以看看：

http://www.ada-auth.org/standards/2xrm/html/RM-3-5-5.html#I1764

http://www.ada-auth.org/standards/2xrm/html/RM-3-5.html#I1632

uj5u.com熱心網友回復：

這是您演算法的相當簡單的翻譯，翻譯

Root * 2 - Data'First   1

進入

Index_Type'Val
  (Index_Type'Pos (Root) * 2 - Index_Type'Pos (Data'First)   1)

（’Pos回傳與輸入在列舉中的位置相對應的從零開始的整數，’Val反之亦然）。

with Ada.Text_IO; use Ada.Text_IO;
procedure Gdi512 is

   generic
      type Element is private;
   procedure Generic_Swap (Left, Right : in out Element);

   procedure Generic_Swap (Left, Right : in out Element) is
      Buffer : constant Element := Left;
   begin
      Left := Right;
      Right := Buffer;
   end Generic_Swap;

   generic
      type Element_Type is private;
      type Index_Type is (<>);
      type Array_Type is array (Index_Type range <>) of Element_Type;
      with function ">" (Left, Right : Element_Type) return Boolean is <>;
   procedure Generic_Heap_Sort (Data : in out Array_Type);

   procedure Generic_Heap_Sort (Data : in out Array_Type) is

      function Left_Heap_Index (Root : Index_Type) return Index_Type is
        (Index_Type'Val
           (Index_Type'Pos (Root) * 2 - Index_Type'Pos (Data'First)   1));

      function Right_Heap_Index (Root : Index_Type) return Index_Type is
        (Index_Type'Val
           (Index_Type'Pos (Root) * 2 - Index_Type'Pos (Data'First)   2));

      procedure Swap is new Generic_Swap (Element_Type);

      procedure Heap_Insert (Index, Heap_Last : in Index_Type) is
         Left  : constant Index_Type := Left_Heap_Index (Index);
         Right : constant Index_Type := Right_Heap_Index (Index);
         Swap_Index : Index_Type := Index;
      begin
         if Left <= Heap_Last and then Data (Left) > Data (Swap_Index) then
            Swap_Index := Left;
         end if;
         if Right <= Heap_Last and then Data (Right) > Data (Swap_Index) then
            Swap_Index := Right;
         end if;
         if Swap_Index /= Index then
            Swap (Data (Swap_Index), Data (Index));
            Heap_Insert (Swap_Index, Heap_Last);
         end if;
      end Heap_Insert;

   begin
      for Index in reverse Data'First ..
        Index_Type'Val
          ((Index_Type'Pos (Data'Last) - Index_Type'Pos (Data'First)) / 2)
      loop
         Heap_Insert (Index, Data'Last);
      end loop;
      for Index in reverse Index_Type'Succ (Data'First) .. Data'Last loop
         Swap (Data (Data'First), Data (Index));
         Heap_Insert (Data'First, Index_Type'Pred (Index));
      end loop;
   end Generic_Heap_Sort;

   type Alpha is
     (A, B, C, D, E, F, G, H, I, J, K, L, M,
      N, O, P, Q, R, S, T, U, V, W, X, Y, Z);

   type Arry is array (Alpha range <>) of Integer;

   procedure Sort_Up is new Generic_Heap_Sort (Element_Type => Integer,
                                               Index_Type => Alpha,
                                               Array_Type => Arry);
   procedure Sort_Down is new Generic_Heap_Sort (Element_Type => Integer,
                                                 Index_Type => Alpha,
                                                 Array_Type => Arry,
                                                 ">" => "<");

   Data : Arry := (D => 9,
                   E => 8,
                   F => 7,
                   G => 6,
                   H => 5,
                   I => 4,
                   J => 3,
                   K => 2);

begin
   Sort_Up (Data);
   for J in Data'Range loop
      Put_Line (J'Image & " " & Data (J)'Image);
   end loop;
   New_Line;
   Sort_Down (Data);
   for J in Data'Range loop
      Put_Line (J'Image & " " & Data (J)'Image);
   end loop;
end Gdi512;

輸出：

$ ./gdi512 
D  2
E  3
F  4
G  5
H  6
I  7
J  8
K  9

D  9
E  8
F  7
G  6
H  5
I  4
J  3
K  2

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/405560.html

標籤：

上一篇：基于泛型型別的WPF資料模板選擇器

下一篇：expressmongoDB聚合總和