How to Sort Two-dimensional Array Based on Column Index

General
1

I’m trying to sort a two dimensional array based on an arbitrary column like this:

order_organizer.adb

with Ada.Wide_Text_IO; use Ada.Wide_Text_IO;
with Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Strings.Wide_Unbounded; use Ada.Strings.Wide_Unbounded;

with PragmARC.Line_Fields;

with Sorting_Tools;

procedure Order_Organizer is
   -- User input value to select a given column of data in the two-dimensional array
   i : Integer := 1;

   Num_Orders_In_Order_Array : Integer := 0;
   Index, Starting_Point, Current_Index : Integer := 1;
   
   Header_String, Order_Entry_String : Unbounded_String;
   In_File_Name : String := "MegaOrder_dummy.txt";
   Out_File_Name : String := "MegaOrder_new.txt";

   Header_List, Parsed_Field_List : PragmARC.Line_Fields.Field_List;
   Order_File_Handle, New_Order_File_Handle: File_Type;
   Mega_Order_Array : Sorting_Tools.Order_Entry_Type (Integer range 1 .. Sorting_Tools.Max_Order_Size);
  
begin
   -- Open the MegaOrder file.
   Open (Order_File_Handle, Mode => In_File, Name => In_File_Name);

   -- Read and strip out the the header.
   Header_List := PragmARC.Line_Fields.Parsed (Get_Line (Order_File_Handle), '|');
   while not End_Of_File (Order_File_Handle) loop
      Parsed_Field_List := PragmARC.Line_Fields.Parsed (Get_Line (Order_File_Handle), '|');
      Mega_Order_Array (Index)(1) := Parsed_Field_List (1);
      Mega_Order_Array (Index)(2) := Parsed_Field_List (2);
      Mega_Order_Array (Index)(3) := Parsed_Field_List (3);
      Index := Index + 1;
   end loop;
   Num_Orders_In_Order_Array := Index-1;

   Sorting_Tools.Sort_By_Index (Mega_Order_Array);
   --Sorting_Tools.Sort_By_Index (Mega_Order_Array, i);

   Current_Index := Starting_Point;
   Create (New_Order_File_Handle, Out_File, Out_File_Name);
   Put_Line (New_Order_File_Handle, "orderName|orderStatus|orderQuantity");
   for Index in 1 .. Num_Orders_In_Order_Array loop
      
      Put_Line (New_Order_File_Handle, To_Wide_String (
              Mega_Order_Array (Current_Index)(1)
      & "|" & Mega_Order_Array (Current_Index)(2) 
      & "|" & Mega_Order_Array (Current_Index)(3)));

      Current_Index := Current_Index + 1;
   end loop;
   Close (New_Order_File_Handle);

   Put_Line ("End of program.");
end Order_Organizer;

sorting_tools.adb

with Ada.Strings.Wide_Unbounded; use Ada.Strings.Wide_Unbounded;
with Ada.Text_IO;           use Ada.Text_IO;
with Ada.Containers.Generic_Array_Sort;

package body Sorting_Tools is
   
   function Index_Asc (L, R : Order_Entry_Array) return Boolean is
   --function Index_Asc (L, R : Order_Entry_Array; i: Integer) return Boolean is
	begin
      --return L(1) < R(1);
      return L(3) < R(3);
      --return L(i) < R(i);
	end Index_Asc;
end Sorting_Tools;

sorting_tools.ads

with Ada.Strings.Wide_Unbounded;
with Ada.Containers.Generic_Array_Sort;
with Ada.Wide_Characters;
with Ada.Wide_Text_IO;

package Sorting_Tools is
	type Order_Entry_Array is array (1 .. 5) of Ada.Strings.Wide_Unbounded.Unbounded_Wide_String;
	type Order_Entry_Type is array (Natural range <>) of Order_Entry_Array;

	Max_Order_Size: constant Integer := 6;
	
	function Index_Asc (L, R : Order_Entry_Array) return Boolean;
	-- function Index_Asc (L, R : Order_Entry_Array; i : Integer ) return Boolean;
	
	procedure Sort_By_Index is new Ada.Containers.Generic_Array_Sort
	 	(Natural, Order_Entry_Array, Order_Entry_Type, "<" => Index_Asc);
end Sorting_Tools;

MegaOrder_dummy.txt

orderName|orderStatus|orderQuantity
"name13"|"good"|3
"name5"|"good"|6
"name1"|"missing"|4
"name5"|"good"|2
"name6"|"best"|1
"name2"|"good"|44

MegaOrder_new.txt

orderName|orderStatus|orderQuantity
name6|best|1
name5|good|2
name13|good|3
name1|missing|4
name2|good|44
name5|good|6

The problem I’m having is that I don’t know how to pass a column index into the sorting function to tell the generic array sort library to sort on a designated column (e.g. 1, 2, 3). Maybe I need to use a different sorting algorithm. I just don’t want to have to write 50 different function definitions for each column if I had, say, 50 columns in the array I was trying to sort. Note how I have lines of code commented out for how I wish this would work, based on a user-inputted column index.

2

