Subject: sorting intrinsics

From: Guy Steele <[email-masked]>
Date: Wed, 6 May 92 15:44:06 EDT

Proposal for HPF sorting intrinsics

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 6, 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.  [Alternate spec:
the array may be of any type for which the operator .LT. has been defined?]

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.

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.

Question: should stability be guaranteed?

GRADE_DOWN(ARRAY,DIM)

Same as GRADE_UP, with "ascending" replaced by "descending".

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

An alternate approach:

First define the utility intrinsic

INDEX(ARRAY,SUBS)

where SIZE(SUBS,DIM=1) = SIZE(SHAPE(ARRAY)).  If S = SHAPE(ARRAY),
then S(2:) is the shape of the result R, which has the property that

	R(i1,i2,...,in) = ARRAY(SUBS(1,i1,i2,...,in),
                                SUBS(2,i1,i2,...,in),
                                ...
                                SUBS(k,i1,i2,...,in))

where k = SIZE(SHAPE(ARRAY)) and n = SIZE(SHAPE(SUBS))-1.

GRADE(ARRAY1,ARRAY2,...)

Arguments ARRAY2,... are optional.  All arrays must be conformable.
The arrays must be of type integer, real, or character.  [Alternate spec:
the array may be of any type for which the operator .LT. has been defined?]
The arrays need not all be of the same type.

The result S is an array of rank 2, with shape [SIZE(SHAPE(ARRAY1)),
PRODUCT(SHAPE(ARRAY1))], and the property that if j < k then

ARRAY1(S(1,j),...,S(n,j)) .LT. ARRAY1(S(1,k),...,S(n,k))  or
( ARRAY1(S(1,j),...,S(n,j)) .EQ. ARRAY1(S(1,k),...,S(n,k))  and
  ( ARRAY2(S(1,j),...,S(n,j)) .LT. ARRAY2(S(1,k),...,S(n,k))  or
    ( ARRAY2(S(1,j),...,S(n,j)) .EQ. ARRAY2(S(1,k),...,S(n,k))  and
      ( ...

          ARRAYn(S(1,j),...,S(n,j)) .LT.  ARRAYn(S(1,k),...,S(n,k))  or
          ( ARRAYn(S(1,j),...,S(n,j)) .EQ. ARRAYn(S(1,k),...,S(n,k))  )
        ...
      )
    )
  )
)

which can also be written

INDEX(ARRAY1,S(:,j)) .LT. INDEX(ARRAY1,S(:,k))  or
( INDEX(ARRAY1,S(:,j)) .EQ. INDEX(ARRAY1,S(:,k))  and
  ( INDEX(ARRAY2,S(:,j)) .LT. INDEX(ARRAY2,S(:,k))  or
    ( INDEX(ARRAY2,S(:,j)) .EQ. INDEX(ARRAY2,S(:,k))  and
      ( ...

          INDEX(ARRAYn,S(:,j)) .LT. INDEX(ARRAYn,S(:,k))  or
          ( INDEX(ARRAYn,S(:,j)) .EQ. INDEX(ARRAYn,S(:,k))  )
        ...
      )
    )
  )
)

That is, the array arguments are treated as sort fields, with the first
argument most significant (major) and the last argument least significant
(minor).  The result gives a set of indices that can be used to
permute the arrays into a collectively sorted (ascending) order.

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, ROSTER

then the statement

      ROSTER = INDEX(MEMBERS,GRADE(MEMBERS%NAME,MEMBERS%AGE))

causes 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).
To list members with the same name in descending order of age,
the following trick more or less works:

      ROSTER = INDEX(MEMBERS,GRADE(MEMBERS%NAME,-MEMBERS%AGE))

though this is not completely general.