Actual source code: sortip.c


  2: /*
  3:    This file contains routines for sorting integers and doubles with a permutation array.

  5:    The word "register"  in this code is used to identify data that is not
  6:    aliased.  For some compilers, this can cause the compiler to fail to
  7:    place inner-loop variables into registers.
  8:  */
  9: #include <petscsys.h>

 11: #define SWAP(a, b, t) \
 12:   { \
 13:     t = a; \
 14:     a = b; \
 15:     b = t; \
 16:   }

 18: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right)
 19: {
 20:   PetscInt tmp, i, vl, last;

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

 44: /*@
 45:    PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives
 46:    a sorted sequence.

 48:    Not Collective

 50:    Input Parameters:
 51: +  n  - number of values to sort
 52: .  i  - values to sort
 53: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

 55:    Level: intermediate

 57:    Note:
 58:    On output i is unchanged and idx[i] is the position of the i-th smallest index in i.

 60: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()`
 61:  @*/
 62: PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[])
 63: {
 64:   PetscInt j, k, tmp, ik;

 66:   PetscFunctionBegin;
 67:   if (n < 8) {
 68:     for (k = 0; k < n; k++) {
 69:       ik = i[idx[k]];
 70:       for (j = k + 1; j < n; j++) {
 71:         if (ik > i[idx[j]]) {
 72:           SWAP(idx[k], idx[j], tmp);
 73:           ik = i[idx[k]];
 74:         }
 75:       }
 76:     }
 77:   } else {
 78:     PetscCall(PetscSortIntWithPermutation_Private(i, idx, n - 1));
 79:   }
 80:   PetscFunctionReturn(PETSC_SUCCESS);
 81: }

 83: /* ---------------------------------------------------------------------- */

 85: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right)
 86: {
 87:   PetscReal vl;
 88:   PetscInt  tmp, i, last;

 90:   PetscFunctionBegin;
 91:   if (right <= 1) {
 92:     if (right == 1) {
 93:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
 94:     }
 95:     PetscFunctionReturn(PETSC_SUCCESS);
 96:   }
 97:   SWAP(vdx[0], vdx[right / 2], tmp);
 98:   vl   = v[vdx[0]];
 99:   last = 0;
100:   for (i = 1; i <= right; i++) {
101:     if (v[vdx[i]] < vl) {
102:       last++;
103:       SWAP(vdx[last], vdx[i], tmp);
104:     }
105:   }
106:   SWAP(vdx[0], vdx[last], tmp);
107:   PetscCall(PetscSortRealWithPermutation_Private(v, vdx, last - 1));
108:   PetscCall(PetscSortRealWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
109:   PetscFunctionReturn(PETSC_SUCCESS);
110: }

112: /*@
113:    PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives
114:    a sorted sequence.

116:    Not Collective

118:    Input Parameters:
119: +  n  - number of values to sort
120: .  i  - values to sort
121: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

123:    Level: intermediate

125:    Note:
126:    i is unchanged on output.

128: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
129:  @*/
130: PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[])
131: {
132:   PetscInt  j, k, tmp;
133:   PetscReal ik;

135:   PetscFunctionBegin;
136:   if (n < 8) {
137:     for (k = 0; k < n; k++) {
138:       ik = i[idx[k]];
139:       for (j = k + 1; j < n; j++) {
140:         if (ik > i[idx[j]]) {
141:           SWAP(idx[k], idx[j], tmp);
142:           ik = i[idx[k]];
143:         }
144:       }
145:     }
146:   } else {
147:     PetscCall(PetscSortRealWithPermutation_Private(i, idx, n - 1));
148:   }
149:   PetscFunctionReturn(PETSC_SUCCESS);
150: }

152: static PetscErrorCode PetscSortStrWithPermutation_Private(const char *v[], PetscInt vdx[], PetscInt right)
153: {
154:   PetscInt    tmp, i, last;
155:   PetscBool   gt;
156:   const char *vl;

158:   PetscFunctionBegin;
159:   if (right <= 1) {
160:     if (right == 1) {
161:       PetscCall(PetscStrgrt(v[vdx[0]], v[vdx[1]], &gt));
162:       if (gt) SWAP(vdx[0], vdx[1], tmp);
163:     }
164:     PetscFunctionReturn(PETSC_SUCCESS);
165:   }
166:   SWAP(vdx[0], vdx[right / 2], tmp);
167:   vl   = v[vdx[0]];
168:   last = 0;
169:   for (i = 1; i <= right; i++) {
170:     PetscCall(PetscStrgrt(vl, v[vdx[i]], &gt));
171:     if (gt) {
172:       last++;
173:       SWAP(vdx[last], vdx[i], tmp);
174:     }
175:   }
176:   SWAP(vdx[0], vdx[last], tmp);
177:   PetscCall(PetscSortStrWithPermutation_Private(v, vdx, last - 1));
178:   PetscCall(PetscSortStrWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
179:   PetscFunctionReturn(PETSC_SUCCESS);
180: }

182: /*@C
183:    PetscSortStrWithPermutation - Computes the permutation of strings that gives
184:    a sorted sequence.

186:    Not Collective

188:    Input Parameters:
189: +  n  - number of values to sort
190: .  i  - values to sort
191: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

193:    Level: intermediate

195:    Note:
196:    i is unchanged on output.

198: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`
199:  @*/
200: PetscErrorCode PetscSortStrWithPermutation(PetscInt n, const char *i[], PetscInt idx[])
201: {
202:   PetscInt    j, k, tmp;
203:   const char *ik;
204:   PetscBool   gt;

206:   PetscFunctionBegin;
207:   if (n < 8) {
208:     for (k = 0; k < n; k++) {
209:       ik = i[idx[k]];
210:       for (j = k + 1; j < n; j++) {
211:         PetscCall(PetscStrgrt(ik, i[idx[j]], &gt));
212:         if (gt) {
213:           SWAP(idx[k], idx[j], tmp);
214:           ik = i[idx[k]];
215:         }
216:       }
217:     }
218:   } else {
219:     PetscCall(PetscSortStrWithPermutation_Private(i, idx, n - 1));
220:   }
221:   PetscFunctionReturn(PETSC_SUCCESS);
222: }