1 /* 2 This file contains routines for sorting integers and doubles with a permutation array. 3 4 The word "register" in this code is used to identify data that is not 5 aliased. For some compilers, this can cause the compiler to fail to 6 place inner-loop variables into registers. 7 */ 8 #include <petscsys.h> /*I "petscsys.h" I*/ 9 10 #define SWAP(a, b, t) \ 11 do { \ 12 t = a; \ 13 a = b; \ 14 b = t; \ 15 } while (0) 16 17 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right) 18 { 19 PetscInt tmp, i, vl, last; 20 21 PetscFunctionBegin; 22 if (right <= 1) { 23 if (right == 1) { 24 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp); 25 } 26 PetscFunctionReturn(PETSC_SUCCESS); 27 } 28 SWAP(vdx[0], vdx[right / 2], tmp); 29 vl = v[vdx[0]]; 30 last = 0; 31 for (i = 1; i <= right; i++) { 32 if (v[vdx[i]] < vl) { 33 last++; 34 SWAP(vdx[last], vdx[i], tmp); 35 } 36 } 37 SWAP(vdx[0], vdx[last], tmp); 38 PetscCall(PetscSortIntWithPermutation_Private(v, vdx, last - 1)); 39 PetscCall(PetscSortIntWithPermutation_Private(v, vdx + last + 1, right - (last + 1))); 40 PetscFunctionReturn(PETSC_SUCCESS); 41 } 42 43 /*@ 44 PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives 45 a sorted sequence. 46 47 Not Collective 48 49 Input Parameters: 50 + n - number of values to sort 51 . i - values to sort 52 - idx - permutation array. Must be initialized to 0:n-1 on input. 53 54 Level: intermediate 55 56 Note: 57 On output i is unchanged and idx[i] is the position of the i-th smallest index in i. 58 59 .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()` 60 @*/ 61 PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[]) 62 { 63 PetscInt j, k, tmp, ik; 64 65 PetscFunctionBegin; 66 if (n < 8) { 67 for (k = 0; k < n; k++) { 68 ik = i[idx[k]]; 69 for (j = k + 1; j < n; j++) { 70 if (ik > i[idx[j]]) { 71 SWAP(idx[k], idx[j], tmp); 72 ik = i[idx[k]]; 73 } 74 } 75 } 76 } else { 77 PetscCall(PetscSortIntWithPermutation_Private(i, idx, n - 1)); 78 } 79 PetscFunctionReturn(PETSC_SUCCESS); 80 } 81 82 /* ---------------------------------------------------------------------- */ 83 84 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right) 85 { 86 PetscReal vl; 87 PetscInt tmp, i, last; 88 89 PetscFunctionBegin; 90 if (right <= 1) { 91 if (right == 1) { 92 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp); 93 } 94 PetscFunctionReturn(PETSC_SUCCESS); 95 } 96 SWAP(vdx[0], vdx[right / 2], tmp); 97 vl = v[vdx[0]]; 98 last = 0; 99 for (i = 1; i <= right; i++) { 100 if (v[vdx[i]] < vl) { 101 last++; 102 SWAP(vdx[last], vdx[i], tmp); 103 } 104 } 105 SWAP(vdx[0], vdx[last], tmp); 106 PetscCall(PetscSortRealWithPermutation_Private(v, vdx, last - 1)); 107 PetscCall(PetscSortRealWithPermutation_Private(v, vdx + last + 1, right - (last + 1))); 108 PetscFunctionReturn(PETSC_SUCCESS); 109 } 110 111 /*@ 112 PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives 113 a sorted sequence. 114 115 Not Collective 116 117 Input Parameters: 118 + n - number of values to sort 119 . i - values to sort 120 - idx - permutation array. Must be initialized to 0:n-1 on input. 121 122 Level: intermediate 123 124 Note: 125 i is unchanged on output. 126 127 .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()` 128 @*/ 129 PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[]) 130 { 131 PetscInt j, k, tmp; 132 PetscReal ik; 133 134 PetscFunctionBegin; 135 if (n < 8) { 136 for (k = 0; k < n; k++) { 137 ik = i[idx[k]]; 138 for (j = k + 1; j < n; j++) { 139 if (ik > i[idx[j]]) { 140 SWAP(idx[k], idx[j], tmp); 141 ik = i[idx[k]]; 142 } 143 } 144 } 145 } else { 146 PetscCall(PetscSortRealWithPermutation_Private(i, idx, n - 1)); 147 } 148 PetscFunctionReturn(PETSC_SUCCESS); 149 } 150 151 static PetscErrorCode PetscSortStrWithPermutation_Private(const char *v[], PetscInt vdx[], PetscInt right) 152 { 153 PetscInt tmp, i, last; 154 PetscBool gt; 155 const char *vl; 156 157 PetscFunctionBegin; 158 if (right <= 1) { 159 if (right == 1) { 160 PetscCall(PetscStrgrt(v[vdx[0]], v[vdx[1]], >)); 161 if (gt) SWAP(vdx[0], vdx[1], tmp); 162 } 163 PetscFunctionReturn(PETSC_SUCCESS); 164 } 165 SWAP(vdx[0], vdx[right / 2], tmp); 166 vl = v[vdx[0]]; 167 last = 0; 168 for (i = 1; i <= right; i++) { 169 PetscCall(PetscStrgrt(vl, v[vdx[i]], >)); 170 if (gt) { 171 last++; 172 SWAP(vdx[last], vdx[i], tmp); 173 } 174 } 175 SWAP(vdx[0], vdx[last], tmp); 176 PetscCall(PetscSortStrWithPermutation_Private(v, vdx, last - 1)); 177 PetscCall(PetscSortStrWithPermutation_Private(v, vdx + last + 1, right - (last + 1))); 178 PetscFunctionReturn(PETSC_SUCCESS); 179 } 180 181 /*@C 182 PetscSortStrWithPermutation - Computes the permutation of strings that gives 183 a sorted sequence. 184 185 Not Collective 186 187 Input Parameters: 188 + n - number of values to sort 189 . i - values to sort 190 - idx - permutation array. Must be initialized to 0:n-1 on input. 191 192 Level: intermediate 193 194 Note: 195 i is unchanged on output. 196 197 .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()` 198 @*/ 199 PetscErrorCode PetscSortStrWithPermutation(PetscInt n, const char *i[], PetscInt idx[]) 200 { 201 PetscInt j, k, tmp; 202 const char *ik; 203 PetscBool gt; 204 205 PetscFunctionBegin; 206 if (n < 8) { 207 for (k = 0; k < n; k++) { 208 ik = i[idx[k]]; 209 for (j = k + 1; j < n; j++) { 210 PetscCall(PetscStrgrt(ik, i[idx[j]], >)); 211 if (gt) { 212 SWAP(idx[k], idx[j], tmp); 213 ik = i[idx[k]]; 214 } 215 } 216 } 217 } else { 218 PetscCall(PetscSortStrWithPermutation_Private(i, idx, n - 1)); 219 } 220 PetscFunctionReturn(PETSC_SUCCESS); 221 } 222