From: Guy Steele <[email-masked]>
Date: Wed, 20 May 92 18:03:59 EDT

Proposal for HPF sorting intrinsics

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 20, 1992

The ideas and names here are inspired by APL.  I have used the
term "grade" rather than "rank" because the latter is already used
in the Fortran 90 standard to mean the size of the shape of an array
(that is, the number of dimensions).

GRADE_UP(ARRAY,DIM)

The array may be of type integer, real, or character.

If the optional DIM argument is present, then the result has the same
shape as the ARRAY.  Suppose DIM has the value k; then the result R
has the property that if one computes the array

	B(i1,i2,...,ik,...in)=ARRAY(i1,i2,...,R(i1,i2,...,ik,...,in),...,in)

then for all i1,i2,...,(omit ik),...,in, the vector B(i1,i2,...,:,...,in) is
sorted in ascending order; moreover, R(i1,i2,...,:,...,in) is a permutation of
all the integers in the range LBOUND(ARRAY,k):UBOUND(ARRAY,k).  The sort is
stable; that is, if j < m and B(i1,i2,...,j,...,in) .EQ. B(i1,i2,...,m,...,in),
then R(i1,i2,...,:,...,in) < R(i1,i2,...,:,...,in).

If the optional DIM argument is absent, then the result S is an
array of rank 2, with shape [SIZE(SHAPE(ARRAY)), PRODUCT(SHAPE(ARRAY))]
and the property that if one computes the rank-1 array

	B(k)=ARRAY(S(1,k),S(2,k),...,S(n,k))

where n=SIZE(SHAPE(ARRAY)), then B is sorted in ascending order;
moreover, all columns of S are distinct, that is, if j /= m then
ALL(S(:,j) .EQ. S(:,m)) will be false.  The sort is stable;
if j < m and B(j) .EQ. B(m), then ARRAY(S(1,j),S(2,j),...,S(n,j))
precedes ARRAY(S(1,m),S(2,m),...,S(n,m)) in the array element ordering
of ARRAY.

GRADE_DOWN(ARRAY,DIM)

The array may be of type integer, real, or character.

If the optional DIM argument is present, then the result has the same
shape as the ARRAY.  Suppose DIM has the value k; then the result R
has the property that if one computes the array

	B(i1,i2,...,ik,...in)=ARRAY(i1,i2,...,R(i1,i2,...,ik,...,in),...,in)

then for all i1,i2,...,(omit ik),...,in, the vector B(i1,i2,...,:,...,in) is
sorted in descending order; moreover, R(i1,i2,...,:,...,in) is a permutation of
all the integers in the range LBOUND(ARRAY,k):UBOUND(ARRAY,k).  The sort is
stable; that is, if j < m and B(i1,i2,...,j,...,in) .EQ. B(i1,i2,...,m,...,in),
then R(i1,i2,...,:,...,in) < R(i1,i2,...,:,...,in).  (Yes, that last "<" sign
really should be a "<", not a ">".)

If the optional DIM argument is absent, then the result S is an
array of rank 2, with shape [SIZE(SHAPE(ARRAY)), PRODUCT(SHAPE(ARRAY))]
and the property that if one computes the rank-1 array

	B(k)=ARRAY(S(1,k),S(2,k),...,S(n,k))

where n=SIZE(SHAPE(ARRAY)), then B is sorted in descending order; moreover, all
columns of S are distinct, that is, if j /= m then ALL(S(:,j) .EQ. S(:,m)) will
be false.  The sort is stable; if j < m and B(j) .EQ. B(m), then
ARRAY(S(1,j),S(2,j),...,S(n,j)) precedes (yes, "precedes", not "follows")
ARRAY(S(1,m),S(2,m),...,S(n,m)) in the array element ordering of ARRAY.

----------------------------------------------------------------

Because of the stability requirement, it is not true in general that
GRADE_DOWN(A(1:N)) equals GRADE_UP(A(N:1:-1)).  Indeed, these results
are equal if and only if A contains no duplicate values.

The stability requirement allows one to cascade grading operations in order to
sort on multiple fields.  For example, suppose one had the following derived
type (example taken from section 4.4.1 of the Fortran 90 standard):

      TYPE PERSON
        INTEGER AGE
        CHARACTER (LEN = 50) NAME
      END TYPE PERSON

now consider two arrays of persons:

      TYPE(PERSON), DIMENSION(100000) :: MEMBERS, ROSTERintrinsics-sort-proposal, version 2

Also assume a work vector for indices:

      INTEGER, DIMENSION(100000) :: V

Then the statements

      V = GRADE_UP(MEMBERS%AGE)
      V = V(GRADE_UP(MEMBERS(V)%NAME))
      ROSTER = MEMBERS(V)

cause ROSTER to be a rearrangement of MEMBERS that is sorted
primarily by name and secondarily by age (that is, members with
the same name are grouped together in order of ascending age).
Note that the minor sort field is graded first, and that more
statements like the second one may be inserted to sort on additional
fields.

To list members with the same name in descending order of age,
change the first GRADE_UP to GRADE_DOWN:

      V = GRADE_DOWN(MEMBERS%AGE)
      V = V(GRADE_UP(MEMBERS(V)%NAME))
      ROSTER = MEMBERS(V)