Rationale for Ada 2012
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
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);
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
String_Sort(Bigpet);
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
generic
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;
begin
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
record
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
begin
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);
MV_Sorting.Sort(My_Vector);
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.
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by:
