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