How best to sort an array of records

General
1

In my online searches I found the best way to sort an array of records is by using Ada.Containers.Generic_Array_Sort and then defining the “<” operator as follows:

type Order_Entry is record
Order_Name : Ada.Strings.Wide_Unbounded.Unbounded_Wide_String;
Order_Status : Ada.Strings.Wide_Unbounded.Unbounded_Wide_String;
end record;

type Order_Type is array (Natural range <>) of Order_Entry;

function “<” (L, R : Order_Entry) return Boolean;

procedure Sort is new Ada.Containers.Generic_Array_Sort (Natural, Order_Entry, Order_Type);

This uses some Ada concepts that are still vague to me, like the fact that you can redefine the “<” operator. Because of my lack of understanding, I am not sure how to modify this sorting function to sort on different entry values in the record like this:

function “<” (L, R : Order_Entry) return Boolean is
begin
return L.Order_Name < R.Order_Name;
–return L.Order_Status < R.Order_Status;
end “<”;

As you can see, if I want to sort the array of records based on “Order_Status,” I have to comment out that line and then recompile. Is there a better way to switch between sorting based on different entry values within an array of records?

2

Ah!
This is what the function that you pass to Generic_Array_Sort is.
Allow me to simplify things a bit and walk you through.

Consider the following:

