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