Then you don’t want to use Ada.Containers.Generic_Array_Sort… at least not directly.
Take a look at the formal parameters:

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 Ada.Containers.Generic_Array_Sort (Container : in out Array_Type)

As you can see, the formal parameters indicate that the Array_Type is singly indexed, by an Index_Type value. But this needn’t be a “showstopper”… we will need to employ a bit of “dark-magic” though:

Type Matrix is array (Positive range <>, Positive range <>) of Integer;
Procedure Sort_2D( Object : in out Matrix ) is
  Type Columns is Array ( Object'Range(1) ) of Integer;
  Type Rows    is Array ( Object'Range(2) ) of Columns;
  Alt_Object : Rows
    with Import, Address => Object'Address;
  Procedure Sort_Rows is new .Ada.Containers.Generic_Array_Sort
    ( Index_Type   => Positive,
      Element_Type => Columns;
      Array_Type   => Rows,
      others => <>
    );
  Procedure Sort_Cols is new .Ada.Containers.Generic_Array_Sort
    ( Index_Type   => Positive,
      Element_Type => Integer;
      Array_Type   => Columns,
      others => <>
    );
Begin
  -- if columns should NOT be sorted, then delete the for-loop:
  for Line of Alt_Object loop
    Sort_Cols( Line );
  end loop;
  Sort_Rows( Alt_Object );
End Sort_2D;

There you are.
You can, of course, make a sort for the particular “shape” of your array, manually.

3

Which should not be used anyway, as was explained before in another discussion. It is not the way to deal with relational tables. However hitting the head against the wall has certain educational effect too. :grinning:

4

So if it isn’t adviseable to sort this data using generic array sort, then would you please remind me of how to best sort this table data?

5

Why would you call this dark magic? I thought Ada’s strength was that it was clear and easy to read. I am concerned that this code is obscure. Or is it just that I am not familiar enough with the language?

6

Because it’s using memory-overlays.

It is clear what the code is doing.
The overlay is saying: “Instead of looking at this as Array(x,y) of Integer, look at this as Array (y) of Array(x) of Integer” — IOW, it’s just factoring out an index.

There’s a few other “dark magic” tricks that aren’t so complex such as:

Type Matrix is Array(Positive range <>, Positive range <>) of Integer;

Function Transpose(M : Matrix) return Matrix is
    subtype Constrained is Matrix(M'Range(2), M'Range(1));
    Type Xposed is new Matrix with Convention => Fortran;
    Temp   : Xposed := Xposed(M);
    Result : Constrained with Import, Address => Temp'Address;
 begin
    Return Result;
 end Transpose;

— which relies on the fact that Fortran convention is Column-major, while Ada’s is Row-major. So, converting between the two is transposition, (Remember that in-memory, the elements are linear, with the indices offsetting as-needed… as xy = yx, all we need to do is “reverse” the indices and let the type-conversion take care of the “view”.)

1 Like
7

By never ever sorting it. You define relational table with three columns. For each column you create an index. When adding a row indices are kept ordered. Index is a sorted array or list of pointers to the table rows.

You cannot use the same ordering for all columns, obviously. Names are unique, other fields are not. The “<” function for each column is different.

It does not make sense to use column numbers. Names of the columns are as good.

The package interface may look this way:

with Ada.Finalization;
with Generic_Set;

package Order_Lists is
   type Order_Entry (Name_Length, Status_Length : Natural) is record
      Name     : String (1..Name_Length);
      Status   : String (1..Status_Length);
      Quantity : Positive;
   end record;
   type Order_List is tagged limited private;
   procedure Add
             (  List         : in out Order_List;
                Name, Status : String;
                Quantity     : Positive
             );
   function Get_By_Name (List : Order_List; Index : Positive)
      return Order_Entry;
   function Get_By_Status (List : Order_List; Index : Positive)
      return Order_Entry;
   function Get_By_Quantity (List : Order_List; Index : Positive)
      return Order_Entry;
   function Get_Size (List : Order_List) return Natural;
private
   type By_Name_Ptr is access Order_Entry;
   function "<" (Left, Right : By_Name_Ptr) return Boolean;
   function Equal (Left, Right : By_Name_Ptr) return Boolean;
   package By_Name_Sets is new Generic_Set (By_Name_Ptr, null, "=" => Equal);

   type By_Status_Ptr is access all Order_Entry;
   function "<" (Left, Right : By_Status_Ptr) return Boolean;
   package By_Status_Sets is new Generic_Set (By_Status_Ptr, null);

   type By_Quantity_Ptr is access all Order_Entry;
   function "<" (Left, Right : By_Quantity_Ptr) return Boolean;
   package By_Quantity_Sets is new Generic_Set (By_Quantity_Ptr, null);

   type Order_List is
      new Ada.Finalization.Limited_Controlled with
   record
      By_Name     : By_Name_Sets.Set;
      By_Status   : By_Status_Sets.Set;
      By_Quantity : By_Quantity_Sets.Set;
   end record;

   overriding procedure Finalize (List : in out Order_List);
end Order_Lists;

In a relational database you can add and remove columns. Which is merely adding removing an index.

1 Like
8

Thanks for you response and clarification. I will experiment with this to see if I can make sense out of it.