Type Vector is Array(Positive range <>) of Natural;
Procedure Bubble( Object : in out Vector ) is
Begin
  For Outer in Object'First..Natural'Pred(Object'Last) loop
    For Inner in Outer..Object'Last loop
      if Object(Outer) > Object(Inner) then
        Swap:
        Declare
          Temp: Constant Natural:= Object( Outer );
        Begin
          Object( Outer ):= Object( Inner );
          Object( Inner ):= Temp;
        End Swap;
      end if;
    End loop;
  End loop;
End Bubble;

Now, we have a simple Bubble-sort, and we are swapping the items only when the second (“Inner”) is greater than the first (“Outer”), using the ">"-operator, therefore yielding a ascending sort; so in order to make a descending sort, we would have to copy everything and change the operator in the if-condition to "<". — Generics allow us to do this, using functions as a formal-parameter; like so:

Generic
  with Function ">"( Left, Right: Natural ) return Boolean;
Procedure Bubble( Object : in out Vector ) is
Begin
  For Outer in Object'First..Natural'Pred(Object'Last) loop
    For Inner in Outer..Object'Last loop
      if Object(Outer) > Object(Inner) then
        Swap:
        Declare
          Temp: Constant Natural:= Object( Outer );
        Begin
          Object( Outer ):= Object( Inner );
          Object( Inner ):= Temp;
        End Swap;
      end if;
    End loop;
  End loop;
End Bubble;

Procedure Asc  is new Bubble( ">" => ">" );
Procedure Desc is new Bubble( ">" => "<" );

Above we make two instantiations Asc and Desc to to the sorting, passing in the appropriate operators for the parameter named ">".— That is enough to address the generic part of your question, but there’s another part that you likely missed, and that is defining your operators!

Let’s say that we wanted to make a rule that “evens are always less than odds”, we can do this with:

Function Evens_Over_Odds( Left, Right: Natural ) return Boolean is
  Left_Even  : Boolean renames "="( Left rem 2, 0 );
  Right_Even : Boolean renames "="( Right rem 2, 0 );
Begin
  if Left_Even = Right_Even then
    return Left < Right;
  else
    return Left_Even;
  end if;
End Evens_Over_Odds;

We can then say:

Procedure Evens is new Bubble( ">" => Evens_Over_Odds );

So, with that you now have enough to answer your question: simply make the comparison function you need, and pass that as your comparator parameter.

4 Likes
3

Use a custom data structure. Add integrated indices for different sorting criteria, basically sorted arrays of Order_Entry access types. [ In-place array sorting is a very bad idea.] You can use one index (the main index) as the items holder.

Binary search is the common method to keep the indices when new item is added or use an ordered set, e.g. Ada.Containers.Ordered_Sets,

One of Ada type system strengths is that pointers are typed. So you can declare an access type for each index with its own operations “<” and “=”.

Do not use unbounded strings. Fixed length strings are much faster and you will have control over memory allocation:

type Order_Entry (Name_Length, Status_Length : Positive) is record
   Name : String (1..Name_Length);
   Status : String (1..Status_Length);
end record;

type By_Name is access Order_Entry;
function "<" (Left, Right : By_Name) return Boolean;
function "=" (Left, Right : By_Name) return Boolean;
package By_Name_Index is new Ada.Containers.Ordered_Sets (By_Name);

etc.

1 Like
4

I wish Ada allowed the following:-

type Order_Entry (<>) is record
   Name : String;
   Status : String;
end record;

So that you could simply do:-
Append (My_List, (Name => "Beer", Status => "Foamy"));

5

Typically you will implement two comparison functions and use them to create two instances of Ada.Containers.Generic_Array_Sort:

function Less_Name (Left : in Order_Entry; Right : in Order_Entry) return Boolean is
   (Left.Order_Name < Right.Order_Name);
procedure Sort_Name is new Ada.Containers.Generic_Array_Sort
   (Index_Type => Natural, Element_Type => Order_Entry, Array_Type => Order_Type, "<" => Less_Name);

function Less_Status (Left : in Order_Entry; Right : in Order_Entry) return Boolean is
   (Left.Order_Status < Right.Order_Status);
procedure Sort_Status is new Ada.Containers.Generic_Array_Sort
   (Index_Type => Natural, Element_Type => Order_Entry, Array_Type => Order_Type, "<" => Less_Status);
2 Likes
6

It looks interesting. Indeed, why not

new Order_Entry (Name => "Beer", Status => "Foamy");

The missing discriminants would be anonymous.

1 Like
7

Ok, so the reason such cannot exist is because there is no bounding of the discriminants precisely because it is anonymous.

 S : String := "Steve"; -- is S:String(1..5):= ('S', 't', 'e', 'v', 'e');

Remember that the unconstrained subtyped variable takes its constraints from the value you initialize it with, and the constraints are needed so that the compiler can allocate space for that item.

For small records (one or two fields) you can use the operators/functions to do the lifting of setting the discriminants:

type Order_Entry (Name_Length, Status_Length : Natural) is record
   Name   : String(1..Name_Length);
   Status : String(1..Status_Length);
end record;

Function "**"(Left, Right : String) return Order_Entry is
( Name_Length   => Left'Length,
  Status_Length => Right'Length, 
  Name          => Left,
  Status        => Right
);

for records with more than one or two fields, a function that produces the proper value from the parameters, which gets you the advantage over a direct aggregate in that you can use the parameters to take care of the linked discriminants within the aggregate.

8 
Order_Entry'(Name => "Beer", Status => "Foamy")

is constrained.

1 Like
9

You can use Unbounded_Strings and overload the “+” unary operator:

function "+"(Item : String) return Unbounded_String
   renames To_Unbounded_String;
function "+"(Item : Unbounded_String) return String
   renames To_String;

Then it becomes:

Append (My_List, (Name => +"Beer", Status => +"Foamy"));

You can use the + operator to get the strings back out of Name and Status as well:

Put_Line(+My_List(1).Name);  -- assuming it is a vector here

If you want to still use the name String for your types, you can do a local redefinition of the string type:

with Ada.Text_IO; use Ada.Text_IO;  
with Ada.Strings.Unbounded;
with Ada.Containers.Vectors;

procedure Test is

	package My_Package is
	
		-- You can temporarily redefine the String type.  Any use of String
		-- after this line in this package (and in child packages) will 
		-- use this type instead of the standard String type. If you need to 
		-- reference the standard String type still, then Standard.String
		-- will work
		type String is new Ada.Strings.Unbounded.Unbounded_String;
		
		function "+"(Item : Standard.String) return String
			renames To_Unbounded_String;
		function "+"(Item : String) return Standard.String
			renames To_String;
			
		type Order_Entry is record
		   Name   : String;
		   Status : String;
		end record;
		
		package Order_Vectors is new Ada.Containers.Vectors(Positive, Order_Entry);
		subtype Order_Vector is Order_Vectors.Vector; 
	
	end My_Package;

    -- Outside of My_Package, 'String' refers to the standard String type
	
	My_List : My_Package.Order_Vector;
	
	use all type My_Package.String;  -- This brings in the "+" operators
	
begin
	My_List.Append((Name => +"Beer", Status => +"Foamy"));
end Test;

Though you will be have to be careful if you use My_Package anywhere as you local String type could conflict (you can always qualify the type though if that becomes a problem).

10

Having value-constructing operators/functions is all well and good but it feels kludgy (to me) and won’t help with:-

generic
   type Status_Type (<>) is private;
package Order_Handling is
   type Order_Entry (<>) is record
      Name : String;
      Status : Status_Type;
   end record;
11

This a different issue. Ada’s initialisation model unfortunately lacks the stage of determining the constraints (and allocation):

  • Determine constraints from the parameters and allocate
  • Initialize components using parameters

E.g. Ada could have attribute X’Constraints returning a record type with discriminants, bounds, tag (for class-wides) of X. Then a new instance could be created using these constraints:

Y : T (X'Constraints);

12

If I can declare:

Order_Name : String := Name_Param;
Order_Status : Status_Type := Status_Param;

Then I should also be able to declare:
Order : Order_Entry := (Name_Param, Status_Param);

Or call:
Append (My_List, (Name_Param, Status_Param));

13

It is a magic of array types (and class-wide types) which record types lack.

14

Maybe the new Ada 2022 literals could be of some kind of use here? User-Defined Literals — learn.adacore.com

15

So should I use your bubble sort instead of the Generic_Array_Sort? I was hoping to use that instead of writing my own sorting algorithm. I was hoping someone could explain how Generic_Array_Sort works. For example, I don’t understand how Generic_Array_Sort’s arguments are defined. How do you even know that it takes three arguments? When I open the specification it has this:

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

So I thought that the fourth parameter would be the “<” and I could try this for descending sorting:

procedure Sort is new Ada.Containers.Generic_Array_Sort ( Natural, Order_Entry, Order_Type, “<” => “>”);

But when I try this I get a compilation error:

error: no visible subprogram matches the specification for “<”

I still have a lot of basics to master, like I don’t understand how generics work.

16

“Should” is a hard question to answer, it really depends on the qualities you need in your program.

Ok, so there’s a paper on explaining generics here.

You are correct in that the fourth parameter is the less-than operator, let’s do a quick overview of everything first, the numbers below corresponding to the numbers commented in above:

  1. The Generic keyword, introducing the formal parameters;
  2. A discrete type, named Index;
  3. A non-limited, non-discriminated type, named Element;
  4. An array, unconstrained, indexed by Index, of type Element;
  5. The less-than operator, comparing values of Element, defaulting to a visible "<" at the point of instantiation;
  6. The item paired to the Generic of #1, a procedure taking a parameter of the array in #4.

So, this gives you enough to understand the message you received:

So, what the compiler is telling you is that there is no "<"-operator visible which matches… and given what you’ve shown, there is no ">", only a "<".

So, one thing you can do, and I’ve used this in several places, when you have a lot of the-same-stuff, is factor out into a generic —in a VM, I used this technique generalized for binary operators— and then use renames-as-a-body and we can do this with your code:

-- Specification:
Function ">"(Left, Right : In Order_Entry) return Boolean;

Generic
  with Function "="(Left, Right : Ada.Strings.Wide_Unbounded.Unbounded_Wide_String) return Boolean is <>;
  with Function "<"(Left, Right : Ada.Strings.Wide_Unbounded.Unbounded_Wide_String) return Boolean is <>;
Function Compare(Left, Right : In Order_Entry) return Boolean;
-- Implementation:
Function Compare(Left, Right : In Order_Entry) return Boolean is
Begin
  if Left.Order_Name = Right.Order_Name then
    return Left.Order_Status < Right.Order_Status;
  else
    return Left.Order_Name < Right.Order_Name;
  end if;
End Compare;

-- I may be misremembering the actuals for string comparision here...
-- Also, this is a place where named-association really helps:
Function GT is new Compare(
   "="  => Ada.Strings.Equal_Case_Insensitive, 
   "<"  => Ada.Strings.Less_Than_Case_Insensitive 
  );

Function ">"(Left, Right : In Order_Entry) return Boolean
  renames GT;

Read that linked paper, I think that’ll clear a lot of stuff up; there’s two others in the series: one on packages, the other on Ada’s OOP.

1 Like
17

Were you (@codiac) expecting that defining a “<” operator would automatically generate a “>” operator? (never mind that even if it did the opposite of “<” is “>=”, which wouldn’t work here). Ada does this for “=”: in fact you can’t define “/=”.

1 Like
18

Ada reference manual requires complexity of an implementation no worse than O(n**2). That is the complexity of the bubble sort. So no, you should not.

In any case expect a catastrophic performance. Swapping Order_Entry would require deep copy of Unbounded_String or bounded size strings depending on how you declare Order_Entry and that with O(n**2)!

You need a visible function:

function ">" (Left, Right : Order_Entry) return Boolean;

provided, you meant descending order. “<” in the message refers the parameter name.

1 Like
19

Yes, the paper is really clearing things up. It is really well-organized. I especially like the color coding in Figure 3. Thank you so much!

20

Thank you, dmitry-kazakov. I made the changes like you indicated and it compiled and worked the first try. That never happens!