Rationale for Ada 2012

John Barnes
Contents   Index   References   Search   Previous   Next 

8.7 Sorting

Ada 2005 provides two containers for sorting arrays; one is for unconstrained array types and one is for constrained array types. The specification of the unconstrained one is
   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);
pragma Pure(Ada.Containers.Generic_Array_Sort);
This does the obvious thing. It sorts the array Container so that the components are in the order defined by the generic parameter "<".
We could for example sort the letters in a string into alphabetical order. We would declare
procedure String_Sort is
   new Ada.Containers.Generic_Array_Sort (Positive, Character, String);
and then if we had a string such as
Bigpet: String := "rabbit";
we could apply String_Sort to it thus
and the value in Bigpet will now be "abbirt".
That is all in Ada 2005. However, sorting doesn't just apply to arrays and Ada 2012 provides a much more flexible approach. An additional container is provided whose specification is
   type Index_Type is (<>);
   with function Before(Left, Right: Index_Type) return Boolean;
   with procedure Swap(Left, Right: in Index_Type);
procedure Ada.Containers.Generic_Sort(First, Last: Index_Type'Base);
pragma Pure(Ada.Containers.Generic_Sort);
This can be used to sort any indexable structure and not just arrays. The generic parameters define the required ordering through the parameter Before much as expected. The cunning trick however, is that the means of interchanging two items in the structure is provided by the parameter Swap.
As an illustration we can use this on the array Bigpet. We can use an expression function for BP_Before and so we write
function BP_Before(L, R: Positive) return Boolean is
   (Bigpet(L) < Bigpet(R));
procedure BP_Swap(L, R: in Positive) is
   Temp: Character;
   Temp := Bigpet(L);
   Bigpet(L) := Bigpet(R);
   Bigpet(R) := Temp;
end BP_Swap;
procedure BP_Sort is
   new Ada.Containers.Generic_Sort (Positive, BP_Before, BP_Swap);
and then we actually do the sort by
BP_Sort(Bigpet'First, Bigpet'Last);
That may seem to be rather a struggle but the key point is that the technique can be used to sort items in any indexable structure such as a vector container.
Suppose we have a number of records of a type Score which might be
type Score is
      N: Natural := 0;
      OS: Other_Stuff;
   end record;
and we declare a vector container to hold such objects thus
package Scores is new Ada.Containers.Vectors(Natural, Score);
My_Vector: Scores.Vector;
Now assume that we have added various objects of the type Score to our vector and that we decide that we would like them sorted into order determined by their component N.
We write
function MV_Before(L, R: Natural) return Boolean is
   (Scores.Element(My_Vector, L).N < Scores.Element(My_Vector, R).N);
procedure MV_Swap(L, R: in Natural) is
   Scores.Swap(My_Vector, L, R);
end MV_Swap;
procedure MV_Sort is
   new Ada.Containers.Generic_Sort (Natural, MV_Before, MV_Swap);
and then we do the sort by
MV_Sort(Scores.First_Index(My_Vector), Scores.Last_Index(My_Vector));
Note that the vectors container package conveniently already has a procedure Swap.
This vector example is not very exciting because it might be recalled that the vectors containers already have their own internal generic sort. To use it on this example we would have to write
package MV_Sorting is
   new Scores.Generic_Sorting(MV_Before);
which is somewhat simpler. However, note that this sorts the whole vector. If we only wanted to sort part of it, say from elements in index range P to Q then it cannot be used. But that would be easy with the new one since we would simply write
MV_Sort(P, Q);
Note that curiously this does not need to mention My_Vector.

Contents   Index   References   Search   Previous   Next 
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association:


and   Ada-Europe: