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>
6: #define SWAP(a, b, t) \
7: do { \
8: t = a; \
9: a = b; \
10: b = t; \
11: } while (0)
13: #if PetscDefined(USE_DEBUG)
14: #define PetscCheckIdentity(n, idx) \
15: do { \
16: 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); \
17: } while (0)
18: #else
19: #define PetscCheckIdentity(n, idx) (void)0
20: #endif
22: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right)
23: {
24: PetscInt tmp, i, vl, last;
26: PetscFunctionBegin;
27: if (right <= 1) {
28: if (right == 1) {
29: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
30: }
31: PetscFunctionReturn(PETSC_SUCCESS);
32: }
33: SWAP(vdx[0], vdx[right / 2], tmp);
34: vl = v[vdx[0]];
35: last = 0;
36: for (i = 1; i <= right; i++) {
37: if (v[vdx[i]] < vl) {
38: last++;
39: SWAP(vdx[last], vdx[i], tmp);
40: }
41: }
42: SWAP(vdx[0], vdx[last], tmp);
43: PetscCall(PetscSortIntWithPermutation_Private(v, vdx, last - 1));
44: PetscCall(PetscSortIntWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
45: PetscFunctionReturn(PETSC_SUCCESS);
46: }
48: /*@
49: PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives
50: a sorted sequence.
52: Not Collective
54: Input Parameters:
55: + n - number of values to sort
56: . i - values to sort
57: - idx - permutation array. Must be initialized to 0:`n`-1 on input.
59: Level: intermediate
61: Note:
62: On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscInt` in `i`.
64: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()`
65: @*/
66: PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[])
67: {
68: PetscInt j, k, tmp, ik;
70: PetscFunctionBegin;
71: if (n > 0) {
72: PetscAssertPointer(i, 2);
73: PetscAssertPointer(idx, 3);
74: PetscCheckIdentity(n, idx);
75: }
76: if (n < 8) {
77: for (k = 0; k < n; k++) {
78: ik = i[idx[k]];
79: for (j = k + 1; j < n; j++) {
80: if (ik > i[idx[j]]) {
81: SWAP(idx[k], idx[j], tmp);
82: ik = i[idx[k]];
83: }
84: }
85: }
86: } else {
87: PetscCall(PetscSortIntWithPermutation_Private(i, idx, n - 1));
88: }
89: PetscFunctionReturn(PETSC_SUCCESS);
90: }
92: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right)
93: {
94: PetscReal vl;
95: PetscInt tmp, i, last;
97: PetscFunctionBegin;
98: if (right <= 1) {
99: if (right == 1) {
100: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
101: }
102: PetscFunctionReturn(PETSC_SUCCESS);
103: }
104: SWAP(vdx[0], vdx[right / 2], tmp);
105: vl = v[vdx[0]];
106: last = 0;
107: for (i = 1; i <= right; i++) {
108: if (v[vdx[i]] < vl) {
109: last++;
110: SWAP(vdx[last], vdx[i], tmp);
111: }
112: }
113: SWAP(vdx[0], vdx[last], tmp);
114: PetscCall(PetscSortRealWithPermutation_Private(v, vdx, last - 1));
115: PetscCall(PetscSortRealWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
116: PetscFunctionReturn(PETSC_SUCCESS);
117: }
119: /*@
120: PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives
121: a sorted sequence.
123: Not Collective
125: Input Parameters:
126: + n - number of values to sort
127: . i - values to sort
128: - idx - permutation array. Must be initialized to 0:`n`-1 on input.
130: Level: intermediate
132: Note:
133: On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscReal` in `i`.
135: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
136: @*/
137: PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[])
138: {
139: PetscInt j, k, tmp;
140: PetscReal ik;
142: PetscFunctionBegin;
143: if (n > 0) {
144: PetscAssertPointer(i, 2);
145: PetscAssertPointer(idx, 3);
146: PetscCheckIdentity(n, idx);
147: }
148: if (n < 8) {
149: for (k = 0; k < n; k++) {
150: ik = i[idx[k]];
151: for (j = k + 1; j < n; j++) {
152: if (ik > i[idx[j]]) {
153: SWAP(idx[k], idx[j], tmp);
154: ik = i[idx[k]];
155: }
156: }
157: }
158: } else {
159: PetscCall(PetscSortRealWithPermutation_Private(i, idx, n - 1));
160: }
161: PetscFunctionReturn(PETSC_SUCCESS);
162: }
164: static PetscErrorCode PetscSortStrWithPermutation_Private(const char *v[], PetscInt vdx[], PetscInt right)
165: {
166: PetscInt tmp, i, last;
167: PetscBool gt;
168: const char *vl;
170: PetscFunctionBegin;
171: if (right <= 1) {
172: if (right == 1) {
173: PetscCall(PetscStrgrt(v[vdx[0]], v[vdx[1]], >));
174: if (gt) SWAP(vdx[0], vdx[1], tmp);
175: }
176: PetscFunctionReturn(PETSC_SUCCESS);
177: }
178: SWAP(vdx[0], vdx[right / 2], tmp);
179: vl = v[vdx[0]];
180: last = 0;
181: for (i = 1; i <= right; i++) {
182: PetscCall(PetscStrgrt(vl, v[vdx[i]], >));
183: if (gt) {
184: last++;
185: SWAP(vdx[last], vdx[i], tmp);
186: }
187: }
188: SWAP(vdx[0], vdx[last], tmp);
189: PetscCall(PetscSortStrWithPermutation_Private(v, vdx, last - 1));
190: PetscCall(PetscSortStrWithPermutation_Private(v, vdx + last + 1, right - (last + 1)));
191: PetscFunctionReturn(PETSC_SUCCESS);
192: }
194: /*@
195: PetscSortStrWithPermutation - Computes the permutation of strings that gives
196: a sorted sequence.
198: Not Collective, No Fortran Support
200: Input Parameters:
201: + n - number of values to sort
202: . i - values to sort
203: - idx - permutation array. Must be initialized to 0:`n`-1 on input.
205: Level: intermediate
207: Note:
208: On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `char *` in `i`.
210: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`
211: @*/
212: PetscErrorCode PetscSortStrWithPermutation(PetscInt n, const char *i[], PetscInt idx[])
213: {
214: PetscInt j, k, tmp;
215: const char *ik;
216: PetscBool gt;
218: PetscFunctionBegin;
219: if (n > 0) {
220: PetscAssertPointer(i, 2);
221: PetscAssertPointer(idx, 3);
222: PetscCheckIdentity(n, idx);
223: }
224: if (n < 8) {
225: for (k = 0; k < n; k++) {
226: ik = i[idx[k]];
227: for (j = k + 1; j < n; j++) {
228: PetscCall(PetscStrgrt(ik, i[idx[j]], >));
229: if (gt) {
230: SWAP(idx[k], idx[j], tmp);
231: ik = i[idx[k]];
232: }
233: }
234: }
235: } else {
236: PetscCall(PetscSortStrWithPermutation_Private(i, idx, n - 1));
237: }
238: PetscFunctionReturn(PETSC_SUCCESS);
239: }