Actual source code: sortip.c

      1: /*
      2:    This file contains routines for sorting integers and doubles with a permutation array.
      3:  */
      4: #include <petsc/private/petscimpl.h>
      5: #include <petscsys.h>

      7: #define SWAP(a, b, t) \
      8:   do { \
      9:     t = a; \
     10:     a = b; \
     11:     b = t; \
     12:   } while (0)

     14: #if PetscDefined(USE_DEBUG)
     15:   #define PetscCheckIdentity(n, idx) \
     16:     do { \
     17:       for (PetscInt i = 0; i < n; ++i) PetscCheck(idx[i] == i, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array needs to be initialized to 0:%" PetscInt_FMT, n - 1); \
     18:     } while (0)
     19: #else
     20:   #define PetscCheckIdentity(n, idx) (void)0
     21: #endif

     23: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right)
     24: {
     25:   PetscInt tmp, i, vl, last;

     27:   PetscFunctionBegin;
     28:   if (right <= 1) {
     29:     if (right == 1) {
     30:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
     31:     }
     32:     PetscFunctionReturn(PETSC_SUCCESS);
     33:   }
     34:   SWAP(vdx[0], vdx[right / 2], tmp);
     35:   vl   = v[vdx[0]];
     36:   last = 0;
     37:   for (i = 1; i <= right; i++) {
     38:     if (v[vdx[i]] < vl) {
     39:       last++;
     40:       SWAP(vdx[last], vdx[i], tmp);
     41:     }
     42:   }
     43:   SWAP(vdx[0], vdx[last], tmp);
     44:   PetscCall(PetscSortIntWithPermutation_Private(v, vdx, last - 1));
     45:   PetscCall(PetscSortIntWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
     46:   PetscFunctionReturn(PETSC_SUCCESS);
     47: }

     49: /*@
     50:   PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives
     51:   a sorted sequence.

     53:   Not Collective

     55:   Input Parameters:
     56: + n   - number of values to sort
     57: . i   - values to sort
     58: - idx - permutation array. Must be initialized to 0:`n`-1 on input.

     60:   Level: intermediate

     62:   Note:
     63:   On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscInt` in `i`.

     65: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()`
     66:  @*/
     67: PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[])
     68: {
     69:   PetscInt j, k, tmp, ik;

     71:   PetscFunctionBegin;
     72:   if (n > 0) {
     73:     PetscAssertPointer(i, 2);
     74:     PetscAssertPointer(idx, 3);
     75:     PetscCheckIdentity(n, idx);
     76:   }
     77:   if (n < 8) {
     78:     for (k = 0; k < n; k++) {
     79:       ik = i[idx[k]];
     80:       for (j = k + 1; j < n; j++) {
     81:         if (ik > i[idx[j]]) {
     82:           SWAP(idx[k], idx[j], tmp);
     83:           ik = i[idx[k]];
     84:         }
     85:       }
     86:     }
     87:   } else {
     88:     PetscCall(PetscSortIntWithPermutation_Private(i, idx, n - 1));
     89:   }
     90:   PetscFunctionReturn(PETSC_SUCCESS);
     91: }

     93: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right)
     94: {
     95:   PetscReal vl;
     96:   PetscInt  tmp, i, last;

     98:   PetscFunctionBegin;
     99:   if (right <= 1) {
    100:     if (right == 1) {
    101:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
    102:     }
    103:     PetscFunctionReturn(PETSC_SUCCESS);
    104:   }
    105:   SWAP(vdx[0], vdx[right / 2], tmp);
    106:   vl   = v[vdx[0]];
    107:   last = 0;
    108:   for (i = 1; i <= right; i++) {
    109:     if (v[vdx[i]] < vl) {
    110:       last++;
    111:       SWAP(vdx[last], vdx[i], tmp);
    112:     }
    113:   }
    114:   SWAP(vdx[0], vdx[last], tmp);
    115:   PetscCall(PetscSortRealWithPermutation_Private(v, vdx, last - 1));
    116:   PetscCall(PetscSortRealWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
    117:   PetscFunctionReturn(PETSC_SUCCESS);
    118: }

    120: /*@
    121:   PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives
    122:   a sorted sequence.

    124:   Not Collective

    126:   Input Parameters:
    127: + n   - number of values to sort
    128: . i   - values to sort
    129: - idx - permutation array. Must be initialized to 0:`n`-1 on input.

    131:   Level: intermediate

    133:   Note:
    134:   On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscReal` in `i`.

    136: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
    137:  @*/
    138: PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[])
    139: {
    140:   PetscInt  j, k, tmp;
    141:   PetscReal ik;

    143:   PetscFunctionBegin;
    144:   if (n > 0) {
    145:     PetscAssertPointer(i, 2);
    146:     PetscAssertPointer(idx, 3);
    147:     PetscCheckIdentity(n, idx);
    148:   }
    149:   if (n < 8) {
    150:     for (k = 0; k < n; k++) {
    151:       ik = i[idx[k]];
    152:       for (j = k + 1; j < n; j++) {
    153:         if (ik > i[idx[j]]) {
    154:           SWAP(idx[k], idx[j], tmp);
    155:           ik = i[idx[k]];
    156:         }
    157:       }
    158:     }
    159:   } else {
    160:     PetscCall(PetscSortRealWithPermutation_Private(i, idx, n - 1));
    161:   }
    162:   PetscFunctionReturn(PETSC_SUCCESS);
    163: }

    165: static PetscErrorCode PetscSortStrWithPermutation_Private(const char *v[], PetscInt vdx[], PetscInt right)
    166: {
    167:   PetscInt    tmp, i, last;
    168:   PetscBool   gt;
    169:   const char *vl;

    171:   PetscFunctionBegin;
    172:   if (right <= 1) {
    173:     if (right == 1) {
    174:       PetscCall(PetscStrgrt(v[vdx[0]], v[vdx[1]], &gt));
    175:       if (gt) SWAP(vdx[0], vdx[1], tmp);
    176:     }
    177:     PetscFunctionReturn(PETSC_SUCCESS);
    178:   }
    179:   SWAP(vdx[0], vdx[right / 2], tmp);
    180:   vl   = v[vdx[0]];
    181:   last = 0;
    182:   for (i = 1; i <= right; i++) {
    183:     PetscCall(PetscStrgrt(vl, v[vdx[i]], &gt));
    184:     if (gt) {
    185:       last++;
    186:       SWAP(vdx[last], vdx[i], tmp);
    187:     }
    188:   }
    189:   SWAP(vdx[0], vdx[last], tmp);
    190:   PetscCall(PetscSortStrWithPermutation_Private(v, vdx, last - 1));
    191:   PetscCall(PetscSortStrWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
    192:   PetscFunctionReturn(PETSC_SUCCESS);
    193: }

    195: /*@C
    196:   PetscSortStrWithPermutation - Computes the permutation of strings that gives
    197:   a sorted sequence.

    199:   Not Collective, No Fortran Support

    201:   Input Parameters:
    202: + n   - number of values to sort
    203: . i   - values to sort
    204: - idx - permutation array. Must be initialized to 0:`n`-1 on input.

    206:   Level: intermediate

    208:   Note:
    209:   On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `char *` in `i`.

    211: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`
    212:  @*/
    213: PetscErrorCode PetscSortStrWithPermutation(PetscInt n, const char *i[], PetscInt idx[])
    214: {
    215:   PetscInt    j, k, tmp;
    216:   const char *ik;
    217:   PetscBool   gt;

    219:   PetscFunctionBegin;
    220:   if (n > 0) {
    221:     PetscAssertPointer(i, 2);
    222:     PetscAssertPointer(idx, 3);
    223:     PetscCheckIdentity(n, idx);
    224:   }
    225:   if (n < 8) {
    226:     for (k = 0; k < n; k++) {
    227:       ik = i[idx[k]];
    228:       for (j = k + 1; j < n; j++) {
    229:         PetscCall(PetscStrgrt(ik, i[idx[j]], &gt));
    230:         if (gt) {
    231:           SWAP(idx[k], idx[j], tmp);
    232:           ik = i[idx[k]];
    233:         }
    234:       }
    235:     }
    236:   } else {
    237:     PetscCall(PetscSortStrWithPermutation_Private(i, idx, n - 1));
    238:   }
    239:   PetscFunctionReturn(PETSC_SUCCESS);
    240: }