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> /*I "petscsys.h" I*/ 6 7 #define SWAP(a, b, t) \ 8 do { \ 9 t = a; \ 10 a = b; \ 11 b = t; \ 12 } while (0) 13 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 22 23 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right) 24 { 25 PetscInt tmp, i, vl, last; 26 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 } 48 49 /*@ 50 PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives 51 a sorted sequence. 52 53 Not Collective 54 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. 59 60 Level: intermediate 61 62 Note: 63 On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscInt` in `i`. 64 65 .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()` 66 @*/ 67 PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[]) 68 { 69 PetscInt j, k, tmp, ik; 70 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 } 92 93 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right) 94 { 95 PetscReal vl; 96 PetscInt tmp, i, last; 97 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 } 119 120 /*@ 121 PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives 122 a sorted sequence. 123 124 Not Collective 125 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. 130 131 Level: intermediate 132 133 Note: 134 On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `PetscReal` in `i`. 135 136 .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()` 137 @*/ 138 PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[]) 139 { 140 PetscInt j, k, tmp; 141 PetscReal ik; 142 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 } 164 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; 170 171 PetscFunctionBegin; 172 if (right <= 1) { 173 if (right == 1) { 174 PetscCall(PetscStrgrt(v[vdx[0]], v[vdx[1]], >)); 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]], >)); 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 } 194 195 /*@C 196 PetscSortStrWithPermutation - Computes the permutation of strings that gives 197 a sorted sequence. 198 199 Not Collective, No Fortran Support 200 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. 205 206 Level: intermediate 207 208 Note: 209 On output, `i` is unchanged and `idx[j]` is the position of the `j`th smallest `char *` in `i`. 210 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; 218 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]], >)); 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 } 241